минимизация невыпуклой функции с помощью Нелдера-Мида

Я использую scipy.optimize.minimize с методом по умолчанию ("Neldear-Mead"). Функция, которую я пытаюсь минимизировать, не является строго выпуклой. На некоторых значительных участках он остается прежним.

У меня проблема в том, что шаги, предпринимаемые алгоритмом, слишком малы. Например, моя начальная точка имеет первую координату x0 = 0.2. Я знаю, что функция выдаст другое значение только для значительного шага, например, сдвинется на 0,05. К сожалению, я вижу, что алгоритм делает очень маленький шаг (перемещение примерно на 0,000001). В итоге моя функция возвращает одно и то же значение, а алгоритм не сходится. Могу ли я изменить это поведение?

Для удобства вот код scipy:

def _minimize_neldermead(func, x0, args=(), callback=None,
                         xtol=1e-4, ftol=1e-4, maxiter=None, maxfev=None,
                         disp=False, return_all=False,
                         **unknown_options):
    """
    Minimization of scalar function of one or more variables using the
    Nelder-Mead algorithm.

    Options for the Nelder-Mead algorithm are:
        disp : bool
            Set to True to print convergence messages.
        xtol : float
            Relative error in solution `xopt` acceptable for convergence.
        ftol : float
            Relative error in ``fun(xopt)`` acceptable for convergence.
        maxiter : int
            Maximum number of iterations to perform.
        maxfev : int
            Maximum number of function evaluations to make.

    This function is called by the `minimize` function with
    `method=Nelder-Mead`. It is not supposed to be called directly.
    """
    _check_unknown_options(unknown_options)
    maxfun = maxfev
    retall = return_all

    fcalls, func = wrap_function(func, args)
    x0 = asfarray(x0).flatten()
    N = len(x0)
    rank = len(x0.shape)
    if not -1 < rank < 2:
        raise ValueError("Initial guess must be a scalar or rank-1 sequence.")
    if maxiter is None:
        maxiter = N * 200
    if maxfun is None:
        maxfun = N * 200

    rho = 1
    chi = 2
    psi = 0.5
    sigma = 0.5
    one2np1 = list(range(1, N + 1))

    if rank == 0:
        sim = numpy.zeros((N + 1,), dtype=x0.dtype)
    else:
        sim = numpy.zeros((N + 1, N), dtype=x0.dtype)
    fsim = numpy.zeros((N + 1,), float)
    sim[0] = x0
    if retall:
        allvecs = [sim[0]]
    fsim[0] = func(x0)
    nonzdelt = 0.05
    zdelt = 0.00025
    for k in range(0, N):
        y = numpy.array(x0, copy=True)
        if y[k] != 0:
            y[k] = (1 + nonzdelt)*y[k]
        else:
            y[k] = zdelt

        sim[k + 1] = y
        f = func(y)
        fsim[k + 1] = f

    ind = numpy.argsort(fsim)
    fsim = numpy.take(fsim, ind, 0)
    # sort so sim[0,:] has the lowest function value
    sim = numpy.take(sim, ind, 0)

    iterations = 1

    while (fcalls[0] < maxfun and iterations < maxiter):
        if (numpy.max(numpy.ravel(numpy.abs(sim[1:] - sim[0]))) <= xtol and
                numpy.max(numpy.abs(fsim[0] - fsim[1:])) <= ftol):
            break

        xbar = numpy.add.reduce(sim[:-1], 0) / N
        xr = (1 + rho) * xbar - rho * sim[-1]
        fxr = func(xr)
        doshrink = 0

        if fxr < fsim[0]:
            xe = (1 + rho * chi) * xbar - rho * chi * sim[-1]
            fxe = func(xe)

            if fxe < fxr:
                sim[-1] = xe
                fsim[-1] = fxe
            else:
                sim[-1] = xr
                fsim[-1] = fxr
        else:  # fsim[0] <= fxr
            if fxr < fsim[-2]:
                sim[-1] = xr
                fsim[-1] = fxr
            else:  # fxr >= fsim[-2]
                # Perform contraction
                if fxr < fsim[-1]:
                    xc = (1 + psi * rho) * xbar - psi * rho * sim[-1]
                    fxc = func(xc)

                    if fxc <= fxr:
                        sim[-1] = xc
                        fsim[-1] = fxc
                    else:
                        doshrink = 1
                else:
                    # Perform an inside contraction
                    xcc = (1 - psi) * xbar + psi * sim[-1]
                    fxcc = func(xcc)

                    if fxcc < fsim[-1]:
                        sim[-1] = xcc
                        fsim[-1] = fxcc
                    else:
                        doshrink = 1

                if doshrink:
                    for j in one2np1:
                        sim[j] = sim[0] + sigma * (sim[j] - sim[0])
                        fsim[j] = func(sim[j])

        ind = numpy.argsort(fsim)
        sim = numpy.take(sim, ind, 0)
        fsim = numpy.take(fsim, ind, 0)
        if callback is not None:
            callback(sim[0])
        iterations += 1
        if retall:
            allvecs.append(sim[0])

    x = sim[0]
    fval = numpy.min(fsim)
    warnflag = 0

    if fcalls[0] >= maxfun:
        warnflag = 1
        msg = _status_message['maxfev']
        if disp:
            print('Warning: ' + msg)
    elif iterations >= maxiter:
        warnflag = 2
        msg = _status_message['maxiter']
        if disp:
            print('Warning: ' + msg)
    else:
        msg = _status_message['success']
        if disp:
            print(msg)
            print("         Current function value: %f" % fval)
            print("         Iterations: %d" % iterations)
            print("         Function evaluations: %d" % fcalls[0])

    result = OptimizeResult(fun=fval, nit=iterations, nfev=fcalls[0],
                            status=warnflag, success=(warnflag == 0),
                            message=msg, x=x)
    if retall:
        result['allvecs'] = allvecs
    return result

person DevShark    schedule 31.03.2016    source источник
comment
По моему опыту работы с Нелдером Мидом, они хорошо работают с выпуклыми задачами, но не подходят для невыпуклых задач общего назначения. Не зная точно пространства параметров, которое вы собираетесь использовать Nelder Mead, будет трудно сказать, всегда ли сдвиг его на 0,05 обеспечит решение.   -  person Spinor8    schedule 31.03.2016
comment
Это имеет смысл. У вас есть предложение для невыпуклой функции?   -  person DevShark    schedule 31.03.2016
comment
Функция для вас, чтобы определить. Судя по вашему описанию, есть как минимум регион, где есть плоское плато. Местные минимумы тоже есть? Самое замечательное в Нелдер Миде то, что он очень физический. Вы можете буквально думать об этом как о воде, текущей по физическому ландшафту.   -  person Spinor8    schedule 31.03.2016
comment
Извините, я не был ясен. У меня определенно есть невыпуклая функция с несколькими локальными минимумами (я не беспокоюсь об этом, я просто добавлю несколько хороших отправных точек). Я имел в виду, есть ли у вас предложение по алгоритму минимизации?   -  person DevShark    schedule 31.03.2016
comment
Существует два основных подхода: детерминированная и стохастическая глобальная оптимизация. Обе эти области содержат много очень интересных идей/эвристик. Я не эксперт, но если бы у меня возникла проблема глобальной оптимизации, я бы попытался понять общую структуру пространства параметров. Затем выберите, как я хочу атаковать проблему. Это может быть гибридный подход, в котором различные методы/алгоритмы объединяются вместе.   -  person Spinor8    schedule 31.03.2016
comment
Для детерминированной глобальной оптимизации я обнаружил, что алгоритм DIRECT довольно хорошо работает для задач, над которыми я работал. Вы можете проверить интерфейс, похожий на scipy.optimize, здесь: github.com/andim/scipydirect   -  person Andi    schedule 03.04.2016


Ответы (1)


Я использовал Nelder-Mead давно, но, насколько я помню, вы найдете разные локальные минимумы, если начнете с разных начальных точек. Вы не дали нам свою функцию, поэтому мы могли только догадываться, какая стратегия для вас будет лучшей. .Вы также должны прочитать это

http://www.webpages.uidaho.edu/~fuchang/res/ANMS.pdf

Затем вы можете попробовать чистую реализацию Python

https://github.com/fchollet/nelder-mead/blob/master/nelder_mead.py

person Richard Rublev    schedule 31.03.2016
comment
Спасибо за вашу помощь. Я знаю о разных локальных минимумах и позабочусь об этом. Я пройдусь по вашим ссылкам. - person DevShark; 31.03.2016