Semidefinite Programming

Also known as SDP

Semidefinite programming optimizes over positive semidefinite matrices, providing a way to solve convex problems and to approximate difficult discrete or nonconvex ones with bounds and certificates. Common approaches include SDP relaxations for tasks such as MAXCUT, clustering, state estimation, and motion planning, alongside low-rank methods, chordal sparsity, and first-order or ADMM solvers. Recent work also uses differentiable optimization layers and learned warm starts to bring SDP-based methods into neural-network verification, control, and real-time robotics. The central tension is improving scalability without sacrificing tight bounds or reliable global certificates, especially when problems are large, sparse, or degenerate.

Latest papers

21 papers3 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Sparse Sum-of-Squares Layers for Certified Learning
Oct 25, 2026Ege Gursoy, Nicolas MansardSemidefinite Programming Differentiable Optimization
LAAS-CNRS · ANITI
Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares
Oct 18, 2026Yuxiang Zhao, Ting GanConstrained Optimization Semidefinite Programming
School of Computer Science, Wuhan University, Wuhan, China
Towards Certifiable State Estimation under Observability Degeneracy
Oct 14, 2026Baoshan SongRobot State Estimation Semidefinite Programming
Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration
Sep 2, 2026Connor Holmes, Abhishek Goudar, Timothy D. BarfootSemidefinite Programming Point Cloud Registration
University of Toronto Robotics Institute, University of Toronto, Toronto, Ontario, Canada
$(\text{DNN})^2$ : Doubly Non-Negative Relaxations for Deep Neural Networks
Aug 25, 2026Hanna Jiamei Zhang, Alan Papalia, Michael Everett +1Neural Network Verification ReLU Neural Networks
Departments of Computer Science, Electrical and Computer Engineering, and Mathematics Northeastern University, Boston, MA. · Department of Naval Architecture and Marine Engineering, University of Michigan, Ann Arbor, MI.
Semidefinite Relaxations for Collision-Free Motion Planning
Jun 12, 2026Bernhard Paus Graesdal, Alexandre Amice, Pablo A. Parrilo +1Semidefinite Programming Constrained Motion Planning
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA.
Scalable Deep Unfolding of Conic Optimizers
Jun 11, 2026Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. TheodorouSemidefinite Programming Implicit Differentiation
Georgia Institute of Technology
Conditioned free-energy density of proteins using unbalanced solutions to constraint satisfaction problems
May 31, 2026Pratik Worah, Subhash Khot, Srinivasa VaradhanFree Energy Calculation Semidefinite Programming
Exploiting Chordal Sparsity for Globally Optimal Estimation with Factor Graphs
May 28, 2026Avinash Subramanian, Connor Holmes, Timothy D. Barfoot +2Semidefinite Programming Factor Graph Optimization
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA · Robotics Institute, University of Toronto, Toronto, ON, Canada · Department of Mechanical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA
TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics
May 13, 2026Ishaan Mahajan, Jon Arrizabalaga, Andrea Grillo +4Semidefinite Programming Constrained Motion Planning
Columbia University, USA · Massachusetts Institute of Technology, USA · ´Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Switzerland +1
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
Globally Solving Unbalanced Optimal Transport and Density Control for Gaussian Distributions
May 5, 2026Haruto Nakashima, Siddhartha Ganguly, Kenji KashimaSemidefinite Programming Stochastic Optimal Control
The Applied Mathematics and Physics Department, Graduate School of Informatics, Kyoto University, Kyoto, Japan · Daniel Guggenheim School of Aerospace, Georgia Institute of Technology, Atlanta, USA
On the Expressive Power of GNNs to Solve Linear SDPs
Apr 30, 2026Chendi Qian, Christopher MorrisSemidefinite Programming Graph Neural Networks
Faculty of Computer Science, RWTH Aachen University, Germany
LMI-Net: Linear Matrix Inequality--Constrained Neural Networks via Differentiable Projection Layers
Apr 7, 2026Sunbochen Tang, Andrea Goertzen, Navid AzizanConstrained Optimization Differentiable Optimization
Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA 02139, USA
Demystifying Lipschitz verification: positive matrices, negative results
Mar 30, 2026Simon Kuang, Yuezhu Xu, S. Sivaranjani +1Neural Network Verification Lipschitz Neural Networks
Department of Mechanical and Aerospace Engineering University of California, Davis · Edwardson School of Industrial Engineering Purdue University
Compact Lifted Relaxations for Low-Rank Optimization
Mar 5, 2026Ryan Cory-Wright, Jean PauphiletSemidefinite Programming Nonconvex Optimization
Department of Analytics, Marketing and Operations, Imperial Business School, London, UK · Management Science and Operations, London Business School, London, UK
Fermi-Dirac thermal measurements: A framework for quantum hypothesis testing and semidefinite optimization
Mar 4, 2026Nana Liu, Mark M. WildeQuantum Machine Learning Semidefinite Programming
Institute of Natural Sciences, School of Mathematical Sciences, Ministry of Education Key Laboratory in Scientific and Engineering Computing, and Global College, Shanghai Jiao Tong University, Shanghai 200240, China · School of Electrical and Computer Engineering, Cornell University, Ithaca, New York 14850, USA
Semidefinite Programming for Quantum Channel Learning
Jan 18, 2026Mikhail Gennadievich Belov, Victor Victorovich Dubov, Vadim Konstantinovich Ivanov +3Semidefinite Programming Quantum Machine Learning
Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, GSP-1, Moscow, Vorob’evy Gory, 119991, Russia and Autretech Group, Skolkovo Innovation Center, Nobel Street, Building 7, Moscow, 121205, Russia · Peter the Great St. Petersburg Polytechnic University, 195251, Russia · Ioffe Institute, Politekhnicheskaya 26, St Petersburg, 194021, Russia
Mixtures Closest to a Given Measure: A Semidefinite Programming Approach
Sep 26, 2025Srećko Đurašinović, Jean-Bernard Lasserre, Victor MagronSemidefinite Programming Data Mixture Optimization
College of Computing and Data Science, NTU, Singapore · LAAS-CNRS, Toulouse, France · Toulouse School of Economics +1
Initialization-Free LEO Doppler Positioning via Semidefinite Relaxation: A Cold-Start Approach
Sep 21, 2025Baoshan Song, Weisong Wen, Qi Zhang +4Wireless Localization GNSS-Denied Localization
The Hong Kong Polytechnic University, Hong Kong SAR, China
Semidefinite programming relaxations and debiasing for MAXCUT-based clustering
Jan 16, 2024Shuheng ZhouSemidefinite Programming Unsupervised Clustering
University of California, Riverside, CA 92521

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

Sparse Sum-of-Squares Layers for Certified Learning

Ege Gursoy, Nicolas Mansard

LAAS-CNRS · ANITI

Semidefinite Programming Differentiable Optimization Neural Network Verification

Open paper AskPDF arXiv

A central limitation of modern machine learning systems is the lack of formal certificates guaranteeing their behavior beyond empirical, sample-based evaluation. Sum-of-squares (SOS) methods provide such guarantees by certifying polynomial inequalities over continuous domains via semidefinite programming (SDP). While prior work has introduced SDP layers as differentiable components in neural networks, repeated learning calls can lose the computational benefit of the forward program's sparse representation. We propose Sparse SOS Layers, differentiable value layers whose backward passes reuse the local coordinates of the forward solve. Under a fixed template and learned objective coefficients, each layer avoids building dense certificates and reuses its sparse structure across training steps. Compared with existing methods, our approach achieves up to 2.7 times speedup in total warm-call time, with nearly 100 times lower memory usage (1.7 vs. 160 GiB) for relatively large problem sizes for the tested dense parameterization. Experiments cover sparse polynomial certification, pendulum control, combinatorial relaxations, robotics projection, oscillator chains, and pose graph synchronization. A design study achieves zero certified violations across unseen problem instances and sizes, while requiring roughly 7 times fewer optimization solves than estimating gradients by perturbing the objective coefficients and re-solving the problem (finite differences). These results show that sparse certificate values can be effectively integrated into learning pipelines when the backward pass respects the verifier's structure.