Abstract
We discuss fast implementations of primal-dual interior-point methods for semidefinite programs derived from the Kalman-Yakubovich-Popov lemma, a class of problems that are widely encountered in control and signal processing applications. By exploiting problem structure we achieve a reduction of the complexity by several orders of magnitude compared to general-purpose semidefinite programming solvers.
Keywords
Semidefinite programmingInterior point methodLemma (botany)Semidefinite embeddingSecond-order cone programmingComputer sciencePositive-definite matrixDual (grammatical number)Mathematical optimizationClass (philosophy)Point (geometry)MathematicsQuadratically constrained quadratic programQuadratic programmingConvex optimizationArtificial intelligence
Affiliated Institutions
Related Publications
KYPD: a solver for semidefinite programs derived from the Kalman-Yakubovich-Popov lemma
Semidefinite programs derived from the Kalman-Yakubovich-Popov lemma are quite common in control and signal processing applications. The programs are often of high dimension mak...
An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
We present an O(√nL)-iteration homogeneous and self-dual linear programming (LP) algorithm. The algorithm possesses the following features: • It solves the linear programming pr...
Self-Scaled Barriers and Interior-Point Methods for Convex Programming
This paper provides a theoretical foundation for efficient interior-point algorithms for convex programming problems expressed in conic form, when the cone and its associated ba...
On Finding Primal- and Dual-Optimal Bases
We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for on...
A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties
An exact-penalty-function-based scheme---inspired from an old idea due to Mayne and Polak [Math. Program., 11 (1976), pp.67--80]---is proposed for extending to general smooth co...
Publication Info
- Year
- 2004
- Type
- article
- Pages
- 4658-4663
- Citations
- 11
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
11
OpenAlex
Cite This
Lieven Vandenberghe,
V. Balakrishnan,
Ragnar Wallin
et al.
(2004).
On the implementation of primal-dual interior-point methods for semidefinite programming problems derived from the KYP lemma.
, 4658-4663.
https://doi.org/10.1109/cdc.2003.1272303
Identifiers
- DOI
- 10.1109/cdc.2003.1272303