Convexity in semi-algebraic geometry and polynomial optimization

Jean B. Lasserre (lasserrelaas.fr)

Abstract: We review several (and provide new) results on the theory of moments, sums of squares and basic semi-algebraic sets when convexity is present. In particular, we show that under convexity, the hierarchy of semidefinite relaxations for polynomial optimization simplifies and has finite convergence, a highly desirable feature as convex problems are in principle easier to solve. In addition, if a basic semi-algebraic set $K$ is convex but its defining polynomials are not, we provide a certificate of convexity if a sufficient (and almost necessary) condition is satisfied. This condition can be checked numerically and also provides a new condition for $K$ to have a semidefinite representation. For this we use (and extend) some of recent results from the author and Helton and Nie. Finally, we show that when restricting to a certain class of convex polynomials, the celebrated Jensen's inequality in convex analysis can be extended to linear functionals that are not necessarily probability measures.

Keywords: Convex polynomials; sums of squares; convex sets; Jensen inequality

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: To appear in SIAM J. Optim.

Download: [PDF]

Entry Submitted: 07/02/2008
Entry Accepted: 07/02/2008
Entry Last Modified: 12/04/2008

Modify/Update this entry