Documentation

This is machine translation

Translated by
Mouse over text to see original. Click the button below to return to the English verison of the page.

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-7)
 $0 (1-8)
 $A\left(x\right)<\lambda B\left(x\right)$ (1-9)

where C(x) < D(x) and A(x) < λB(x) denote systems of LMIs. Provided that Equation 1-7 and Equation 1-8 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-7 to Equation 1-9 for λ = 1. The LMIs involving λ are called the linear-fractional constraints while Equation 1-7 and Equation 1-8 are regular LMI constraints. The number of linear-fractional constraints Equation 1-9 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 1-9 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 (1-10)
 ${A}_{1}^{T}P+P{A}_{1}<\alpha P$ (1-11)
 ${A}_{2}^{T}P+P{A}_{2}<\alpha P$ (1-12)
 ${A}_{3}^{T}P+P{A}_{3}<\alpha P$ (1-13)

To set up this problem for `gevp`, first specify the LMIs Equation 1-11 to Equation 1-13with α = 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 1-11 to Equation 1-13, 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)$`

collapse all

Tips

Generalized eigenvalue minimization problems involve standard LMI constraints Equation 1-7 and linear fractional constraints Equation 1-9. 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 1-8 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`.