6.7 Affine conic constraints (new)

Optimization Toolbox for MATLAB can solve conic optimization problems in another format:

\[\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, \\ & & & Fx+g \in \K, & & \end{array}\end{split}\]

where \(F\in\real^{k\times n}\) and \(g\in\real^k\) specify an affine conic constraint of length (dimension) \(k\). Usually \(\K\) will be a product of basic cones corresponding to individual constraints.

In this tutorial we demonstrate how to use the affine conic format. It supports all types of basic cones available in MOSEK and can be combined with semidefinite variables as in Sec. 6.6 (Semidefinite Optimization).

6.7.1 Example AFFCO1

Consider the following simple optimization problem:

(6.13)\[\begin{split}\begin{array} {lrcl} \mbox{maximize} & x_1^{1/3} + (x_1+x_2+0.1)^{1/4} & & \\ \mbox{subject to} & (x_1-0.5)^2+(x_2-0.6)^2 & \leq & 1, \\ & x_1 - x_2 & \leq & 1. \end{array}\end{split}\]

Adding auxiliary variables we convert this problem into an equivalent conic form:

(6.14)\[\begin{split}\begin{array} {lrcl} \mbox{maximize} & t_1+t_2 & & \\ \mbox{subject to} & (1,x_1-0.5,x_2-0.6) & \in & \Q^3, \\ & (x_1,1,t_1) & \in & \POW_3^{1/3,2/3}, \\ & (x_1+x_2+0.1,1,t_2) & \in & \POW_3^{1/4,3/4}, \\ & x_1-x_2 & \leq & 1. \end{array}\end{split}\]

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). Cones will be defined using the cones structure. We construct the matrices \(F,g\) for each of the three cones. For example, the constraint \((1,x_1-0.5,x_2-0.6)\in \Q^3\) is written in matrix form as

\[\begin{split}\left[\begin{array}{cccc}0&0&0&0\\1&0&0&0\\0&1&0&0\end{array}\right] \left[\begin{array}{c}x_1\\x_2\\t_1\\t_2\end{array}\right] + \left[\begin{array}{c}1\\-0.5\\-0.6\end{array}\right] \in \Q^3.\end{split}\]

Below we set up the matrices and define the cone 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_CT_QUAD 3];

Next we demonstrate how to do the same for the second of the power cone constraints. Its affine representation is:

\[\begin{split}\left[\begin{array}{cccc}1&1&0&0\\0&0&0&0\\0&0&0&1\end{array}\right] \left[\begin{array}{c}x_1\\x_2\\t_1\\t_2\end{array}\right] + \left[\begin{array}{c}0.1\\1\\0\end{array}\right] \in \POW^{1/4,3/4}_3.\end{split}\]

The power cone is defined by its type, length, number of additional parameters (always equal to 2) and the exponents \(\alpha,1-\alpha\) appearing in the cone definition. In fact any pair of positive real numbers proportional to \((\alpha,1-\alpha)\) may be used. They will be normalized to add up to 1:

% 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_CT_PPOW 3 2 1.0 3.0];

Once affine conic descriptions of all cones are ready it remains to stack them vertically into the matrix \(F\) and vector \(g\) and concatenate the cone descriptions in one list. Below is the full code for problem (6.14).

Listing 6.12 Script implementing conic version of problem (6.13). Click here to download.
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_CT_QUAD 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_CT_PPOW 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_CT_PPOW 3 2 1.0 3.0];

% All cones
prob.f = [FQ; FP1; FP2];
prob.g = [gQ; gP1; gP2];
prob.cones = [cQ cP1 cP2];

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

res.sol.itr.pobjval
res.sol.itr.xx(1:2)

6.7.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\):

\[\begin{split}\begin{array}{lrcl} \minimize & t & & \\ \st & \sqrt{\sum_i \left(z_i\exp(a_it)\right)^2} & \leq & d, \end{array}\end{split}\]

which can be cast into conic form as:

(6.15)\[\begin{split}\begin{array}{lrcl} \minimize & t & & \\ \st & (d,z_1y_1,\ldots,z_ny_n) & \in & \Q^{n+1},\\ & (y_i, 1, a_it) & \in & \EXP, \ i=1,\ldots,n, \end{array}\end{split}\]

with variable vector \(x=[t,y_1,\ldots,y_n]^T\).

We assemble all conic constraints in the form

\[Fx+g\in \Q^{n+1}\times(\EXP)^n.\]

For the conic quadratic constraint this representation is

\[\begin{split}\left[\begin{array}{cc}0&0_n^T\\0_n& \Diag(z_1,\ldots,z_n)\end{array}\right] \left[\begin{array}{c}t\\y\end{array}\right] + \left[\begin{array}{c}d\\0_n\end{array}\right] \in \Q^{n+1}.\end{split}\]

For the \(i\)-th exponential cone we have

\[\begin{split}\left[\begin{array}{cc}0&e_i^T\\0&0_n\\a_i&0_n\end{array}\right] \left[\begin{array}{c}t\\y\end{array}\right] + \left[\begin{array}{c}0\\1\\0\end{array}\right] \in \EXP,\end{split}\]

where \(e_i\) denotes a vector of length \(n\) with a single \(1\) in position \(i\).

Listing 6.13 Script implementing problem (6.15). Click here to download.
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.cones = [res.symbcon.MSK_CT_QUAD n+1 repmat([res.symbcon.MSK_CT_PEXP 3], 1, n)];

% Solve
[r, res] = mosekopt('minimize', prob);
t = res.sol.itr.xx(1)