9.4 Converting a quadratically constrained problem to conic form

MOSEK employs the following form of quadratic problems:

(9.8)\[\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_{k,j} 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}\]

A conic quadratic constraint has the form

\[x \in \Q^n\]

in its most basic form where

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

A quadratic problem such as (9.8), if convex, can be reformulated in conic form. This is in fact the reformulation MOSEK performs internally. It has many advantages:

• elegant duality theory for conic problems,

• reporting accurate dual information for quadratic inequalities is hard and/or computational expensive,

• it certifies that the original quadratic problem is indeed convex,

• modeling directly in conic form usually leads to a better model [And13] i.e. a faster solution time and better numerical properties.

In addition, there are more types of conic constraints that can be combined with a quadratic cone, for example semidefinite cones.

MOSEK offers a function that performs the conversion from quadratic to conic quadratic form explicitly. Note that the reformulation is not unique. The approach followed by MOSEK is to introduce additional variables, linear constraints and quadratic cones to obtain a larger but equivalent problem in which the original variables are preserved.

In particular:

• all variables and constraints are kept in the problem,

• each quadratic constraint and quadratic terms in the objective generate one rotated quadratic cone,

• each quadratic constraint will contain no coefficients and upper/lower bounds will be set to \(\infty,-\infty\) respectively.

This allows the user to recover the original variable and constraint values, as well as their dual values, with no conversion or additional effort.

Note

Task.toconic modifies the input task in-place: this means that if the reformulation is not possible, i.e. the problem is not conic representable, the state of the task is in general undefined. The user should consider cloning the original task.

9.4.1 Quadratic Constraint Reformulation

Let us assume we want to convert the following quadratic constraint

\[l \leq \half x^T Qx + \sum_{j=0}^{n-1} a_j x_j \leq u\]

to conic form. We first check whether \(l = -\infty\) or \(u = \infty\), otherwise either the constraint can be dropped, or the constraint is not convex. Thus let us consider the case

(9.9)\[\half x^T Q x + \sum_{j=0}^{n-1} a_j^T x_j \leq u.\]

Introducing an additional variable \(w\) such that

(9.10)\[ w = u - \sum_{j=0}^{n-1} a_j^T x_j\]

we obtain the equivalent form

\[\begin{split}\begin{array} {lrc} \half x^T Q x & \leq & w,\\ u - \sum_{j=0}^{n-1} a_j x_j & = & w. \end{array}\end{split}\]

If \(Q\) is positive semidefinite, then there exists a matrix \(F\) such that

(9.11)\[Q = FF^T\]

and therefore we can write

\[\begin{split}\begin{array} {lrc} \| F x \|^2 & \leq & 2 w,\\ u - \sum_{j=0}^{n-1} a_j^T x_j & = & w. \end{array}\end{split}\]

Introducing an additional variable \(z = 1\), and setting \(y = Fx\) we obtain the conic formulation

(9.12)\[\begin{split}\begin{array} {lrc} (w,z, y ) & \in \Qr,\\ z = 1 & \\ y = Fx &\\ w = u - a^Tx . \end{array}\end{split}\]

Summarizing, for each quadratic constraint involving \(t\) variables, MOSEK introduces

1. a rotated quadratic cone of dimension \(t+2\),

2. two additional variables for the cone roots,

3. \(t\) additional variables to map the remaining part of the cone,

4. \(t\) linear constraints.

A quadratic term in the objective is reformulated in a similar fashion. We refer to [And13] for a more thorough discussion.

Example

Next we consider a simple problem with quadratic objective function:

\[\begin{split}\begin{array}{ll} \minimize & \frac{1}{2} (13 x_0^2 + 17 x_1^2 + 12 x_2^2 + 24 x_0 x_1 + 12 x_1 x_2 - 4 x_0 x_2 ) - 22 x_0 - 14.5 x_1 + 12 x_2 + 1 \\ \st & -1 \leq x_0, x_1, x_2 \leq 1 \end{array}\end{split}\]

We can specify it in the human-readable OPF format.

[comment]
An example of small QO problem from Boyd and Vandenberghe, "Convex Optimization", page 189 ex 4.3
The solution is (1,0.5,-1)
[/comment]

[variables]
x0 x1 x2
[/variables]

[objective min]
0.5 (13 x0^2  + 17 x1^2 + 12 x2^2 + 24 x0 * x1 + 12 x1 * x2 - 4 x0 * x2 ) - 22 x0 - 14.5 x1 + 12 x2 + 1
[/objective]

[bounds]
[b] -1 <= * <= 1 [/b]
[/bounds]

The objective function is convex, the minimum is attained for \(x^\star = (1,0.5,-1)\). The conversion will introduce first a variable \(x_3\) in the objective function such that \(x_3\geq 1/2 x^TQx\) and then convert the latter directly in conic form. The converted problem follows:

\[\begin{split}\begin{array}{lr} \minimize & - 22 x_0 - 14.5 x_1 + 12 x_2 + x_3 + 1 \\ \st & 3.61 x_0 + 3.33 x_1 - 0.55 x_2 - x_6 = 0 \\ & + 2.29 x_1 + 3.42 x_2 - x_7 = 0 \\ & 0.81 x_1 - x_8 = 0\\ & - x_3 + x_4 = 0\\ & x_5 = 1\\ & (x_4, x_5, x_6, x_7, x_8 ) \in \mathcal{Q_r} \\ & -1 \leq x_0,x_1,x_2 \leq 1\\ \end{array}\end{split}\]

The model generated by Task.toconic is

[comment]
   Written by MOSEK version 8.1.0.19
   Date 21-08-17
   Time 10:53:36
[/comment]

[hints]
  [hint NUMVAR] 9 [/hint]
  [hint NUMCON] 4 [/hint]
  [hint NUMANZ] 11 [/hint]
  [hint NUMQNZ] 0 [/hint]
  [hint NUMCONE] 1 [/hint]
[/hints]

[variables disallow_new_variables]
  x0000_x0 x0001_x1 x0002_x2 x0003 x0004
  x0005 x0006 x0007 x0008
[/variables]

[objective minimize]
   - 2.2e+01 x0000_x0 - 1.45e+01 x0001_x1 + 1.2e+01 x0002_x2 + x0003
   + 1e+00
[/objective]

[constraints]
  [con c0000]  3.605551275463989e+00 x0000_x0 - 5.547001962252291e-01 x0002_x2 + 3.328201177351375e+00 x0001_x1 - x0006 = 0e+00 [/con]
  [con c0001]  3.419401657060442e+00 x0002_x2 + 2.294598480395823e+00 x0001_x1 - x0007 = 0e+00 [/con]
  [con c0002]  8.111071056538127e-01 x0001_x1 - x0008 = 0e+00 [/con]
  [con c0003]  - x0003 + x0004 = 0e+00 [/con]
[/constraints]

[bounds]
  [b] -1e+00     <= x0000_x0,x0001_x1,x0002_x2 <= 1e+00 [/b]
  [b]               x0003,x0004 free [/b]
  [b]               x0005 =  1e+00 [/b]
  [b]               x0006,x0007,x0008 free [/b]
  [cone rquad k0000] x0004, x0005, x0006, x0007, x0008 [/cone]
[/bounds]

We can clearly see that constraints c0000, c0001 and c0002 represent the original linear constraints as in (9.11), while c0003 corresponds to (9.10). The cone roots are x0005 and x0004.