Minimize Linear Objectives under LMI Constraints

Consider the optimization problem:

Minimize Trace(X) subject to

 ATX + XA + XBBTX + Q < 0 (1)

with data

$A=\left(\begin{array}{ccc}-1& -2& 1\\ 3& 2& 1\\ 1& -2& -1\end{array}\right);\text{ }B=\left(\begin{array}{c}1\\ 0\\ 1\end{array}\right);\text{ }Q=\left(\begin{array}{ccc}1& -1& 0\\ -1& -3& -12\\ 0& -12& -36\end{array}\right).$

It can be shown that the minimizer X* is simply the stabilizing solution of the algebraic Riccati equation

ATX + XA + XBBTX + Q = 0

This solution can be computed directly with the Riccati solver care and compared to the minimizer returned by mincx.

From an LMI optimization standpoint, the problem specified in Equation 1 is equivalent to the following linear objective minimization problem:

Minimize Trace(X) subject to

 $\left(\begin{array}{cc}{A}^{T}X+XA+Q& XB\\ {B}^{T}X& -I\end{array}\right)<0.$ (2)

Since Trace(X) is a linear function of the entries of X, this problem falls within the scope of the mincx solver and can be numerically solved as follows:

1. Define the LMI constraint of Equation 1 by the sequence of commands

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

2. Write the objective Trace(X) as cTx where x is the vector of free entries of X. Since c should select the diagonal entries of X, it is obtained as the decision vector corresponding to X = I, that is,

c = mat2dec(LMIs,eye(3))

Note that the function defcx provides a more systematic way of specifying such objectives (see Specifying cTx Objectives for mincx for details).

3. 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)

Here 1e–5 specifies the desired relative accuracy on copt.

The following trace of the iterative optimization performed by mincx appears on the screen:

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. Note that no value is displayed at the first iteration, which means that a feasible x satisfying the constraint (Equation 2) was found only at the second iteration. Lower bounds on the global minimum of cTx are sometimes detected as the optimization progresses. These lower bounds are reported by the message

*** new lower bound: xxx

Upon termination, mincx reports that the global minimum for the objective Trace(X) is –18.716695 with relative accuracy of at least 9.5×10–6. This is the value copt returned by mincx.

4. 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)

which returns

${X}_{opt}=\left(\begin{array}{ccc}-6.3542& -5.8895& 2.2046\\ -5.8895& -6.2855& 2.2201\\ 2.2046& 2.2201& -6.0771\end{array}\right).$

This result can be compared with the stabilizing Riccati solution computed by care:

Xst = care(a,b,q,-1)
norm(Xopt-Xst)

ans =
6.5390e-05