Research in nonconvex nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) 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 exist a variety of important applications that these methods are unable to address. Compared to liner programming and convex NLP solvers, global 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 NLPs and MINLPs. 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 proposed relaxations will be performed, and new classes of polynomially solvable optimization problems will be presented.
The proposed convexification techniques will provide sharper polyhedral relaxations for mixed-integer nonlinear optimization problems containing multilinear components. Polynomial time separation algorithms for the proposed cutting planes will be developed and their impact on the overall computational cost of branch-and-cut based algorithms will be investigated. The code containing the implementation of the proposed algorithms will be made freely available to academics and the cut generation algorithms will be incorporated into widely-used open-source global solvers.
(This project is led jointly with Aida Khajavirad at UT-Austin)
