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.
Citation
Working paper, Tepper School of Business, Carnegie Mellon University