Standard form problem
MathOptInterface represents optimization problems in the standard form:
\[\begin{align} & \min_{x \in \mathbb{R}^n} & f_0(x) \\ & \;\;\text{s.t.} & f_i(x) & \in \mathcal{S}_i & i = 1 \ldots m \end{align}\]
where:
- the functions $f_0, f_1, \ldots, f_m$ are specified by
AbstractFunction
objects - the sets $\mathcal{S}_1, \ldots, \mathcal{S}_m$ are specified by
AbstractSet
objects
For more information on this standard form, read our paper.
MOI defines some commonly used functions and sets, but the interface is extensible to other sets recognized by the solver.
Functions
The function types implemented in MathOptInterface.jl are:
VariableIndex
: $x_j$, i.e., projection onto a single coordinate defined by a variable index $j$.VectorOfVariables
: projection onto multiple coordinates (i.e., extracting a subvector).ScalarAffineFunction
: $a^T x + b$, where $a$ is a vector and $b$ scalar.VectorAffineFunction
: $A x + b$, where $A$ is a matrix and $b$ is a vector.ScalarQuadraticFunction
: $\frac{1}{2} x^T Q x + a^T x + b$, where $Q$ is a symmetric matrix, $a$ is a vector, and $b$ is a constant.VectorQuadraticFunction
: a vector of scalar-valued quadratic functions.
Extensions for nonlinear programming are present but not yet well documented.
One-dimensional sets
The one-dimensional set types implemented in MathOptInterface.jl are:
LessThan(upper)
: $\{ x \in \mathbb{R} : x \le \mbox{upper} \}$GreaterThan(lower)
: $\{ x \in \mathbb{R} : x \ge \mbox{lower} \}$EqualTo(value)
: $\{ x \in \mathbb{R} : x = \mbox{value} \}$Interval(lower, upper)
: $\{ x \in \mathbb{R} : x \in [\mbox{lower},\mbox{upper}] \}$Integer()
: $\mathbb{Z}$ZeroOne()
: $\{ 0, 1 \}$Semicontinuous(lower,upper)
: $\{ 0\} \cup [\mbox{lower},\mbox{upper}]$Semiinteger(lower,upper)
: $\{ 0\} \cup \{\mbox{lower},\mbox{lower}+1,\ldots,\mbox{upper}-1,\mbox{upper}\}$
Vector cones
The vector-valued set types implemented in MathOptInterface.jl are:
Reals(dimension)
: $\mathbb{R}^{\mbox{dimension}}$Zeros(dimension)
: $0^{\mbox{dimension}}$Nonnegatives(dimension)
: $\{ x \in \mathbb{R}^{\mbox{dimension}} : x \ge 0 \}$Nonpositives(dimension)
: $\{ x \in \mathbb{R}^{\mbox{dimension}} : x \le 0 \}$SecondOrderCone(dimension)
: $\{ (t,x) \in \mathbb{R}^{\mbox{dimension}} : t \ge \lVert x \rVert_2 \}$RotatedSecondOrderCone(dimension)
: $\{ (t,u,x) \in \mathbb{R}^{\mbox{dimension}} : 2tu \ge \lVert x \rVert_2^2, t,u \ge 0 \}$ExponentialCone()
: $\{ (x,y,z) \in \mathbb{R}^3 : y \exp (x/y) \le z, y > 0 \}$DualExponentialCone()
: $\{ (u,v,w) \in \mathbb{R}^3 : -u \exp (v/u) \le \exp(1) w, u < 0 \}$GeometricMeanCone(dimension)
: $\{ (t,x) \in \mathbb{R}^{n+1} : x \ge 0, t \le \sqrt[n]{x_1 x_2 \cdots x_n} \}$ where $n$ is $\mbox{dimension} - 1$PowerCone(exponent)
: $\{ (x,y,z) \in \mathbb{R}^3 : x^{\mbox{exponent}} y^{1-\mbox{exponent}} \ge |z|, x,y \ge 0 \}$DualPowerCone(exponent)
: $\{ (u,v,w) \in \mathbb{R}^3 : \frac{u}{\mbox{exponent}}^{\mbox{exponent}}\frac{v}{1-\mbox{exponent}}^{1-\mbox{exponent}} \ge |w|, u,v \ge 0 \}$NormOneCone(dimension)
: $\{ (t,x) \in \mathbb{R}^{\mbox{dimension}} : t \ge \lVert x \rVert_1 \}$ where $\lVert x \rVert_1 = \sum_i \lvert x_i \rvert$NormInfinityCone(dimension)
: $\{ (t,x) \in \mathbb{R}^{\mbox{dimension}} : t \ge \lVert x \rVert_\infty \}$ where $\lVert x \rVert_\infty = \max_i \lvert x_i \rvert$.RelativeEntropyCone(dimension)
: $\{ (u, v, w) \in \mathbb{R}^{\mbox{dimension}} : u \ge \sum_i w_i \log (\frac{w_i}{v_i}), v_i \ge 0, w_i \ge 0 \}$
Matrix cones
The matrix-valued set types implemented in MathOptInterface.jl are:
RootDetConeTriangle(dimension)
: $\{ (t,X) \in \mathbb{R}^{1+\mbox{dimension}(1+\mbox{dimension})/2} : t \le \det(X)^{1/\mbox{dimension}}, X \mbox{ is the upper triangle of a PSD matrix} \}$RootDetConeSquare(dimension)
: $\{ (t,X) \in \mathbb{R}^{1+\mbox{dimension}^2} : t \le \det(X)^{1/\mbox{dimension}}, X \mbox{ is a PSD matrix} \}$PositiveSemidefiniteConeTriangle(dimension)
: $\{ X \in \mathbb{R}^{\mbox{dimension}(\mbox{dimension}+1)/2} : X \mbox{ is the upper triangle of a PSD matrix} \}$PositiveSemidefiniteConeSquare(dimension)
: $\{ X \in \mathbb{R}^{\mbox{dimension}^2} : X \mbox{ is a PSD matrix} \}$LogDetConeTriangle(dimension)
: $\{ (t,u,X) \in \mathbb{R}^{2+\mbox{dimension}(1+\mbox{dimension})/2} : t \le u\log(\det(X/u)), X \mbox{ is the upper triangle of a PSD matrix}, u > 0 \}$LogDetConeSquare(dimension)
: $\{ (t,u,X) \in \mathbb{R}^{2+\mbox{dimension}^2} : t \le u \log(\det(X/u)), X \mbox{ is a PSD matrix}, u > 0 \}$NormSpectralCone(row_dim, column_dim)
: $\{ (t, X) \in \mathbb{R}^{1 + \mbox{row\_dim} \times \mbox{column\_dim}} : t \ge \sigma_1(X), X \mbox{ is a matrix with row\_dim rows and column\_dim columns} \}$NormNuclearCone(row_dim, column_dim)
: $\{ (t, X) \in \mathbb{R}^{1 + \mbox{row\_dim} \times \mbox{column\_dim}} : t \ge \sum_i \sigma_i(X), X \mbox{ is a matrix with row\_dim rows and column\_dim columns} \}$
Some of these cones can take two forms: XXXConeTriangle
and XXXConeSquare
.
In XXXConeTriangle
sets, the matrix is assumed to be symmetric, and the elements are provided by a vector, in which the entries of the upper-right triangular part of the matrix are given column by column (or equivalently, the entries of the lower-left triangular part are given row by row).
In XXXConeSquare
sets, the entries of the matrix are given column by column (or equivalently, row by row), and the matrix is constrained to be symmetric. As an example, given a 2-by-2 matrix of variables X
and a one-dimensional variable t
, we can specify a root-det constraint as [t, X11, X12, X22] ∈ RootDetConeTriangle
or [t, X11, X12, X21, X22] ∈ RootDetConeSquare
.
We provide both forms to enable flexibility for solvers who may natively support one or the other. Transformations between XXXConeTriangle
and XXXConeSquare
are handled by bridges, which removes the chance of conversion mistakes by users or solver developers.
Multi-dimensional sets with combinatorial structure
SOS1(weights)
: A special ordered set of Type I.SOS2(weights)
: A special ordered set of Type II.Indicator(set)
: A set to specify indicator constraints.Complements(dimension)
: A set for mixed complementarity constraints.