Main Content

mincx

Minimize linear objective under LMI constraints

collapse all in page

Syntax

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

Description

[copt,xopt] = mincx(lmisys,c) solves the convex program:

minimize cTx subject to NTL(x)N≤MTR(x)M

where x denotes the vector of scalar decision variables, the free scalar variables in the system. lmisys describes the system of LMIs. mincx returns the global minimum copt for the objective cTx and the minimizing value xopt of the vector of decision variables.

example

[copt,xopt] = mincx(lmisys,c,options) specifies certain control parameters of the optimization code.

[copt,xopt] = mincx(lmisys,c,options,xinit) specifies an initial guess for the minimizer xopt, which might speed up the computation.

[copt,xopt] = mincx(lmisys,c,options,xinit,target) sets a target for the objective value. The code terminates when mincx finds some feasible x such that cTx ≤ target.

Examples

collapse all

Suppose that you have formulated a problem in terms of LMI constraints on a set of decision variables X and defined those constraints in MATLAB® using lmivar and lmiterm. Find an optimum set of values that satisfies the LMI constraint.

First, specify the vector c for the objective cTx. You can use defcx to derive this vector (See Specifying cTx Objectives for mincx). For this example, suppose that X is a 3-by-3 matrix and that the goal is to minimize Trace(x). In this case, construct c to pick out the diagonal values of x. 

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

Call mincx to perform the minimization.

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

Upon termination, mincx returns the global minimum for the objective Trace(X) in the variable copt. The function also returns the optimizing vector of decision-variable values xopt. To obtain the corresponding optimal value of the matrix variable X, use mat2dec.

Xopt = dec2mat(LMIs,xopt,X);

Input Arguments

collapse all

Optimization problem to solve, specified as a vector that encodes the internal representation of an LMI system. To obtain this vector, use setlmis, lmivar, lmiterm, and getlmis, as described in Specify LMI System at the Command Line.

Objectives for the optimization, specified as a vector. The vector c corresponds to the objectives cTx. 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, use defcx to derive c.

Control parameters, specified as a five-element vector whose elements have the following values.

  • options(1) sets the desired relative accuracy on the optimal value copt (default = 10e-2).

  • options(2) sets the maximum number of iterations allowed before the optimization terminates (default = 100).

  • options(3) sets the feasibility radius. Its purpose and usage are as for feasp.

  • options(4) helps speed up termination. If you set this element to an integer value J > 0, the optimization terminates when the objective cTx has failed to decrease by the desired relative accuracy during the last J iterations.

  • options(5) = 1 turns off the trace of execution of the optimization procedure. Setting 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.

Set options to [] to use the xinit and target arguments with the default options.

Initial guess for the decision variables x, specified as a vector of the same length as c. You can construct xinit from initial values of the matrix variables using mat2dec. Specifying feasible xinit might speed up the optimization. When the value is infeasible, mincx ignores this argument.

Target optimization value, specified as a scalar. mincx terminates when it finds feasible x such that cTx < target or when the conditions specified in options(2) and options(4), are met, whichever comes first.

Output Arguments

collapse all

Global minimum value of the objective cTx when the optimization terminates, returned as a scalar.

Optimizing vector of decision variables, returned as a vector. To obtain the corresponding values of the matrix variables from xopt, use dec2mat.

Tips

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

    minx|Ax−b|

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

    If you see this error, 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.

Algorithms

The solver mincx implements Nesterov and Nemirovski's Projective Method as described in [1] and [2]. The optimization is performed by the C-MEX file pds.mex.

References

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

[2] Nemirovski, A., and P. Gahinet, “The Projective Method for Solving Linear Matrix Inequalities,” Proc. Amer. Contr. Conf., 1994, Baltimore, Maryland, pp. 840-844.

Version History

Introduced before R2006a

See Also

| | | |

Topics