9.4 Converting a quadratically constrained problem to conic form¶
MOSEK employs the following form of quadratic problems:
A conic quadratic constraint has the form
in its most basic form where
A quadratic problem such as (1), 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,
- modelling 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.
- 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.
MSK_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
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
Introducing an additional variable \(w\) such that
we obtain the equivalent form
If \(Q\) is positive semidefinite, then there exists a matrix \(F\) such that
and therefore we can write
Introducing an additional variable \(z = 1\), and setting \(y = Fx\) we obtain the conic formulation
Summarizing, for each quadratic constraint involving \(t\) variables, MOSEK introduces
- a rotated quadratic cone of dimension \(t+2\),
- two additional variables for the cone roots,
- \(t\) additional variables to map the remaining part of the cone,
- \(t\) linear constraints.
A quadratic term in the objective is reformulated in a similar fashion. We refer to [And13] for a more thorough discussion.
Next we consider a simple problem with quadratic objective function:
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:
The model generated by
[comment] Written by MOSEK version 220.127.116.11 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]