Convex Relaxation

Latest papers

12 papers2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Learning to Design Convex Relaxations for Nonconvex Optimization
Oct 12, 2026Jinrun Liu, Bai Yan, Tengfei Liu +5Convex Relaxation Nonconvex Optimization
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
Certified Robustness via Sparse Second-Order Cone Relaxations
Oct 12, 2026Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma +3Convex Relaxation Neural Network Verification
Toronto Metropolitan University · University of Minnesota Twin Cities · Johns Hopkins University +2
Input convex neural networks as surrogates in mathematical optimisation
Aug 10, 2026Yu Liu, Jan Kronqvist, Fabricio OliveiraSurrogate-Assisted Optimization Mixed-Integer Linear Programming
Department of Mathematics and Systems Analysis, School of Science, Aalto University, Espoo, Finland · Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden · DTU Management, Technical University of Denmark, Lyngby, Denmark
AI-Assisted Discovery of Convex Relaxations via Dual Agents
Jun 30, 2026Sungyoon Kim, Mert PilanciPrimal-Dual Optimization Convex Relaxation
Department of Electrical Engineering, Stanford University, CA, USA.
Phase Transition in Convex Relaxations for Graph Alignment
Jun 14, 2026Laurent Massoulié, Sushil Mahavir Varma, Louis Vassaux +1Convex Relaxation Phase Transitions
INRIA, DI/ENS, PSL Research University, Paris, France · Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan, USA. · CNRS, INRIA, Universit´e Paris Dauphine, Paris, France
DisjunctiveNet: Neural Symbolic Learning via Differentiable Convexified Optimization Layers
May 28, 2026Shraman Pal, Can LiConvex Relaxation Differentiable Optimization
Davidson School of Chemical Engineering, Purdue University, West Lafayette, USA.
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
May 8, 2026Hao Chen, Chendi Qian, Christopher Morris +2Max-Cut Semidefinite Programming
1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech
Denoising data using convex relaxations
May 4, 2026Charles Fefferman, Aalok Gangopadhyay, Matti Lassas +2Convex Relaxation Cryo-Electron Microscopy
Department of Mathematics, Princeton University, Princeton, NJ 08544, USA. · TCS Research · Department of Mathematics and Statistics, University of Helsinki, FI-00014 Helsinki, Finland. +2
The Cost of Relaxation: Evaluating the Error in Convex Neural Network Verification
Apr 20, 2026Merkouris Papamichail, Konstantinos Varsos, Giorgos Flouris +1Neural Network Verification Certified Robustness
Foundation for Research and Technology – Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1
Advances in Global Solvers for 3D Vision
Feb 16, 2026Zhenjun Zhao, Heng Yang, Bangyan Liao +7Convex Relaxation Global Optimization
University of Zaragoza, Zaragoza, Spain. · Harvard University, Cambridge, MA, USA. · Westlake University, Hangzhou, China. +3
Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming
Jan 7, 2026Valentine Olanubi, Phineas Agar, Brendan AmesConvex Relaxation Stochastic Block Model
University of Alabama, Department of Mathematics · Department of Mathematics, University of Alabama, Tuscaloosa, AL, USA · University of Southampton, School of Mathematical Sciences +1
A global optimization SAR image segmentation model can be easily transformed to a general ROF denoising model
Dec 8, 2023Guangming LiuImage Segmentation Convex Relaxation
Yantai Science and Technology Association

Oct 12, 2026J/K move · Enter open · S save

Learning to Design Convex Relaxations for Nonconvex Optimization

Jinrun Liu, Bai Yan, Tengfei Liu, Qunfeng Liu+4

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 Relaxation Nonconvex Optimization Learning to Optimize Constrained Optimization

Open paper AskPDF arXiv

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.