Conic Optimization

This page is under construction

Definition

#TODO

Convex sum-of-squares

#TODO

Problem formulation

#TODO

Relaxation to SDP

#TODO

Conic problems

#TODO

High level formulation

Add sdpsol definition here. Remark: example at the end

Low-level formulation

#TODO

Examples in CaΣoS

#TODO

Semidefinite Program

Consider Example 6.7.1 from the Mosek documentation.

The problem involves semidefinite and conic constraints with a linear cost function, that is:

$$ \begin{aligned} &\text{minimize} \quad && \left\langle \begin{pmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{pmatrix}, \bar{X} \right\rangle + x_0 \\ &\text{subject to} \quad && \left\langle \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \bar{X} \right\rangle + x_0 &= 1, \\ &&& \left\langle \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}, \bar{X} \right\rangle + x_1 + x_2 &= \frac{1}{2}, \\ &&& x_0 \geq \sqrt{x_1^2 + x_2^2}, \\ &&& \bar{X} \succeq 0. \end{aligned} $$

In CaΣoS, the implementation of this problem is rather straightforward.

Decision Variables

We start off by defining the symbolic decision variables as casadi.SX objects with

x_bar = casadi.SX.sym('x_bar', 3, 3);
x = casadi.SX.sym('x', 3, 1);

Note that $\bar{X}$ is a $3\times3$-matrix. Both are decision variables, meaning we define the sdp-struct with

sdp.x = [x; x_bar(:)];

Note

All problem decision variables need to be defined as one vector.

With the syntax

opts.Kx = struct('lin', [3], 'psd', [3]);

we define that there are linear bounds on $x_0, x_1, x_2$ and that $\bar{X} \in \mathbb{R}^{3\times3}$ is a positive semidefinite matrix. Since only $n \times n$ matrices can be positive semidefinite, we write ...'psd', 3... instead of ...'psd', 9....

Finally, we need to define the linear upper and lower bounds on $x_0,x_1,x_2$ with

lbx = -inf(3,1); % no bound -> set to -inf
ubx = inf(3,1); % no bound -> set to inf

Cost and constraints

We define the three matrices (cost function and first two constraints) with

A = [2 1 0; 1 2 1; 0 1 2];
B = eye(3);
C = ones(3, 3);

which now allows us to use standard Matlab syntax to define the cost function

sdp.f = trace(A*x_bar) + x(1);   % cost

and the three constraints with

sdp.g = [    % constraints
    trace(B*x_bar) + x(1);
    trace(C*x_bar) + x(2) + x(3);
    [x(1); x(2); x(3)];
]

where the actual dimension is size(sdp.g)= [5 1] since the Lorentz cone constraint considers three variables which we define with the K_-notation:

% cones
opts.Kc = struct('lin', [2], 'lor', [3]);

Since we could potentially have several Lorentz constraints, [3] can correctly be defined as a list (best practice). Finally, we add the upper and lower bounds for the first two linear constraints

lbg = [1; .5];
ubg = [1; .5];

to force the equality constraints given in the problem.

Now we can build the solver and obtain the solution with

% Use high-level interface
S = casos.sdpsol('S','mosek',sdp,opts);
sol = S('lbx',lbx,'ubx',ubx,'lbg',lbg,'ubg',ubg);

The complete code is given by:

% https://docs.mosek.com/latest/toolbox/tutorial-sdo-shared.html#example-sdo1

% Decision variables
x_bar = casadi.SX.sym('x_bar', 3, 3); % matrix
x = casadi.SX.sym('x', 3, 1); % vector

sdp.x = [x; x_bar(:)]; % List of decision variables

lbx = -inf(3,1); % lower bound
ubx = inf(3,1); % upper bound


opts.Kx = struct('lin', [3], 'psd', [3]);

% Cost and constraints
A = [2 1 0; 1 2 1; 0 1 2];
B = eye(3);
C = ones(3, 3);

sdp.f = trace(A*x_bar) + x(1); % cost

% constraints
sdp.g = [
    trace(B*x_bar) + x(1);
    trace(C*x_bar) + x(2) + x(3);
    [x(1); x(2); x(3)];
]

% Conic constraints
opts.Kc = struct('lin', [2], 'lor', [3]);

% Linear upper and lower bound
lbg = [1; .5];
ubg = [1; .5];

% Use SDP interface
S = casos.sdpsol('S','mosek',sdp,opts);
sol = S('lbx',lbx,'ubx',ubx,'lbg',lbg,'ubg',ubg);