LMI approximations for cones of positive semidefinite forms

Luis Zuluaga (lzuluagaandrew.cmu.edu)
Juan Vera (jveraandrew.cmu.edu)
Javier Pena (jfpandrew.cmu.edu)

Abstract: An interesting recent trend in optimization is the application of semidefinite programming techniques to new classes of optimization problems. In particular, this trend has been successful in showing that under suitable circumstances, polynomial optimization problems can be approximated via a sequence of semidefinite programs. Similar ideas apply to conic optimization over the cone of copositive matrices, and to certain optimization problems involving random variables with some known moment information. In this paper we address the approximability of cones of positive semidefinite forms (homogeneous polynomials). This perspective allows us to extract some key common ideas underlying the approximations mentioned above. At the same time, our approach suggests natural new approximation schemes. In particular, we show that for several interesting cones of positive semidefinite forms it is possible to construct polyhedral approximations, which opens the possibility of using linear programming technology in optimization problems over these cones.

Keywords: polynomial optimization, semidefinite programming, copositive cone

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: SIAM Journal on Optimization 16 (2006) pp. 796--817

Download:

Entry Submitted: 05/09/2003
Entry Accepted: 05/09/2003
Entry Last Modified: 05/07/2006

Modify/Update this entry