Learning to automate smarter problem relaxations for faster solutions
Learning to Design Convex Relaxations for Nonconvex Optimization
Machine LearningMathematical Software
Summary
Finding the best way to simplify really hard math problems so they’re easier to solve is usually done by experts manually. This paper shows how a computer can learn to do that automatically by understanding the problem’s structure and choosing the best ways to simplify it step-by-step. Their method helps improve the quality of the simplified problem and keeps the problem size manageable. Testing on various math problems showed the learned approach was often nearly as good as the best manual methods while being more efficient.
What this means in practice
- •For optimization engineers: Use automated convex relaxation design to generate stronger, more efficient problem simplifications for complex quadratic and fractional optimization tasks.
- •For wireless network designers: Improve beamforming and sensor-network localization by applying learned relaxation policies to achieve near-best known bounds with smaller problem formulations.
Authors
Jinrun Liu, Bai Yan, Tengfei Liu, Qunfeng Liu, Jian Yang, Shi Cheng, Yuhui Shi, Qi Zhao
Abstract
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.