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

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 … Read more

Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube

We consider the problem of minimizing a polynomial on the hypercube [0,1]^n and derive new error bounds for the hierarchy of semidefinite programming approximations to this problem corresponding to the Positivstellensatz of Schmuedgen (1991). The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates … Read more

The matricial relaxation of a linear matrix inequality

Given linear matrix inequalities (LMIs) L_1 and L_2, it is natural to ask: (Q1) when does one dominate the other, that is, does L_1(X) PsD imply L_2(X) PsD? (Q2) when do they have the same solution set? Such questions can be NP-hard. This paper describes a natural relaxation of an LMI, based on substituting matrices … Read more

Transposition theorems and qualification-free optimality conditions

New theorems of the alternative for polynomial constraints (based on the Positivstellensatz from real algebraic geometry) and for linear constraints (generalizing the transposition theorems of Motzkin and Tucker) are proved. Based on these, two Karush-John optimality conditions — holding without any constraint qualification — are proved for single- or multi-objective constrained optimization problems. The first … Read more