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

Аппроксимация эллипсоида

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

Модель взята из раздела 4.9 работы BenTal2001.

Связанный пример см. также в руководстве Minimal ellipses.

Формулировка задачи

Предположим, дано множество , состоящее из точек в -мерном пространстве:

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

содержал и имел наименьший возможный объем.

Оптимальные и определяются следующей задачей оптимизации:

где Missing open brace for subscript и Missing open brace for subscript .

Требуемые пакеты

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

using JuMP
import LinearAlgebra
import Plots
import Random
import SCS
import Test

Данные

Сначала нужно сгенерировать точки для работы.

function generate_point_cloud(
    m;            # количество двухмерных точек
    a = 10,       # масштабирование в направлении x
    b = 2,        # масштабирование в направлении y
    rho = π / 6,  # поворот точек вокруг начала координат
    random_seed = 1,
)
    rng = Random.MersenneTwister(random_seed)
    P = randn(rng, Float64, m, 2)
    Phi = [a*cos(rho) a*sin(rho); -b*sin(rho) b*cos(rho)]
    S = P * Phi
    return S
end
generate_point_cloud (generic function with 1 method)

Для этого примера возьмем :

S = generate_point_cloud(600);

Визуализируем точки (и эллипсы) с помощью пакета Plots:

r = 1.1 * maximum(abs.(S))
plot = Plots.scatter(
    S[:, 1],
    S[:, 2];
    xlim = (-r, r),
    ylim = (-r, r),
    label = nothing,
    c = :green,
    shape = :x,
    size = (600, 600),
)

Формулировка на языке JuMP

Теперь построим модель JuMP. и вычислим после решения.

model = Model(SCS.Optimizer)
# В этом примере нужно использовать более строгий допуск, иначе ограничивающий
# эллипс на самом деле не будет ограничивающим...
set_attribute(model, "eps_rel", 1e-6)
set_silent(model)
m, n = size(S)
@variable(model, z[1:n])
@variable(model, Z[1:n, 1:n], PSD)
@variable(model, s)
@variable(model, t)
@constraint(model, [s z'; z Z] >= 0, PSDCone())
@constraint(
    model,
    [i in 1:m],
    S[i, :]' * Z * S[i, :] - 2 * S[i, :]' * z + s <= 1,
)
@constraint(model, [t; vec(Z)] in MOI.RootDetConeSquare(n))
@objective(model, Max, t)
optimize!(model)
Test.@test is_solved_and_feasible(model)
solution_summary(model)
* Solver : SCS

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "solved"

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : FEASIBLE_POINT
  Objective value    : 4.50777e-03
  Dual objective value : 4.47966e-03

* Work counters
  Solve time (sec)   : 1.20850e+00

Результаты

После решения модели можно восстановить решение в терминах и :

D = value.(Z)
2×2 Matrix{Float64}:
  0.00707822  -0.0102173
 -0.0102173    0.0175624
c = D \ value.(z)
2-element Vector{Float64}:
 -3.2480287747737338
 -1.842825686604818

Наконец, наложив решение на график, мы увидим аппроксимирующий эллипсоид с минимальным объемом:

P = sqrt(D)
q = -P * c
data = [tuple(P \ [cos(θ) - q[1], sin(θ) - q[2]]...) for θ in 0:0.05:(2pi+0.05)]
Plots.plot!(plot, data; c = :crimson, label = nothing)

Альтернативные формулировки

В формулировке model используется MOI.RootDetConeSquare. Однако, поскольку SCS изначально не поддерживает этот конус, JuMP автоматически переформулирует задачу в эквивалентную задачу, поддерживаемую SCS. Выбранную JuMP переформулировку можно просмотреть с помощью print_active_bridges:

print_active_bridges(model)
 * Unsupported objective: MOI.VariableIndex
 |  bridged by:
 |   MOIB.Objective.FunctionConversionBridge{Float64, MOI.ScalarAffineFunction{Float64}, MOI.VariableIndex}
 |  may introduce:
 |   * Supported objective: MOI.ScalarAffineFunction{Float64}
 * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.LessThan{Float64}
 |  bridged by:
 |   MOIB.Constraint.LessToGreaterBridge{Float64, MOI.ScalarAffineFunction{Float64}, MOI.ScalarAffineFunction{Float64}}
 |  may introduce:
 |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.GreaterThan{Float64}
 |   |  bridged by:
 |   |   MOIB.Constraint.VectorizeBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.Nonnegatives, MOI.ScalarAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeSquare
 |  bridged by:
 |   MOIB.Constraint.SquareBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.ScalarAffineFunction{Float64}, MOI.PositiveSemidefiniteConeTriangle, MOI.PositiveSemidefiniteConeSquare}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |   |  bridged by:
 |   |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   |  bridged by:
 |   |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.EqualTo{Float64}
 |   |  bridged by:
 |   |   MOIB.Constraint.VectorizeBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.Zeros, MOI.ScalarAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Zeros
 * Unsupported constraint: MOI.VectorOfVariables-in-MOI.PositiveSemidefiniteConeTriangle
 |  bridged by:
 |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |  bridged by:
 |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 * Unsupported constraint: MOI.VectorOfVariables-in-MOI.RootDetConeSquare
 |  bridged by:
 |   MOIB.Constraint.SquareBridge{Float64, MOI.VectorOfVariables, MOI.ScalarAffineFunction{Float64}, MOI.RootDetConeTriangle, MOI.RootDetConeSquare}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.RootDetConeTriangle
 |   |  bridged by:
 |   |   MOIB.Constraint.RootDetBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables, MOI.VectorOfVariables}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   |   |  bridged by:
 |   |   |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |   |  may introduce:
 |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 |   |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.GeometricMeanCone
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.FunctionConversionBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables, MOI.GeometricMeanCone}
 |   |   |  may introduce:
 |   |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.GeometricMeanCone
 |   |   |   |  bridged by:
 |   |   |   |   MOIB.Constraint.GeoMeanToPowerBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |   |  may introduce:
 |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PowerCone{Float64}
 |   |   |   |   * Unsupported variable: MOI.Nonnegatives
 |   |   |   |   |  adding as constraint:
 |   |   |   |   |   * Supported variable: MOI.Reals
 |   |   |   |   |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.Nonnegatives
 |   |   |   |   |   |  bridged by:
 |   |   |   |   |   |   MOIB.Constraint.FunctionConversionBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables, MOI.Nonnegatives}
 |   |   |   |   |   |  may introduce:
 |   |   |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 |   |   * Supported variable: MOI.Reals
 |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.EqualTo{Float64}
 |   |  bridged by:
 |   |   MOIB.Constraint.VectorizeBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.Zeros, MOI.ScalarAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Zeros

Здесь много всего происходит, но первым пунктом идет следующее:

* Unsupported objective: MOI.VariableIndex
|  bridged by:
|   MOIB.Objective.FunctionizeBridge{Float64}
|  introduces:
|   * Supported objective: MOI.ScalarAffineFunction{Float64}

Это означает, что SCS не поддерживает целевую функцию MOI.VariableIndex и что в JuMP был использован объект MOI.Bridges.Objective.FunctionizeBridge для ее преобразования в целевую функцию MOI.ScalarAffineFunction{Float64}.

Мы можем поручить переформулирование задачи JuMP или переписать модель так, чтобы ее целевая функция изначально поддерживалась решателем SCS:

@objective(model, Max, 1.0 * t + 0.0);

Если повторно вывести активные мосты:

print_active_bridges(model)
 * Supported objective: MOI.ScalarAffineFunction{Float64}
 * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.LessThan{Float64}
 |  bridged by:
 |   MOIB.Constraint.LessToGreaterBridge{Float64, MOI.ScalarAffineFunction{Float64}, MOI.ScalarAffineFunction{Float64}}
 |  may introduce:
 |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.GreaterThan{Float64}
 |   |  bridged by:
 |   |   MOIB.Constraint.VectorizeBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.Nonnegatives, MOI.ScalarAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeSquare
 |  bridged by:
 |   MOIB.Constraint.SquareBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.ScalarAffineFunction{Float64}, MOI.PositiveSemidefiniteConeTriangle, MOI.PositiveSemidefiniteConeSquare}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |   |  bridged by:
 |   |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   |  bridged by:
 |   |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.EqualTo{Float64}
 |   |  bridged by:
 |   |   MOIB.Constraint.VectorizeBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.Zeros, MOI.ScalarAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Zeros
 * Unsupported constraint: MOI.VectorOfVariables-in-MOI.PositiveSemidefiniteConeTriangle
 |  bridged by:
 |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |  bridged by:
 |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 * Unsupported constraint: MOI.VectorOfVariables-in-MOI.RootDetConeSquare
 |  bridged by:
 |   MOIB.Constraint.SquareBridge{Float64, MOI.VectorOfVariables, MOI.ScalarAffineFunction{Float64}, MOI.RootDetConeTriangle, MOI.RootDetConeSquare}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.RootDetConeTriangle
 |   |  bridged by:
 |   |   MOIB.Constraint.RootDetBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables, MOI.VectorOfVariables}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   |   |  bridged by:
 |   |   |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |   |  may introduce:
 |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 |   |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.GeometricMeanCone
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.FunctionConversionBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables, MOI.GeometricMeanCone}
 |   |   |  may introduce:
 |   |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.GeometricMeanCone
 |   |   |   |  bridged by:
 |   |   |   |   MOIB.Constraint.GeoMeanToPowerBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |   |  may introduce:
 |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PowerCone{Float64}
 |   |   |   |   * Unsupported variable: MOI.Nonnegatives
 |   |   |   |   |  adding as constraint:
 |   |   |   |   |   * Supported variable: MOI.Reals
 |   |   |   |   |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.Nonnegatives
 |   |   |   |   |   |  bridged by:
 |   |   |   |   |   |   MOIB.Constraint.FunctionConversionBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables, MOI.Nonnegatives}
 |   |   |   |   |   |  may introduce:
 |   |   |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 |   |   * Supported variable: MOI.Reals
 |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.EqualTo{Float64}
 |   |  bridged by:
 |   |   MOIB.Constraint.VectorizeBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.Zeros, MOI.ScalarAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Zeros

получим * Supported objective: MOI.ScalarAffineFunction{Float64}.

Можно вручную реализовать некоторые другие переформулировки, чтобы изменить модель так, чтобы она лучше поддерживалась SCS:

  • заменить MOI.VectorOfVariables в ограничении MOI.PositiveSemidefiniteConeTriangle @variable(model, Z[1:n, 1:n], PSD) на

    MOI.VectorAffineFunction in MOI.PositiveSemidefiniteConeTriangle @constraint(model, Z >= 0, PSDCone());

  • заменить MOI.VectorOfVariables в ограничении MOI.PositiveSemidefiniteConeSquare [s z'; z Z] >= 0, PSDCone() на

    MOI.VectorAffineFunction in MOI.PositiveSemidefiniteConeTriangle @constraint(model, LinearAlgebra.Symmetric([s z'; z Z]) >= 0, PSDCone());

  • заменить MOI.ScalarAffineFunction в ограничениях MOI.GreaterThan на векторизованный эквивалент

    MOI.VectorAffineFunction in MOI.Nonnegatives

  • заменить MOI.VectorOfVariables в ограничении MOI.RootDetConeSquare на MOI.VectorAffineFunction в

    MOI.RootDetConeTriangle.

Обратите внимание, что по-прежнему необходимо соединить мостами ограничения MOI.PositiveSemidefiniteConeTriangle, так как в SCS вместо этого используется внутреннее множество SCS.ScaledPSDCone.

model = Model(SCS.Optimizer)
set_attribute(model, "eps_rel", 1e-6)
set_silent(model)
@variable(model, z[1:n])
@variable(model, s)
@variable(model, t)
# Прежний вызов @variable(model, Z[1:n, 1:n], PSD)
@variable(model, Z[1:n, 1:n], Symmetric)
@constraint(model, Z >= 0, PSDCone())
# Прежнее ограничение [s z'; z Z] >= 0, PSDCone()
@constraint(model, LinearAlgebra.Symmetric([s z'; z Z]) >= 0, PSDCone())
# Прежнее ограничение S[i, :]' * Z * S[i, :] - 2 * S[i, :]' * z + s <= 1
f = [1 - S[i, :]' * Z * S[i, :] + 2 * S[i, :]' * z - s for i in 1:m]
@constraint(model, f in MOI.Nonnegatives(m))
# Прежнее ограничение [t; vec(Z)] в MOI.RootDetConeSquare(n)
@constraint(model, 1 * [t; triangle_vec(Z)] .+ 0 in MOI.RootDetConeTriangle(n))
# Прежняя целевая функция @objective(model, Max, t)
@objective(model, Max, 1 * t + 0)
optimize!(model)
Test.@test is_solved_and_feasible(model)
solve_time_1 = solve_time(model)
1.0828576840000002

В результате этой переформулировки получается гораздо меньший граф:

print_active_bridges(model)
 * Supported objective: MOI.ScalarAffineFunction{Float64}
 * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |  bridged by:
 |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |  bridged by:
 |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.RootDetConeTriangle
 |  bridged by:
 |   MOIB.Constraint.RootDetBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |   |  bridged by:
 |   |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   |  bridged by:
 |   |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.GeometricMeanCone
 |   |  bridged by:
 |   |   MOIB.Constraint.GeoMeanToPowerBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PowerCone{Float64}
 |   |   * Unsupported variable: MOI.Nonnegatives
 |   |   |  adding as constraint:
 |   |   |   * Supported variable: MOI.Reals
 |   |   |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.Nonnegatives
 |   |   |   |  bridged by:
 |   |   |   |   MOIB.Constraint.FunctionConversionBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorOfVariables, MOI.Nonnegatives}
 |   |   |   |  may introduce:
 |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 |   * Supported variable: MOI.Reals

В последнем пункте показано, как среда JuMP переформулировала ограничение MOI.RootDetConeTriangle, добавив комбинацию ограничений MOI.PositiveSemidefiniteConeTriangle и MOI.GeometricMeanCone.

Так как SCS изначально не поддерживает MOI.GeometricMeanCone, эти ограничения были далее соединены с помощью MOI.Bridges.Constraint.GeoMeanToPowerBridge с рядом ограничений MOI.PowerCone.

Однако существует множество других способов переформулирования MOI.GeometricMeanCone в форму, поддерживаемую SCS. Посмотрим, что произойдет, если с помощью remove_bridge](../../api.md#JuMP.remove_bridge-Union{Tuple{S}, Tuple{T}, Tuple{GenericModel{S}, Type{<:MathOptInterface.Bridges.AbstractBridge}}} where {T, S}) удалить [MOI.Bridges.Constraint.GeoMeanToPowerBridge:

remove_bridge(model, MOI.Bridges.Constraint.GeoMeanToPowerBridge)
optimize!(model)
Test.@test is_solved_and_feasible(model)
Test Passed

На этот раз решение заняло:

solve_time_2 = solve_time(model)
0.678388821

в то время как ранее оно занимало:

solve_time_1
1.0828576840000002

Почему время решения разное?

print_active_bridges(model)
 * Supported objective: MOI.ScalarAffineFunction{Float64}
 * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |  bridged by:
 |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |  bridged by:
 |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.RootDetConeTriangle
 |  bridged by:
 |   MOIB.Constraint.RootDetBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |  may introduce:
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.PositiveSemidefiniteConeTriangle
 |   |  bridged by:
 |   |   MOIB.Constraint.SetDotScalingBridge{Float64, MOI.PositiveSemidefiniteConeTriangle, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   |  bridged by:
 |   |   |   SCS.ScaledPSDConeBridge{Float64, MOI.VectorAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-SCS.ScaledPSDCone
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.GeometricMeanCone
 |   |  bridged by:
 |   |   MOIB.Constraint.GeoMeanBridge{Float64, MOI.ScalarAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.LessThan{Float64}
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.LessToGreaterBridge{Float64, MOI.ScalarAffineFunction{Float64}, MOI.ScalarAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Unsupported constraint: MOI.ScalarAffineFunction{Float64}-in-MOI.GreaterThan{Float64}
 |   |   |   |  bridged by:
 |   |   |   |   MOIB.Constraint.VectorizeBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.Nonnegatives, MOI.ScalarAffineFunction{Float64}}
 |   |   |   |  may introduce:
 |   |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.RotatedSecondOrderCone
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.RSOCtoSOCBridge{Float64, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |   |  may introduce:
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.SecondOrderCone
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 |   |   * Supported variable: MOI.Reals
 |   * Supported variable: MOI.Reals

На этот раз в JuMP использовался объект MOI.Bridges.Constraint.GeoMeanBridge для переформулирования ограничения в набор ограничений MOI.RotatedSecondOrderCone, которые затем были переформулированы в набор поддерживаемых ограничений MOI.SecondOrderCone.

Так как эти две модели эквивалентны, можно сделать вывод, что для данной конкретной модели формулировка MOI.SecondOrderCone более эффективна.

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