Прямое и двойственное начальные значения

Некоторые конические решатели позволяют задавать начальные значения для прямого и двойственного решения. Это может повысить производительность, особенно если приходится многократно решать последовательность взаимосвязанных задач.

Общую реализацию этой функции, которая была добавлена в JuMP после написания данного руководства, см. в описании set_start_values.

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

В этом руководстве не задаются начальные значения для нелинейных моделей.

В этом руководстве используются следующие пакеты.

using JuMP
import SCS

Основным элементом этого руководства является следующая функция. В первую очередь следует обратить внимание на то, что сначала кэшируются все значения решения, а затем уже изменяется модель. (В JuMP не допускается чередовать запросы значений и изменения модели.)

function set_optimal_start_values(model::Model)
    # Сохраняем сопоставление прямого решения для переменной
    variable_primal = Dict(x => value(x) for x in all_variables(model))
    # Далее переберем каждое ограничение и сохраним сопоставление
    # индекса ограничения с кортежем, содержащим прямое и двойственное
    # решения.
    constraint_solution = Dict()
    for (F, S) in list_of_constraint_types(model)
        # Здесь добавляется блок try-catch, потому что некоторые типы ограничений могут
        # не поддерживать получение прямого или двойственного решения.
        try
            for ci in all_constraints(model, F, S)
                constraint_solution[ci] = (value(ci), dual(ci))
            end
        catch
            @info("Something went wrong getting $F-in-$S. Skipping")
        end
    end
    # Теперь можно перебрать кэшированные решения и установить начальные значения.
    for (x, primal_start) in variable_primal
        set_start_value(x, primal_start)
    end
    for (ci, (primal_start, dual_start)) in constraint_solution
        set_start_value(ci, primal_start)
        set_dual_start_value(ci, dual_start)
    end
    return
end

set_optimal_start_values (generic function with 1 method)

Для тестирования функции мы используем следующую линейную программу:

model = Model(SCS.Optimizer)
@variable(model, x[1:3] >= 0)
@constraint(model, sum(x) <= 1)
@objective(model, Max, sum(i * x[i] for i in 1:3))
optimize!(model)
@assert is_solved_and_feasible(model)

------------------------------------------------------------------
	       SCS v3.2.6 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 3, constraints m: 4
cones: 	  l: linear vars: 4
settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
	  alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
	  max_iters: 100000, normalize: 1, rho_x: 1.00e-06
	  acceleration_lookback: 10, acceleration_interval: 10
	  compiled with openmp parallelization enabled
lin-sys:  sparse-direct-amd-qdldl
	  nnz(A): 6, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 4.42e+01  1.00e+00  1.28e+02 -6.64e+01  1.00e-01  1.82e-03
    75| 5.30e-07  2.63e-06  3.15e-07 -3.00e+00  1.00e-01  1.26e-02
------------------------------------------------------------------
status:  solved
timings: total: 1.26e-02s = setup: 8.66e-05s + solve: 1.25e-02s
	 lin-sys: 1.30e-05s, cones: 6.86e-06s, accel: 3.97e-06s
------------------------------------------------------------------
objective = -2.999998
------------------------------------------------------------------

В журнале видно, что SCS потребовалось 75 итераций, чтобы найти оптимальное решение. Теперь установим оптимальное решение в качестве отправной точки:

set_optimal_start_values(model)

и выполним оптимизацию повторно:

optimize!(model)

------------------------------------------------------------------
	       SCS v3.2.6 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 3, constraints m: 4
cones: 	  l: linear vars: 4
settings: eps_abs: 1.0e-04, eps_rel: 1.0e-04, eps_infeas: 1.0e-07
	  alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
	  max_iters: 100000, normalize: 1, rho_x: 1.00e-06
	  acceleration_lookback: 10, acceleration_interval: 10
	  compiled with openmp parallelization enabled
lin-sys:  sparse-direct-amd-qdldl
	  nnz(A): 6, nnz(P): 0
------------------------------------------------------------------
 iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
     0| 1.90e-05  1.56e-06  9.14e-05 -3.00e+00  1.00e-01  3.39e-04
------------------------------------------------------------------
status:  solved
timings: total: 3.40e-04s = setup: 4.95e-05s + solve: 2.90e-04s
	 lin-sys: 1.30e-06s, cones: 1.74e-06s, accel: 4.30e-08s
------------------------------------------------------------------
objective = -3.000044
------------------------------------------------------------------

Теперь оптимизация завершается после 0 итераций, так как начальная точка уже оптимальна.

Обратите внимание, что некоторые решатели поддерживают настройку не всех элементов начального решения. Например, они могут поддерживать set_start_value только для переменных. Если возникает ошибка UnsupportedSupported для атрибута MOI.VariablePrimalStart, MOI.ConstraintPrimalStart или MOI.ConstraintDualStart, закомментируйте соответствующую часть функции set_optimal_start_values.