12.4 Quadratic and Quadratically Constrained Optimization

A convex quadratic and quadratically constrained optimization problem has the form

(1)\[\begin{split}\begin{array}{lrcccll} \mbox{minimize} & & & \half x^T Q^o x + c^T x + c^f & & &\\ \mbox{subject to} & l_k^c & \leq & \half x^T Q^k x + \sum_{j=0}^{n-1} a_{kj} x_j & \leq & u_k^c, & k =0,\ldots ,m-1, \\ & l_j^x & \leq & x_j & \leq & u_j^x, & j=0,\ldots, n-1, \end{array}\end{split}\]

where \(Q^o\) and all \(Q^k\) are symmetric matrices. Moreover, for convexity, \(Q^o\) must be a positive semidefinite matrix and \(Q^k\) must satisfy

\[\begin{split}\begin{array}{rcl} -\infty <l_k^c & \Rightarrow & Q^k \mbox{ is negative semidefinite},\\ u_k^c < \infty & \Rightarrow & Q^k \mbox{ is positive semidefinite}, \\ -\infty < l_k^c \leq u_k^c < \infty & \Rightarrow & Q^k = 0. \end{array}\end{split}\]

The convexity requirement is very important and MOSEK checks whether it is fulfilled.

12.4.1 A Recommendation

Any convex quadratic optimization problem can be reformulated as a conic quadratic optimization problem, see [MOSEKApS12] and in particular [And13]. In fact MOSEK does such conversion internally as a part of the solution process for the following reasons:

  • the conic optimizer is numerically more robust than the one for quadratic problems.
  • the conic optimizer is usually faster because quadratic cones are simpler than quadratic functions, even though the conic reformulation usually has more constraints and variables than the original quadratic formulation.
  • it is easy to dualize the conic formulation if deemed worthwhile potentially leading to (huge) computational savings.

However, instead of relying on the automatic reformulation we recommend to formulate the problem as a conic problem from scratch because:

  • it saves the computational overhead of the reformulation including the convexity check. A conic problem is convex by construction and hence no convexity check is needed for conic problems.
  • usually the modeller can do a better reformulation than the automatic method because the modeller can exploit the knowledge of the problem at hand.

To summarize we recommend to formulate quadratic problems and in particular quadratically constrained problems directly in conic form.

12.4.2 Duality for Quadratic and Quadratically Constrained Optimization

The dual problem corresponding to the quadratic and quadratically constrained 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 + \half x^T \left\lbrace \sum_{k=0}^{m-1} y_k Q^k - Q^o \right\rbrace x + c^f\\ \mbox{subject to} & A^T y + s_l^x - s_u^x + \left\lbrace \sum_{k=0}^{m-1} y_k Q^k - Q^o \right\rbrace x = c, \\ & -y + s_l^c - s_u^c = 0, \\ & s_l^c,s_u^c,s_l^x,s_u^x \geq 0. \end{array}\end{split}\]

The dual problem is related to the dual problem for linear optimization (see Section 12.1.1), but depends on the variable \(x\) which in general can not be eliminated. In the solutions reported by MOSEK, the value of \(x\) is the same for the primal problem (1) and the dual problem (2).

12.4.3 Infeasibility for Quadratic and Quadratically Constrained Optimization

In case MOSEK finds a problem to be infeasible it reports a certificate of infeasibility. This works exactly as for linear problems (see Section 12.1.2).

12.4.3.1 Primal Infeasible Problems

If the problem (1) with all \(Q^k = 0\) is infeasible, MOSEK will report a certificate of primal infeasibility. As the constraints are the same as for a linear problem, the certificate of infeasibility is the same as for linear optimization (see Section 12.1.2.1).

12.4.3.2 Dual Infeasible Problems

If the problem (2) with all \(Q^k = 0\) is dual 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}{lrcccll} \mbox{minimize} & & & c^T x & & & \\ \mbox{subject to} & \hat{l}^c & \leq & A x & \leq & \hat{u}^c, & \\ & 0 & \leq & Q^o x & \leq & 0, &\\ & \hat{l}^x & \leq & x & \leq & \hat{u}^x, & \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.