Bridges
MathOptInterface.Bridges.AbstractBridge
— TypeAbstractBridge
Represents a bridged constraint or variable in a MathOptInterface.Bridges.AbstractBridgeOptimizer
. It contains the indices of the variables and constraints that it has created in the model. These can be obtained using MathOptInterface.NumberOfVariables
, MathOptInterface.ListOfVariableIndices
, MathOptInterface.NumberOfConstraints
and MathOptInterface.ListOfConstraintIndices
using MathOptInterface.get
with the bridge in place of the MathOptInterface.ModelLike
. Attributes of the bridged model such as MathOptInterface.ConstraintDual
and MathOptInterface.ConstraintPrimal
, can be obtained using MathOptInterface.get
with the bridge in place of the constraint index. These calls are used by the MathOptInterface.Bridges.AbstractBridgeOptimizer
to communicate with the bridge so they should be implemented by the bridge.
MathOptInterface.Bridges.AbstractBridgeOptimizer
— TypeAbstractBridgeOptimizer
A bridge optimizer applies given constraint bridges to a given optimizer thus extending the types of supported constraints. The attributes of the inner optimizer are automatically transformed to make the bridges transparent, e.g. the variables and constraints created by the bridges are hidden.
By convention, the inner optimizer should be stored in a model
field and the dictionary mapping constraint indices to bridges should be stored in a bridges
field. If a bridge optimizer deviates from these conventions, it should implement the functions MOI.optimize!
and bridge
respectively.
MathOptInterface.Bridges.LazyBridgeOptimizer
— TypeLazyBridgeOptimizer{OT<:MOI.ModelLike} <: AbstractBridgeOptimizer
The LazyBridgeOptimizer
combines several bridges, which are added using the add_bridge
function.
Whenever a constraint is added, it only attempts to bridge it if it is not supported by the internal model (hence its name Lazy
).
When bridging a constraint, it selects the minimal number of bridges needed.
For example, if a constraint F
-in-S
can be bridged into a constraint F1
-in-S1
(supported by the internal model) using bridge 1 or bridged into a constraint F2
-in-S2
(unsupported by the internal model) using bridge 2 which can then be bridged into a constraint F3
-in-S3
(supported by the internal model) using bridge 3, it will choose bridge 1 as it allows to bridge F
-in-`S using only one bridge instead of two if it uses bridge 2 and 3.
MathOptInterface.Bridges.add_bridge
— Functionadd_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})
Enable the use of the bridges of type BT
by b
.
MathOptInterface.Bridges.remove_bridge
— Functionremove_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})
Disable the use of the bridges of type BT
by b
.
MathOptInterface.Bridges.has_bridge
— Functionhas_bridge(b::LazyBridgeOptimizer, BT::Type{<:AbstractBridge})
Return a Bool
indicating whether the bridges of type BT
are used by b
.
MathOptInterface.Bridges.full_bridge_optimizer
— Functionfull_bridge_optimizer(model::MOI.ModelLike, ::Type{T}) where {T}
Returns a LazyBridgeOptimizer
bridging model
for every bridge defined in this package (see below for the few exceptions) and for the coefficient type T
in addition to the bridges in the list returned by MOI.get(model, MOI.Bridges.ListOfNonstandardBridges{T}())
.
See also ListOfNonstandardBridges
.
The following bridges are not added by full_bridge_optimizer
except if they are in the list returned by MOI.get(model, MOI.Bridges.ListOfNonstandardBridges{T}())
(see the docstrings of the corresponding bridge for the reason they are not added):
Constraint.SOCtoNonConvexQuadBridge
,Constraint.RSOCtoNonConvexQuadBridge
andConstraint.SOCtoPSDBridge
.- The subtypes of
Constraint.AbstractToIntervalBridge
(i.e.Constraint.GreaterToIntervalBridge
andConstraint.LessToIntervalBridge
) ifT
is not a subtype ofAbstractFloat
.
MathOptInterface.Bridges.ListOfNonstandardBridges
— TypeListOfNonstandardBridges{T}() <: MOI.AbstractOptimizerAttribute
Any optimizer can be wrapped in a LazyBridgeOptimizer
using full_bridge_optimizer
. However, by default LazyBridgeOptimizer
uses a limited set of bridges that are:
- implemented in
MOI.Bridges
- generally applicable for all optimizers.
For some optimizers however, it is useful to add additional bridges, such as those that are implemented in external packages (e.g., within the solver package itself) or only apply in certain circumstances (e.g., Constraint.SOCtoNonConvexQuadBridge
).
Such optimizers should implement the ListOfNonstandardBridges
attribute to return a vector of bridge types that are added by full_bridge_optimizer
in addition to the list of default bridges.
Note that optimizers implementing ListOfNonstandardBridges
may require package-specific functions or sets to be used if the non-standard bridges are not added. Therefore, you are recommended to use model = MOI.instantiate(Package.Optimizer; with_bridge_type = T)
instead of model = MOI.instantiate(Package.Optimizer)
. See MathOptInterface.instantiate
.
Examples
An optimizer using a non-default bridge in MOI.Bridges
Solvers supporting MOI.ScalarQuadraticFunction
can support MOI.SecondOrderCone
and MOI.RotatedSecondOrderCone
by defining:
function MOI.get(::MyQuadraticOptimizer, ::ListOfNonstandardBridges{Float64})
return Type[
MOI.Bridges.Constraint.SOCtoNonConvexQuadBridge{Float64},
MOI.Bridges.Constraint.RSOCtoNonConvexQuadBridge{Float64},
]
end
An optimizer defining an internal bridge
Suppose an optimizer can exploit specific structure of a constraint, e.g., it can exploit the structure of the matrix A
in the linear system of equations A * x = b
.
The optimizer can define the function:
struct MatrixAffineFunction{T} <: MOI.AbstractVectorFunction
A::SomeStructuredMatrixType{T}
b::Vector{T}
end
and then a bridge
struct MatrixAffineFunctionBridge{T} <: MOI.Constraint.AbstractBridge
# ...
end
# ...
from VectorAffineFunction{T}
to the MatrixAffineFunction
. Finally, it defines:
function MOI.get(::Optimizer{T}, ::ListOfNonstandardBridges{T}) where {T}
return Type[MatrixAffineFunctionBridge{T}]
end
MathOptInterface.Bridges.debug_supports_constraint
— Functiondebug_supports_constraint(
b::LazyBridgeOptimizer,
F::Type{<:MOI.AbstractFunction},
S::Type{<:MOI.AbstractSet};
io::IO = Base.stdout,
)
Prints to io
explanations for the value of MOI.supports_constraint
with the same arguments.
MathOptInterface.Bridges.debug_supports
— Functiondebug_supports(
b::LazyBridgeOptimizer,
::MOI.ObjectiveFunction{F};
io::IO = Base.stdout,
) where F
Prints to io
explanations for the value of MOI.supports
with the same arguments.
MathOptInterface.Bridges.bridged_variable_function
— Functionbridged_variable_function(
b::AbstractBridgeOptimizer,
vi::MOI.VariableIndex,
)
Return a MOI.AbstractScalarFunction
of variables of b.model
that equals vi
. That is, if the variable vi
is bridged, it returns its expression in terms of the variables of b.model
. Otherwise, it returns vi
.
MathOptInterface.Bridges.unbridged_variable_function
— Functionunbridged_variable_function(
b::AbstractBridgeOptimizer,
vi::MOI.VariableIndex,
)
Return a MOI.AbstractScalarFunction
of variables of b
that equals vi
. That is, if the variable vi
is an internal variable of b.model
created by a bridge but not visible to the user, it returns its expression in terms of the variables of bridged variables. Otherwise, it returns vi
.
MathOptInterface.Bridges.bridged_function
— Functionbridged_function(b::AbstractBridgeOptimizer, value)::typeof(value)
Substitute any bridged MOI.VariableIndex
in value
by an equivalent expression in terms of variables of b.model
.
MathOptInterface.Bridges.Variable.unbridged_map
— Functionunbridged_map( bridge::MOI.Bridges.Variable.AbstractBridge, vi::MOI.VariableIndex, )
For a bridged variable in a scalar set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vi
.
unbridged_map(
bridge::MOI.Bridges.Variable.AbstractBridge,
vis::Vector{MOI.VariableIndex},
)
For a bridged variable in a vector set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vis
. If this method is not implemented, it falls back to calling the following method for every variable of vis
.
unbridged_map(
bridge::MOI.Bridges.Variable.AbstractBridge,
vi::MOI.VariableIndex,
i::MOIB.IndexInVector,
)
For a bridged variable in a vector set, return a tuple of pairs mapping the variables created by the bridge to an affine expression in terms of the bridged variable vi
corresponding to the i
th variable of the vector.
If there is no way to recover the expression in terms of the bridged variable(s) vi(s)
, return nothing
. See ZerosBridge
for an example of bridge returning nothing
.
Constraint bridges
MathOptInterface.Bridges.Constraint.AbstractBridge
— TypeAbstractBridge
Subtype of MathOptInterface.Bridges.AbstractBridge
for constraint bridges.
MathOptInterface.Bridges.Constraint.AbstractFunctionConversionBridge
— Typeabstract type AbstractFunctionConversionBridge{F, S} <: AbstractBridge end
Bridge a constraint G
-in-S
into a constraint F
-in-S
where F
and G
are equivalent representations of the same function. By convention, the transformed function is stored in the constraint
field.
MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer
— TypeSingleBridgeOptimizer{BT<:AbstractBridge, OT<:MOI.ModelLike} <:
AbstractBridgeOptimizer
The SingleBridgeOptimizer
bridges any constraint supported by the bridge BT
. This is in contrast with the MathOptInterface.Bridges.LazyBridgeOptimizer
which only bridges the constraints that are unsupported by the internal model, even if they are supported by one of its bridges.
MathOptInterface.Bridges.Constraint.add_all_bridges
— Functionadd_all_bridges(bridged_model, ::Type{T}) where {T}
Add all bridges defined in the Bridges.Constraint
submodule to bridged_model
. The coefficient type used is T
.
SetMap bridges
MathOptInterface.Bridges.Variable.SetMapBridge
— Typeabstract type SetMapBridge{T,S1,S2} <: AbstractBridge end
Consider two type of sets S1
, S2
and a linear mapping A
that the image of a set of type S1
under A
is a set of type S2
. A SetMapBridge{T,S1,S2}
is a bridge that substitutes constrained variables in S2
into the image through A
of constrained variables in S1
.
The linear map A
is described by MathOptInterface.Bridges.map_set
, MathOptInterface.Bridges.map_function
. Implementing a method for these two functions is sufficient to bridge constrained variables. In order for the getters and setters of dual solutions, starting values, etc... to work as well a method for the following functions should be implemented as well: MathOptInterface.Bridges.inverse_map_set
, MathOptInterface.Bridges.inverse_map_function
, MathOptInterface.Bridges.adjoint_map_function
and MathOptInterface.Bridges.inverse_adjoint_map_function
. See the docstrings of the function to see which feature would be missing it it was not implemented for a given bridge.
MathOptInterface.Bridges.Constraint.SetMapBridge
— Typeabstract type SetMapBridge{T,S2,S1,F,G} <: AbstractBridge end
Consider two type of sets S1
, S2
and a linear mapping A
that the image of a set of type S1
under A
is a set of type S2
. A SetMapBridge{T,S2,S1,F,G}
is a bridge that maps G
-in-S2
constraints into F
-in-S1
by mapping the function through A
.
The linear map A
is described by MathOptInterface.Bridges.map_set
, MathOptInterface.Bridges.map_function
. Implementing a method for these two functions is sufficient to bridge constraints. In order for the getters and setters of dual solutions, starting values, etc... to work as well a method for the following functions should be implemented as well: MathOptInterface.Bridges.inverse_map_set
, MathOptInterface.Bridges.inverse_map_function
, MathOptInterface.Bridges.adjoint_map_function
and MathOptInterface.Bridges.inverse_adjoint_map_function
. See the docstrings of the function to see which feature would be missing it it was not implemented for a given bridge.
MathOptInterface.Bridges.map_set
— Functionmap_set(::Type{BT}, set) where {BT}
Return the image of set
through the linear map A
defined in Variable.SetMapBridge
and Constraint.SetMapBridge
. This is used for bridging the constraint and setting the MathOptInterface.ConstraintSet
.
MathOptInterface.Bridges.inverse_map_set
— Functioninverse_map_set(::Type{BT}, set) where {BT}
Return the preimage of set
through the linear map A
defined in Variable.SetMapBridge
and Constraint.SetMapBridge
. This is used for getting the MathOptInterface.ConstraintSet
.
MathOptInterface.Bridges.map_function
— Functionmap_function(::Type{BT}, func) where {BT}
Return the image of func
through the linear map A
defined in Variable.SetMapBridge
and Constraint.SetMapBridge
. This is used for getting the MathOptInterface.ConstraintPrimal
of variable bridges. For constraint bridges, this is used for bridging the constraint, setting the MathOptInterface.ConstraintFunction
and MathOptInterface.ConstraintPrimalStart
and modifying the function with MathOptInterface.modify
.
map_function(::Type{BT}, func, i::IndexInVector) where {BT}
Return the scalar function at the i
th index of the vector function that would be returned by map_function(BT, func)
except that it may compute the i
th element. This is used by bridged_function
and for getting the MathOptInterface.VariablePrimal
and MathOptInterface.VariablePrimalStart
of variable bridges.
MathOptInterface.Bridges.inverse_map_function
— Functioninverse_map_function(::Type{BT}, func) where {BT}
Return the image of func
through the inverse of the linear map A
defined in Variable.SetMapBridge
and Constraint.SetMapBridge
. This is used by Variable.unbridged_map
and for setting the MathOptInterface.VariablePrimalStart
of variable bridges and for getting the MathOptInterface.ConstraintFunction
, the MathOptInterface.ConstraintPrimal
and the MathOptInterface.ConstraintPrimalStart
of constraint bridges.
MathOptInterface.Bridges.adjoint_map_function
— Functionadjoint_map_function(::Type{BT}, func) where {BT}
Return the image of func
through the adjoint of the linear map A
defined in Variable.SetMapBridge
and Constraint.SetMapBridge
. This is used for getting the MathOptInterface.ConstraintDual
and MathOptInterface.ConstraintDualStart
of constraint bridges.
MathOptInterface.Bridges.inverse_adjoint_map_function
— Functioninverse_adjoint_map_function(::Type{BT}, func) where {BT}
Return the image of func
through the inverse of the adjoint of the linear map A
defined in Variable.SetMapBridge
and Constraint.SetMapBridge
. This is used for getting the MathOptInterface.ConstraintDual
of variable bridges and setting the MathOptInterface.ConstraintDualStart
of constraint bridges.
Bridges implemented
MathOptInterface.Bridges.Constraint.FlipSignBridge
— TypeFlipSignBridge{T, S1, S2, F, G}
Bridge a G
-in-S1
constraint into an F
-in-S2
constraint by multiplying the function by -1
and taking the point reflection of the set across the origin. The flipped F
-in-S
constraint is stored in the constraint
field by convention.
MathOptInterface.Bridges.Constraint.AbstractToIntervalBridge
— TypeAbstractToIntervalBridge{T, S1, F}
Bridge a F
-in-Interval
constraint into an F
-in-Interval{T}
constraint where we have either:
S1 = MOI.GreaterThan{T}
S1 = MOI.LessThan{T}
The F
-in-Interval{T}
constraint is stored in the constraint
field by convention.
It is required that T
be a AbstractFloat
type because otherwise typemin
and typemax
would either be not implemented (e.g. BigInt
) or would not give infinite value (e.g. Int
). For this reason, this bridge is only added to MathOptInterface.Bridges.full_bridge_optimizer
.
when T
is a subtype of AbstractFloat
.
MathOptInterface.Bridges.Constraint.GreaterToIntervalBridge
— TypeGreaterToIntervalBridge{T, F<:MOI.AbstractScalarFunction} <:
AbstractToIntervalBridge{T, MOI.GreaterThan{T}, F}
Transforms a F
-in-GreaterThan{T}
constraint into an F
-in-Interval{T}
constraint.
MathOptInterface.Bridges.Constraint.LessToIntervalBridge
— TypeLessToIntervalBridge{T, F<:MOI.AbstractScalarFunction} <:
AbstractToIntervalBridge{T, MOI.LessThan{T}, F}
Transforms a F
-in-LessThan{T}
constraint into an F
-in-Interval{T}
constraint.
MathOptInterface.Bridges.Constraint.GreaterToLessBridge
— TypeGreaterToLessBridge{
T,
F<:MOI.AbstractScalarFunction,
G<:MOI.AbstractScalarFunction
} <: FlipSignBridge{T, MOI.GreaterThan{T}, MOI.LessThan{T}, F, G}
Transforms a G
-in-GreaterThan{T}
constraint into an F
-in-LessThan{T}
constraint.
MathOptInterface.Bridges.Constraint.LessToGreaterBridge
— TypeLessToGreaterBridge{
T,
F<:MOI.AbstractScalarFunction,
G<:MOI.AbstractScalarFunction
} <: FlipSignBridge{T, MOI.LessThan{T}, MOI.GreaterThan{T}, F, G}
Transforms a G
-in-LessThan{T}
constraint into an F
-in-GreaterThan{T}
constraint.
MathOptInterface.Bridges.Constraint.NonnegToNonposBridge
— TypeNonnegToNonposBridge{
T,
F<:MOI.AbstractVectorFunction,
G<:MOI.AbstractVectorFunction
} <: FlipSignBridge{T, MOI.Nonnegatives, MOI.Nonpositives, F, G}
Transforms a G
-in-Nonnegatives
constraint into a F
-in-Nonpositives
constraint.
MathOptInterface.Bridges.Constraint.NonposToNonnegBridge
— TypeNonposToNonnegBridge{
T,
F<:MOI.AbstractVectorFunction,
G<:MOI.AbstractVectorFunction,
} <: FlipSignBridge{T, MOI.Nonpositives, MOI.Nonnegatives, F, G}
Transforms a G
-in-Nonpositives
constraint into a F
-in-Nonnegatives
constraint.
MathOptInterface.Bridges.Constraint.VectorizeBridge
— TypeVectorizeBridge{T,F,S,G}
Transforms a constraint G
-in-scalar_set_type(S, T)
where S <: VectorLinearSet
to F
-in-S
.
Examples
The constraint VariableIndex
-in-LessThan{Float64}
becomes VectorAffineFunction{Float64}
-in-Nonpositives
, where T = Float64
, F = VectorAffineFunction{Float64}
, S = Nonpositives
, and G = VariableIndex
.
MathOptInterface.Bridges.Constraint.ScalarizeBridge
— TypeScalarizeBridge{T, F, S}
Transforms a constraint AbstractVectorFunction
-in-vector_set_type(S)
where S <: LPCone{T}
to F
-in-S
.
MathOptInterface.Bridges.Constraint.ScalarSlackBridge
— TypeScalarSlackBridge{T, F, S}
The ScalarSlackBridge
converts a constraint G
-in-S
where G
is a function different from VariableIndex
into the constraints F
-in-EqualTo{T}
and VariableIndex
-in-S
.
F
is the result of subtracting a VariableIndex
from G
. Typically G
is the same as F
, but that is not mandatory.
MathOptInterface.Bridges.Constraint.VectorSlackBridge
— TypeVectorSlackBridge{T, F, S}
The VectorSlackBridge
converts a constraint G
-in-S
where G
is a function different from VectorOfVariables
into the constraints F
in-Zeros
and VectorOfVariables
-in-S
.
F
is the result of subtracting a VectorOfVariables
from G
. Typically G
is the same as F
, but that is not mandatory.
MathOptInterface.Bridges.Constraint.ScalarFunctionizeBridge
— TypeScalarFunctionizeBridge{T, S}
The ScalarFunctionizeBridge
converts a constraint VariableIndex
-in-S
into the constraint ScalarAffineFunction{T}
-in-S
.
MathOptInterface.Bridges.Constraint.VectorFunctionizeBridge
— TypeVectorFunctionizeBridge{T, S}
The VectorFunctionizeBridge
converts a constraint VectorOfVariables
-in-S
into the constraint VectorAffineFunction{T}
-in-S
.
MathOptInterface.Bridges.Constraint.SplitIntervalBridge
— TypeSplitIntervalBridge{T, F, S, LS, US}
The SplitIntervalBridge
splits a F
-in-S
constraint into a F
-in-LS
and a F
-in-US
constraint where we have either:
S = MOI.Interval{T}
,LS = MOI.GreaterThan{T}
andUS = MOI.LessThan{T}
,S = MOI.EqualTo{T}
,LS = MOI.GreaterThan{T}
andUS = MOI.LessThan{T}
, orS = MOI.Zeros
,LS = MOI.Nonnegatives
andUS = MOI.Nonpositives
.
For instance, if F
is MOI.ScalarAffineFunction
and S
is MOI.Interval
, it transforms the constraint $l ≤ ⟨a, x⟩ + α ≤ u$ into the constraints $⟨a, x⟩ + α ≥ l$ and $⟨a, x⟩ + α ≤ u$.
If T<:AbstractFloat
and S
is MOI.Interval{T}
then no lower (resp. upper) bound constraint is created if the lower (resp. upper) bound is typemin(T)
(resp. typemax(T)
). Similarly, when MathOptInterface.ConstraintSet
is set, a lower or upper bound constraint may be deleted or created accordingly.
MathOptInterface.Bridges.Constraint.SOCtoRSOCBridge
— TypeSOCtoRSOCBridge{T, F, G}
We simply do the inverse transformation of RSOCtoSOCBridge
. In fact, as the transformation is an involution, we do the same transformation.
MathOptInterface.Bridges.Constraint.RSOCtoSOCBridge
— TypeRSOCtoSOCBridge{T, F, G}
The RotatedSecondOrderCone
is SecondOrderCone
representable; see [BN01, p. 104]. Indeed, we have $2tu = (t/√2 + u/√2)^2 - (t/√2 - u/√2)^2$ hence
\[2tu \ge \lVert x \rVert_2^2\]
is equivalent to
\[(t/√2 + u/√2)^2 \ge \lVert x \rVert_2^2 + (t/√2 - u/√2)^2.\]
We can therefore use the transformation $(t, u, x) \mapsto (t/√2+u/√2, t/√2-u/√2, x)$. Note that the linear transformation is a symmetric involution (i.e. it is its own transpose and its own inverse). That means in particular that the norm of constraint primal and dual values are preserved by the tranformation.
[BN01] Ben-Tal, Aharon, and Nemirovski, Arkadi. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001.
MathOptInterface.Bridges.Constraint.SOCtoNonConvexQuadBridge
— TypeSOCtoNonConvexQuadBridge{T}
Constraints of the form VectorOfVariables
-in-SecondOrderCone
can be transformed into a ScalarQuadraticFunction
-in-LessThan
and a ScalarAffineFunction
-in-GreaterThan
. Indeed, the definition of the second-order cone
\[t \ge \lVert x \rVert_2 \ (1)\]
is equivalent to
\[\sum x_i^2 \le t^2 (2)\]
with $t \ge 0$. (3)
This transformation starts from a convex constraint (1) and creates a non-convex constraint (2), because the Q matrix associated with the constraint (2) has one negative eigenvalue. This might be wrongly interpreted by a solver. Some solvers can look at (2) and understand that it is a second order cone, but this is not a general rule. For these reasons this bridge is not automatically added by MOI.Bridges.full_bridge_optimizer
. Care is recommended when adding this bridge to a optimizer.
MathOptInterface.Bridges.Constraint.RSOCtoNonConvexQuadBridge
— TypeRSOCtoNonConvexQuadBridge{T}
Constraints of the form VectorOfVariables
-in-SecondOrderCone
can be transformed into a ScalarQuadraticFunction
-in-LessThan
and a ScalarAffineFunction
-in-GreaterThan
. Indeed, the definition of the second-order cone
\[2tu \ge \lVert x \rVert_2^2, t,u \ge 0 (1)\]
is equivalent to
\[\sum x_i^2 \le 2tu (2)\]
with $t,u \ge 0$. (3)
WARNING This transformation starts from a convex constraint (1) and creates a non-convex constraint (2), because the Q matrix associated with the constraint 2 has two negative eigenvalues. This might be wrongly interpreted by a solver. Some solvers can look at (2) and understand that it is a rotated second order cone, but this is not a general rule. For these reasons, this bridge is not automatically added by MOI.Bridges.full_bridge_optimizer
. Care is recommended when adding this bridge to an optimizer.
MathOptInterface.Bridges.Constraint.QuadtoSOCBridge
— TypeQuadtoSOCBridge{T}
The set of points x
satisfying the constraint
\[\frac{1}{2}x^T Q x + a^T x + b \le 0\]
is a convex set if Q
is positive semidefinite and is the union of two convex cones if a
and b
are zero (i.e. homogeneous case) and Q
has only one negative eigenvalue. Currently, only the non-homogeneous transformation is implemented, see the Note section below for more details.
Non-homogeneous case
If Q
is positive semidefinite, there exists U
such that $Q = U^T U$, the inequality can then be rewritten as
\[\|U x\|_2^2 \le 2 (-a^T x - b)\]
which is equivalent to the membership of (1, -a^T x - b, Ux)
to the rotated second-order cone.
Homogeneous case
If Q
has only one negative eigenvalue, the set of x
such that $x^T Q x \le 0$ is the union of a convex cone and its opposite. We can choose which one to model by checking the existence of bounds on variables as shown below.
Second-order cone
If Q
is diagonal and has eigenvalues (1, 1, -1)
, the inequality $x^2 + x^2 \le z^2$ combined with $z \ge 0$ defines the Lorenz cone (i.e. the second-order cone) but when combined with $z \le 0$, it gives the opposite of the second order cone. Therefore, we need to check if the variable z
has a lower bound 0 or an upper bound 0 in order to determine which cone is
Rotated second-order cone
The matrix Q
corresponding to the inequality $x^2 \le 2yz$ has one eigenvalue 1 with eigenvectors (1, 0, 0)
and (0, 1, -1)
and one eigenvalue -1
corresponding to the eigenvector (0, 1, 1)
. Hence if we intersect this union of two convex cone with the halfspace $x + y \ge 0$, we get the rotated second-order cone and if we intersect it with the halfspace $x + y \le 0$ we get the opposite of the rotated second-order cone. Note that y
and z
have the same sign since yz
is nonnegative hence $x + y \ge 0$ is equivalent to $x \ge 0$ and $y \ge 0$.
Note
The check for existence of bound can be implemented (but inefficiently) with the current interface but if bound is removed or transformed (e.g. ≤ 0
transformed into ≥ 0
) then the bridge is no longer valid. For this reason the homogeneous version of the bridge is not implemented yet.
MathOptInterface.Bridges.Constraint.SOCtoPSDBridge
— TypeThe SOCtoPSDBridge
transforms the second order cone constraint $\lVert x \rVert \le t$ into the semidefinite cone constraints
\[\begin{pmatrix} t & x^\top\\ x & tI \end{pmatrix} \succeq 0\]
Indeed by the Schur Complement, it is positive definite iff
\[\begin{align*} tI & \succ 0\\ t - x^\top (tI)^{-1} x & \succ 0 \end{align*}\]
which is equivalent to
\[\begin{align*} t & > 0\\ t^2 & > x^\top x \end{align*}\]
This bridge is not added by default by MOI.Bridges.full_bridge_optimizer
as bridging second order cone constraints to semidefinite constraints can be achieved by the SOCtoRSOCBridge
followed by the RSOCtoPSDBridge
while creating a smaller semidefinite constraint.
MathOptInterface.Bridges.Constraint.RSOCtoPSDBridge
— TypeThe RSOCtoPSDBridge
transforms the second order cone constraint $\lVert x \rVert \le 2tu$ with $u \ge 0$ into the semidefinite cone constraints
\[\begin{pmatrix} t & x^\top\\ x & 2uI \end{pmatrix} \succeq 0\]
Indeed by the Schur Complement, it is positive definite iff
\[\begin{align*} uI & \succ 0\\ t - x^\top (2uI)^{-1} x & \succ 0 \end{align*}\]
which is equivalent to
\[\begin{align*} u & > 0\\ 2tu & > x^\top x \end{align*}\]
MathOptInterface.Bridges.Constraint.NormInfinityBridge
— TypeNormInfinityBridge{T}
The NormInfinityCone
is representable with LP constraints, since $t \ge \max_i \lvert x_i \rvert$ if and only if $t \ge x_i$ and $t \ge -x_i$ for all $i$.
MathOptInterface.Bridges.Constraint.NormOneBridge
— TypeNormOneBridge{T}
The NormOneCone
is representable with LP constraints, since $t \ge \sum_i \lvert x_i \rvert$ if and only if there exists a vector y such that $t \ge \sum_i y_i$ and $y_i \ge x_i$, $y_i \ge -x_i$ for all $i$.
MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge
— TypeGeoMeantoRelEntrBridge{T}
The geometric mean cone
is representable with a relative entropy constraint and a nonnegative auxiliary variable.
This is because $u \le \prod_{i=1}^n w_i^{1/n}$ is equivalent to $y \ge 0$ and $0 \le u + y \le \prod_{i=1}^n w_i^{1/n}$, and the latter inequality is equivalent to $1 \le \prod_{i=1}^n (\frac{w_i}{u + y})^{1/n}$, which is equivalent to $0 \le \sum_{i=1}^n \log (\frac{w_i}{u + y})^{1/n}$, which is equivalent to $0 \ge \sum_{i=1}^n (u + y) \log (\frac{u + y}{w_i})$.
Thus $(u, w) \in GeometricMeanCone(1 + n)$ is representable as $y \ge 0$, $(0, w, (u + y) e) \in RelativeEntropyCone(1 + 2n)$, where $e$ is a vector of ones.
MathOptInterface.Bridges.Constraint.GeoMeanBridge
— TypeGeoMeanBridge{T, F, G, H}
The GeometricMeanCone
is SecondOrderCone
representable; see [1, p. 105].
The reformulation is best described in an example.
Consider the cone of dimension 4:
\[t \le \sqrt[3]{x_1 x_2 x_3}\]
This can be rewritten as $\exists x_{21} \ge 0$ such that:
\[\begin{align*} t & \le x_{21},\\ x_{21}^4 & \le x_1 x_2 x_3 x_{21}. \end{align*}\]
Note that we need to create $x_{21}$ and not use $t^4$ directly as $t$ is allowed to be negative. Now, this is equivalent to:
\[\begin{align*} t & \le x_{21}/\sqrt{4},\\ x_{21}^2 & \le 2x_{11} x_{12},\\ x_{11}^2 & \le 2x_1 x_2, & x_{12}^2 & \le 2x_3(x_{21}/\sqrt{4}). \end{align*}\]
[1] Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001.
MathOptInterface.Bridges.Constraint.RelativeEntropyBridge
— TypeRelativeEntropyBridge{T}
The RelativeEntropyCone
is representable with exponential cone and LP constraints, since $u \ge \sum_{i=1}^n w_i \log (\frac{w_i}{v_i})$ if and only if there exists a vector $y$ such that $u \ge \sum_i y_i$ and $y_i \ge w_i \log (\frac{w_i}{v_i})$ or equivalently $v_i \ge w_i \exp (\frac{-y_i}{w_i})$ or equivalently $(-y_i, w_i, v_i) \in ExponentialCone$, for all $i$.
MathOptInterface.Bridges.Constraint.NormSpectralBridge
— TypeNormSpectralBridge{T}
The NormSpectralCone
is representable with a PSD constraint, since $t \ge \sigma_1(X)$ if and only if $[tI X^\top; X tI] \succ 0$.
MathOptInterface.Bridges.Constraint.NormNuclearBridge
— TypeNormNuclearBridge{T}
The NormNuclearCone
is representable with an SDP constraint and extra variables, since $t \ge \sum_i \sigma_i (X)$ if and only if there exists symmetric matrices $U, V$ such that $[U X^\top; X V] \succ 0$ and $t \ge (tr(U) + tr(V)) / 2$.
MathOptInterface.Bridges.Constraint.SquareBridge
— TypeSquareBridge{T, F<:MOI.AbstractVectorFunction,
G<:MOI.AbstractScalarFunction,
TT<:MOI.AbstractSymmetricMatrixSetTriangle,
ST<:MOI.AbstractSymmetricMatrixSetSquare} <: AbstractBridge
The SquareBridge
reformulates the constraint of a square matrix to be in ST
to a list of equality constraints for pair or off-diagonal entries with different expressions and a TT
constraint the upper triangular part of the matrix.
For instance, the constraint for the matrix
\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ 1 + x & 2 + x & 3 - x\\ 2 - 3x & 2 + x & 2x \end{pmatrix}\]
to be PSD can be broken down to the constraint of the symmetric matrix
\[\begin{pmatrix} 1 & 1 + x & 2 - 3x\\ \cdot & 2 + x & 3 - x\\ \cdot & \cdot & 2x \end{pmatrix}\]
and the equality constraint between the off-diagonal entries (2, 3) and (3, 2) $2x == 1$. Note that now symmetrization constraint need to be added between the off-diagonal entries (1, 2) and (2, 1) or between (1, 3) and (3, 1) since the expressions are the same.
MathOptInterface.Bridges.Constraint.RootDetBridge
— TypeRootDetBridge{T,F,G,H}
The RootDetConeTriangle
is representable by a PositiveSemidefiniteConeTriangle
and an GeometricMeanCone
constraints; see [1, p. 149].
Indeed, $t \le \det(X)^{1/n}$ if and only if there exists a lower triangular matrix $Δ$ such that:
\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ t & \le (Δ_{11} Δ_{22} \cdots Δ_{nn})^{1/n} \end{align*}\]
[1] Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001.
MathOptInterface.Bridges.Constraint.LogDetBridge
— TypeLogDetBridge{T,F,G,H,I}
The LogDetConeTriangle
is representable by a PositiveSemidefiniteConeTriangle
and ExponentialCone
constraints.
Indeed, $\log\det(X) = \log(\delta_1) + \cdots + \log(\delta_n)$ where $\delta_1$, ..., $\delta_n$ are the eigenvalues of $X$.
Adapting the method from [1, p. 149], we see that $t \le u \log(\det(X/u))$ for $u > 0$ if and only if there exists a lower triangular matrix $Δ$ such that
\[\begin{align*} \begin{pmatrix} X & Δ\\ Δ^\top & \mathrm{Diag}(Δ) \end{pmatrix} & \succeq 0\\ t & \le u \log(Δ_{11}/u) + u \log(Δ_{22}/u) + \cdots + u \log(Δ_{nn}/u) \end{align*}\]
[1] Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics, 2001. ```
MathOptInterface.Bridges.Constraint.IndicatorActiveOnFalseBridge
— TypeIndicatorActiveOnFalseBridge{T}
The IndicatorActiveOnFalseBridge
replaces an indicator constraint activated on 0 with a variable $z_0$ with the constraint activated on 1, with a variable $z_1$. It stores the added variable
and added constraints:
- $z_1 \in \mathbb{B}$ in
zero_one_cons
- $z_0 + z_1 == 1$ in `
in
disjunction_cons` - The added
ACTIVATE_ON_ONE
indicator constraint inindicator_cons_index
.
MathOptInterface.Bridges.Constraint.IndicatorSOS1Bridge
— TypeIndicatorSOS1Bridge{T,S<:MOI.AbstractScalarSet}
The IndicatorSOS1Bridge
replaces an indicator constraint of the following form: $z \in \mathbb{B}, z == 1 \implies f(x) \in S$ with a SOS1 constraint: $z \in \mathbb{B}, slack \text{ free}, f(x) + slack \in S, SOS1(slack, z)$.
MathOptInterface.Bridges.Constraint.SemiToBinaryBridge
— TypeSemiToBinaryBridge{T, S <: MOI.AbstractScalarSet}
The SemiToBinaryBridge
replaces a Semicontinuous constraint: $x \in \mathsf{Semicontinuous}(l, u)$ is replaced by: $z \in \{0, 1\}$, $x \leq z \cdot u$, $x \geq z \cdot l$.
The SemiToBinaryBridge
replaces a Semiinteger constraint: $x \in Semiinteger(l, u)$ is replaced by: $z \in \{0, 1\}$, $x \in \mathbb{Z}$, $x \leq z \cdot u$, $x \geq z \cdot l$.
MathOptInterface.Bridges.Constraint.ZeroOneBridge
— TypeZeroOneBridge{T}
The ZeroOneBridge
splits a MOI.VariableIndex
-in-MOI.ZeroOne
constraint into a MOI.VariableIndex
-in-MOI.Integer
constraint and a MOI.VariableIndex
-in-MOI.Interval(0, 1)
constraint.
Variable bridges
MathOptInterface.Bridges.Variable.AbstractBridge
— TypeAbstractBridge
Subtype of MathOptInterface.Bridges.AbstractBridge
for variable bridges.
MathOptInterface.Bridges.Variable.SingleBridgeOptimizer
— TypeSingleBridgeOptimizer{BT<:AbstractBridge, OT<:MOI.ModelLike} <:
AbstractBridgeOptimizer
The SingleBridgeOptimizer
bridges any constrained variables supported by the bridge BT
. This is in contrast with the MathOptInterface.Bridges.LazyBridgeOptimizer
which only bridges the constrained variables that are unsupported by the internal model, even if they are supported by one of its bridges.
Two bridge optimizers using variable bridges cannot be used together as both of them assume that the underlying model only returns variable indices with nonnegative values.
MathOptInterface.Bridges.Variable.add_all_bridges
— Functionadd_all_bridges(bridged_model, ::Type{T}) where {T}
Add all bridges defined in the Bridges.Variable
submodule to bridged_model
. The coefficient type used is T
.
Bridges implemented
MathOptInterface.Bridges.Variable.FlipSignBridge
— TypeFlipSignBridge{T, S1, S2}
Bridge constrained variables in S1
into constrained variables in S2
by multiplying the variables by -1
and taking the point reflection of the set across the origin. The flipped MOI.VectorOfVariables
-in-S
constraint is stored in the flipped_constraint
field by convention.
MathOptInterface.Bridges.Variable.ZerosBridge
— TypeZerosBridge{T} <: Bridges.Variable.AbstractBridge
Transforms constrained variables in MathOptInterface.Zeros
to zeros, which ends up creating no variables in the underlying model.
The bridged variables are therefore similar to parameters with zero values. Parameters with non-zero value can be created with constrained variables in MOI.EqualTo
by combining a VectorizeBridge
and this bridge. The functions cannot be unbridged, given a function, we cannot determine, if the bridged variables were used.
The dual values cannot be determined by the bridge but they can be determined by the bridged optimizer using MathOptInterface.Utilities.get_fallback
if a CachingOptimizer
is used (since ConstraintFunction
cannot be got as functions cannot be unbridged).
MathOptInterface.Bridges.Variable.FreeBridge
— TypeFreeBridge{T} <: Bridges.Variable.AbstractBridge
Transforms constrained variables in MOI.Reals
to the difference of constrained variables in MOI.Nonnegatives
.
MathOptInterface.Bridges.Variable.NonposToNonnegBridge
— TypeNonposToNonnegBridge{T} <:
FlipSignBridge{T, MOI.Nonpositives, MOI.Nonnegatives}
Transforms constrained variables in Nonpositives
into constrained variables in Nonnegatives
.
MathOptInterface.Bridges.Variable.VectorizeBridge
— TypeVectorizeBridge{T, S}
Transforms a constrained variable in scalar_set_type(S, T)
where S <: VectorLinearSet
into a constrained vector of one variable in S
. For instance, VectorizeBridge{Float64, MOI.Nonnegatives}
transforms a constrained variable in MOI.GreaterThan{Float64}
into a constrained vector of one variable in MOI.Nonnegatives
.
MathOptInterface.Bridges.Variable.SOCtoRSOCBridge
— TypeSOCtoRSOCBridge{T} <: Bridges.Variable.SetMapBridge{T,MOI.RotatedSecondOrderCone,MOI.SecondOrderCone}
Same transformation as MOI.Bridges.Constraint.SOCtoRSOCBridge
.
MathOptInterface.Bridges.Variable.RSOCtoSOCBridge
— TypeRSOCtoSOCBridge{T} <: Bridges.Variable.SetMapBridge{T,MOI.SecondOrderCone,MOI.RotatedSecondOrderCone}
Same transformation as MOI.Bridges.Constraint.RSOCtoSOCBridge
.
MathOptInterface.Bridges.Variable.RSOCtoPSDBridge
— TypeRSOCtoPSDBridge{T} <: Bridges.Variable.AbstractBridge
Transforms constrained variables in MathOptInterface.RotatedSecondOrderCone
to constrained variables in MathOptInterface.PositiveSemidefiniteConeTriangle
.
Objective bridges
MathOptInterface.Bridges.Objective.AbstractBridge
— TypeAbstractBridge
Subtype of MathOptInterface.Bridges.AbstractBridge
for objective bridges.
MathOptInterface.Bridges.Objective.SingleBridgeOptimizer
— TypeSingleBridgeOptimizer{BT<:AbstractBridge, OT<:MOI.ModelLike} <: AbstractBridgeOptimizer
The SingleBridgeOptimizer
bridges any objective functions supported by the bridge BT
. This is in contrast with the MathOptInterface.Bridges.LazyBridgeOptimizer
which only bridges the objective functions that are unsupported by the internal model, even if they are supported by one of its bridges.
MathOptInterface.Bridges.Objective.add_all_bridges
— Functionadd_all_bridges(bridged_model, ::Type{T}) where {T}
Add all bridges defined in the Bridges.Objective
submodule to bridged_model
. The coefficient type used is T
.
Bridges implemented
MathOptInterface.Bridges.Objective.SlackBridge
— TypeSlackBridge{T, F, G}
The SlackBridge
converts an objective function of type G
into a MOI.VariableIndex
objective by creating a slack variable and a F
-in-MOI.LessThan
constraint for minimization or F
-in-MOI.LessThan
constraint for maximization where F
is MOI.Utilities.promote_operation(-, T, G, MOI.VariableIndex}
. Note that when using this bridge, changing the optimization sense is not supported. Set the sense to MOI.FEASIBILITY_SENSE
first to delete the bridge in order to change the sense, then re-add the objective.
MathOptInterface.Bridges.Objective.FunctionizeBridge
— TypeFunctionizeBridge{T}
The FunctionizeBridge
converts a VariableIndex
objective into a ScalarAffineFunction{T}
objective.