# Learning to Design Convex Relaxations for Nonconvex Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 12 Oct 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Hybrid Beamforming for Reconfigurable Intelligent Surface based Multi-user Communications: Achievable Rates with Limited Discrete Phase Shifts](https://mlsanity.com/paper/1910.14328/) (2019)
- [NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs](https://mlsanity.com/paper/2410.03720/) (2024)
- [NC2C: Automated Convexification of Generic Non-Convex Optimization Problems](https://mlsanity.com/paper/2601.04789/) (2026)
- [AI-Assisted Discovery of Convex Relaxations via Dual Agents](https://mlsanity.com/paper/2606.31182/) (2026)
- [Learning to Relax Nonconvex Quadratically Constrained Quadratic Programs](https://mlsanity.com/paper/2501.03954/) (2025)
- [Learn to Relax with Large Language Models: Solving Constraint Optimization Problems via Bidirectional Coevolution](https://mlsanity.com/paper/2509.12643/) (2025)

## Abstract (arXiv)

Convex relaxations make nonconvex optimization tractable by replacing hard nonconvex problems with convex surrogates that give valid bounds. Yet their design is still largely manual: a human expert must decide where to relax, which relaxation to use, and how much formulation growth is worth paying. We show that this design process can be learned. The method proposed in this paper, AutoConvexRelax, represents the symbolic formulation of a nonconvex problem as a tripartite graph linking variables, symbolic terms, and their objective or constraint positions. It then learns a policy that composes symbolic rewrites into problem-specific relaxation trajectories as the formulation evolves. We prove that finite action sequences generated by the learned policy preserve relaxation validity under explicit domain, occurrence-context, and representation-consistency conditions. We further establish computable error bounds for mixed relaxations and sufficient conditions for feasible recovery and global-optimality certification. As a first instantiation, we apply the method to nonconvex quadratic problems and fractional problems. On 241 benchmark quadratic instances, the learned policy strengthens McCormick lower bounds by 13.52%. Its mean lower bound is 3.70% below strengthened semidefinite relaxations on the normalized comparison metric, while it uses substantially smaller formulations. The learned policy retains this trade-off on fractional instances and reaches near-semidefinite bounds on beamforming and sensor-network localization instances. These results suggest that convex relaxation design can move from a fixed handcrafted choice to an automated learning process that adapts to problem structures. Code is available at https://github.com/auto4opt/AutoConvexRelax.