# 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\left(x\right) (1)
 $0 (2)
 $A\left(x\right)<\lambda B\left(x\right)$ (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, x0) is available, it can be passed to `gevp` by setting `linit` to λ0 and `xinit` to x0. 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

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

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

α subject to

 $I (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