6.2 From Linear to Conic Optimization¶
In Sec. 6.1 (Linear Optimization) we demonstrated setting up the linear part of an optimization problem, namely the objective, linear bounds and linear (in)equalities. In this tutorial we show how to define conic constraints.
A single conic constraint in MOSEK is constructed in the following form
where
\(x\in\real^n\) is the optimization variable vector of length \(n\),
\(F_i\in\real^{d\times n}\) is a \(d \times n\) matrix of coefficients (problem data), where \(d\) is the number of affine expressions (AFEs) in the conic constraint,
\(g_i\in \real^d\) is a vector of constants (problem data). Thus, the affine combination \(F_i x + g_i\) results in a \(d\)-vector where each element is a scalar-valued AFE,
\(\D_i\subseteq \real^d\) is a conic domain of dimension \(d\), representing one of the cone types supported by MOSEK.
Constraints of this form are called affine conic constraints, or ACC for short. Therefore, in this section we show how to set up a problem of the form
where \(F\in\real^{k\times n}\), \(g\in\real^k\), \(k = \sum_{i=1}^{l} d_i\) and \(d_i=\text{dim}(\D_i)\). The problem in (6.3) consists of \(l\) affine conic constraints. The first ACC is made by restricting the first \(d_1\) affine expressions (out of the total \(k\)) to the \(\D_1\) domain. The \(d_2\) AFEs thereafter belong to the \(\D_2\) domain, forming the second ACC, and so on. The complete ACC data of a problem is therefore obtained by stacking together the descriptions of \(l\) ACCs.
Generalization of linear constraints
Conic constraints are a natural generalization of linear constraints to the general nonlinear case. For example, a typical linear constraint of the form
can also be written as membership in the cone of nonnegative real numbers (also called the positive orthant cone):
and that naturally generalizes to
for more complicated domains \(\D\) from Sec. 15.8 (Supported domains).
6.2.1 Example AFFCO1¶
Consider the following simple optimization problem:
Adding auxiliary variables we convert this problem into an equivalent conic form:
Note that each of the vectors constrained to a cone is in a natural way an affine combination of the problem variables.
We first set up the linear part of the problem, including the number of variables, objective and all bounds precisely as in Sec. 6.1 (Linear Optimization). Affine conic constraints will be defined using the accs structure. We construct the matrices \(F,g\) for each of the three ACCs. For example, the constraint \((1,x_1-0.5,x_2-0.6)\in \Q^3\) is written in matrix form as
Below we set up the matrices and define the conic domain type as a quadratic cone of length \(3\):
% The quadratic cone
FQ = sparse([zeros(1,4); speye(2) zeros(2,2)]);
gQ = [1 -0.5 -0.6]';
cQ = [res.symbcon.MSK_DOMAIN_QUADRATIC_CONE 3];
Next we demonstrate how to do the same for the second of the power cone constraints. Its affine representation is:
The power cone is defined by its type, length, number of additional parameters (here equal to 2) and the exponents \(\alpha_i\) appearing in the power cone definition:
% The power cone for (x_1+x_2+0.1, 1, t_2) \in POW3^(1/4,3/4)
FP2 = sparse([1 1 zeros(1,2); zeros(1,4); zeros(1,2) 0 1]);
gP2 = [0.1 1 0]';
cP2 = [res.symbcon.MSK_DOMAIN_PRIMAL_POWER_CONE 3 2 1.0 3.0];
Once affine conic descriptions of all constraints are ready it remains to stack them vertically into the matrix \(F\) and vector \(g\) and concatenate the ACC descriptions in one list. Below is the full code for problem (6.5).
function affco1()
[rcode, res] = mosekopt('symbcon echo(0)');
prob = [];
% Variables [x1; x2; t1; t2]
prob.c = [0, 0, 1, 1];
% Linear inequality x_1 - x_2 <= 1
prob.a = sparse([1, -1, 0, 0]);
prob.buc = 1;
prob.blc = [];
% The quadratic cone
FQ = sparse([zeros(1,4); speye(2) zeros(2,2)]);
gQ = [1 -0.5 -0.6]';
cQ = [res.symbcon.MSK_DOMAIN_QUADRATIC_CONE 3];
% The power cone for (x_1, 1, t_1) \in POW3^(1/3,2/3)
FP1 = sparse([1 0 zeros(1,2); zeros(1,4); zeros(1,2) 1 0]);
gP1 = [0 1 0]';
cP1 = [res.symbcon.MSK_DOMAIN_PRIMAL_POWER_CONE 3 2 1/3 2/3];
% The power cone for (x_1+x_2+0.1, 1, t_2) \in POW3^(1/4,3/4)
FP2 = sparse([1 1 zeros(1,2); zeros(1,4); zeros(1,2) 0 1]);
gP2 = [0.1 1 0]';
cP2 = [res.symbcon.MSK_DOMAIN_PRIMAL_POWER_CONE 3 2 1.0 3.0];
% All cones
prob.f = [FQ; FP1; FP2];
prob.g = [gQ; gP1; gP2];
prob.accs = [cQ cP1 cP2];
[r, res] = mosekopt('maximize', prob);
res.sol.itr.pobjval
res.sol.itr.xx(1:2)
6.2.2 Example AFFCO2¶
Consider the following simple linear dynamical system. A point in \(\real^n\) moves along a trajectory given by \(z(t) = z(0)\exp(At)\), where \(z(0)\) is the starting position and \(A=\Diag(a_1,\ldots,a_n)\) is a diagonal matrix with \(a_i<0\). Find the time after which \(z(t)\) is within euclidean distance \(d\) from the origin. Denoting the coordinates of the starting point by \(z(0)=(z_1,\ldots,z_n)\) we can write this as an optimization problem in one variable \(t\):
which can be cast into conic form as:
with variable vector \(x=[t,y_1,\ldots,y_n]^T\).
We assemble all conic constraints in the form
For the conic quadratic constraint this representation is
For the \(i\)-th exponential cone we have
where \(e_i\) denotes a vector of length \(n\) with a single \(1\) in position \(i\).
function t = firstHittingTime(n, z, a, d)
[rcode, res] = mosekopt('symbcon echo(0)');
prob = [];
% Variables [t, y1, ..., yn]
prob.a = sparse(0, n+1);
prob.c = [1 zeros(1,n)];
% Quadratic cone
FQ = diag([0; z]);
gQ = [d; zeros(n,1)];
% All exponential cones
FE = sparse([1:3:3*n 3:3:3*n], ...
[2:n+1 ones(1,n)], ...
[ones(1,n) a']);
gE = repmat([0; 1; 0], n, 1);
% Assemble input data
prob.f = [FQ; FE];
prob.g = [gQ; gE];
prob.accs = [res.symbcon.MSK_DOMAIN_QUADRATIC_CONE n+1 repmat([res.symbcon.MSK_DOMAIN_PRIMAL_EXP_CONE 3], 1, n)];
% Solve
[r, res] = mosekopt('minimize', prob);
t = res.sol.itr.xx(1)
