gevp

Generalized eigenvalue minimization under LMI constraints

Syntax

[lopt,xopt] = gevp(lmisys,numlfc)

[lopt,xopt] = gevp(lmisys,numlfc,options)

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

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

Description

[lopt,xopt] = gevp(lmisys,numlfc) solves the generalized eigenvalue minimization problem of minimizing λ, subject to:

$$C(x)<D(x)$$

$$0<B(x)$$

$$A(x)<\lambda B(x)$$

Here, C(x) < D(x) and A(x) < λB(x) denote systems of LMIs. Provided that these two equations are jointly feasible, gevp returns the global minimum value of λ and the minimizing value of the vector of decision variables x.

The argument lmisys describes the system of LMIs given by the three above equations when λ = 1. The LMIs involving λ are called linear-fractional constraints, while the first two equations are regular LMI constraints. Use the input argument numlfc to specify the number of linear-fractional constraints.

[lopt,xopt] = gevp(lmisys,numlfc,options) further specifies control parameters for the optimization.

[lopt,xopt] = gevp(lmisys,numlfc,options,linit,xinit) initiates the optimization with an initial feasible pair of values (λ₀, x₀). The initial point is ignored when infeasible.

[lopt,xopt] = gevp(lmisys,numlfc,options,linit,xinit,target) terminates the optimization as soon as it finds a feasible pair (λ, x) with λ ≤ target.

Examples

Eigenvalue Minimization Problem

Given the following matrices,

A1 = [-1   2;   1   -3];
A2 = [-0.8 1.5; 1.3 -2.7];
A3 = [-1.4 0.9; 0.7 -2.0];

consider the problem of finding a single Lyapunov function $\mathit{V}\left(\mathit{x}\right)={\mathit{x}}^{\mathit{T}}\mathit{Px}$ that proves stability of

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

and maximizes the decay rate

$\frac{\mathit{dV}\left(\mathit{x}\right)}{\mathit{dt}}$.

This problem is equivalent to minimizing α subject to the following constraints.

$$\begin{array}{l}\mathit{I}<\mathit{P}\\ {\mathit{A}}_1^{\mathit{T}}\mathit{P}+\mathit{P}{\mathit{A}}_1<\alpha \mathit{P}\\ {\mathit{A}}_2^{\mathit{T}}\mathit{P}+\mathit{P}{\mathit{A}}_2<\alpha \mathit{P}\\ {\mathit{A}}_3^{\mathit{T}}\mathit{P}+\mathit{P}{\mathit{A}}_3<\alpha \mathit{P}\end{array}$$

The constraint $\mathit{I}<\mathit{P}$ enforces positive definiteness of the right sides of the linear-fractional constraints ${\mathit{A}}_{\mathit{i}}^{\mathit{T}}\mathit{P}+\mathit{P}{\mathit{A}}_{\mathit{i}}<\alpha \mathit{P}$ .

To set up this problem for gevp, first declare the variable P using setlmis.

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

Specify the first LMI, $\mathit{I}<\mathit{P}$, using lmiterm.

lmiterm([1 1 1 0],1) 	    % I > P : (left-hand side)
lmiterm([-1 1 1 P],1,1) 	% I > P : (right-hand side) 

Specify the remaining three LMIs. These LMIs represent the linear fractional constraints, so specify them last.

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) 
lmisys = getlmis;

To minimize α subject to these LMIs, call gevp specifying three linear fractional constraints.

numlfc = 3;
[alpha,popt] = gevp(lmisys,numlfc);

 Solver for generalized eigenvalue minimization 
 Iterations   :    Best objective value so far 
      1                 309.375000
     2                 146.808105
     3                  12.992181
     4                   2.197944
     5                   1.516582
***                 new lower bound:  -154.086399
     6                   1.046441
     7                  -0.026895
     8                  -0.035232
     9                  -0.046154
    10                  -0.060462
    11                  -0.116112
    12                  -0.116112
    13                  -0.117273
    14                  -0.118446
    15                  -0.119630
    16                  -0.120826
***                 new lower bound:    -0.156715
    17                  -0.121948
***                 new lower bound:    -0.155594
    18                  -0.121948
    19                  -0.121948
***                 new lower bound:    -0.138771
    20                  -0.122107
***                 new lower bound:    -0.126067
    21                  -0.122107
    22                  -0.122107
***                 new lower bound:    -0.123097

 Result:  feasible solution of required accuracy
          best value of t:    -0.122107
          guaranteed absolute accuracy:  9.90e-04
          f-radius saturation:  0.000% of R =  1.00e+08 
 

The optimization returns alpha = -0.122 as the optimal value, meaning that the largest decay rate is 0.122. You can use dec2mat to convert popt to the value of P that achieves optimal result.

Pval = dec2mat(lmisys,popt,P)

Pval = 2×2

    5.5789   -8.3503
   -8.3503   18.6443

Input Arguments

lmisys — Optimization problem

vector

Optimization problem to solve, specified as a vector that encodes the internal representation of an LMI system. To obtain this vector, use setlmis, lmivar, lmiterm, and getlmis, as described in Specify LMI System at the Command Line. When setting up your problem for gevp:

• Include the constraint B(x) > 0 or any other LMI constraint that enforces B(x) > 0. This positivity constraint is required for regularity and good formulation of the optimization problem. For instance, in the example Eigenvalue Minimization Problem, the extra LMI constraint P > I enforces positivity of the right sides of all linear-fractional constraints.

• Specify the linear-fractional constraints $$A(x)<\lambda B(x)$$ last in the LMI system. gevp assumes that the last numlfc LMIs are the linear-fractional constraints.

numlfc — Number of linear-fractional constraints

integer

Number of linear-fractional constraints of the form $$A(x)<\lambda B(x)$$ in the LMI system, specified as an integer. gevp interprets this argument to mean that the last numlfc LMIs in lmisys are the linear-fractional constraints.

options — Control parameters

[0,0,0,0,0] (default) | five-element vector | []

Control parameters, specified as a five-element vector whose elements have the following values.

• options(1) sets the desired relative accuracy on the minimal value lopt (default = 10e-2).

• options(2) sets the maximum number of iterations allowed before the optimization terminates (default = 100).

• options(3) sets the feasibility radius. Its purpose and usage are the same as for feasp.

• options(4) might help speed up termination. If you set this element to an integer value J > 0, the optimization terminates when λ has decreased by less than the desired relative accuracy over the last J iterations. The default value is five iterations.

• options(5) = 1 turns off the trace of execution of the optimization procedure. Setting 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.

Set options to [] to use the linit, xinit and target arguments with the default options.

linit — Initial guess for λ

scalar

Initial guess for λ, specified as a scalar. Providing feasible initial values linit and xinit for (λ,x) might speed up the optimization. If provide linit and xinit are infeasible, gevp ignores the values.

xinit — Initial guess for x

vector

Initial guess for the decision variables x, specified as a vector of length decnbr(lmisys), which is the number of decision variables in lmisys. You can construct xinit from initial values of the matrix variables using mat2dec.Providing feasible initial values linit and xinit for (λ,x) might speed up the optimization. If provide linit and xinit are infeasible, gevp ignores the values.

target — Target λ value

-1e4 (default) | scalar

Target λ value, specified as a scalar. gevp terminates the optimization when it finds a feasible pair (λ, x) with λ ≤ target or when the conditions specified in options(2) and options(4), are met, whichever comes first.

Output Arguments

lopt — Minimized value of λ

scalar

Minimized value of λ, returned as a scalar.

xopt — Optimizing vector of decision variables

vector

Optimizing vector of decision variables that yields the minimized value of λ, returned as a vector. To obtain the corresponding values of the matrix variables from xopt, use dec2mat.

Algorithms

The solver gevp is based on Nesterov and Nemirovskii's Projective Method described in Nesterov, Yurii, and Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming Society for Industrial and Applied Mathematics, 1994. https://doi.org/10.1137/1.9781611970791

Version History

Introduced before R2006a