6.3 Conic Quadratic Optimization

Conic optimization is a generalization of linear optimization, allowing constraints of the type

\[x^t \in \K_t,\]

where \(x^t\) is a subset of the problem variables and \(\K_t\) is a convex cone. Since the set \(\real^n\) of real numbers is also a convex cone, we can simply write a compound conic constraint \(x\in \K\) where \(\K=\K_1\times\cdots\times\K_l\) is a product of smaller cones and \(x\) is the full problem variable.

MOSEK can solve conic quadratic optimization problems of the form

\[\begin{split}\begin{array}{lccccl} \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 the domain restriction, \(x \in \K\), implies that all variables are partitioned into convex cones

\[x = (x^0, x^1, \ldots , x^{p-1}),\quad \mbox{with } x^t \in \K_t \subseteq \real^{n_t}.\]

For convenience, a user defining a conic quadratic problem only needs to specify subsets of variables \(x^t\) belonging to quadratic cones. These are:

  • Quadratic cone:

    \[\Q^n = \left\lbrace x \in \real^n: x_0 \geq \sqrt{\sum_{j=1}^{n-1} x_j^2} \right\rbrace.\]
  • Rotated quadratic cone:

    \[\Qr^n = \left\lbrace x \in \real^n: 2 x_0 x_1 \geq \sum_{j=2}^{n-1} x_j^2,\quad x_0\geq 0,\quad x_1 \geq 0 \right\rbrace.\]

For example, the following constraint:

\[(x_4, x_0, x_2) \in \Q^3\]

describes a convex cone in \(\real^3\) given by the inequality:

\[x_4 \geq \sqrt{x_0^2 + x_2^2}.\]

Furthermore, each variable may belong to one cone at most. The constraint \(x_i - x_j = 0\) would however allow \(x_i\) and \(x_j\) to belong to different cones with same effect.

6.3.1 Example CQO1

Consider the following conic quadratic problem which involves some linear constraints, a quadratic cone and a rotated quadratic cone.

(1)\[\begin{split}\begin{array} {lccc} \mbox{minimize} & x_4 + x_5 + x_6 & & \\ \mbox{subject to} & x_1+x_2+ 2 x_3 & = & 1, \\ & x_1,x_2,x_3 & \geq & 0, \\ & x_4 \geq \sqrt{x_1^2 + x_2^2}, & & \\ & 2 x_5 x_6 \geq x_3^2 & & \end{array}\end{split}\]

The linear constraints are specified as if the problem was a linear problem whereas the cones are specified using two index lists cones.subptr and cones.sub and list of cone-type identifiers cones.type. The elements of all the cones are listed in cones.sub, and cones.subptr specifies the index of the first element in cones.sub for each cone.

Listing 6.4 demonstrates how to solve the example (1) using MOSEK.

Listing 6.4 Script implementing problem (1). Click here to download.
function cqo1()

clear prob;

[r, res] = mosekopt('symbcon');
% Specify the non-conic part of the problem.

prob.c   = [0 0 0 1 1 1];
prob.a   = sparse([1 1 2 0 0 0]);
prob.blc = 1;
prob.buc = 1;
prob.blx = [0 0 0 -inf -inf -inf];
prob.bux = inf*ones(6,1);

% Specify the cones.

prob.cones.type   = [res.symbcon.MSK_CT_QUAD, res.symbcon.MSK_CT_RQUAD];
prob.cones.sub    = [4, 1, 2, 5, 6, 3];
prob.cones.subptr = [1, 4];
% The field 'type' specifies the cone types, i.e., quadratic cone
% or rotated quadratic cone. The keys for the two cone types are MSK_CT_QUAD
% and MSK_CT_RQUAD, respectively.
%
% The fields 'sub' and 'subptr' specify the members of the cones,
% i.e., the above definitions imply that 
%   x(4) >= sqrt(x(1)^2+x(2)^2) and 2 * x(5) * x(6) >= x(3)^2.

% Optimize the problem. 

[r,res]=mosekopt('minimize',prob);

% Display the primal solution.

res.sol.itr.xx'

Note in particular that:

  • No variable can be member of more than one cone. This is not serious restriction — see the following section.
  • The \(\real\) set is not specified explicitly.