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-4 and Equation 1-5 are jointly feasible,
the global minimum
lopt and the minimizing value
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-4 to Equation 1-6 for λ =
1. The LMIs involving λ are called the linear-fractional
constraints while Equation 1-4 and Equation 1-5 are regular LMI constraints. The
number of linear-fractional constraints Equation 1-6 is specified by
All other input arguments are optional. If an initial feasible pair
is available, it can be passed to
gevp by setting
xinit to x0.
xinit should be of length
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
Always specify the linear-fractional constraints Equation 1-6 last in
the LMI system.
gevp systematically assumes that
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
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) = 1 turns off the trace
of execution of the optimization procedure. Resetting
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
Generalized eigenvalue minimization problems involve standard LMI constraints Equation 1-4 and linear fractional constraints Equation 1-6. 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-5 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