Semidefinite Programming Relaxations of Non-Convex Problems in Control and Combinatorial Optimization

S. Boyd and L. Vandenberghe

Chapter 15 of Communications, Computation, Control and Signal Processing: A Tribute to Thomas Kailath, A. Paulraj, V. Roychowdhuri, and C. Schaper, editors, Kluwer, pages 279-288, 1997.

We point out some connections between applications of semidefinite programming in control and in combinatorial optimization. In both fields semidefinite programs arise as convex relaxations of NP-hard quadratic optimization problems. We also show that these relaxations are readily extended to optimization problems over bilinear matrix inequalities.