arXiv preprint ·
Learning to Design Convex Relaxations for Nonconvex Optimization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
GpFlash: Maximizing Speed and Minimizing Memory for Gaussian Process Training and Prediction
PADO-Pauli: A GPU-Accelerated Implementation of Pauli Propagation
A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization
Separating Statistical Inference from Experimental Runtime: An Architecture for Sequential Scientific Analysis
ArcTN: Efficient Tensor-Network Contraction Planning for Quantum Circuit Simulation
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.