Interior point methods and software for convex optimization problems with semidefinite and quadratic constraints
Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique42, Avenue Gaspard Coriolis
31057 Toulouse Cedex
Tel : 05 61 19 31 31 - Fax : 05 61 19 30 00
INTERIOR POINT METHODS AND SOFTWARE FOR CONVEX OPTIMIZATION PROBLEMS WITH SEMIDEFINITE AND QUADRATIC CONSTRAINTS
Prof. Michael L. Overton
Courant Institute of Mathematical Sciences New York University, USA
(This is joint work with J.-P Haeberly and M. Nayakkankuppam)
Tuesday June 16, 11.00 a.m. Parallel Algorithms Seminar CERFACS Conference Room
Semidefinite programming (SDP) is an extension of linear programming (LP), with vector variables replaced by block diagonal symmetric matrix variables and nonnegativity constraints replaced by positive semidefinite constraints. Unlike LP, SDP is a nonlinear convex programming problem, because the boundary of the cone of positive semidefinite matrices is nonlinear. Nonetheless, LP and SDP share two key aspects:
Duality theory: most of the theory of duality extends directly from LP to SDP.
Interior-point methods: SDP can be very effectively solved by generalizing interior-point methods developed originally for LP. While the question of superiority of simplex versus interior-point methods for LP remains a controversial question, there is no contest for SDP, because there is no SDP simplex method.
Like LP, SDP has many applications, especially in the field of robust control theory (in this field SDP is known as LMI, for linear matrix inequalities.)
Mixed semidefinite-quadratic-linear programs (SQLP) include convex quadratic and linear constraints as well as semidefinite constraints. We will discuss interior-point algorithms and software for solving SQLP. Our codes use a primal-dual path-following algorithm based on Mehrotra's predictor-corrector method for LP.
Cerfacs' Conferences 1998 Home Page
