Structural Properties and Strong Relaxations for Mixed Integer Polynomial Optimization

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Research in mixed-integer nonlinear optimization has witnessed a significant growth at the theoretical, algorithmic and software levels over the last few years. While these new classes of algorithms have already had a remarkable impact across science, engineering, and economics, there exists a variety of important applications that these methods are unable to address. Compared to linear and convex nonlinear solvers, mixed-integer nonlinear solvers are very slow, cannot handle large-scale problems, and require a high level of user expertise. In fact, many optimization experts believe that in case of nonconvex nonlinear problems, one has to give up on either speed or the guarantee of solution quality. This project aims to address this trade-off, by developing foundational theory to construct strong and tractable polyhedral relaxations for a variety of nonconvex sets that frequently appear as building blocks of nonconvex mixed-integer nonlinear optimization problems. Successful resolution of the research goals of this project will potentially transform solver technology for mixed-integer nonlinear optimization problems; a very powerful framework that subsumes many real-world optimization problems. The project addresses the educational and outreach activities through graduate student mentoring, integration of research results in course work, and broad dissemination of the results of the research. Factorable programming is a widely-used technique for bounding general nonconvex functions. In particular, factorable reformulations of many nonconvex problems, including quadratic programs, multilinear programs, and polynomial optimization problems, contain a collection of multilinear equations. A main focus of this research is to study the facial structure of the convex hull of a set defined by a system of multilinear equations in the space of the original variables. Through an elegant hypergraph-based representation scheme, various structural properties, decomposition techniques, and lifting operations for such sets will be studied. A rigorous study of the strength and complexity of the relaxations will be performed, and new classes of polynomially-solvable optimization problems will be presented.