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.
Entry Submitted: 07/02/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|