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

OptimizationIpopt.jl

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

OptimizationIpopt.jl — это пакет-оболочка, который интегрирует Ipopt.jl с экосистемой Optimization.jl. Это позволяет использовать эффективный решатель Ipopt (Interior Point OPTimizer, оптимизатор методом внутренней точки) через унифицированный интерфейс Optimization.jl.

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

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

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

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

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

Методы

OptimizationIpopt.jl предоставляет алгоритм IpoptOptimizer, который инкапсулирует решатель Ipopt.jl для использования с Optimization.jl. Это алгоритм внутренней точки, который использует методы фильтрации путем линейного поиска и особенно эффективен для решения следующих задач:

  • масштабные нелинейные задачи;

  • задачи с нелинейными ограничениями;

  • задачи, требующие высокой точности решений.

Требования для алгоритма

IpoptOptimizer требуются следующие данные:

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

  • информация о гессиане (аппроксимируется или предоставляется);

  • якобиан ограничений (для задач с ограничениями);

  • гессиан ограничений (для задач с ограничениями).

Алгоритм поддерживает следующие ограничения:

  • прямоугольные ограничения, заданные посредством lb и ub в OptimizationProblem;

  • общие нелинейные ограничения в виде равенств и неравенств, заданные в lcons и ucons.

Базовое использование

using Optimization, OptimizationIpopt

# Создаем оптимизатор с настройками по умолчанию
opt = IpoptOptimizer()

# Или настраиваем специальные параметры Ipopt
opt = IpoptOptimizer(
    acceptable_tol = 1e-8,
    mu_strategy = "adaptive"
)

# Решаем задачу
sol = solve(prob, opt)

Параметры

Параметры общего интерфейса

Согласно общему интерфейсу Optimization.jl в качестве именованных аргументов в функцию solve можно передать следующие параметры:

  • maxiters: максимальное количество итераций (переопределяет параметр Ipopt max_iter)

  • maxtime: максимальное фактическое время в секундах (переопределяет параметр Ipopt max_wall_time)

  • abstol: абсолютный допуск (не используется в Ipopt напрямую)

  • reltol: допуск на сходимость (переопределяет параметр Ipopt tol)

  • verbose: уровень детализации выходных данных (переопределяет параметр Ipopt print_level)

    • false или 0: без выходных данных

    • true или 5: стандартные выходные данные

    • Целочисленные значения 0—​12: различные уровни детализации

Параметры конструктора IpoptOptimizer

Специальные параметры Ipopt передаются в конструктор IpoptOptimizer. Наиболее часто используемые параметры доступны в виде полей структуры:

Параметры завершения

  • acceptable_tol::Float64 = 1e-6: допустимый допуск на сходимость (относительный)

  • acceptable_iter::Int = 15: допустимое количество итераций до завершения

  • dual_inf_tol::Float64 = 1.0: желательный порог для двойственной недопустимости

  • constr_viol_tol::Float64 = 1e-4: желательный порог нарушения ограничений

  • compl_inf_tol::Float64 = 1e-4: желательный порог для условий комплементарности

Параметры линейного решателя

  • linear_solver::String = "mumps": используемый линейный решатель

  • linear_system_scaling::String = "none": Метод масштабирования линейной системы. Для решателей HSL используйте mc19.

Параметры масштабирования нелинейных программ (NLP)

  • nlp_scaling_method::String = "gradient-based": метод масштабирования NLP

    • Возможные значения: none, user-scaling, gradient-based, equilibration-based

  • nlp_scaling_max_gradient::Float64 = 100.0: максимальный градиент после масштабирования

Параметры для барьерного параметра

  • mu_strategy::String = "monotone": стратегия обновления барьерного параметра (monotone, adaptive)

  • mu_init::Float64 = 0.1: начальное значение барьерного параметра

  • mu_oracle::String = "quality-function": оракул для адаптивной стратегии mu

Параметры гессиана

  • hessian_approximation::String = "exact": способ аппроксимации гессиана

    • "exact": использовать точный гессиан

    • "limited-memory": использовать аппроксимацию L-BFGS

  • limited_memory_max_history::Int = 6: размер истории для L-BFGS

  • limited_memory_update_type::String = "bfgs": квазиньютоновская формула обновления (bfgs, sr1)

Параметры линейного поиска

  • line_search_method::String = "filter": метод линейного поиска (filter, penalty)

  • accept_every_trial_step::String = "no": принимать каждый пробный шаг (линейный поиск отключается)

Параметры вывода

  • print_timing_statistics::String = "no": вывод подробной информации о времени

  • print_info_string::String = "no": вывод строки с информацией об алгоритме

Параметры мягкого запуска

  • warm_start_init_point::String = "no": использовать мягкий запуск с опорой на предыдущее решение

Параметры этапа восстановления

  • expect_infeasible_problem::String = "no": включите, если ожидается, что задача недопустимая

Словарь дополнительных параметров

Для параметров Ipopt, недоступных в качестве полей структуры, используйте словарь additional_options:

opt = IpoptOptimizer(
    linear_solver = "ma57",
    additional_options = Dict(
        "derivative_test" => "first-order",
        "derivative_test_tol" => 1e-4,
        "fixed_variable_treatment" => "make_parameter",
        "alpha_for_y" => "primal"
    )
)

Полный список доступных параметров приводится в справке по параметрам Ipopt.

Приоритет параметров

Параметры имеют следующий порядок приоритета (от самого высокого к самому низкому):

  1. аргументы общего интерфейса, передаваемые в функцию solve (например, reltol, maxiters);

  2. параметры в словаре additional_options;

  3. значения полей структуры в IpoptOptimizer.

Пример с параметрами из нескольких источников:

opt = IpoptOptimizer(
    acceptable_tol = 1e-6,           # Поле структуры
    mu_strategy = "adaptive",        # Поле структуры
    linear_solver = "ma57",          # Поле структуры (требуется HSL)
    print_timing_statistics = "yes", # Поле структуры
    additional_options = Dict(
        "alpha_for_y" => "primal",   # Не поле структуры
        "max_iter" => 500            # Переопределяется параметром maxiters ниже
    )
)

sol = solve(prob, opt;
    maxiters = 1000,  # Переопределяет max_iter в additional_options
    reltol = 1e-8     # Задает параметр tol в Ipopt
)

Примеры

Базовая оптимизация без ограничений

Функцию Розенброка можно минимизировать с помощью IpoptOptimizer:

using Optimization, OptimizationIpopt
using Zygote

rosenbrock(x, p) = (p[1] - x[1])^2 + p[2] * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]

# Ipopt требуется информация о градиенте
optfunc = OptimizationFunction(rosenbrock, AutoZygote())
prob = OptimizationProblem(optfunc, x0, p)
sol = solve(prob, IpoptOptimizer())
retcode: Success
u: 2-element Vector{Float64}:
 0.9999999999999899
 0.9999999999999792

Оптимизация с прямоугольными ограничениями

Добавление прямоугольных ограничений для ограничения пространства поиска:

using Optimization, OptimizationIpopt
using Zygote

rosenbrock(x, p) = (p[1] - x[1])^2 + p[2] * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]

optfunc = OptimizationFunction(rosenbrock, AutoZygote())
prob = OptimizationProblem(optfunc, x0, p;
                          lb = [-1.0, -1.0],
                          ub = [1.5, 1.5])
sol = solve(prob, IpoptOptimizer())
retcode: Success
u: 2-element Vector{Float64}:
 0.9999999942690103
 0.9999999885017182

Нелинейная оптимизация с ограничениями

Решение задач с нелинейными ограничениями в виде равенств и неравенств:

using Optimization, OptimizationIpopt
using Zygote

# Цель: минимизировать x[1]^2 + x[2]^2
objective(x, p) = x[1]^2 + x[2]^2

# Ограничения: x[1]^2 + x[2]^2 - 2*x[1] = 0 (равенство)
# и x[1] + x[2] >= 1 (неравенство)
function constraints(res, x, p)
    res[1] = x[1]^2 + x[2]^2 - 2*x[1]  # ограничение в виде равенства
    res[2] = x[1] + x[2]                # ограничение в виде неравенства
end

x0 = [0.5, 0.5]
optfunc = OptimizationFunction(objective, AutoZygote(); cons = constraints)

# Первое ограничение — это равенство (lcons = ucons = 0)
# Второе ограничение — это неравенство (lcons = 1, ucons = Inf)
prob = OptimizationProblem(optfunc, x0;
                          lcons = [0.0, 1.0],
                          ucons = [0.0, Inf])

sol = solve(prob, IpoptOptimizer())
retcode: Success
u: 2-element Vector{Float64}:
 0.29289321506718563
 0.7071067774417749

Использование аппроксимации BFGS с ограниченной памятью

Для масштабных задач, когда вычисление точного гессиана требует слишком больших затрат:

using Optimization, OptimizationIpopt
using Zygote

# Масштабная задача
n = 100
rosenbrock_nd(x, p) = sum(p[2] * (x[i+1] - x[i]^2)^2 + (p[1] - x[i])^2 for i in 1:n-1)

x0 = zeros(n)
p = [1.0, 100.0]

# Автоматическое дифференцирование используется только для градиентов
optfunc = OptimizationFunction(rosenbrock_nd, AutoZygote())
prob = OptimizationProblem(optfunc, x0, p)

# Для гессиана используется аппроксимация L-BFGS
sol = solve(prob, IpoptOptimizer(
           hessian_approximation = "limited-memory",
           limited_memory_max_history = 10);
           maxiters = 1000)
retcode: Success
u: 100-element Vector{Float64}:
 1.000000000045498
 0.9999999999674329
 0.9999999999760841
 1.0000000000439668
 0.9999999999656436
 0.9999999999982687
 1.0000000000174465
 0.9999999999961191
 0.9999999999984535
 1.0000000000270632
 ⋮
 1.0000000000791858
 0.9999999998741496
 0.9999999998274194
 0.9999999997875975
 0.9999999993748642
 0.9999999990813158
 0.9999999981939615
 0.9999999966259885
 0.9999999933639284

Пример оптимизации портфеля

Практический пример оптимизации портфеля с ограничениями:

using Optimization, OptimizationIpopt
using Zygote
using LinearAlgebra

# Оптимизация портфеля: минимизация риска с учетом ограничения на доходность
n_assets = 5
μ = [0.05, 0.10, 0.15, 0.08, 0.12]  # Ожидаемая доходность
Σ = [0.05 0.01 0.02 0.01 0.00;      # Ковариационная матрица
     0.01 0.10 0.03 0.02 0.01;
     0.02 0.03 0.15 0.02 0.03;
     0.01 0.02 0.02 0.08 0.02;
     0.00 0.01 0.03 0.02 0.06]

target_return = 0.10

# Цель: минимизировать дисперсию портфеля
portfolio_risk(w, p) = dot(w, Σ * w)

# Ограничения: сумма весов = 1, ожидаемая доходность >= целевой
function portfolio_constraints(res, w, p)
    res[1] = sum(w) - 1.0                    # Сумма равна 1 (равенство)
    res[2] = dot(μ, w) - target_return       # Минимальная доходность (неравенство)
end

optfunc = OptimizationFunction(portfolio_risk, AutoZygote();
                              cons = portfolio_constraints)
w0 = fill(1.0/n_assets, n_assets)

prob = OptimizationProblem(optfunc, w0;
                          lb = zeros(n_assets),     # Запрет на продажи без покрытия
                          ub = ones(n_assets),      # Не монопортфель > 100 %
                          lcons = [0.0, 0.0],       # Ограничения в виде равенств и неравенств
                          ucons = [0.0, Inf])

sol = solve(prob, IpoptOptimizer();
           reltol = 1e-8,
           verbose = 5)

println("Optimal weights: ", sol.u)
println("Expected return: ", dot(μ, sol.u))
println("Portfolio variance: ", sol.objective)
This is Ipopt version 3.14.19, running with linear solver MUMPS 5.8.2.

Number of nonzeros in equality constraint Jacobian...:        5
Number of nonzeros in inequality constraint Jacobian.:        5
Number of nonzeros in Lagrangian Hessian.............:       15

Total number of variables............................:        5
                     variables with only lower bounds:        0
                variables with lower and upper bounds:        5
                     variables with only upper bounds:        0
Total number of equality constraints.................:        1
Total number of inequality constraints...............:        1
        inequality constraints with only lower bounds:        1
   inequality constraints with lower and upper bounds:        0
        inequality constraints with only upper bounds:        0

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
   0  3.1200000e-02 0.00e+00 3.43e-02  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
   1  3.2177561e-02 0.00e+00 1.30e-02  -1.7 1.78e-02    -  9.93e-01 1.00e+00h  1
   2  3.0759152e-02 0.00e+00 4.26e-02  -2.5 5.87e-02    -  9.79e-01 1.00e+00f  1
   3  2.9846484e-02 0.00e+00 2.83e-08  -2.5 1.07e-01    -  1.00e+00 1.00e+00f  1
   4  2.8068833e-02 0.00e+00 2.47e-02  -3.8 3.60e-02    -  8.65e-01 1.00e+00f  1
   5  2.7401391e-02 0.00e+00 1.50e-09  -3.8 2.41e-02    -  1.00e+00 1.00e+00f  1
   6  2.7234938e-02 0.00e+00 1.46e-04  -5.7 1.03e-02    -  9.79e-01 1.00e+00f  1
   7  2.7232343e-02 0.00e+00 1.84e-11  -5.7 1.85e-03    -  1.00e+00 1.00e+00f  1
   8  2.7230500e-02 2.22e-16 2.51e-14  -8.6 1.40e-04    -  1.00e+00 1.00e+00f  1

Number of Iterations....: 8

                                   (scaled)                 (unscaled)
Objective...............:   2.7230500043271134e-02    2.7230500043271134e-02
Dual infeasibility......:   2.5091040356528538e-14    2.5091040356528538e-14
Constraint violation....:   2.2204460492503131e-16    2.2204460492503131e-16
Variable bound violation:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   6.4320485361915960e-09    6.4320485361915960e-09
Overall NLP error.......:   6.4320485361915960e-09    6.4320485361915960e-09


Number of objective function evaluations             = 9
Number of objective gradient evaluations             = 9
Number of equality constraint evaluations            = 9
Number of inequality constraint evaluations          = 9
Number of equality constraint Jacobian evaluations   = 9
Number of inequality constraint Jacobian evaluations = 9
Number of Lagrangian Hessian evaluations             = 8
Total seconds in IPOPT                               = 1.813

EXIT: Optimal Solution Found.
Optimal weights: [0.23290714113956607, 0.16055161296302972, 0.0967086319310212, 0.08466825825418363, 0.4251643557121995]
Expected return: 0.09999999648873309
Portfolio variance: 0.027230500043271134

Советы и рекомендации

  1. Масштабирование: Ipopt работает лучше, когда переменные и ограничения правильно масштабированы. Если величины переменных сильно различаются, попробуйте нормализовать задачу.

  2. Начальные точки: по возможности предоставляйте подходящие начальные предположения. Ipopt — это локальный оптимизатор, и качество решения зависит от начальной точки.

  3. Аппроксимация гессиана: если задача большая или вычисление гессиана требует больших затрат, используйте hessian_approximation = "limited-memory" в конструкторе IpoptOptimizer.

  4. Выбор линейного решателя: выбор линейного решателя может существенно повлиять на производительность. Для больших проблем лучше использовать решатели HSL (ma27, ma57, ma86, ma97). Имейте в виду, что решатели HSL необходимо устанавливать отдельно, — инструкции по установке см. в документации по Ipopt.jl. Стандартный решатель MUMPS хорошо подходит для небольших и средних задач.

  5. Формулирование ограничений: Ipopt хорошо работает с ограничениями в виде равенств. По возможности формулируйте ограничения в виде равенств, а не пар неравенств.

  6. Мягкий запуск: при решении серии однотипных задач используйте решение предыдущей задачи в качестве отправной точки для следующей. Включить мягкий запуск можно с помощью IpoptOptimizer(warm_start_init_point = "yes").

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

Более подробные сведения об алгоритмах и параметрах Ipopt см. в следующих материалах: