Learning to Design Convex Relaxations for Nonconvex Optimization
Authors: Jinrun Liu, Bai Yan, Tengfei Liu, Qunfeng Liu, Jian Yang, Shi Cheng, Yuhui Shi, Qi Zhao
Organizations: Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China · School of Computer Science and Technology, Dongguan University of Technology, Dongguan 523808, China · School of Artificial Intelligence and Computer Science, Shaanxi Normal University, Xi’an 710119, China
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.
Figures & tables
Figure 1: Overview of the AutoConvexRelax method proposed in this paper. A symbolic nonconvex problem is encoded as a tripartite graph. A factorized policy selects a relaxation location and an admissible relaxation operator. The resulting valid transformations construct a convex surrogate whose bound quality and formulation cost are evaluated by a solver.
Figure 2: Augmented tripartite graph representation of a symbolic formulation. Variable, term, and objective/constraint-position nodes encode the structural dependencies used for relaxation decisions.
Finite bounds; correct direction at every changed occurrence
Bound tightening
Propagate implied bounds
Supported affine or positive square-sum constraints
Table 1: Action library and main applicability conditions. Full validity conditions are given in Appendix B.2 .
Solver root relaxation
Lower-bound improvement (%)
Tighter / Tie / Weaker (%)
Gurobi
+21.88
53.9 / 29.5 / 16.6
SCIP
+15.37
48.5 / 14.0 / 37.4
Table 2: Bound improvement of learned trajectories over solver root relaxations. The reported lower-bound improvements are computed as instance-wise normalized differences and averaged over 241 held-out instances. Tighter/tie/weaker reports the fraction of instances on which the learned trajectory gives a tighter, equal, or weaker lower bound than the corresponding solver root relaxation.
Figure 3: a , Pairwise comparison with Gurobi and SCIP root relaxations. Each bar reports the percentage of test instances on which the learned relaxation gives a tighter, equal, or weaker lower bound than the corresponding solver root relaxation. b , Ranked lower-bound improvement over solver root relaxations. Test instances are sorted by the percentage improvement of the learned lower bound over the corresponding solver root bound. Positive values indicate tighter learned relaxations.
Reference & baseline relaxation
Lower-bound improvement (%)
Tighter / Tie / Weaker (%)
Δ Vars (%)
Δ Cons (%)
Δ NNZ (%)
McCormick
+13.52
47.3 / 44.4 / 8.3
+190.97
+274.88
+252.71
SDP
-3.70
1.2 / 74.3 / 24.5
-34.90
-29.52
-28.79
Random
+17.68
68.5 / 27.4 / 4.1
+112.87
+211.42
+191.06
Heuristic
+13.80
49.8 / 43.6 / 6.6
+190.97
+310.32
+272.61
Table 3: Bound quality and formulation growth of learned trajectories over reference and baseline relaxations. Δ Vars, Δ Cons, and Δ NNZ are formulation-growth metrics. They report relative changes in the numbers of variables, constraints, and nonzeros of the learned formulation with respect to the reference formulation. Positive values indicate a larger learned formulation; negative values indicate smaller.
Figure 4: Relaxation action composition in learned trajectories across QCQP structural families. Only accepted actions that changed the formulation are counted.
Instance
Root LB
AutoConvexRelax LB
McC. LB
SDP LB
H_MIXED_5 _n3_4_615
−29.73
−11.60
−29.73
−11.30
E_EXP_P3 _n4_945
−246.44
−34.28
−35.06
−34.28
H_MIXED_1 _n4_929
−84.40
−84.82
−85.65
−84.40
Table 4: Lower bounds of held-out instances for term-level trajectory inspection. Root LB, AutoConvexRelax LB, McC. LB, and SDP LB are short for lower bounds of solver root relaxation, learned trajectory, McCormick, and SDP, respectively.
Reference & baseline relaxation
Lower-bound improvement (%)
Tighter / Tie / Weaker (%)
Δ Vars (%)
Δ Cons (%)
Δ NNZ (%)
McCormick
+11.11
53.3 / 46.7 / 0.0
+8.82
+10.13
+3.83
SDP
-7.52
0.0 / 46.7 / 53.3
-28.32
-21.89
-20.74
Random
+9.05
33.3 / 46.7 / 20.0
+9.37
+24.25
+23.81
Heuristic
+11.11
53.3 / 46.7 / 0.0
+8.82
+10.13
+3.83
Table 5: Bound quality and formulation growth of learned trajectories over reference and baseline relaxations on 15 held-out nonconvex fractional instances.
Inst.
Reference
AutoConvexRelax
McCormick
SDP
AutoConvexRelax gap
B1
8.57
8.57
8.58
8.57
3.38×10−6
B2
2.76
2.76
3.23
2.76
3.68×10−5
B3
1.35
1.35
1.35
1.35
1.02×10−6
B4
0.34
0.34
0.34
0.34
2.91×10−6
S1
6.99
6.81
6.25
6.81
2.71×10−2
S2
7.00
6.86
6.23
6.86
2.00×10−2
Table 6: Bound quality on application-derived QCQPs. B1–B4 are the maximization beamforming instances; the reported values are upper bounds. S1–S4 are the minimization localization instances; the reported values are lower bounds. Reference values are the best objective values returned by the solvers; AutoConvexRelax values are convex surrogate objectives induced by the learned policy; AutoConvexRelax gap reports the relative error to the reference.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Component
Configuration
Message-passing layers
2
Graph hidden dimension
512
Unprojected pooled dimension
3×512=1536
Node / global readout
512→256 / 1536→256
Policy-token dimension
256
Graph pooling
Type-wise mean pooling
Appendix
Table F.1: Encoder and policy architecture settings.
Setting
Value
Setting
Value
Optimizer
Adam
Learning rate / epsilon
10−4 / 10−8
Discount factor γ
0.99
PPO clip ratio ϵ
0.15
Value loss / clipping
0.5 / 0.2
Entropy coefficient
0.03 , then 0.02→0.005
PPO epochs / minibatch
1 / 128
Problems per update
32
Rollout steps / problem
16
Maximum gradient norm
0.5
Training / post-convex horizon
20 / 4
Progress signal
1 / −0.1
Appendix
Table F.2: Policy optimization and implementation settings.
Figure H.1: Structure-dependent root-bound improvement of learned trajectories. Points denote the mean improvement over the Gurobi root relaxation within each QCQP structural family; error bars are computed over random seeds.
Figure H.2: Bound–cost trade-off of learned trajectories. Each point represents a held-out instance averaged over converged random seeds. The horizontal axis reports added nonzeros as a proxy for formulation growth on a logarithmic scale; the vertical axis reports root-bound improvement over the Gurobi root relaxation. Colors indicate QCQP structural families.
Instance
Step
Target term or structure
Operator
Rewrite and role
H_MIXED_5 _n3_4_615
1
diagonal term x⊤Qxx
McCormick
x⊤Qxx↦∑iqiwxixi ; envelope relaxation of the diagonal quadratic term
2
dense term y⊤Qyy
SDP
y⊤Qyy↦Tr(QyZy) ; matrix lifting for the dense quadratic term
E_EXP_P3 _n4_945
1
binary term b∈{0,1}4
RelaxIntegrality
b∈{0,1}4↦b∈[0,1]4 ; domain relaxation before lifting
2
bilinear coupling 2b⊤Ax
McCormick
2b⊤Ax↦⟨C,wbx⟩ ; envelope relaxation of binary–continuous coupling
3
concave quadratic −0.4375∥x∥22
SDP
−0.4375∥x∥22↦−0.4375Tr(Zx) ; lifting of the remaining concave quadratic term
H_MIXED_1 _n4_929
1
diagonal bilinear term 2x⊤Dy
McCormick
2x⊤Dy↦∑i2diwxiyi ; envelope relaxation of cross-variable coupling
Appendix
Table I.1: Relaxation trajectories produced by the policy. The trajectories are reported as decision-level summary of the target term, relaxation operator, and rewrite role. Full algebraic rewrites are provided in Appendix I .
The Alternating Direction Method of Multipliers (ADMM) is a widely used method for structured convex optimization, and its practical performance depends strongly on the choice of penalty and relaxation parameters. Motivated by settings such as Model Predictive Control (MPC), where one repeatedly solves related optimization problems with fixed structure and changing parameter values, we propose learning online updates of the relaxation parameter to improve average performance on problem classes of interest, while guaranteeing that asymptotic convergence is not compromised for the worst-case realization of such problems. This choice is computationally attractive in the Operator Splitting Quadratic Program (OSQP)-like architectures, since adapting relaxation does not trigger the matrix refactorizations associated with penalty updates. We establish convergence guarantees for ADMM with time-varying penalty and relaxation parameters under mild assumptions, and show on benchmark quadratic programs that the resulting learned policies improve both iteration count and wall-clock time on average over baseline OSQP.
Junan Lin, Paul J. Goulart, Luca Furieri
Department of Engineering Science, University of Oxford, OX1 3PJ Oxford, UK
Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighter relaxations giving stronger bounds. We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by \citet{tao2025alphaevolve} - the first autocorrelation inequality (C6.2) and the Erdős minimum-overlap constant (C6.5) - we improve the certified lower bounds from 1.28 to 1.2937 and from 0.379005 to 0.37912, respectively.
Sungyoon Kim, Mert Pilanci
Department of Electrical Engineering, Stanford University, CA, USA.
This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at KKT stationary points. Leveraging a unified game-theoretic interpretation of eight classical algorithm families--including block coordinate descent, ADMM, generalized Benders decomposition, successive convex approximation, interior-point methods, mirror descent, Frank-Wolfe, and Riemannian gradient descent--we show that the normalized multiplier vector carries an algorithm-independent structural fingerprint. Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid. We establish four structural theorems characterizing the partition: invariance under natural KKT symmetries, local stability under data perturbation with explicit Lipschitz margins from Robinson's strong regularity, codimension-one regime transitions, and the topological identification of the Hybrid regime as the Lebesgue-null boundary of the core regimes. A linear-time classifier is proposed with provable guarantees on correctness, iteration stabilization, sample complexity, and online tracking under data drift. Numerical experiments on 104 mixed-integer nonlinear programs and a downlink beamforming instance validate the theoretical predictions. The framework provides a foundational tool for regime-aware algorithm design and robustness analysis in non-convex optimization.
Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabi
Department of Computer Engineering, Sharif University of Technology, Azadi, Tehran, 11365-9517, Tehran, Iran.