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

Ellipsoid approximation

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

This tutorial was generated using Literate.jl. Download the source as a .jl file.

This tutorial considers the problem of computing extremal ellipsoids: finding ellipsoids that best approximate a given set. As an extension, we show how to use JuMP to inspect the bridges that were used, and how to explore alternative formulations.

The model comes from Section 4.9 of BenTal2001.

For a related example, see also the Minimal ellipses tutorial.

Problem formulation

Suppose that we are given a set consisting of points in -dimensional space:

Our goal is to determine an optimal vector and an optimal real symmetric matrix such that the ellipse:

contains and has the smallest possible volume.

The optimal and are given by the optimization problem:

where Missing open brace for subscript and Missing open brace for subscript .

Required packages

This tutorial uses the following packages:

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

Data

We first need to generate some points to work with.

function generate_point_cloud(
    m;            # number of 2-dimensional points
    a = 10,       # scaling in x direction
    b = 2,        # scaling in y direction
    rho = π / 6,  # rotation of points around origin
    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)

For the sake of this example, let’s take :

S = generate_point_cloud(600);

We will visualise the points (and ellipse) using the Plots package:

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 formulation

Now let’s build and the JuMP model. We’ll compute and after the solve.

model = Model(SCS.Optimizer)
# We need to use a tighter tolerance for this example, otherwise the bounding
# ellipse won't actually be bounding...
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)   : 7.34481e-01

Results

After solving the model to optimality we can recover the solution in terms of and :

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

Finally, overlaying the solution in the plot we see the minimal volume approximating ellipsoid:

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)

Alternative formulations

The formulation of model uses MOI.RootDetConeSquare. However, because SCS does not natively support this cone, JuMP automatically reformulates the problem into an equivalent problem that SCS does support. You can see the reformulation that JuMP chose using 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

There’s a lot going on here, but the first bullet is:

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

This says that SCS does not support a MOI.VariableIndex objective function, and that JuMP used a MOI.Bridges.Objective.FunctionizeBridge to convert it into a MOI.ScalarAffineFunction{Float64} objective function.

We can leave JuMP to do the reformulation, or we can rewrite our model to have an objective function that SCS natively supports:

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

Re-printing the active bridges:

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

we get * Supported objective: MOI.ScalarAffineFunction{Float64}.

We can manually implement some other reformulations to change our model to something that SCS more closely supports by:

  • Replacing the MOI.VectorOfVariables in MOI.PositiveSemidefiniteConeTriangle constraint @variable(model, Z1:n, 1:n], PSD) with the [MOI.VectorAffineFunction in MOI.PositiveSemidefiniteConeTriangle @constraint(model, Z >= 0, PSDCone()).

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

  • Replacing the MOI.ScalarAffineFunction in MOI.GreaterThan constraints with the vectorized equivalent of MOI.VectorAffineFunction in MOI.Nonnegatives

  • Replacing the MOI.VectorOfVariables in MOI.RootDetConeSquare constraint with MOI.VectorAffineFunction in MOI.RootDetConeTriangle.

Note that we still need to bridge MOI.PositiveSemidefiniteConeTriangle constraints because SCS uses an internal SCS.ScaledPSDCone set instead.

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)
# The former @variable(model, Z[1:n, 1:n], PSD)
@variable(model, Z[1:n, 1:n], Symmetric)
@constraint(model, Z >= 0, PSDCone())
# The former [s z'; z Z] >= 0, PSDCone()
@constraint(model, LinearAlgebra.Symmetric([s z'; z Z]) >= 0, PSDCone())
# The former constraint 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))
# The former constraint [t; vec(Z)] in MOI.RootDetConeSquare(n)
@constraint(model, 1 * [t; triangle_vec(Z)] .+ 0 in MOI.RootDetConeTriangle(n))
# The former @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)
0.7327927020000001

This formulation gives the much smaller graph:

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

The last bullet shows how JuMP reformulated the MOI.RootDetConeTriangle constraint by adding a mix of MOI.PositiveSemidefiniteConeTriangle and MOI.GeometricMeanCone constraints.

Because SCS doesn’t natively support the MOI.GeometricMeanCone, these constraints were further bridged using a MOI.Bridges.Constraint.GeoMeanToPowerBridge to a series of MOI.PowerCone constraints.

However, there are many other ways that a MOI.GeometricMeanCone can be reformulated into something that SCS supports. Let’s see what happens if we use remove_bridge](../../api.md#JuMP.remove_bridge-Union{Tuple{S}, Tuple{T}, Tuple{GenericModel{S}, Type{<:MathOptInterface.Bridges.AbstractBridge}}} where {T, S}) to remove the [MOI.Bridges.Constraint.GeoMeanToPowerBridge:

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

This time, the solve took:

solve_time_2 = solve_time(model)
0.370975449

where previously it took

solve_time_1
0.7327927020000001

Why was the solve time different?

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

This time, JuMP used a MOI.Bridges.Constraint.GeoMeanBridge to reformulate the constraint into a set of MOI.RotatedSecondOrderCone constraints, which were further reformulated into a set of supported MOI.SecondOrderCone constraints.

Since the two models are equivalent, we can conclude that for this particular model, the MOI.SecondOrderCone formulation is more efficient.

In general though, the performance of a particular reformulation is problem- and solver-specific. Therefore, JuMP chooses to minimize the number of bridges in the default reformulation, leaving you to explore alternative formulations using the tools and techniques shown in this tutorial.