We present recent results on strong formulations and polyhedral relaxations for mixed-integer nonlinear optimization. First, we address the question of bounding the optimal value of a convex integer program. We derive a novel hierarchy of upper and lower bounds on the optimal value using monomial orders on the integer lattice. Although the approximation factor of these bounds can be as bad as n (number of integer variables), we show that for 0/1 problems, each hierarchy converges to the optimum, yielding a structural characterization with connections to matroid optimization and a new formulation that can be leveraged for generating strong valid inequalities to the integer hull. For mixed-integer programs, our trick of using ordered sets allows us to strengthen split cuts and intersection cuts for separating a solution of the continuous relaxation. A key part of this enhanced computational strength of the cutting planes lies in our ability to describe the combinatorial structure of some polytopes arising from monomial orders.

In the second part, we analyze polyhedral relaxations for nonconvex polynomial optimization. Such problems have deep connections to integer programming, particularly combinatorial optimization. For the question of optimizing a real-valued multivariate polynomial of bounded degree d over [0,1]^n, we give bounds, in terms of degree d, on the additive error (w.r.t. global optimum) of the relaxation obtained by convexifying each monomial separately. Our first-of-its-kind analysis generalizes the small number of results from literature that are primarily for bilinear monomials, and also proves in a sense that for optimizing certain polynomials over a box, the worst case error from semidefinite programming (SDP) is better than that from polyhedral relaxations only if the size of the SDP grows cubic in the degree of the polynomial. For nonconvex square-free (bilinear) quadratic functions over arbitrary polyhedral domains, we give constructive schemes for building extended formulations of the associated convex hull, and identify several cases for which polynomial-sized extensions can be obtained explicitly. We will also highlight the computational impact of our relaxation techniques on an application of widespread interest.

Bio:
Akshay Gupte is an assistant professor of mathematical sciences at Clemson University. He obtained his Ph.D. in operations research from Georgia Insitute of Technology in 2012, where he worked on mixed-integer bilinear programming. His research interests are primarily in theory and algorithms for mixed-integer optimization, with secondary interests in polyhedral combinatorics, discrete mathematics, and more recently, applied algebraic geometry. His research has been funded by federal agencies such as ONR, NSF, and ED, and he has received fellowships and scholarships from Oberwolfach, IMA, and Georgia Tech. He is the Vice-Chair of Integer and Discrete Optimization at the INFORMS Optimization Society, and the main organizer of the 15th Mixed Integer Programming Workshop MIP2018.