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:
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
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.
When setting up your
gevp problem, be cautious to
Always specify the linear-fractional constraints Equation 3 last in the LMI system.
gevpsystematically assumes that the last
nlfcLMI 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
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) = 1turns off the trace of execution of the optimization procedure. Resetting
options(5)to zero (default value) turns it back on.
option(i) to zero is equivalent to setting the corresponding control parameter to its default value.
consider the problem of finding a single Lyapunov function V(x) = xTPx that proves stability of
and maximizes the decay rate . This is equivalent to minimizing
α subject to
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
alpha = -0.122 as the optimal value (the largest decay rate is therefore 0.122). This value is achieved for:
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.
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