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. Recently, Polynomial Optimization has acquired increased computational maturity; the celebrated hierarchies due to Lasserre, for example, emerged as good computational templates. These hierarchies often rely on possibly large semidefinite programs; and due to scalability and numerical issues associated to SDPs, alternatives are arising.

In this talk we will explore theoretical and practical LP-based techniques for polynomial optimization problems. Motivated by the AC-OPF problem in Power Systems, we will review how sparsity can be exploited as a tool for analysis of the fundamental complexity of the problem, by showing LP formulations that can efficiently approximate sparse problems. In addition, we will show a computationally practical approach for constructing such approximations on-the-fly. Our methods rely on the maturity of current LP technology; we believe these contributions are important for the development of manageable approaches to general polynomial optimization problems.