11.4 Quadratic and Quadratically Constrained Optimization

A convex quadratic and quadratically constrained optimization problem has the form

(11.22)\[\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 all variables and bounds have the same meaning as for linear problems (see Sec. 11.1 (Linear Optimization)) and \(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.

11.4.1 A Recommendation

Any convex quadratic optimization problem can be reformulated as a conic quadratic optimization problem, see Modeling Cookbook and [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 modeler can do a better reformulation than the automatic method because the modeler 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.

11.4.2 Duality for Quadratic and Quadratically Constrained Optimization

The dual problem corresponding to the quadratic and quadratically constrained optimization problem (11.22) is given by

(11.24)\[\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 Sec. 11.1.1 (Duality for Linear Optimization)), 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 (11.22) and the dual problem (11.24).

11.4.3 Infeasibility for Quadratic Optimization

In case MOSEK finds a problem to be infeasible it reports a certificate of infeasibility. We write them out explicitly for quadratic problems, that is when \(Q^k=0\) for all \(k\) and quadratic terms appear only in the objective \(Q^o\). In this case the constraints both in the primal and dual problem are linear, and MOSEK produces for them the same infeasibility certificate as for linear problems.

The certificate of primal infeasibility is a solution to the problem (11.5) such that the objective value is strictly positive.

The certificate of dual infeasibility is a solution to the problem (11.6) together with an additional constraint

\[Q^o x = 0\]

such that the objective value is strictly negative.