Integer programming techniques for Polynomial Optimization

Modern problems arising in many domains are driving a need for more capable, state-of-the-art optimization tools. A sharp focus on performance and accuracy has appeared, for example, in science and engineering applications. In particular, we have seen a growth in studies related to Polynomial Optimization: a field with beautiful and deep theory, offering flexibility for modeling and high impact in diverse areas. The understanding of structural aspects of the feasible sets in Polynomial Optimization, mainly studied in Real Algebraic Geometry, has a long tradition in Mathematics and it has recently acquired increased computational maturity, opening the gate for new Optimization methodologies to be developed. The celebrated hierarchies due to Lasserre, for example, emerged as good algorithmic templates. They allow the representation of semi-algebraic sets, possibly non-convex, through convex sets in lifted spaces, thus enabling the use of long-studied Convex Optimization methods. Nonetheless, there are some computational drawbacks for these approaches: they often rely on possibly large semidefinite programs, and due to scalability and numerical issues associated with SDPs, alternatives and complements are arising. In this dissertation, we will explore theoretical and practical Integer-Programming-based techniques for Polynomial Optimization problems. We first present a Linear Programming relaxation for the AC-OPF problem in Power Systems, a non-convex quadratic problem, and show how such relaxation can be used to develop a tractable MIP-based algorithm for the AC Transmission Switching problem. From a more theoretical perspective, and motivated by the AC-OPF problem, we study how sparsity can be exploited as a tool for analysis of the fundamental complexity of a Polynomial Optimization problem, by showing LP formulations that can efficiently approximate sparse polynomial problems. Finally, we show a computationally practical approach for constructing strong LP approximations on-the-fly, using cutting plane approaches. We will show two different frameworks that can generate cutting planes, which are based on classical methods used in Mixed-Integer Programming. Our methods mainly rely on the maturity of current MIP technology; we believe these contributions are important for the development of manageable approaches to general Polynomial Optimization problems