7.2 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}.\]

In Fusion the coordinates of a cone are not restricted to single variables. They can be arbitrary linear expressions, and an auxiliary variable will be substituted by Fusion in a way transparent to the user.

7.2.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}{ll} \minimize & y_1 + y_2 + y_3 \\ \st & x_1 + x_2 + 2.0 x_3 = 1.0,\\ & x_1,x_2,x_3 \geq 0.0,\\ & (y_1,x_1,x_2) \in \Q^3,\\ & (y_2,y_3,x_3) \in \Qr^3. \end{array}\end{split}\]

We start by creating the optimization model:

      using (Model M = new Model("cqo1"))
      {

We then define variables x and y. Two logical variables (aliases) z1 and z2 are introduced to model the quadratic cones. These are not new variables, but map onto parts of x and y for the sake of convenience.

        Variable x = M.Variable("x", 3, Domain.GreaterThan(0.0));
        Variable y = M.Variable("y", 3, Domain.Unbounded());

        // Create the aliases
        //      z1 = [ y[0],x[0],x[1] ]
        //  and z2 = [ y[1],y[2],x[2] ]
        Variable z1 = Var.Vstack(y.Index(0),  x.Slice(0, 2));
        Variable z2 = Var.Vstack(y.Slice(1, 3), x.Index(2));

The linear constraint is defined using the dot product:

        // Create the constraint
        //      x[0] + x[1] + 2.0 x[2] = 1.0
        double[] aval = new double[] {1.0, 1.0, 2.0};
        M.Constraint("lc", Expr.Dot(aval, x), Domain.EqualsTo(1.0));

The conic constraints are defined using the logical views z1 and z2 created previously. Note that this is a basic way of defining conic constraints, and that in practice they would have more complicated structure.

        // Create the constraints
        //      z1 belongs to C_3
        //      z2 belongs to K_3
        // where C_3 and K_3 are respectively the quadratic and
        // rotated quadratic cone of size 3, i.e.
        //                 z1[0] >= sqrt(z1[1]^2 + z1[2]^2)
        //  and  2.0 z2[0] z2[1] >= z2[2]^2
        Constraint qc1 = M.Constraint("qc1", z1.AsExpr(), Domain.InQCone());
        Constraint qc2 = M.Constraint("qc2", z2.AsExpr(), Domain.InRotatedQCone());

We only need the objective function:

        // Set the objective function to (y[0] + y[1] + y[2])
        M.Objective("obj", ObjectiveSense.Minimize, Expr.Sum(y));

Calling the Model.Solve method invokes the solver:

        M.Solve();

The primal and dual solution values can be retrieved using Variable.Level, Constraint.Level and Variable.Dual, Constraint.Dual, respectively:

        // Get the linear solution values
        double[] solx = x.Level();
        double[] soly = y.Level();
        // Get conic solution of qc1
        double[] qc1lvl = qc1.Level();
        double[] qc1sn  = qc1.Dual();
Listing 4 Fusion implementation of model (1). Click here to download.
using System;
using mosek.fusion;

namespace mosek.fusion.example
{
  public class cqo1
  {
    public static void Main(string[] args)
    {
      using (Model M = new Model("cqo1"))
      {

        Variable x = M.Variable("x", 3, Domain.GreaterThan(0.0));
        Variable y = M.Variable("y", 3, Domain.Unbounded());

        // Create the aliases
        //      z1 = [ y[0],x[0],x[1] ]
        //  and z2 = [ y[1],y[2],x[2] ]
        Variable z1 = Var.Vstack(y.Index(0),  x.Slice(0, 2));
        Variable z2 = Var.Vstack(y.Slice(1, 3), x.Index(2));

        // Create the constraint
        //      x[0] + x[1] + 2.0 x[2] = 1.0
        double[] aval = new double[] {1.0, 1.0, 2.0};
        M.Constraint("lc", Expr.Dot(aval, x), Domain.EqualsTo(1.0));

        // Create the constraints
        //      z1 belongs to C_3
        //      z2 belongs to K_3
        // where C_3 and K_3 are respectively the quadratic and
        // rotated quadratic cone of size 3, i.e.
        //                 z1[0] >= sqrt(z1[1]^2 + z1[2]^2)
        //  and  2.0 z2[0] z2[1] >= z2[2]^2
        Constraint qc1 = M.Constraint("qc1", z1.AsExpr(), Domain.InQCone());
        Constraint qc2 = M.Constraint("qc2", z2.AsExpr(), Domain.InRotatedQCone());

        // Set the objective function to (y[0] + y[1] + y[2])
        M.Objective("obj", ObjectiveSense.Minimize, Expr.Sum(y));

        // Solve the problem
        M.Solve();

        // Get the linear solution values
        double[] solx = x.Level();
        double[] soly = y.Level();
        Console.WriteLine("x1,x2,x3 = {0}, {1}, {2}", solx[0], solx[1], solx[2]);
        Console.WriteLine("y1,y2,y3 = {0}, {1}, {2}", soly[0], soly[1], soly[2]);

        // Get conic solution of qc1
        double[] qc1lvl = qc1.Level();
        double[] qc1sn  = qc1.Dual();
        
        Console.Write("qc1 levels = {0}", qc1lvl[0]);
        for (int i = 1; i < qc1lvl.Length; ++i)
          Console.Write(", {0}", qc1lvl[i]);
        Console.WriteLine();

        Console.Write("qc1 dual conic var levels = {0}", qc1sn[0]);
        for (int i = 1; i < qc1sn.Length; ++i)
          Console.Write(", {0}", qc1sn[i]);
        Console.WriteLine();
      }
    }
  }
}