Tools for Specifying and Solving LMIs

The LMI Lab is a high-performance package for solving general LMI problems. It blends simple tools for the specification and manipulation of LMIs with powerful LMI solvers for three generic LMI problems. Thanks to a structure-oriented representation of LMIs, the various LMI constraints can be described in their natural block-matrix form. Similarly, the optimization variables are specified directly as matrix variables with some given structure. Once an LMI problem is specified, it can be solved numerically by calling the appropriate LMI solver. The three solvers feasp, mincx, and gevp constitute the computational engine of the LMI portion of Robust Control Toolbox™ software. Their high performance is achieved through C-MEX implementation and by taking advantage of the particular structure of each LMI.

The LMI Lab offers tools to

Specify LMI systems either symbolically with the LMI Editor or incrementally with the lmivar and lmiterm commands
Retrieve information about existing systems of LMIs
Modify existing systems of LMIs
Solve the three generic LMI problems (feasibility problem, linear objective minimization, and generalized eigenvalue minimization)
Validate results

This chapter gives a tutorial introduction to the LMI Lab as well as more advanced tips for making the most out of its potential.

Some Terminology

Any linear matrix inequality can be expressed in the canonical form

L(x) = L₀ + x₁L₁ + . . . + x_NL_N < 0

where

L₀, L₁, . . . , L_N are given symmetric matrices
x = (x₁, . . . , x_N)^T ∊ R^N is the vector of scalar variables to be determined. We refer to x₁, . . . , x_N as the decision variables. The names “design variables” and “optimization variables” are also found in the literature.

Even though this canonical expression is generic, LMIs rarely arise in this form in control applications. Consider for instance the Lyapunov inequality

A^{T} X + X A < 0

(1)

where

$A = (\begin{matrix} - 1 & 2 \\ 0 & - 2 \end{matrix})$

and the variable

$X = (\begin{matrix} x_{1} & x_{2} \\ x_{2} & x_{3} \end{matrix})$

is a symmetric matrix. Here the decision variables are the free entries x₁, x₂, x₃ of X and the canonical form of this LMI reads

x_{1} (\begin{matrix} - 2 & 2 \\ 2 & 0 \end{matrix}) + x_{2} (\begin{matrix} 0 & - 3 \\ - 3 & 4 \end{matrix}) + x_{3} (\begin{matrix} 0 & 0 \\ 0 & - 4 \end{matrix}) < 0.

(2)

Clearly this expression is less intuitive and transparent than Equation 1. Moreover, the number of matrices involved in Equation 2 grows roughly as n² /2 if n is the size of the A matrix. Hence, the canonical form is very inefficient from a storage viewpoint since it requires storing o(n² /2) matrices of size n when the single n-by-n matrix A would be sufficient. Finally, working with the canonical form is also detrimental to the efficiency of the LMI solvers. For these various reasons, the LMI Lab uses a structured representation of LMIs. For instance, the expression A^TX + XA in the Lyapunov inequality Equation 1 is explicitly described as a function of the matrix variable X, and only the A matrix is stored.

In general, LMIs assume a block matrix form where each block is an affine combination of the matrix variables. As a fairly typical illustration, consider the following LMI drawn from H^∞ theory

N^{T} (\begin{matrix} A^{T} X + X A & X C^{T} & B \\ C X & - γ I & D \\ B^{T} & D^{T} & - γ I \end{matrix}) N < 0

(3)

where A, B, C, D, and N are given matrices and the problem variables are X = X^T ∊ R^n×n and γ ∊ R. We use the following terminology to describe such LMIs:

N is called the outer factor, and the block matrix
$L (X, γ) = (\begin{matrix} A^{T} X + X A & X C^{T} & B \\ C X & - γ I & D \\ B^{T} & D^{T} & - γ I \end{matrix})$
is called the inner factor. The outer factor needs not be square and is often absent.
X and γ are the matrix variables of the problem. Note that scalars are considered as 1-by-1 matrices.
The inner factor L(X, γ) is a symmetric block matrix, its block structure being characterized by the sizes of its diagonal blocks. By symmetry, L(X, γ) is entirely specified by the blocks on or above the diagonal.
Each block of L(X, γ) is an affine expression in the matrix variables X and γ. This expression can be broken down into a sum of elementary terms. For instance, the block (1,1) contains two elementary terms: A^TX and XA.
Terms are either constant or variable. Constant terms are fixed matrices like B and D above. Variable terms involve one of the matrix variables, like XA, XC^T, and –γI above.

The LMI (Equation 3) is specified by the list of terms in each block, as is any LMI regardless of its complexity.

As for the matrix variables X and γ, they are characterized by their dimensions and structure. Common structures include rectangular unstructured, symmetric, skew-symmetric, and scalar. More sophisticated structures are sometimes encountered in control problems. For instance, the matrix variable X could be constrained to the block-diagonal structure:

$X = (\begin{matrix} x_{1} & 0 & 0 \\ 0 & x_{2} & x_{3} \\ 0 & x_{3} & x_{4} \end{matrix}) .$

Another possibility is the symmetric Toeplitz structure:

$X = (\begin{matrix} x_{1} & x_{2} & x_{3} \\ x_{2} & x_{1} & x_{2} \\ x_{3} & x_{2} & x_{1} \end{matrix}) .$

Summing up, structured LMI problems are specified by declaring the matrix variables and describing the term content of each LMI. This term-oriented description is systematic and accurately reflects the specific structure of the LMI constraints. There is no built-in limitation on the number of LMIs that you can specify or on the number of blocks and terms in any given LMI. LMI systems of arbitrary complexity can therefore, be defined in the LMI Lab.

Overview of the LMI Lab

The LMI Lab offers tools to specify, manipulate, and numerically solve LMIs. Its main purpose is to

Allow for straightforward description of LMIs in their natural block-matrix form
Provide easy access to the LMI solvers (optimization codes)
Facilitate result validation and problem modification

The structure-oriented description of a given LMI system is stored as a single vector called the internal representation and generically denoted by LMISYS in the sequel. This vector encodes the structure and dimensions of the LMIs and matrix variables, a description of all LMI terms, and the related numerical data. It must be stressed that you need not attempt to read or understand the content of LMISYS since all manipulations involving this internal representation can be performed in a transparent manner with LMI-Lab tools.

The LMI Lab supports the following functionalities:

Specification of a System of LMIs

LMI systems can be either specified as symbolic matrix expressions with the interactive user interface lmiedit, or assembled incrementally with the two commands lmivar and lmiterm. The first option is more intuitive and transparent while the second option is more powerful and flexible.

Information Retrieval

The interactive function lmiinfo answers qualitative queries about LMI systems created with lmiedit or lmivar and lmiterm. You can also use lmiedit to visualize the LMI system produced by a particular sequence of lmivar/lmiterm commands.

Solvers for LMI Optimization Problems

General-purpose LMI solvers are provided for the three generic LMI problems defined in LMI Applications. These solvers can handle very general LMI systems and matrix variable structures. They return a feasible or optimal vector of decision variables x*. The corresponding values $X_{1}^{*}, \dots, X_{K}^{*}$ of the matrix variables are given by the function dec2mat.

Result Validation

The solution x* produced by the LMI solvers is easily validated with the functions evallmi and showlmi. This allows a fast check and/or analysis of the results. With evallmi, all variable terms in the LMI system are evaluated for the value x* of the decision variables. The left and right sides of each LMI then become constant matrices that can be displayed with showlmi.

Modification of a System of LMIs

An existing system of LMIs can be modified in two ways:

An LMI can be removed from the system with dellmi.
A matrix variable X can be deleted using delmvar. It can also be instantiated, that is, set to some given matrix value. This operation is performed by setmvar and allows, for example, to fix some variables and solve the LMI problem with respect to the remaining ones.