gevp

Generalized eigenvalue minimization under LMI constraints

Syntax

[lopt,xopt] = gevp(lmisys,nlfc,options,linit,xinit,target)

Description

gevp solves the generalized eigenvalue minimization problem of minimizing λ, subject to:

C (x) < D (x)

(1)

0 < B (x)

(2)

A (x) < λ B (x)

(3)

where C(x) < D(x) and A(x) < λB(x) denote systems of LMIs. Provided that Equation 1 and Equation 2 are jointly feasible, gevp returns the global minimum lopt and the minimizing value xopt of the vector of decision variables x. The corresponding optimal values of the matrix variables are obtained with dec2mat.

The argument lmisys describes the system of LMIs Equation 1 to Equation 3 for λ = 1. The LMIs involving λ are called the linear-fractional constraints while Equation 1 and Equation 2 are regular LMI constraints. The number of linear-fractional constraints Equation 3 is specified by nlfc. All other input arguments are optional. If an initial feasible pair (λ₀, x₀) is available, it can be passed to gevp by setting linit to λ₀ and xinit to x₀. Note that xinit should be of length decnbr(lmisys) (the number of decision variables). The initial point is ignored when infeasible. Finally, the last argument target sets some target value for λ. The code terminates as soon as it has found a feasible pair (λ, x) with λ ≤ target.

Caution

When setting up your gevp problem, be cautious to

Always specify the linear-fractional constraints Equation 3 last in the LMI system. gevp systematically assumes that the last nlfc LMI constraints are linear fractional.
Add the constraint B(x) > 0 or any other LMI constraint that enforces it (see Remark below). This positivity constraint is required for regularity and good formulation of the optimization problem.

Control Parameters

The optional argument options lets you access control parameters of the optimization code. In gevp, 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 the same as for feasp.
options(4) helps speed up termination. If set to an integer value J > 0, the code terminates when the progress in λ over the last J iterations falls below the desired relative accuracy. Progress means the amount by which λ decreases. The default value is 5 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.

Examples

Given

$A 1 = (\begin{matrix} - 1 & 2 \\ 1 & - 3 \end{matrix}), A 2 = (\begin{matrix} - 0.8 & 1.5 \\ 1.3 & - 2.7 \end{matrix}), A 3 = (\begin{matrix} - 1.4 & 0.9 \\ 0.7 & - 2.0 \end{matrix}),$

consider the problem of finding a single Lyapunov function V(x) = x^TPx that proves stability of

$\dot{x} = A_{i} x (i = 1, 2, 3)$

and maximizes the decay rate $\frac{d V (x)}{d t}$ . This is equivalent to minimizing

α subject to

I < P

(4)

A_{1}^{T} P + P A_{1} < α P

(5)

A_{2}^{T} P + P A_{2} < α P

(6)

A_{3}^{T} P + P A_{3} < α P

(7)

To set up this problem for gevp, first specify the LMIs Equation 5 to Equation 7with α = 1:

setlmis([]); 
p = lmivar(1,[2 1])

lmiterm([1 1 1 0],1) 	% P > I : I 
lmiterm([-1 1 1 p],1,1) 	% P > I : P 
lmiterm([2 1 1 p],1,a1,'s') 	% LFC # 1 (lhs) 
lmiterm([-2 1 1 p],1,1) 	% LFC # 1 (rhs) 
lmiterm([3 1 1 p],1,a2,'s') 	% LFC # 2 (lhs) 
lmiterm([-3 1 1 p],1,1) 	% LFC # 2 (rhs) 
lmiterm([4 1 1 p],1,a3,'s') 	% LFC # 3 (lhs) 
lmiterm([-4 1 1 p],1,1) 	% LFC # 3 (rhs) 
lmis = getlmis

Note that the linear fractional constraints are defined last as required. To minimize α subject to Equation 5 to Equation 7, call gevp by

[alpha,popt]=gevp(lmis,3)

This returns alpha = -0.122 as the optimal value (the largest decay rate is therefore 0.122). This value is achieved for:

$P = (\begin{matrix} 5.58 & - 8.35 \\ - 8.35 & 18.64 \end{matrix})$

Tips

Generalized eigenvalue minimization problems involve standard LMI constraints Equation 1 and linear fractional constraints Equation 3. For well-posedness, the positive definiteness of B(x) must be enforced by adding the constraint B(x) > 0 to the problem. Although this could be done automatically from inside the code, this is not desirable for efficiency reasons. For instance, the set of constraints Equation 2 may reduce to a single constraint as in the example above. In this case, the single extra LMI “P > I ” is enough to enforce positivity of all linear-fractional right sides. It is therefore left to the user to devise the least costly way of enforcing this positivity requirement.

References

The solver gevp is based on Nesterov and Nemirovski's Projective Method described in

Nesterov, Y., and A. Nemirovski, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, SIAM, Philadelphia, 1994.

The optimization is performed by the C MEX-file fpds.mex.

Documentation