Optimization Online


A new look at nonnegativity on closed sets and polynomial optimization

Jean Bernard Lasserre (lasserre***at***laas.fr)

Abstract: We first show that a continuous function "f" is nonnegative on a closed set K if and only if (countably many) moment matrices of some signed measure dnu = fdmu are all positive semidefinite (if K is compact mu is an arbitrary finite Borel measure with support exactly K). In particular, we obtain a convergent explicit hierarchy of semidefinite (outer) approximations with no lifting, of the cone of nonnegative polynomials of degree at most d. Wen used in polynomial optimization on certain simple closed sets K (like e.g., the whole space, the positive orthant, a box, a simplex, or the vertices of the hypercube), it provides a nonincreasing sequence of upper bounds which converges to the global minimum by solving a hierarchy of semidefinite programs with only one variable (in fact, a generalized eigenvalue problem). In the compact case, this convergent sequence of upper bounds complements the convergent sequence of lower bounds obtained by solving a hierarchy of semidefinite relaxations already obtained by the author.

Keywords: closed sets; nonnegative functions; nonnegative polynomials; semidefinite approximations

Category 1: Global Optimization (Theory )

Category 2: Global Optimization (Applications )

Category 3: Nonlinear Optimization

Citation: LAAS-CNRS and Institute of Mathematics, Toulouse, France

Download: [PDF]

Entry Submitted: 04/26/2011
Entry Accepted: 04/26/2011
Entry Last Modified: 04/28/2011

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