12.2 Conic Optimization

Conic optimization is an extension of linear optimization (see Sec. 12.1 (Linear Optimization)) allowing conic domains to be specified for subsets of the problem variables. A conic optimization problem to be solved by MOSEK can be written as

(12.8)\[\begin{split}\begin{array}{lccccc} \mbox{minimize} & & & c^T x + c^f & & \\ \mbox{subject to} & l^c & \leq & A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x, \\ & & & x \in \K, & & \end{array}\end{split}\]

where

  • \(m\) is the number of constraints.
  • \(n\) is the number of decision variables.
  • \(x \in \real^n\) is a vector of decision variables.
  • \(c \in \real^n\) is the linear part of the objective function.
  • \(c^f\in \real\) is a constant term in the objective
  • \(A \in \real^{m \times n}\) is the constraint matrix.
  • \(l^c \in \real^m\) is the lower limit on the activity for the constraints.
  • \(u^c \in \real^m\) is the upper limit on the activity for the constraints.
  • \(l^x \in \real^n\) is the lower limit on the activity for the variables.
  • \(u^x \in \real^n\) is the upper limit on the activity for the variables.

Lower and upper bounds can be infinite, or in other words the corresponding bound may be omitted.

The set \(\K\) is a Cartesian product of convex cones, namely \(\K = \K_1 \times \cdots \times \K_p\). Having the domain restriction \(x \in \K\), is thus equivalent to

\[x^t \in \K_t \subseteq \real^{n_t},\]

where \(x = (x^1, \ldots , x^p)\) is a partition of the problem variables. Please note that the \(n\)-dimensional Euclidean space \(\real^n\) is a cone itself, so simple linear variables are still allowed. The user only needs to specify subsets of variables which belong to non-trivial cones.

In this section we discuss the formulations which apply to the following cones supported by MOSEK:

  • The set \(\real^n\).

  • The zero cone \(\{(0,\ldots,0)\}\).

  • Quadratic cone

    \[\Q^n = \left\lbrace x \in \real^n: x_1 \geq \sqrt{\sum_{j=2}^n x_j^2} \right\rbrace.\]
  • Rotated quadratic cone

    \[\Qr^n = \left\lbrace x \in \real^n: 2 x_1 x_2 \geq \sum_{j=3}^n x_j^2,\quad x_1 \geq 0,\quad x_2 \geq 0 \right\rbrace.\]
  • Primal exponential cone

    \[\EXP = \left\lbrace x \in \real^{3}: x_1\geq x_2\exp(x_3/x_2),\quad x_1,x_2 \geq 0 \right\rbrace\]

    as well as its dual

    \[\EXP^* = \left\lbrace x \in \real^{3}: x_1 \geq -x_3 e^{-1}\exp(x_2/x_3), \quad x_3\leq 0,x_1 \geq 0 \right\rbrace.\]
  • Primal power cone (with parameter \(0< \alpha< 1\))

    \[\POW^{\alpha,1-\alpha}_n = \left\lbrace x \in \real^{n}: x_1^\alpha x_2^{1-\alpha}\geq \sqrt{\sum_{j=3}^{n} x_j^2},\quad x_1,x_2 \geq 0 \right\rbrace\]

    as well as its dual

    \[(\POW^{\alpha,1-\alpha}_n )^* = \left\lbrace x \in \real^{n}: \left(\frac{x_1}{\alpha}\right)^\alpha \left(\frac{x_2}{1-\alpha}\right)^{1-\alpha} \geq \sqrt{\sum_{j=3}^{n} x^2_j}, \quad x_1, x_2 \geq 0 \right\rbrace.\]

MOSEK supports also the cone of positive semidefinite matrices. Since that is handled through a separate interface, we discuss it in Sec. 12.3 (Semidefinite Optimization).

12.2.1 Duality for Conic Optimization

Corresponding to the primal problem (12.8), there is a dual problem

(12.9)\[\begin{split}\begin{array} {lc} \mbox{maximize} & (l^c)^T s_l^c - (u^c)^T s_u^c + (l^x)^T s_l^x - (u^x)^T s_u^x + c^f\\ \mbox{subject to} &\\ & A^T y + s_l^x - s_u^x + s_n^x = c \\ & -y + s_l^c - s_u^c = 0, \\ & s_l^c,s_u^c,s_l^x ,s_u^x \geq 0, \\ & s_n^x \in \K^*, \end{array}\end{split}\]

where the dual cone \(\K^*\) is a Cartesian product of the cones dual to \(\K_t\). In practice this means that \(s_n^x\) has one entry for each entry in \(x\). Please note that the dual problem of the dual problem is identical to the original primal problem.

If a bound in the primal problem is plus or minus infinity, the corresponding dual variable is fixed at 0, and we use the convention that the product of the bound value and the corresponding dual variable is 0. This is equivalent to removing variable \((s_l^x)_j\) from the dual problem. In other words:

\[l_j^x = -\infty \quad \Rightarrow \quad (s_l^x)_j=0 \mbox{ and } l_j^x\cdot (s_l^x)_j = 0.\]

A solution

\[(y,s_l^c,s_u^c,s_l^x,s_u^x,s_n^x)\]

to the dual problem is feasible if it satisfies all the constraints in (12.9). If (12.9) has at least one feasible solution, then (12.9) is (dual) feasible, otherwise the problem is (dual) infeasible.

A solution

\[(x^*,y^*,(s_l^c)^*,(s_u^c)^*,(s_l^x)^*,(s_u^x)^*,(s_n^x)^*)\]

is denoted a primal-dual feasible solution, if \((x^*)\) is a solution to the primal problem (12.8) and \((y^*,(s_l^c)^*,(s_u^c)^*,(s_l^x)^*,(s_u^x)^*,(s_n^x)^*)\) is a solution to the corresponding dual problem (12.9). We also define an auxiliary vector

\[(x^c)^* := Ax^*\]

containing the activities of linear constraints.

For a primal-dual feasible solution we define the duality gap as the difference between the primal and the dual objective value,

(12.10)\[\begin{split}\begin{array}{l} c^T x^* + c^f - \left\lbrace (l^c)^T (s_l^c)^* - (u^c)^T (s_u^c)^* + (l^x)^T (s_l^x)^* - (u^x)^T (s_u^x)^* + c^f \right\rbrace\\ = \sum_{i=0}^{m-1} \left[ (s_l^c)_i^* ( (x_i^c)^*-l_i^c) + (s_u^c)_i^* (u_i^c-(x_i^c)^*) \right] \\ + \sum_{j=0}^{n-1} \left[ (s_l^x)_j^* (x_j-l_j^x) +(s_u^x)_j^* (u_j^x-x_j^*) \right] + \sum_{j=0}^{n-1}(s_n^x)_j^*x_j^* \geq 0 \end{array}\end{split}\]

where the first relation can be obtained by transposing and multiplying the dual constraints (12.2) by \(x^*\) and \((x^c)^*\) respectively, and the second relation comes from the fact that each term in each sum is nonnegative. It follows that the primal objective will always be greater than or equal to the dual objective.

It is well-known that, under some non-degeneracy assumptions that exclude ill-posed cases, a conic optimization problem has an optimal solution if and only if there exist feasible primal-dual solution so that the duality gap is zero, or, equivalently, that the complementarity conditions

(12.11)\[\begin{split}\begin{array}{rcll} (s_l^c)_i^* ((x_i^c)^*-l_i^c ) & = & 0, & i=0,\ldots ,m-1, \\ (s_u^c)_i^* (u_i^c-(x_i^c)^*) & = & 0, & i=0,\ldots ,m-1, \\ (s_l^x)_j^* (x_j^*-l_j^x ) & = & 0, & j=0,\ldots ,n-1, \\ (s_u^x)_j^* (u_j^x-x_j^* ) & = & 0, & j=0,\ldots ,n-1, \\ \sum_{j=0}^{n-1}(s_n^x)_j^*x_j^* & =& 0. \end{array}\end{split}\]

are satisfied.

If (12.8) has an optimal solution and MOSEK solves the problem successfully, both the primal and dual solution are reported, including a status indicating the exact state of the solution.

12.2.2 Infeasibility for Conic Optimization

12.2.2.1 Primal Infeasible Problems

If the problem (12.8) is infeasible (has no feasible solution), MOSEK will report a certificate of primal infeasibility: The dual solution reported is the certificate of infeasibility, and the primal solution is undefined.

A certificate of primal infeasibility is a feasible solution to the modified dual problem

(12.12)\[\begin{split}\begin{array}{lc} \mbox{maximize} & (l^c)^T s_l^c - (u^c)^T s_u^c + (l^x)^T s_l^x - (u^x)^T s_u^x\\ \mbox{subject to} & \\ & A^T y + s_l^x - s_u^x + s_n^x = 0, \\ & -y + s_l^c - s_u^c = 0, \\ & s_l^c,s_u^c,s_l^x,s_u^x \geq 0, \\ & s_n^x\in \K^*, \end{array}\end{split}\]

such that the objective value is strictly positive, i.e. a solution

\[(y^*,(s_l^c)^*,(s_u^c)^*,(s_l^x)^*,(s_u^x)^*,(s_n^x)^*)\]

to (12.12) so that

\[(l^c)^T (s_l^c)^* - (u^c)^T (s_u^c)^* + (l^x)^T (s_l^x)^* - (u^x)^T (s_u^x)^* > 0.\]

Such a solution implies that (12.12) is unbounded, and that (12.8) is infeasible.

12.2.2.2 Dual Infeasible Problems

If the problem (12.9) is infeasible (has no feasible solution), MOSEK will report a certificate of dual infeasibility: The primal solution reported is the certificate of infeasibility, and the dual solution is undefined.

A certificate of dual infeasibility is a feasible solution to the modified primal problem

(12.13)\[\begin{split}\begin{array} {lccccl} \mbox{minimize} & & & c^T x & & \\ \mbox{subject to} & \hat l^c & \leq & A x & \leq & \hat u^c, \\ & \hat l^x & \leq & x & \leq & \hat u^x, \\ & & & x\in K,& & \end{array}\end{split}\]

where

(12.14)\[\begin{split}\hat l_i^c = \left\lbrace \begin{array} {ll} 0 & \mbox{if } l_i^c > -\infty , \\ -\infty & \mbox{otherwise}, \end{array} \right\rbrace \quad \mbox{and}\quad \hat u_i^c := \left\lbrace \begin{array}{ll} 0 & \mbox{if } u_i^c < \infty , \\ \infty & \mbox{otherwise}, \end{array} \right\rbrace\end{split}\]

and

(12.15)\[\begin{split}\hat l_j^x = \left\lbrace \begin{array} {ll} 0 & \mbox{if } l_j^x > -\infty , \\ -\infty & \mbox{otherwise}, \end{array} \right\rbrace \quad \mbox{and}\quad \hat u_j^x := \left\lbrace \begin{array}{ll} 0 & \mbox{if } u_j^x < \infty , \\ \infty & \mbox{otherwise}, \end{array} \right\rbrace\end{split}\]

such that

\[c^T x<0.\]

Such a solution implies that (12.13) is unbounded, and that (12.9) is infeasible.

In case that both the primal problem (12.8) and the dual problem (12.9) are infeasible, MOSEK will report only one of the two possible certificates — which one is not defined (MOSEK returns the first certificate found).

12.2.3 Minimalization vs. Maximalization

When the objective sense of problem (12.8) is maximization, i.e.

\[\begin{split}\begin{array} {lccccl} \mbox{maximize} & & & c^T x+c^f & & \\ \mbox{subject to} & l^c & \leq & A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x, \\ & & & x\in \K, & & \end{array}\end{split}\]

the objective sense of the dual problem changes to minimization, and the domain of all dual variables changes sign in comparison to (12.2). The dual problem thus takes the form

\[\begin{split}\begin{array}{lc} \mbox{minimize} & (l^c)^T s_l^c - (u^c)^T s_u^c + (l^x)^T s_l^x - (u^x)^T s_u^x + c^f\\ \mbox{subject to} & A^T y + s_l^x - s_u^x + s_n^x = c,\\ & -y + s_l^c - s_u^c = 0, \\ & s_l^c,s_u^c,s_l^x,s_u^x \leq 0,\\ & -s_n^x \in \K^* \end{array}\end{split}\]

This means that the duality gap, defined in (12.10) as the primal minus the dual objective value, becomes nonpositive. It follows that the dual objective will always be greater than or equal to the primal objective. The primal infeasibility certificate will be reported by MOSEK as a solution to the system

(12.16)\[\begin{split}\begin{array}{lc} & A^T y + s_l^x - s_u^x + s_n^x = 0, \\ & -y + s_l^c - s_u^c = 0, \\ & s_l^c,s_u^c,s_l^x,s_u^x \leq 0, \\ & -s_n^x\in\K^* \end{array}\end{split}\]

such that the objective value is strictly negative

\[(l^c)^T (s_l^c)^* - (u^c)^T (s_u^c)^* + (l^x)^T (s_l^x)^* - (u^x)^T (s_u^x)^* < 0.\]

Similarly, the certificate of dual infeasibility is an \(x\) satisfying the requirements of (12.13) such that \(c^Tx>0\).