  


Positive polynomials on unbounded equalityconstrained domains
Javier Pena (jfpandrew.cmu.edu) Abstract: Certificates of nonnegativity are fundamental tools in optimization. A "certificate" is generally understood as an expression that makes the nonnegativity of the function in question evident. Some classical certificates of nonnegativity are Farkas Lemma and the Slemma. The liftandproject procedure can be seen as a certificate of nonnegativity for affine functions over the union of two polyhedra. These certificates of nonnegativity underlie powerful algorithmic techniques for various types of optimization problems. Recently, more elaborate sumofsquares certificates of nonnegativity for higher degree polynomials have been used to obtain powerful numerical techniques for solving polynomial optimization problems, particularly for mixed integer programs and nonconvex binary programs. We present a new certificate of nonnegativity 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 nonnegative polynomials over $S$ and the ideal generated by $h(x)$. Our certificate of nonnegativity 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 nonnegativity, 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  