9.2 Conic Quadratic Optimization

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

(1)\[\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 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.

MOSEK supports only a limited number of cones, specifically:

  • The \(\real^n\) set.
  • The quadratic cone:
\[\Q^n = \left\lbrace x \in \real^n: x_1 \geq \sqrt{\sum_{j=2}^n x_j^2} \right\rbrace.\]
  • The 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.\]

Although these cones may seem to provide only limited expressive power they can be used to model a wide range of problems as demonstrated in [MOSEKApS12].

9.2.1 Duality for Conic Quadratic Optimization

The dual problem corresponding to the conic quadratic optimization problem (1) is given by

(2)\[\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

\[\K^*= \K^*_1 \times \cdots \times \K^*_p,\]

where each \(\K^*_t\) is the dual cone of \(\K_t\). For the cone types MOSEK can handle, the relation between the primal and dual cone is given as follows:

  • The \(\real^n\) set:
\[\K_t = \real^{n_t} \quad \Leftrightarrow \quad \K^*_t = \left\lbrace s \in \real^{n_t}: \quad s=0 \right\rbrace.\]
  • The quadratic cone:
\[\K_t = \Q^{n_t} \quad\Leftrightarrow\quad \K^*_t = \Q^{n_t} = \left\lbrace s \in \real^{n_t}: s_1 \geq \sqrt{\sum_{j=2}^{n_t} s_j^2} \right\rbrace.\]
  • The rotated quadratic cone:
\[\K_t = \Qr^{n_t} \quad\Leftrightarrow\quad \K^*_t = \Qr^{n_t} = \left\lbrace s \in \real^{n_t}: 2 s_1 s_2 \geq \sum_{j=3}^{n_t} s_j^2,\quad s_1 \geq 0,\quad s_2 \geq 0 \right\rbrace.\]

Please note that the dual problem of the dual problem is identical to the original primal problem.

9.2.2 Infeasibility for Conic Quadratic Optimization

In case MOSEK finds a problem to be infeasible it reports a certificate of infeasibility. This works exactly as for linear problems (see Sec. 9.1.2 (Infeasibility for Linear Optimization)).

9.2.2.1 Primal Infeasible Problems

If the problem (1) is infeasible, 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 problem

\[\begin{split}\begin{array} {lccccc} \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.

9.2.2.2 Dual infeasible problems

If the problem (2) is infeasible, 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 problem

\[\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

\[\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

\[\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 the objective value is strictly negative.