The Lasserre hierarchy of semide nite programming approximations to convex polynomial optimization problems is known to converge nitely 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 nite convergence property, under weaker assumptions than were known before. In addition, we show that | under the assumptions for nite convergence | the number of steps needed for convergence depends on more than the input size of the problem.
Additional Metadata
Keywords convex polynomial optimization, sum of squares of polynomials, positivstellensatz, semide nite programming.
THEME Logistics (theme 3)
Publisher S.I.A.M.
Journal SIAM Journal on Optimization
Project Semidefinite programming and combinatorial optimization
Citation
Laurent, M, & de Klerk, E. (2011). On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems. SIAM Journal on Optimization, 21, 824–832.