arXiv：cs.LG· Jinrun Liu, Bai Yan, Tengfei Liu, Qunfeng Liu, Jian Yang, Shi Cheng, Yuhui Shi, Qi Zhao·· 7 小时前
AutoConvexRelax：用学习自动设计非凸优化的凸松弛
Learning to Design Convex Relaxations for Nonconvex Optimization
AI 导读
论文提出 AutoConvexRelax，将非凸问题的符号表达式表示为变量、符号项及其目标或约束位置构成的三分图，并学习策略把符号重写组合成问题专属的松弛轨迹。
正文
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 this https URL.
| Subjects: | Machine Learning (cs.LG); Mathematical Software (cs.MS) |
| Cite as: | arXiv:2610.16948 [cs.LG] |
| (or arXiv:2610.16948v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.16948 arXiv-issued DOI via DataCite |
Submission history
From: Qi Zhao [view email]
[v1]
Mon, 12 Oct 2026 15:20:24 UTC (1,436 KB)
[v2]
Wed, 14 Oct 2026 09:30:39 UTC (1,434 KB)
来源：arXiv：cs.LG · arxiv.org