Generalized eigenvalue minimization under LMI constraints

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

`gevp`

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

$$C(x)<D(x)$$ | (1-7) |

$$0<B(x)$$ | (1-8) |

$$A(x)<\lambda B(x)$$ | (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}, *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.

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.

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.

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}*

$$\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$$ | (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)$$

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`

.

Was this topic helpful?