Further Mathematical Background on LMI Problems

Efficient interior-point algorithms are now available to solve the three generic LMI problems Equation 2–Equation 2 defined in LMI Applications. These algorithms have a polynomial-time complexity. That is, the number N(ɛ) of flops needed to compute an ɛ-accurate solution is bounded by

M N³ log(V/ɛ)

where M is the total row size of the LMI system, N is the total number of scalar decision variables, and V is a data-dependent scaling factor. Robust Control Toolbox™ software implements the Projective Algorithm of Nesterov and Nemirovski [20], [19]. In addition to its polynomial-time complexity, this algorithm does not require an initial feasible point for the linear objective minimization problem Equation 1 or the generalized eigenvalue minimization problem Equation 2.

Some LMI problems are formulated in terms of inequalities rather than strict inequalities. For instance, a variant of Equation 1 is

Minimize c^Tx subject to A(x) < 0.

While this distinction is immaterial in general, it matters when A(x) can be made negative semi-definite but not negative definite. A simple example is:

Minimize c^Tx subject to

$$\left(\begin{array}{cc}x& x\\ x& x\end{array}\right)\ge 0.$$

(1)

Such problems cannot be handled directly by interior-point methods which require strict feasibility of the LMI constraints. A well-posed reformulation of Equation 3 would be

Minimize c^Tx subject to x ≥ 0.

Keeping this subtlety in mind, we always use strict inequalities in this manual.