Learning to Design Convex Relaxations for Nonconvex Optimization

The gist 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 and then learns a policy that composes symbolic rewrites into problem-specific relaxation trajectories as the formulation evolves.

Motivation

Nonconvex optimization appears throughout science and engineering from signal processing and communications to control, machine learning, and scientific computing Its difficulty comes from nonconvex couplings between variables such as bilinear products, indefinite quadratics, polynomial expressions, or more general nonlinear compositions Convex relaxation handles the difficulty by replacing the nonconvex structure with a tractable convex surrogate that gives a valid bound. A set of relaxation tools has been developed such as McCormick envelopes, moment relaxations, semidefinite relaxations, and branch-and-bound methods based on relaxation This makes relaxation design nontrivial. These choices remain largely manual.

Methodology

The AutoConvexRelax method treats convex relaxation design as a sequence of validity-preserving symbolic transformations. A state is the current symbolic formulation derived from the original nonconvex problem. An action specifies which term to relax and which admissible operator to apply. The key is to give the policy a decision state that preserves the symbolic semantics needed for relaxation design. This representation is a tripartite graph with nodes for variables, symbolic terms, and objective or constraint positions. A Graph Neural Encoder turns this representation into the state used by the policy.

Policy and Actions

The policy selects a target term and then chooses a relaxation operator conditioned on that target. The location head uses graph-level and candidate-term embeddings contextualized by multihead self-attention. The operator head combines the selected token with its domain and structural attributes. Validity is enforced by the action system, which only chooses from admissible actions whose applicability conditions are satisfied at the current formulation state. The policy is trained through solver feedback, where the reward favors tighter lower bounds and penalizes formulation growth from auxiliary variables and constraints.

Theoretical Guarantees

The analysis establishes three complementary guarantees: policy-independent composition validity, unified error propagation across heterogeneous representations, and feasible recovery with an optimality-gap certificate. Proposition 1 (Context-consistent composition) proves that any finite action sequence preserves valid bound semantics under explicit domain, occurrence-context, and representation-consistency conditions. Theorem 1 (Error propagation for mixed representations) derives computable objective and constraint discrepancy bounds by propagating local errors through mixed quadratic and fractional representations. Corollary 1 (Feasible recovery and optimality certification) establishes sufficient conditions for feasible recovery and a global-optimality certification based on the certified lower bound.

Results

Across 241 held-out QCQPs, 15 held-out fractional instances, and application-derived beamforming and sensor network localization problems, the learned policy constructs mixed trajectories that apply McCormick relaxations, semidefinite lifting, QCR, and integrality relaxation to different parts of a formulation. The learned trajectories strengthen lightweight relaxations and approach semidefinite bounds without committing to a full semidefinite construction. The learned trajectories improve the mean lower bound by 21.88% over the Gurobi root relaxation and give tighter bounds on 53.9% of the test instances. The policy adapts its relaxation choices to problem structure, with SDP lifting appearing in all families but its intensity modulated by problem structure. The learned policy transfers beyond standard QCQPs to fractional formulations, confirming that it can operate across symbolic expression classes. It also generalizes to application-derived problems, achieving near-exact performance on beamforming instances and consistently improving relaxation over McCormick for localization instances. The learned trajectories place and sequence relaxation mechanisms to achieve this trade-off, showing that the policy organizes them into a sequential program rather than a static collection of operators.

Conclusion

AutoConvexRelax makes convex relaxation design an executable, learnable construction process. The theoretical analysis establishes policy-independent validity for admissible compositions, unified mixed-error bounds, and sufficient conditions for feasible recovery and optimality certification. Experiments show that learned construction strengthens lightweight relaxations and approaches SDP bounds with smaller formulations. Structure-level and term-level analyses explain how selective placement and sequencing achieve this trade-off. Fractional and application-derived instances demonstrate transfer beyond standard QCQPs. Future work will expand the validity-checked operator library to broader factorable, polynomial, and mixed-integer nonlinear problems. The paper is available at https://github.com/auto4opt/AutoConvexRelax.

References

Anstreicher, K. M., Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming Baltean-Lugojan, R., Bonami, P., Misener, R., & Tramontani, A., Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks [Preprint] Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., & Mahajan, A., Mixedinteger nonlinear optimization Bengio, Y., Lodi, A., & Prouvost, A., Machine learning for combinatorial optimization: A methodological tour d’horizon Billionnet, A., Elloumi, S., & Plateau, M.-C., Improving the performance of standard solvers for quadratic 0–1 programs by a tight convex reformulation: The QCR method Goemans, M. X., & Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming Lasserre, J. B., Global optimization with polynomials and the problem of moments Luo, Z.-Q., Ma, W.-K., So, A. M.-C., Ye, Y., & Zhang, S., Semidefinite relaxation of quadratic optimization problems McCormick, G. P., Computability of global solutions to factorable nonconvex programs: Part I—convex underestimating problems Parrilo, P. A., Semidefinite programming relaxations for semialgebraic problems Paulus, M. B., Zarpellon, G., Krause, A., Charlin, L., & Maddison, C. J., Learning to cut by looking ahead: Cutting plane selection via imitation learning Peng, X., Liu, Y., Cang, Y., Zhang, Y., Wang, X., Deng, S., & Cao, J., NC2C: Automated convexification of generic non-convex optimization problems [Preprint] Sahinidis, N. V., BARON: A general purpose global optimization software package Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O., Proximal policy optimization algorithms [Preprint] Xiong, Z., Zong, F., Ye, H., & Xu, H.

1. The AutoConvexRelax method can be used to learn where to relax, which relaxation to use, and how much formulation growth is worth paying, moving from a fixed handcrafted choice to an automated learning process that adapts to problem structures. This allows AI systems to autonomously construct a relaxation trajectory by choosing target terms and admissible operators based on the current symbolic formulation state.

2. AI systems can generate problem-specific relaxation trajectories that strengthen lightweight relaxations and approach semidefinite bounds without committing to a full semidefinite construction, as demonstrated by the results where learned trajectories achieve a mean lower bound of 3.70% below strengthened semidefinite relaxations on the normalized comparison metric, while it uses substantially smaller formulations.

3. The system can perform structural adaptation by learning how to combine heterogeneous relaxation actions and select them based on problem structure; for example, the policy learns to apply SDP lifting appears in all families, but its intensity is modulated by problem structure, matching the need to handle nonconvex curvature through lifting in concave quadratic objectives.

4. AI systems can achieve policy-independent validity for admissible compositions and derive sufficient conditions for feasible recovery and global-optimality certification through theoretical guarantees like Proposition 1, ensuring that any finite action sequence preserves valid bound semantics, independently of policy quality.

5. The system can generate novel convex surrogates by optimizing a reward function that includes step rewards for convexification progress, structural simplification, and penalizing formulation growth (The step reward is r t = α T [r prog t + r struct t + r dense t] - β Cost]t - ξt).