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.
Citation
SIAM Journal on Optimization 16 (2006) pp. 796--817