Interior-point algorithms for semidefinite programming problems
derived from the Kalman-Yakubovich-Popov Lemma
Interior-point algorithms for semidefinite programming problems
derived from the Kalman-Yakubovich-Popov Lemma
V. Balakrishnan
Presented at the European Union RTN Summer School on Multi-Agent Control,
Hamilton Institute,
8 September 2003
Abstract
Over the past decade, semidefinite programming (SDP), i.e., convex
optimization with linear matrix inequality (LMI) constraints, has been
established as a powerful numerical tool in systems and control.
While new applications are still being discovered, research into the
reformulation of systems and control problems as SDP problems has
reached a level of considerable maturity. However, some limitations
of SDP have also become apparent. Most important, the reduction of a
control problem to an SDP problem often requires a large number of
auxiliary variables, so that the resulting SDP problem can be very
large, even though the underlying control problem is not particularly
large-scale. This limits the problem sizes that can be handled by
general-purpose SDP solvers, and hence the applicability of SDP in
practical engineering problems. In order to have an impact on systems
and control practice, future SDP solvers will have to be able to take
advantage of problem structure, without overly restricting their scope
of applicability or sacrificing reliability.
With these observations serving as the backdrop, we discuss efficient
implementations of primal-dual interior-point methods for SDP problems
where the underlying LMIs have a special form that is typically
encountered with the application of the Kalman-Yakubovich-Popov Lemma.
Such LMIs are widely encountered in several systems engineering
applications such as control and signal processing. We show how
orders-of-magnitude savings in computation can be realized with
primal-dual interior-point methods when problem structure is exploited
using straightforward linear algebra techniques.
(This work was performed jointly with L. Vandenberghe of UCLA, and
A. Hansson and R. Wallin of Linkoping University.)
Download Talk PDF
Bibtex entry