Optimization Online


On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems

Etienne De Klerk (e.deklerk***at***uvt.nl)
Monique Laurent (m.laurent***at***cwi.nl)

Abstract: The Lasserre hierarchy of semidefinite programming approximations to convex polynomial optimization problems is known to converge finitely under some assumptions. [J.B. Lasserre. Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19, 1995-2014, 2009.] We give a new proof of the finite convergence property, that does not require the assumption that the Hessian of the objective be positive definite on the entire feasible set, but only at the optimal solution. In addition, we show that the number of steps needed for convergence depends on more than the input size of the problem. In particular, the size of the semidefinite program that gives the exact reformulation of the convex polynomial optimization problem may be exponential in the input size.

Keywords: convex polynomial optimization, sum of squares of polynomials, positivstellensatz, semidefinite programming

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: Manuscript, Tilburg University, The Netherlands, November 2010 SIAM J. Optimization, to appear.

Download: [PDF]

Entry Submitted: 11/07/2010
Entry Accepted: 11/08/2010
Entry Last Modified: 06/06/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society