7.2 Conic Quadratic Optimization¶
Conic optimization is a generalization of linear optimization, allowing constraints of the type
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
where the domain restriction, \(x \in \K\), implies that all variables are partitioned into convex cones
In this tutorial we describe how to use the two types of quadratic cones defined as:
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 other types of cones supported by MOSEK see Sec. 7.3 (Power Cone Optimization), Sec. 7.4 (Conic Exponential Optimization), Sec. 7.5 (Semidefinite Optimization). See Domain
for a list and definitions of available cone types. Different cone types can appear together in one optimization problem.
For example, the following constraint:
describes a convex cone in \(\real^3\) given by the inequality:
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.
We start by creating the optimization model:
with Model('cqo1') as M:
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.
x = M.variable('x', 3, Domain.greaterThan(0.0))
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] ]
z1 = Var.vstack(y.index(0), x.slice(0, 2))
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
M.constraint("lc", Expr.dot([1.0, 1.0, 2.0], 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
qc1 = M.constraint("qc1", z1, Domain.inQCone())
qc2 = M.constraint("qc2", z2, 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()
M.writeTask('cqo1.opf')
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
solx = x.level()
soly = y.level()
# Get conic solution of qc1
qc1lvl = qc1.level()
qc1sn = qc1.dual()
from mosek.fusion import *
with Model('cqo1') as M:
x = M.variable('x', 3, Domain.greaterThan(0.0))
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] ]
z1 = Var.vstack(y.index(0), x.slice(0, 2))
z2 = Var.vstack(y.slice(1, 3), x.index(2))
# Create the constraint
# x[0] + x[1] + 2.0 x[2] = 1.0
M.constraint("lc", Expr.dot([1.0, 1.0, 2.0], 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
qc1 = M.constraint("qc1", z1, Domain.inQCone())
qc2 = M.constraint("qc2", z2, 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()
M.writeTask('cqo1.opf')
# Get the linear solution values
solx = x.level()
soly = y.level()
print('x1,x2,x3 = %s' % str(solx))
print('y1,y2,y3 = %s' % str(soly))
# Get conic solution of qc1
qc1lvl = qc1.level()
qc1sn = qc1.dual()
print('qc1 levels = %s' % str(qc1lvl))
print('qc1 dual conic var levels = %s' % str(qc1sn))