A survey of the S-lemma

Imre Pólik (imre.polikgmail.com)
Tamás Terlaky (terlakymcmaster.ca)

Abstract: In this survey we review the many faces of the S-lemma, a result about the correctness of the S-procedure. The basic idea of this widely used method came from control theory but it has important consequences in quadratic and semidefinite optimization, convex geometry and linear algebra as well. These were active research areas, but as there was little interaction between researchers, their results remained mainly isolated. Here we give a unified analysis of the theory by providing three different proofs for the S-lemma and revealing hidden connections with various areas of mathematics. We prove some new duality results and present applications from control theory, error estimation and computational geometry.

Keywords: S-lemma, S-procedure, control theory, nonconvex theorem of alternatives, numerical range, relaxation theory, semidefinite optimization, generalized convexities

Category 1: Nonlinear Optimization (Other )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Category 3: Applications -- Science and Engineering (Control Applications )

Citation: SIAM Review, 49 (2007), pp. ?-?.

Download:

Entry Submitted: 10/04/2004
Entry Accepted: 10/04/2004
Entry Last Modified: 07/17/2007

Modify/Update this entry