Сообщество Engee
Engee Community
/
Примеры и проекты
/
Аппроксимация эллипсоидом

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

Автор
avatar-artpgchartpgch
Notebook

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

Дополнительно мы покажем, как с помощью пакета JuMP можно изучать используемые преобразования (bridges) и исследовать альтернативные формулировки задачи.

Импортируем необходимые пакеты:

import Pkg
Pkg.add(["JuMP", "Clarabel", "LinearAlgebra", "Plots", "Random", "Test"])
using JuMP, Clarabel, LinearAlgebra, Plots, Random, Test

   Resolving package versions...
  No Changes to `~/.project/Project.toml`
  No Changes to `~/.project/Manifest.toml`

Постановка задачи


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

a.png

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

b.png

содержал множество S и имел наименее возможный объём (площадь).

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

s.png

Данные

Сгенерируем несколько точек:

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

создать_набор_точек (generic function with 1 method)

Для простоты этого примера возьмём m = 100 :

S = создать_набор_точек(100);

Визуализируем точки:

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. В результате решения задачи будет вычислены значения D и c.

модель = Model(Clarabel.Optimizer)
set_silent(модель)
m, n = size(S)
@variable(модель, z[1:n])
@variable(модель, Z[1:n, 1:n], PSD)
@variable(модель, s)
@variable(модель, t)
@constraint(модель, [s z'; z Z] >= 0, PSDCone())
@constraint(
    модель,
    [i in 1:m],
    S[i, :]' * Z * S[i, :] - 2 * S[i, :]' * z + s <= 1,
)
@constraint(модель, [t; vec(Z)] in MOI.RootDetConeSquare(n))
@objective(модель, Max, t)
optimize!(модель)
assert_is_solved_and_feasible(модель)
solution_summary(модель)

solution_summary(; result = 1, verbose = false)
├ solver_name          : Clarabel
├ Termination
│ ├ termination_status : OPTIMAL
│ ├ result_count       : 1
│ └ raw_status         : SOLVED
├ Solution (result = 1)
│ ├ primal_status        : FEASIBLE_POINT
│ ├ dual_status          : FEASIBLE_POINT
│ ├ objective_value      : 7.92350e-03
│ └ dual_objective_value : 7.92350e-03
└ Work counters
  ├ solve_time (sec)   : 2.76754e+00
  └ barrier_iterations : 15

Результаты вычислений

В результате оптимизации модели, получаем значения D и c:

D = value.(Z)

2×2 Matrix{Float64}:
  0.012616  -0.02132
 -0.02132    0.0410053
c = D \ value.(z)

2-element Vector{Float64}:
 -1.6318778932525726
 -0.6704582481106572

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

наибольший_радиус = maximum(map(x -> (x - c)' * D * (x - c), eachrow(S)))

0.9999999992711166

Совмещая полученное решение с графиком, мы видим эллипсоид, минимизирующий объём аппроксимации:

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)

Альтернативные постановки задачи


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

print_active_bridges(модель)

 * 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:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   * 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:
 |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 * 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:
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.GeometricMeanCone
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.GeoMeanToPowerBridge{Float64, MOI.VectorOfVariables}
 |   |   |  may introduce:
 |   |   |   * Supported constraint: MOI.VectorOfVariables-in-MOI.PowerCone{Float64}
 |   |   |   * Supported variable: 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.FunctionConversionBridge{Float64}
    | may introduce:
    | * Supported objective: MOI.ScalarAffineFunction{Float64}

Здесь говорится о том, что Clarabel не поддерживает целевую функцию типа MOI.VariableIndex, и что JuMP использовал MOI.Bridges.Objective.FunctionConversionBridge, чтобы преобразовать её в целевую функцию типа MOI.ScalarAffineFunction{Float64}.

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

@objective(модель, Max, 1.0 * t + 0.0);

Активные мосты (active bridges) — это концепция в контексте JuMP и MOI (MathOptInterface), которая используется для описания механизмов преобразования или адаптации между различными типами данных или структур в процессе оптимизации.

С помощью команды print_active_bridges, снова выведем активные мосты:

print_active_bridges(модель)

 * 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:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   * 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:
 |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 * 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:
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   |   * Unsupported constraint: MOI.VectorOfVariables-in-MOI.GeometricMeanCone
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.GeoMeanToPowerBridge{Float64, MOI.VectorOfVariables}
 |   |   |  may introduce:
 |   |   |   * Supported constraint: MOI.VectorOfVariables-in-MOI.PowerCone{Float64}
 |   |   |   * Supported variable: 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

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

  • Заменить MOI.VectorOfVariables в ограничении MOI.PositiveSemidefiniteConeTriangle @variable(model, Z[1:n, 1:n], PSD) на MOI.VectorAffineFunction в MOI.PositiveSemidefiniteConeTriangle @constraint(model, Z >= 0, PSDCone()).

  • Заменить MOI.VectorOfVariables в ограничении MOI.PositiveSemidefiniteConeSquare [s z'; z Z] >= 0, PSDCone() на MOI.VectorAffineFunction в MOI.PositiveSemidefiniteConeTriangle @constraint(model, LinearAlgebra.Symmetric([s z'; z Z]) >= 0, PSDCone()).

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

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

модель = Model(Clarabel.Optimizer)
set_silent(модель)
@variable(модель, z[1:n])
@variable(модель, s)
@variable(модель, t)
@variable(модель, Z[1:n, 1:n], Symmetric)
@constraint(модель, Z >= 0, PSDCone())
@constraint(модель, LinearAlgebra.Symmetric([s z'; z Z]) >= 0, PSDCone())
f = [1 - S[i, :]' * Z * S[i, :] + 2 * S[i, :]' * z - s for i in 1:m]
@constraint(модель, f in MOI.Nonnegatives(m))
@constraint(модель, 1 * [t; triangle_vec(Z)] .+ 0 in MOI.RootDetConeTriangle(n))
@objective(модель, Max, 1 * t + 0)
optimize!(модель)
assert_is_solved_and_feasible(модель)
solve_time_1 = solve_time(модель)

0.005081831

Данная формулировка выводит наиболее краткий результат:

print_active_bridges(модель)

 * 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:
 |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 * 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:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   * 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}
 |   |   * Supported variable: MOI.Nonnegatives
 |   * Supported variable: MOI.Reals

Обратите внимание, что нам все еще нужно устранить ограничения MOI.PositiveSemidefiniteConeTriangle.

модель = Model(Clarabel.Optimizer)
set_silent(модель)
@variable(модель, z[1:n])
@variable(модель, s)
@variable(модель, t)
@variable(модель, Z[1:n, 1:n], Symmetric)
f = triangle_vec(Z)
scale_f = [1.0, sqrt(2), 1.0]
@constraint(модель, scale_f .* f in MOI.Scaled(MOI.PositiveSemidefiniteConeTriangle(n)))
g = triangle_vec(LinearAlgebra.Symmetric([s z'; z Z]))
scale_g = [1.0, sqrt(2), 1.0, sqrt(2), sqrt(2), 1.0]
@constraint(модель, scale_g .* g in MOI.Scaled(MOI.PositiveSemidefiniteConeTriangle(1 + n)))
f = [1 - S[i, :]' * Z * S[i, :] + 2 * S[i, :]' * z - s for i in 1:m]
@constraint(модель, f in MOI.Nonnegatives(m))
@constraint(модель, 1 * [t; triangle_vec(Z)] .+ 0 in MOI.RootDetConeTriangle(n))
@objective(модель, Max, 1 * t + 0)
optimize!(модель)
assert_is_solved_and_feasible(модель)
solve_time_2 = solve_time(модель)

0.005723413

Данная формулировка выводит ещё более краткий результат:

print_active_bridges(модель)

 * Supported objective: MOI.ScalarAffineFunction{Float64}
 * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 * 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:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   * 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}
 |   |   * Supported variable: MOI.Nonnegatives
 |   * Supported variable: MOI.Reals
 * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}

Сейчас существует только один пункт с Unsupported constraint, показывающий, как JuMP переформулировал ограничение MOI.RootDetConeTriangle, добавив смесь ограничений MOI.PositiveSemidefiniteConeTriangle и MOI.GeometricMeanCone.

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

Однако существует множество других способов, как можно переформулировать MOI.GeometricMeanCone в нечто, что поддерживает Clarabel. Давайте посмотрим, что произойдет, если использовать функцию remove_bridge для удаления MOI.Bridges.Constraint.GeoMeanToPowerBridge.

remove_bridge(модель, MOI.Bridges.Constraint.GeoMeanToPowerBridge)
optimize!(модель)
assert_is_solved_and_feasible(модель)

Теперь время, затраченное на решение, составляет:

solve_time_3 = solve_time(модель)

0.21579577800000002

При этом, ранее оно составляло:

solve_time_2

0.005723413

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

print_active_bridges(модель)

 * Supported objective: MOI.ScalarAffineFunction{Float64}
 * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Nonnegatives
 * 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:
 |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}
 |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.GeometricMeanCone
 |   |  bridged by:
 |   |   MOIB.Constraint.GeoMeantoRelEntrBridge{Float64, MOI.VectorOfVariables, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}}
 |   |  may introduce:
 |   |   * Unsupported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.RelativeEntropyCone
 |   |   |  bridged by:
 |   |   |   MOIB.Constraint.RelativeEntropyBridge{Float64, MOI.ScalarAffineFunction{Float64}, MOI.VectorAffineFunction{Float64}, MOI.VectorAffineFunction{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
 |   |   |   * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.ExponentialCone
 |   |   |   * Supported variable: MOI.Reals
 |   |   * Supported variable: MOI.Nonnegatives
 |   * Supported variable: MOI.Reals
 * Supported constraint: MOI.VectorAffineFunction{Float64}-in-MOI.Scaled{MOI.PositiveSemidefiniteConeTriangle}

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

Выводы

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

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

Группа видимости
ПубличноПросматривать контент могут все пользователи сообщества

Тип

Интерактивные скрипты

Краткое описание

Задача вычисления экстремальных эллипсоидов — нахождения эллипсоидов, которые наилучшим образом аппроксимируют заданное множество

Связанные материалы

Пусто

Теги

Категории

Расчеты в EngeeГрафики и визуализация2-D и 3-D графикиПоверхности
Расчеты в EngeeМатематика и оптимизацияОптимизация

Языки

    Julia

Форматы

Пусто

Уровень

    Средний

Статус

Опубликовано

Обновлено

Источник

Сообщество