LMI Solvers

LMI solvers are provided for the following three generic optimization problems (here x denotes the vector of decision variables, i.e., of the free entries of the matrix variables X1, . . . , XK):

  • Feasibility problem

    Find x ∊ RN (or equivalently matrices X1, . . . , XK with prescribed structure) that satisfies the LMI system

    A(x) < B(x)

    The corresponding solver is called feasp.

  • Minimization of a linear objective under LMI constraints

    Minimize cTx over x ∊ RN subject to A(x) < B(x)

    The corresponding solver is called mincx.

  • Generalized eigenvalue minimization problem

    Minimize λ over x ∊ RN subject to

              C(x) < D(x)

                  0 < B(x)

              A(x) < λB(x).

    The corresponding solver is called gevp.

Note that A(x) < B(x) above is a shorthand notation for general structured LMI systems with decision variables x = (x1, . . . , xN).

The three LMI solvers feasp, mincx, and gevp take as input the internal representation LMISYS of an LMI system and return a feasible or optimizing value x* of the decision variables. The corresponding values of the matrix variables X1, . . . , XK are derived from x* with the function dec2mat. These solvers are C-MEX implementations of the polynomial-time Projective Algorithm Projective Algorithm of Nesterov and Nemirovski [3], [2].

For generalized eigenvalue minimization problems, it is necessary to distinguish between the standard LMI constraints C(x) < D(x) and the linear-fractional LMIs

A(x) < λB(x)

attached to the minimization of the generalized eigenvalue λ. When using gevp, you should follow these three rules to ensure proper specification of the problem:

  • Specify the LMIs involving λ as A(x) < B(x) (without the λ)

  • Specify them last in the LMI system. gevp systematically assumes that the last L LMIs are linear-fractional if L is the number of LMIs involving λ

  • Add the constraint 0 < B(x) or any other constraint that enforces it. This positivity constraint is required for well-posedness of the problem and is not automatically added by gevp.

An initial guess xinit for x can be supplied to mincx or gevp. Use mat2dec to derive xinit from given values of the matrix variables X1, . . . , XK.

The example Minimize Linear Objectives Under LMI Constraints illustrates the use of the mincx solver.

See Also

Topics