Документация Engee

Optim.jl

Страница в процессе перевода.

Optim — это пакет Julia, в котором реализованы различные алгоритмы для выполнения одномерной и многомерной оптимизации.

Установка: OptimizationOptimJL.jl

Чтобы использовать этот пакет, установите пакет OptimizationOptimJL:

import Pkg;
Pkg.add("OptimizationOptimJL");

Методы

В Optim.jl доступны следующие алгоритмы:

  • Optim.NelderMead()

  • Optim.SimulatedAnnealing()

  • Optim.ParticleSwarm()

  • Optim.ConjugateGradient()

  • Optim.GradientDescent()

  • Optim.BFGS()

  • Optim.LBFGS()

  • Optim.NGMRES()

  • Optim.OACCEL()

  • Optim.NewtonTrustRegion()

  • Optim.Newton()

  • Optim.KrylovTrustRegion()

  • Optim.ParticleSwarm()

  • Optim.SAMIN()

Каждый оптимизатор также принимает специальные аргументы, которые описаны в разделах ниже.

С оптимизаторами Optim.jl можно использовать следующие специальные именованные аргументы, не относящиеся к общим аргументам функции solve:

  • x_tol: абсолютный допуск на изменения входного вектора x в бесконечной норме. По умолчанию 0.0.

  • g_tol: абсолютный допуск на градиент в бесконечной норме. По умолчанию 1e-8. Для методов без градиентов будет контролироваться основной допуск на сходимость, который зависит от конкретного решателя.

  • f_calls_limit: мягкий верхний предел количества вызовов целевой функции. Значение по умолчанию — 0 (не ограничено).

  • g_calls_limit: мягкий верхний предел количества вызовов градиента. Значение по умолчанию — 0 (не ограничено).

  • h_calls_limit: мягкий верхний предел количества вызовов гессиана. Значение по умолчанию — 0 (не ограничено).

  • allow_f_increases: разрешает выполнение шагов, которые увеличивают значение целевой функции. По умолчанию false. Обратите внимание, что при установке значения true в качестве минимизатора будет возвращена последняя итерация, даже если значение целевой функции увеличилось.

  • store_trace: следует ли хранить трассировку состояния алгоритма оптимизации. По умолчанию false.

  • show_trace: следует ли отображать трассировку состояния алгоритма оптимизации в stdout. По умолчанию false.

  • extended_trace: сохранение дополнительной информации. Зависит от решателя. По умолчанию false.

  • trace_simplex: следует ли включать полный симплекс в трассировку для NelderMead. По умолчанию false.

  • show_every: выходные данные трассировки выводятся каждую show_every итерацию.

Более подробную документацию по всем алгоритмам и параметрам см. в Documentation.

Локальный оптимизатор

Локальное ограничение

В Optim.jl реализованы следующие алгоритмы локального ограничения:

  • Optim.IPNewton()

    • μ0 задает начальный коэффициент барьерного штрафа в виде числа или :auto.

    • show_linesearch — это параметр для включения детализации линейного поиска.

    • Значения по умолчанию:

      • linesearch::Function = Optim.backtrack_constrained_grad

      • μ0::Union{Symbol,Number} = :auto

      • show_linesearch::Bool = false

Функцию Розенброка с ограничениями можно оптимизировать с помощью Optim.IPNewton() следующим образом:

using Optimization, OptimizationOptimJL
rosenbrock(x, p) = (p[1] - x[1])^2 + p[2] * (x[2] - x[1]^2)^2
cons = (res, x, p) -> res .= [x[1]^2 + x[2]^2]
x0 = zeros(2)
p = [1.0, 100.0]
prob = OptimizationFunction(rosenbrock, Optimization.AutoForwardDiff(); cons = cons)
prob = Optimization.OptimizationProblem(prob, x0, p, lcons = [-5.0], ucons = [10.0])
sol = solve(prob, IPNewton())
retcode: Success
u: 2-element Vector{Float64}:
 0.9999999992669327
 0.9999999985109471

См. также пример нелинейной оптимизации с ограничениями с использованием IPNewton в документации по Optim.jl.

Без вычисления производных

Оптимизаторы без вычисления производных — это оптимизаторы, которые можно использовать даже в тех случаях, когда не указаны производные или автоматическое дифференцирование. Хотя они, как правило, менее эффективны, чем оптимизаторы на основе производных, их можно легко применять в случаях, когда определение производных затруднено. Обратите внимание, что хотя эти методы не поддерживают общие ограничения, все они поддерживают ограничения границ посредством lb и ub в Optimization.OptimizationProblem.

В Optim.jl реализованы следующие алгоритмы без вычисления производных:

  • Optim.NelderMead(): оптимизатор Нелдера — Мида

    • solve(problem, NelderMead(parameters, initial_simplex))

    • parameters = AdaptiveParameters() или parameters = FixedParameters()

    • initial_simplex = AffineSimplexer()

    • Значения по умолчанию:

      • parameters = AdaptiveParameters()

      • initial_simplex = AffineSimplexer()

  • Optim.SimulatedAnnealing(): алгоритм имитации отжига

    • solve(problem, SimulatedAnnealing(neighbor, T, p))

    • neighbor — это изменяющая функция от текущего и предлагаемого x

    • T — это функция от текущей итерации, которая возвращает температуру

    • p — это функция от текущей температуры

    • Значения по умолчанию:

      • neighbor = default_neighbor!

      • T = default_temperature

      • p = kirkpatrick

  • Optim.ParticleSwarm()

Функцию Розенброка можно оптимизировать с помощью Optim.NelderMead() следующим образом:

using Optimization, OptimizationOptimJL
rosenbrock(x, p) = (1 - x[1])^2 + 100 * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]
prob = Optimization.OptimizationProblem(rosenbrock, x0, p)
sol = solve(prob, Optim.NelderMead())
retcode: Success
u: 2-element Vector{Float64}:
 0.9999634355313174
 0.9999315506115275

На основе градиента

Оптимизаторы на основе градиента — это оптимизаторы, которые используют информацию о градиенте на основе определенных производных или автоматического дифференцирования.

В Optim.jl реализованы следующие алгоритмы на основе градиента:

  • Optim.ConjugateGradient(): сопряженный градиентный спуск

    • solve(problem, ConjugateGradient(alphaguess, linesearch, eta, P, precondprep))

    • alphaguess вычисляет начальную длину шага (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные процедуры для начальной длины шага:

      • InitialPrevious

      • InitialStatic

      • InitialHagerZhang

      • InitialQuadratic

      • InitialConstantChange

    • linesearch задает алгоритм линейного поиска (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные алгоритмы линейного поиска:

      • HaegerZhang

      • MoreThuente

      • BackTracking

      • StrongWolfe

      • Static

    • eta определяет направление следующего шага.

    • P — это необязательный предобуславливатель (дополнительные сведения см. в этом источнике).

    • precondpred используется для обновления P по мере изменения переменной состояния x.

    • Значения по умолчанию:

      • alphaguess = LineSearches.InitialHagerZhang()

      • linesearch = LineSearches.HagerZhang()

      • eta = 0.4

      • P = nothing

      • precondprep = (P, x) -> nothing

  • Optim.GradientDescent(): градиентный спуск (квазиньютоновский решатель)

    • solve(problem, GradientDescent(alphaguess, linesearch, P, precondprep))

    • alphaguess вычисляет начальную длину шага (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные процедуры для начальной длины шага:

      • InitialPrevious

      • InitialStatic

      • InitialHagerZhang

      • InitialQuadratic

      • InitialConstantChange

    • linesearch задает алгоритм линейного поиска (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные алгоритмы линейного поиска:

      • HaegerZhang

      • MoreThuente

      • BackTracking

      • StrongWolfe

      • Static

    • P — это необязательный предобуславливатель (дополнительные сведения см. в этом источнике).

    • precondpred используется для обновления P по мере изменения переменной состояния x.

    • Значения по умолчанию:

      • alphaguess = LineSearches.InitialPrevious()

      • linesearch = LineSearches.HagerZhang()

      • P = nothing

      • precondprep = (P, x) -> nothing

  • Optim.BFGS(): алгоритм Бройдена — Флетчера — Гольдфарба — Шанно

    • solve(problem, BFGS(alphaguess, linesearch, initial_invH, initial_stepnorm, manifold))

    • alphaguess вычисляет начальную длину шага (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные процедуры для начальной длины шага:

      • InitialPrevious

      • InitialStatic

      • InitialHagerZhang

      • InitialQuadratic

      • InitialConstantChange

    • linesearch задает алгоритм линейного поиска (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные алгоритмы линейного поиска:

      • HaegerZhang

      • MoreThuente

      • BackTracking

      • StrongWolfe

      • Static

    • initial_invH задает необязательную начальную матрицу.

    • initial_stepnorm определяет, что initial_invH является матрицей тожественности, масштабированной на значение initial_stepnorm, умноженное на сверхнорму градиента в начальной точке.

    • manifold задает (риманово) многообразие, на котором функция должна быть минимизирована (дополнительные сведения см. в этом источнике).

      • Доступные многообразия:

      • Flat

      • Sphere

      • Stiefel

      • Метамногообразия:

      • PowerManifold

      • ProductManifold

      • Пользовательские многообразия

    • Значения по умолчанию:

      • alphaguess = LineSearches.InitialStatic()

      • linesearch = LineSearches.HagerZhang()

      • initial_invH = nothing

      • initial_stepnorm = nothing

      • manifold = Flat()

  • Optim.LBFGS(): алгоритм Бройдена — Флетчера — Гольдфарба — Шанно с ограниченной памятью

    • m — это количество исторических точек.

    • alphaguess вычисляет начальную длину шага (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные процедуры для начальной длины шага:

      • InitialPrevious

      • InitialStatic

      • InitialHagerZhang

      • InitialQuadratic

      • InitialConstantChange

    • linesearch задает алгоритм линейного поиска (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные алгоритмы линейного поиска:

      • HaegerZhang

      • MoreThuente

      • BackTracking

      • StrongWolfe

      • Static

    • P — это необязательный предобуславливатель (дополнительные сведения см. в этом источнике).

    • precondpred используется для обновления P по мере изменения переменной состояния x.

    • manifold задает (риманово) многообразие, на котором функция должна быть минимизирована (дополнительные сведения см. в этом источнике).

      • Доступные многообразия:

      • Flat

      • Sphere

      • Stiefel

      • Метамногообразия:

      • PowerManifold

      • ProductManifold

      • Пользовательские многообразия

    • scaleinvH0: следует ли масштабировать начальную аппроксимацию гессиана

    • Значения по умолчанию:

      • m = 10

      • alphaguess = LineSearches.InitialStatic()

      • linesearch = LineSearches.HagerZhang()

      • P = nothing

      • precondprep = (P, x) -> nothing

      • manifold = Flat()

      • scaleinvH0::Bool = true && (P isa Nothing)

  • Optim.NGMRES()

  • Optim.OACCEL()

Функцию Розенброка можно оптимизировать с помощью Optim.LBFGS() следующим образом:

using Optimization, OptimizationOptimJL
rosenbrock(x, p) = (1 - x[1])^2 + 100 * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]
optprob = OptimizationFunction(rosenbrock, Optimization.AutoForwardDiff())
prob = Optimization.OptimizationProblem(optprob, x0, p, lb = [-1.0, -1.0], ub = [0.8, 0.8])
sol = solve(prob, Optim.LBFGS())
retcode: Success
u: 2-element Vector{Float64}:
 0.799999998888889
 0.639999998209689

Второго порядка на основе гессиана

Методы оптимизации на основе гессиана — это методы оптимизации второго порядка, в которых применяется прямое вычисление гессиана. Они могут сходиться быстрее, но для их применимости требуются быстрые и точные методы вычисления гессиана.

В Optim.jl реализованы следующие алгоритмы на основе гессиана:

  • Optim.NewtonTrustRegion(): метод Ньютона с доверительной областью

    • initial_delta: начальный радиус доверительной области

    • delta_hat: максимально допустимый радиус доверительной области

    • eta: если rho не меньше eta, шаг допускается.

    • rho_lower: когда rho меньше rho_lower, доверительная область уменьшается.

    • rho_upper: когда rho больше rho_upper, доверительная область увеличивается (но не более delta_hat).

    • Значения по умолчанию:

      • initial_delta = 1.0

      • delta_hat = 100.0

      • eta = 0.1

      • rho_lower = 0.25

      • rho_upper = 0.75

  • Optim.Newton(): метод Ньютона с линейным поиском

    • alphaguess вычисляет начальную длину шага (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные процедуры для начальной длины шага:

      • InitialPrevious

      • InitialStatic

      • InitialHagerZhang

      • InitialQuadratic

      • InitialConstantChange

    • linesearch задает алгоритм линейного поиска (дополнительные сведения см. в этом источнике и этом примере).

      • Доступные алгоритмы линейного поиска:

      • HaegerZhang

      • MoreThuente

      • BackTracking

      • StrongWolfe

      • Static

    • Значения по умолчанию:

      • alphaguess = LineSearches.InitialStatic()

      • linesearch = LineSearches.HagerZhang()

Функцию Розенброка можно оптимизировать с помощью Optim.Newton() следующим образом:

using Optimization, OptimizationOptimJL, ModelingToolkit
rosenbrock(x, p) = (1 - x[1])^2 + 100 * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]
f = OptimizationFunction(rosenbrock, Optimization.AutoSymbolics())
prob = Optimization.OptimizationProblem(f, x0, p)
sol = solve(prob, Optim.Newton())
retcode: Success
u: 2-element Vector{Float64}:
 0.9999999999999994
 0.9999999999999989

Второго порядка без гессиана

Методы без гессиана — это методы, которые выполняют оптимизацию второго порядка путем прямого вычисления произведений гессиана на вектор (Hv) без необходимости построения полного гессиана. Таким образом, эти методы могут хорошо подходить для больших задач оптимизации второго порядка, но могут потребовать особого случая при оценке обусловленности гессиана.

В Optim.jl реализованы следующие алгоритмы без гессиана:

  • Optim.KrylovTrustRegion(): метод Ньютона-Крылова с доверительными областями

    • initial_delta: начальный радиус доверительной области

    • delta_hat: максимально допустимый радиус доверительной области

    • eta: если rho не меньше eta, шаг допускается.

    • rho_lower: когда rho меньше rho_lower, доверительная область уменьшается.

    • rho_upper: когда rho больше rho_upper, доверительная область увеличивается (но не более delta_hat).

    • Значения по умолчанию:

      • initial_delta = 1.0

      • delta_hat = 100.0

      • eta = 0.1

      • rho_lower = 0.25

      • rho_upper = 0.75

Функцию Розенброка можно оптимизировать с помощью Optim.KrylovTrustRegion() следующим образом:

using Optimization, OptimizationOptimJL
rosenbrock(x, p) = (1 - x[1])^2 + 100 * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]
optprob = OptimizationFunction(rosenbrock, Optimization.AutoForwardDiff())
prob = Optimization.OptimizationProblem(optprob, x0, p)
sol = solve(prob, Optim.KrylovTrustRegion())
retcode: Success
u: 2-element Vector{Float64}:
 0.999999999999108
 0.9999999999981819

Глобальный оптимизатор

Без уравнений ограничений

Следующий метод в Optim выполняет глобальную оптимизацию для задач с прямоугольными ограничениями или без них. Он работает как с нижними и верхними границами, заданными в lb и ub в Optimization.OptimizationProblem, так и без них.

  • Optim.ParticleSwarm(): оптимизация методом роя частиц

    • solve(problem, ParticleSwarm(lower, upper, n_particles))

    • lower и upper — это векторы соответственно нижних и верхних границ.

    • n_particles — это количество частиц в рое.

    • Значения по умолчанию: lower = [], upper = [], n_particles = 0

Функцию Розенброка можно оптимизировать с помощью Optim.ParticleSwarm() следующим образом:

using Optimization, OptimizationOptimJL
rosenbrock(x, p) = (p[1] - x[1])^2 + p[2] * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]
f = OptimizationFunction(rosenbrock)
prob = Optimization.OptimizationProblem(f, x0, p, lb = [-1.0, -1.0], ub = [1.0, 1.0])
sol = solve(prob, Optim.ParticleSwarm(lower = prob.lb, upper = prob.ub, n_particles = 100))
retcode: Failure
u: 2-element Vector{Float64}:
 1.0
 1.0

С уравнениями ограничений

Следующий метод в Optim выполняет глобальную оптимизацию для задач с прямоугольными ограничениями.

  • Optim.SAMIN(): алгоритм имитации отжига с границами

    • solve(problem, SAMIN(nt, ns, rt, neps, f_tol, x_tol, coverage_ok, verbosity))

    • Значения по умолчанию:

      • nt = 5

      • ns = 5

      • rt = 0.9

      • neps = 5

      • f_tol = 1e-12

      • x_tol = 1e-6

      • coverage_ok = false

      • verbosity = 0

Функцию Розенброка можно оптимизировать с помощью Optim.SAMIN() следующим образом:

using Optimization, OptimizationOptimJL
rosenbrock(x, p) = (1 - x[1])^2 + 100 * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]
f = OptimizationFunction(rosenbrock, Optimization.AutoForwardDiff())
prob = Optimization.OptimizationProblem(f, x0, p, lb = [-1.0, -1.0], ub = [1.0, 1.0])
sol = solve(prob, Optim.SAMIN())
retcode: Failure
u: 2-element Vector{Float64}:
 0.9948619235270484
 0.9929792511914586