Minimize Linear Objectives under LMI Constraints

Consider the optimization problem:

Minimize Trace(X) subject to

A^TX + XA + XBB^TX + Q < 0

(1)

with data

$A = (\begin{matrix} - 1 & - 2 & 1 \\ 3 & 2 & 1 \\ 1 & - 2 & - 1 \end{matrix}); B = (\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}); Q = (\begin{matrix} 1 & - 1 & 0 \\ - 1 & - 3 & - 12 \\ 0 & - 12 & - 36 \end{matrix}) .$

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

A^TX + XA + XBB^TX + 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

(\begin{matrix} A^{T} X + X A + Q & X B \\ B^{T} X & - I \end{matrix}) < 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:

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

Write the objective Trace(X) as c^Tx 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).

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 c^Tx 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 c^Tx 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.

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_{o p t} = (\begin{matrix} - 6.3542 & - 5.8895 & 2.2046 \\ - 5.8895 & - 6.2855 & 2.2201 \\ 2.2046 & 2.2201 & - 6.0771 \end{matrix}) .$
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
```

Minimize Linear Objectives under LMI Constraints

Related Topics