# 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)<\lambda 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 (λ_{0}, *x*_{0}) is available, it can be passed to `gevp`

by setting `linit`

to λ_{0} and `xinit`

to *x*_{0}. 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

$$A1=\left(\begin{array}{cc}-1& 2\\ 1& -3\end{array}\right),\text{}A2=\left(\begin{array}{cc}-0.8& 1.5\\ 1.3& -2.7\end{array}\right),\text{}A3=\left(\begin{array}{cc}-1.4& 0.9\\ 0.7& -2.0\end{array}\right),$$

consider the problem of finding a single Lyapunov function *V*(*x*) = *x ^{T}*

*Px*that proves stability of

$$\dot{x}={A}_{i}x\text{}(i=1,2,3)$$

and maximizes the decay rate $$\frac{dV(x)}{dt}$$. This is equivalent to minimizing

α subject to

$$I<P$$ | (4) |

$${A}_{1}^{T}P+P{A}_{1}<\alpha P$$ | (5) |

$${A}_{2}^{T}P+P{A}_{2}<\alpha P$$ | (6) |

$${A}_{3}^{T}P+P{A}_{3}<\alpha 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=\left(\begin{array}{cc}5.58& -8.35\\ -8.35& 18.64\end{array}\right)$$

## 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`

.

## Version History

**Introduced before R2006a**