Optimization Online


Positive polynomials on unbounded equality-constrained domains

Javier Pena (jfp***at***andrew.cmu.edu)
Juan Vera (j.c.veralizcano***at***uvt.nl)
Luis Zuluaga (lzuluaga***at***unb.ca)

Abstract: Certificates of non-negativity are fundamental tools in optimization. A "certificate" is generally understood as an expression that makes the non-negativity of the function in question evident. Some classical certificates of non-negativity are Farkas Lemma and the S-lemma. The lift-and-project procedure can be seen as a certificate of non-negativity for affine functions over the union of two polyhedra. These certificates of non-negativity underlie powerful algorithmic techniques for various types of optimization problems. Recently, more elaborate sum-of-squares certificates of non-negativity for higher degree polynomials have been used to obtain powerful numerical techniques for solving polynomial optimization problems, particularly for mixed integer programs and non-convex binary programs. We present a new certificate of non-negativity for polynomials over the intersection of a closed set $S$ and the zero set of a given polynomial $h(x)$. The certificate is written in terms of the set of non-negative polynomials over $S$ and the ideal generated by $h(x)$. Our certificate of non-negativity yields a copositive programming reformulation for a very general class of polynomial optimization problems. This copositive programming formulation generalizes Burer's copositive formulation for binary programming and offers an avenue for the development of new algorithms to solve polynomial optimization problems. In particular, the copositive formulation could be used to obtain new semidefinite programming relaxations for binary programs, as our approach is different and complementary to the conventional approaches to obtain semidefinite programming relaxations via matrix relaxations.

Keywords: positive polynomials, certificates of non-negativity, copositive programming

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: Working paper, Tepper School of Business, Carnegie Mellon University

Download: [PDF]

Entry Submitted: 05/31/2011
Entry Accepted: 05/31/2011
Entry Last Modified: 06/01/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