Optimization Online


Convexity in semi-algebraic geometry and polynomial optimization

Jean B. Lasserre (lasserre***at***laas.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

  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 Programming Society