Алгоритм Нелдера-Мида

В настоящее время стандартным алгоритмом является алгоритм Нелдера-Мида, когда производные не предоставляются.

Конструктор

NelderMead(; parameters = AdaptiveParameters(),
             initial_simplex = AffineSimplexer())

Ключевые слова в конструкторе используются для управления следующими частями решателя.

parameters является экземпляром AdaptiveParameters или FixedParameters и используется для создания параметров для алгоритма Нелдера-Мида.
initial_simplex является экземпляром AffineSimplexer. Дополнительные сведения см. ниже.

Описание

Наша текущая реализация алгоритма Нелдера-Мида основана на работах Нелдера (Nelder) и Мида (Mead) (1965), а также Гао (Gao) и Хана (Han) (2010). Методы без градиентов могут быть немного чувствительны к начальным значениям и параметрам настройки, поэтому рекомендуется внимательно относиться к значениям по умолчанию, предоставленным в Optim.

Вместо использования информации о градиенте метод Нелдера-Мида представляет собой метод прямого поиска. Он отслеживает значение функции в нескольких точках в области поиска. Вместе эти точки образуют симплекс. При наличии симплекса можно выполнить одно из четырех действий: отражение, расширение, сжатие или усечение. По сути, цель состоит в том, чтобы итеративно заменить худшую точку лучшей. Более подробную информацию можно найти в работах Нелдера и Мида (1965), Лагариаса и соавторов (1998) или Гао и Хана (2010).

Правило остановки такое же, как и в оригинальной статье, и представляет собой стандартную погрешность значений функции в вершинах. Чтобы задать уровень допуска для этого критерия сходимости, задайте уровень g_tol, как описано в разделе «Настраиваемые параметры».

По завершении работы решателя возвращается минимизатор, который является либо центроидом, либо одной из вершин. Значение функции в центроиде добавляет вычисление функции, поскольку нам нужно вычислить цель в центроиде, чтобы выбрать наименьшее значение функции. Однако даже если значение функции в центроиде может быть возвращено как минимальное, мы не отслеживаем его во время итераций оптимизации. Это необходимо для того, чтобы избежать слишком большого количества вычислений целевой функции, которые могут потребовать больших вычислительных затрат. Как правило, количество f_calls не должно превышать количество iterations более чем в два раза. Добавление вычисления в центроиде при трассировке может значительно увеличить общее время работы алгоритма.

Указание начального симплекса

Для initial_simplex по умолчанию используется AffineSimplexer(). Симплекс представлен -мерным вектором -мерных векторов. Он используется вместе с начальным x для создания начального симплекса. Чтобы построить -ю вершину, он просто умножает запись в начальном векторе на константу b и прибавляет константу a. Это означает, что -я из дополнительных вершин имеет следующий вид:

Если значение равно нулю, нам требуется , чтобы убедиться, что все вершины уникальны. Как правило, рекомендуется начинать с относительно большого симплекса.

Если нужен конкретный симплекс, можно построить -вектор -мерных векторов и передать его решателю, используя новое определение типа и новый метод для функции simplexer. Например, давайте минимизируем двумерную функцию Розенброка и выберем три вершины, элементы которых представляют собой просто стандартные постоянные.

using Optim
struct MySimplexer <: Optim.Simplexer end
Optim.simplexer(S::MySimplexer, initial_x) = [rand(length(initial_x)) for i = 1:length(initial_x)+1]
f(x) = (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2
optimize(f, [.0, .0], NelderMead(initial_simplex = MySimplexer()))

Допустим, мы хотим реализовать начальный симплекс, как в алгоритме fminsearch Matlab. Он выполняется практически аналогично приведенному выше AffineSimplexer, но с небольшой особенностью. Вместо того чтобы всегда добавлять a, константа добавляется только к тем записям, которые равны нулю. Если значение ненулевое, добавляется пять процентов от уровня. Это может быть реализовано (пользователем) следующим образом:

struct MatlabSimplexer{T} <: Optim.Simplexer
    a::T
    b::T
end
MatlabSimplexer(;a = 0.00025, b = 0.05) = MatlabSimplexer(a, b)

function Optim.simplexer(S::MatlabSimplexer, initial_x::AbstractArray{T, N}) where {T, N}
    n = length(initial_x)
    initial_simplex = Array{T, N}[copy(initial_x) for i = 1:n+1]
    for j = 1:n
        initial_simplex[j+1][j] += initial_simplex[j+1][j] != zero(T) ? S.b * initial_simplex[j+1][j] : S.a
    end
    initial_simplex
end

Параметры алгоритма Нелдера-Мида

Для управления различными типами шагов в алгоритме используются четыре параметра: для отражения, для расширения, для сжатия и для усечения. По умолчанию мы используем схему адаптивных параметров из работы Гао и Хана (2010). Они зависят от размерности задачи и определяются следующим образом:

Можно также задать исходные параметры из работы Нелдера и Мида (1965)

указав parameters = Optim.FixedParameters(). Для задания пользовательских значений используется parameters = Optim.FixedParameters(α = a, β = b, γ = g, δ = d), где a, b, g, d — выбранные значения. Если требуется другая спецификация параметров, можно создать пользовательский подтипOptim.NMParameters и добавить метод к функции parameters. Она должна принимать новый тип в качестве первого позиционного аргумента, размерность x в качестве второго позиционного аргумента и возвращать четверной кортеж параметров. Однако зачастую проще указать нужные параметры в FixedParameters.

Справочные материалы

Nelder, John A. and R. Mead (1965). A simplex method for function minimization. Computer Journal 7: 308—313. doi:10.1093/comjnl/7.4.308.

Lagarias, Jeffrey C., et al. Convergence properties of the Nelder—Mead simplex method in low dimensions. SIAM Journal on optimization 9.1 (1998): 112-147.

Gao, Fuchang and Lixing Han (2010). Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications [DOI 10.1007/s10589-010-9329-3]