Minimize Linear Objectives Under LMI Constraints

Consider an optimization to minimize the trace of a variable X subject to the following LMI constraint.

$A^{T} X + XA + XB B^{T} X + Q < 0$ ,

with data

$A = [\begin{array}{c} - 1 & - 2 & 1 \\ 3 & 2 & 1 \\ 1 & - 2 & - 1 \end{array}], B = [\begin{array}{c} 1 \\ 0 \\ 1 \end{array}], Q = [\begin{array}{c} 1 & - 1 & 0 \\ - 1 & - 3 & - 12 \\ 0 & - 12 & - 36 \end{array}] .$

A = [-1 -2  1 ;  3  2  1;  1  -2  -1 ];
B = [ 1; 0; 1];
Q = [ 1 -1  0 ; -1 -3 -12; 0  -12 -36];

The problem specified in is equivalent to the linear objective minimization problem of minimizing Trace(X) subject to:

$[\begin{array}{c} A^{T} X + XA + Q & XB \\ B^{T} X & - I \end{array}] < 0$ .

Trace(X) is a linear function of the entries of X. Therefore, this problem falls within the scope of the mincx LMI solver. To so, first define this set of LMI constraints using lmivar.

setlmis([]) 
X = lmivar(1,[3 1]); % variable X, full symmetric

lmiterm([1 1 1 X],1,A,'s') 
lmiterm([1 1 1 0],Q) 
lmiterm([1 2 2 0],-1) 
lmiterm([1 2 1 X],B',1)

LMIs = getlmis;

Write the objective Trace(X) as $c^{T} x$ where x is the vector of free entries of X. Since C should select the diagonal entries of X, obtained it as the decision vector corresponding to X = I.

c = mat2dec(LMIs,eye(3));

(The function defcx provides an alternative, more systematic way of specifying such objectives. See Advanced LMI Techniques for details.)

Call mincx to compute the minimizer xopt and the global minimum copt = c'*xopt of the objective.

options = [1e-5,0,0,0,0]; 
[copt,xopt] = mincx(LMIs,c,options);

 Solver for linear objective minimization under LMI constraints 

 Iterations   :    Best objective value so far 
 
     1
     2                  -8.511476
     3                 -13.063640
***                 new lower bound:   -34.023978
     4                 -15.768450
***                 new lower bound:   -25.005604
     5                 -17.123012
***                 new lower bound:   -21.306781
     6                 -17.882558
***                 new lower bound:   -19.819471
     7                 -18.339853
***                 new lower bound:   -19.189417
     8                 -18.552558
***                 new lower bound:   -18.919668
     9                 -18.646811
***                 new lower bound:   -18.803708
    10                 -18.687324
***                 new lower bound:   -18.753903
    11                 -18.705715
***                 new lower bound:   -18.732574
    12                 -18.712175
***                 new lower bound:   -18.723491
    13                 -18.714880
***                 new lower bound:   -18.719624
    14                 -18.716094
***                 new lower bound:   -18.717986
    15                 -18.716509
***                 new lower bound:   -18.717297
    16                 -18.716695
***                 new lower bound:   -18.716873

 Result:  feasible solution of required accuracy
          best objective value:   -18.716695
          guaranteed relative accuracy:  9.50e-06
          f-radius saturation:  0.000% of R =  1.00e+09

The iteration number and the best value of cTx at the current iteration appear in the left and right columns, respectively. In this case, no value is displayed at the first iteration, which means that mincx did not find a feasible x satisfying the constraint until the second iteration. The function sometimes detects lower bounds on the global minimum of cTx as the optimization progresses. These lower bounds are reported by the message new lower bound.

Upon termination, mincx returns the global minimum for the objective Trace(X) in the variable copt.

copt

copt = 
-18.7167

mincx also returns the optimizing vector of decision variables xopt. The corresponding optimal value of the matrix variable X is given by

Xopt = dec2mat(LMIs,xopt,X)

Xopt = 3×3

   -6.3542   -5.8895    2.2046
   -5.8895   -6.2855    2.2201
    2.2046    2.2201   -6.0771

It can be shown that the minimizer value of X is the stabilizing solution of the algebraic Riccati equation:

$A^{T} X + X A + X B B^{T} X + Q = 0$ ,

You can compute this solution directly with the Riccati solver icare and confirm that the minimizer returned by mincx is essentially identical.

Xst = icare(A,B,Q,-1);
norm(Xopt-Xst)

ans = 
6.5389e-05

Minimize Linear Objectives Under LMI Constraints

Related Topics