# Polynomial Optimization: Enhancing RLT relaxations with Conic Constraints

arXiv: https://arxiv.org/abs/2208.05608 · HTML: https://mlsanity.com/paper/2208.05608/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 43 references that are in the map.
- First posted on arXiv 11 Aug 2022.

## Builds on (most cited first, 5 of 5)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and R](https://mlsanity.com/paper/1508.04409/) (2015)
- [SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2104.11542/) (2021)
- [Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs](https://mlsanity.com/paper/1802.02688/) (2018)
- [Learning for Spatial Branching: An Algorithm Selection Approach](https://mlsanity.com/paper/2204.10834/) (2022)

## Built on by (most cited first, 1 of 1)

- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)

## Abstract (arXiv)

Conic optimization has recently emerged as a powerful tool for designing tractable and guaranteed algorithms for non-convex polynomial optimization problems. On the one hand, tractability is crucial for efficiently solving large-scale problems and, on the other hand, strong bounds are needed to ensure high quality solutions. In this research, we investigate the strengthening of RLT relaxations of polynomial optimization problems through the addition of nine different types of constraints that are based on linear, second-order cone, and semidefinite programming to solve to optimality the instances of well established test sets of polynomial optimization problems. We describe how to design these conic constraints and their performance with respect to each other and with respect to the standard RLT relaxations. Our first finding is that the different variants of nonlinear constraints (second-order cone and semidefinite) are the best performing ones in around 50% of the instances. Additionally, we present a machine learning approach to decide on the most suitable constraints to add for a given instance. The computational results show that the machine learning approach significantly outperforms each and every one of the nine individual approaches.