Applications of semidefinite programming

✍ Scribed by Lieven Vandenberghe; Stephen Boyd

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 871 KB
• Volume: 29
• Category: Article
• ISSN: 0168-9274
• DOI: 10.1016/s0168-9274(98)00098-1

✦ Synopsis

A wide variety of nonlinear convex optimization problems can be cast as problems involving linear matrix inequalities (LMIs), and hence efficiently solved using recently developed interior-point methods. In this paper, we will consider two classes of optimization problems with LMI constraints:

(1) The semidefinite programming problem, i.e., the problem of minimizing a linear function subject to a linear matrix inequality. Semidefinite programming is an important numerical tool for analysis and synthesis in systems and control theory. It has also been recognized in combinatorial optimization as a valuable technique for obtaining bounds on the solution of NP-hard problems.

(2) The problem of maximizing the determinant of a positive defnite matrix subject to linear matrix inequalities. This problem has applications in computational geometry, experiment design, information and communication theory, and other fields.

We review some of these applications, including some interesting applications that are less well known and arise in statistics, optimal experiment design and VLSI.