mincx

Minimize linear objective under LMI constraints

Synopsis

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

Description

The function mincx solves the convex program

minimize cTx subject to NTL(x)NMTR(x)M(2-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 cTx, as well as the minimizing value 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 cTxtarget is found. Set options to [] to use xinit and target with the default options.

Control Parameters

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 cTx 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.

Tip for Speed-Up

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

minx|Axb|

where x is the vector of decision variables. Two methods are used to solve this problem: Cholesky factorization of ATA (default), and QR factorization of A when the normal equation becomes ill conditioned (when close to the solution typically). The message

* 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.

Memory Problems

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.

References

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.

See Also

| | | | |

Was this topic helpful?