Minimize linear objective under LMI constraints

`[copt,xopt] = mincx(lmisys,c,options,xinit,target)`

`The function `

`mincx`

solves the convex program

$$\text{minimize}{c}^{T}x\text{subjectto}{N}^{T}L(x)N\le {M}^{T}R(x)M$$ | (1-16) |

where *x* denotes the vector of scalar decision
variables.

The system of LMIs is described by `lmisys`

.
The vector `c`

must be of the same length as *x*.
This length corresponds to the number of decision variables returned
by the function `decnbr`

. For
linear objectives expressed in terms of the matrix variables, the
adequate `c`

vector is easily derived with `defcx`

.

The function `mincx`

returns the global minimum `copt`

for
the objective *c ^{T}*

`xopt`

of the vector
of decision variables. The corresponding values of the matrix variables
is derived from `xopt`

with `dec2mat`

.The remaining arguments are optional. The vector `xinit`

is
an initial guess of the minimizer `xopt`

. It is ignored
when infeasible, but may speed up computations otherwise. Note that `xinit`

should
be of the same length as `c`

. As for `target`

,
it sets some target for the objective value. The code terminates as
soon as this target is achieved, that is, as soon as some feasible *x* such
that *c ^{T}*

`target`

is
found. Set `options`

to `[]`

to
use `xinit`

and `target`

with the
default options.The optional argument `options`

gives access
to certain control parameters of the optimization code. In `mincx`

,
this is a five-entry vector organized as follows:

`options(1)`

sets the desired relative accuracy on the optimal value`lopt`

(default = 10–2).`options(2)`

sets the maximum number of iterations allowed to be performed by the optimization procedure (100 by default).`options(3)`

sets the feasibility radius. Its purpose and usage are as for`feasp`

.`options(4)`

helps speed up termination. If set to an integer value*J*> 0, the code terminates when the objective*c*^{T}*x*has not decreased by more than the desired relative accuracy during the last*J*iterations.`options(5) = 1`

turns off the trace of execution of the optimization procedure. Resetting`options(5)`

to zero (default value) turns it back on.

Setting `option(i)`

to zero is equivalent to
setting the corresponding control parameter to its default value.
See `feasp`

for more detail.

In LMI optimization, the computational overhead per iteration mostly comes from solving a least-squares problem of the form

$$\underset{x}{\mathrm{min}}\left|Ax-b\right|$$

where *x* is the vector of decision variables.
Two methods are used to solve this problem: Cholesky factorization
of *A ^{T}A* (default), and
QR factorization of

* switching to QR

is displayed when the solver has to switch to the QR mode.

Since QR factorization is incrementally more expensive in most
problems, it is sometimes desirable to prevent switching to QR. This
is done by setting `options(4) = 1`

. While not guaranteed
to produce the optimal value, this generally achieves a good trade-off
between speed and accuracy.

QR-based linear algebra (see above) is not only expensive in
terms of computational overhead, but also in terms of memory requirement.
As a result, the amount of memory required by QR may exceed your swap
space for large problems with numerous LMI constraints. In such case, MATLAB^{®} issues
the error

??? Error using ==> pds Out of memory. Type HELP MEMORY for your options.

You should then ask your system manager to increase your swap
space or, if no additional swap space is available, set ```
options(4)
= 1
```

. This will prevent switching to QR and `mincx`

will
terminate when Cholesky fails due to numerical instabilities.

The solver `mincx`

implements Nesterov and
Nemirovski's Projective Method as described in

Nesterov, Yu, and A. Nemirovski, *Interior Point Polynomial
Methods in Convex Programming: Theory and Applications*,
SIAM, Philadelphia, 1994.

Nemirovski, A., and P. Gahinet, "The Projective Method
for Solving Linear Matrix Inequalities," *Proc. Amer.
Contr. Conf*., 1994, Baltimore, Maryland, pp. 840-844.

The optimization is performed by the C-MEX file `pds.mex`

.

Was this topic helpful?