Semidefinite Programming

Also known as SDP

Ask about this topic

Momentum

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

Jul 13Week of Sep 28
View on map

Latest papers 12

All topics
CardsList
Sep 2, 2026cs.RO

Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration

Certifiable methods have arisen as a means to guarantee global optimality of solutions to non-convex problems using convex semidefinite programming (SDP) relaxations. The most performant of these methods use a local solver to obtain the candidate solution, and then certify its optimality using efficient linear algebra techniques. However, for many problems of interest in robotics, this local-solve-then-certify approach is impeded by a form of degeneracy in the relaxation, leaving a costly optimization of the relaxation as the only recourse. In this paper, we introduce our Central-Path Certifier (CP-Cert), a certifiable method explicitly tailored to certify candidate optima to problems that exhibit this form of degeneracy. Using a candidate as a starting point, our approach seeks a nearby region of the feasible space -- known as the central path -- where a valid certificate can be readily obtained. The approach is kept efficient by exploiting indirect linear algebra techniques, problem sparsity, and parallelism. We apply CP-Cert to both matrix-weighted pose registration and pointcloud data association, whose novel SDP relaxation is of independent interest. On simulated examples, we explore the properties of this novel relaxation and show that CP-Cert is fast and scalable, achieving runtimes that are up to three orders of magnitude faster than state-of-the-art direct solvers. Finally, we combine these contributions into a certifiable, outlier-robust pose-estimation pipeline, which we apply to real-world data.

Connor Holmes, Abhishek Goudar, Timothy D. Barfoot

University of Toronto Robotics Institute, University of Toronto, Toronto, Ontario, Canada

Semidefinite ProgrammingPoint Cloud Registration
AskPDF
Jun 12, 2026cs.RO

Semidefinite Relaxations for Collision-Free Motion Planning

We study semidefinite relaxations for collision-free motion planning. We focus on a point robot moving from start to goal through spherical obstacles in Rn\mathbb{R}^n, subject to path continuity constraints and squared derivative costs; a setting that is conceptually simple yet captures the hardness of collision-free motion planning. We formulate this problem exactly as a nonconvex problem over polynomial curves, and present a natural semidefinite relaxation. We contribute two key theoretical insights; to our knowledge this is the first theoretical analysis of semidefinite relaxations for collision-free motion planning. First, we show that solving the convex relaxation is equivalent to solving, to global optimality, a related motion planning problem in a potentially higher-dimensional space. This geometric interpretation yields necessary and sufficient conditions for tightness, and a clear intuition for when the relaxation is loose. Second, we show that the relaxation admits a symmetry reduction that makes it significantly smaller than one might expect, with positive semidefinite cone sizes that scale linearly with the polynomial degree and are independent of the ambient dimension. The resulting relaxation is 10 to 100 times faster than direct nonlinear programming transcriptions solved with SNOPT and IPOPT, exhibits significantly lower variance in solve times, and reliably finds a locally optimal path for the original problem. We demonstrate its effectiveness as a convex steering function in an RRT planner for minimum-snap quadrotor planning with C4C^4 continuous trajectories.

Bernhard Paus Graesdal, Alexandre Amice, Pablo A. Parrilo +1

Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA.

Semidefinite ProgrammingConstrained Motion PlanningTrajectory OptimizationMotion Planning
AskPDF
Jun 11, 2026math.OC

Scalable Deep Unfolding of Conic Optimizers

Deep unfolding (DU) accelerates iterative optimizers by introducing learnable components and training them through unrolled iterations, but extending DU to the large-scale semidefinite programs (SDPs) common in robotics has remained limited. Unrolling a full-update conic solver such as COSMO exposes two obstacles that prior work on learned conic solvers has not: backpropagating through the per-iteration linear-system solve incurs memory quadratic in the problem size once the coefficient matrix is formed explicitly, and backpropagating through the positive semidefinite (PSD) cone projection becomes numerically unstable when eigenvalues coincide. We address the first obstacle with a matrix-free implicit differentiation rule that operates entirely through matrix-vector products, reducing memory from O(n2)O(n^2) to O(n)O(n) and enabling backpropagation at scales where direct factorization runs out of memory. We address the second with a backward rule based on the Dalečkii--Krein representation of the Fréchet derivative, which remains well-defined under repeated eigenvalues. Together these make it possible to learn lightweight hyperparameter policies and warm-starts for a full-update conic solver. We evaluate on nonlinear covariance steering problems solved via sequential convex programming (SCP), as well as standalone SDPs and second-order cone programs ranging from max-cut and Lovász ϑ\vartheta SDPs to robust estimation and control problems. The learned policies outperform state-of-the-art solvers across all problems, and can provide up to a 50×\times speedup depending on the class. When used as a subroutine in SCP, the learned approach delivers over a 30×\times speedup compared to COSMO.

Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. Theodorou

Georgia Institute of Technology

Semidefinite ProgrammingAlgorithm UnrollingConstrained OptimizationMatrix OptimizationDifferentiable OptimizationDeep Unfolding
AskPDF
May 31, 2026cs.LG

Conditioned free-energy density of proteins using unbalanced solutions to constraint satisfaction problems

We show that computing the log-partition function (free-energy) of conditioned inhomogeneous Curie--Weiss spin Hamiltonians reduces to an unbalanced 2→12 \to 1 norm computation, and design a polynomial-time SDP algorithm for this problem with a lower bound proof for the amount of unbalance achieved. Applied to the protein Ubiquitin, the framework starts from a known crystal structure, explores alternative backbone conformations across the free-energy landscape, and identifies flexible regions of the protein while preserving its native secondary structure.

Pratik Worah, Subhash Khot, Srinivasa Varadhan

Free Energy CalculationSemidefinite ProgrammingConstraint Satisfaction
AskPDF
May 28, 2026cs.RO

Exploiting Chordal Sparsity for Globally Optimal Estimation with Factor Graphs

Robust and efficient state estimation is crucial for perception, navigation, and control in robotics. State estimation problems are conveniently modeled using the factor-graph framework as enabled by modern software packages such as GTSAM or g2o. However, the standard solvers included in such frameworks are local and may converge to poor local minima, posing significant safety concerns. Conversely, techniques based on convex relaxations have been shown to provide a means of globally solving or certifying many state estimation problems. However, these relaxations 1) often require substantial effort to formulate, and 2) may incur significantly higher cost compared to efficient local solvers, as they require solving a large semidefinite program (SDP). In this work, we address both shortcomings by 1) creating a new procedure within the GTSAM framework for automatically constructing convex SDP relaxations for any factor graphs with common factor and variable types, and by 2) exploiting the Bayes tree constructions native to GTSAM to decompose the SDP problem, leading to significant speedup in solver time for chordally sparse problems. We demonstrate the favorable scaling of this structure-exploiting global estimator compared to standard local solvers for two case studies: A 3D pose-graph SLAM problem with a ring factor graph and a 2D localization problem with a chain factor graph. The software framework is available at https://github.com/borglab/gtsam.

Avinash Subramanian, Connor Holmes, Timothy D. Barfoot +2

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

Semidefinite ProgrammingFactor Graph OptimizationConstrained Optimization
AskPDF
May 13, 2026cs.RO

TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics

Semidefinite programming (SDP) provides a principled framework for convex relaxations of nonconvex geometric constraints in motion planning, yet existing solvers are too computationally expensive for real-time control, particularly on resource-constrained embedded systems. To address this gap, we introduce TinySDP, the first semidefinite programming solver designed for embedded systems, enabling real-time model-predictive control (MPC) on microcontrollers for problems with nonconvex obstacle constraints. Our approach integrates positive-semidefinite cone projections into a cached-Riccati-based ADMM solver, leveraging computational structure for embedded tractability. We pair this solver with an a posteriori rank-1 certificate that converts relaxed solutions into explicit geometric guarantees at each timestep. On challenging benchmarks, e.g., cul-de-sac and dynamic obstacle avoidance scenarios that induce failures in local methods, TinySDP achieves collision-free navigation with up to 73% shorter paths than state-of-the-art baselines. We validate our approach on a Crazyflie quadrotor, demonstrating that semidefinite constraints can be enforced at real-time rates for agile embedded robotics.

Ishaan Mahajan, Jon Arrizabalaga, Andrea Grillo +4

Columbia University, USA · Massachusetts Institute of Technology, USA · ´Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Switzerland +1

Semidefinite ProgrammingConstrained Motion PlanningRoboticsModel Predictive ControlConstrained OptimizationSafe Motion Planning
AskPDF
May 8, 2026cs.LG

Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks

Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for Max-Cut, where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific graph neural network that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update steps of complexity O(n2+ne)\mathcal{O}(n^2 + ne), and predicts both primal- and dual-feasible SDP solutions. The primal SDP solutions yield feasible Max-Cut solutions via the Goemans--Williamson algorithm. In addition, it is trained in a self-supervised fashion without requiring solved SDP relaxations as labels. Empirically, we show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to 10.6×10.6 \times compared with using the state-of-the-art SDP solver Mosek. Our work highlights the potential of learned, validity-preserving surrogates for accelerating exact optimization over structured convex relaxations.

Hao Chen, Chendi Qian, Christopher Morris +2

1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech

Semidefinite ProgrammingGraph Neural NetworksBranch and BoundCombinatorial OptimizationGlobal OptimizationConstrained Optimization
AskPDF
May 5, 2026math.OC

Globally Solving Unbalanced Optimal Transport and Density Control for Gaussian Distributions

In this article, we study unbalanced optimal transport (UOT) and establish a control-theoretic dynamical extension, which we call the unbalanced density control (UDC), for a class of Gaussian reference measures. In the static setting, we consider UOT with quadratic transport cost and Kullback--Leibler penalties on the marginals relative to prescribed Gaussian measures. We show that the infinite-dimensional variational problem admits an exact Gaussian reduction, yielding a finite-dimensional optimization over masses, means, and covariances, together with a closed-form expression for the optimal transported mass. We then formulate UDC for discrete-time linear systems, where the initial and terminal state measures are imposed softly through KL penalties and the intermediate evolution is governed by controlled linear dynamics with quadratic control cost. For this problem, we prove that any feasible solution can be replaced, without loss of optimality, by a Gaussian initial measure and an affine-Gaussian control policy. This leads to an exact finite-dimensional reformulation and, after a standard covariance-steering lifting, to an SDP-based optimization for fixed mass, again coupled with a closed-form mass update. We further establish existence of optimal solutions and identify a sufficient condition under which the affine-Gaussian UDC policy is deterministic. These results provide globally optimal solution methods for both Gaussian UOT and Gaussian UDC. Finally, we illustrate our results with several numerical examples.

Haruto Nakashima, Siddhartha Ganguly, Kenji Kashima

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

Semidefinite ProgrammingStochastic Optimal ControlOptimal ControlOptimal Transport
AskPDF
Apr 30, 2026cs.LG

On the Expressive Power of GNNs to Solve Linear SDPs

Semidefinite programs (SDPs) are a powerful framework for convex optimization and for constructing strong relaxations of hard combinatorial problems. However, solving large SDPs can be computationally expensive, motivating the use of machine learning models as fast computational surrogates. Graph neural networks (GNNs) are a natural candidate in this setting due to their sparsity-awareness and ability to model variable-constraint interactions. In this work, we study what expressive power is sufficient to recover optimal SDP solutions. We first prove negative results showing that standard GNN architectures fail on recovering linear SDP solutions. We then identify a more expressive architecture that captures the key structure of SDPs and can, in particular, emulate the updates of a standard first-order solver. Empirically, on both synthetic and \textsc{SdpLib} benchmarks of various classes of SDPs, this more expressive architecture achieves consistently lower prediction error and objective gap than theoretically weaker baselines. Finally, using the learned high-quality predictions to warm-start the first-order solver yields practical speedups of up to 80%.

Chendi Qian, Christopher Morris

Faculty of Computer Science, RWTH Aachen University, Germany

Semidefinite ProgrammingGraph Neural NetworksGNN ExpressivityConstrained Optimization
AskPDF
Sep 26, 2025math.OC

Mixtures Closest to a Given Measure: A Semidefinite Programming Approach

Mixture models, such as Gaussian mixture models, are widely used in machine learning to represent complex data distributions. A key challenge, especially in high-dimensional settings, is to determine the mixture order and estimate the mixture parameters. We study the problem of approximating a target measure, available only through finitely many of its moments, by a mixture of distributions from a parametric family (e.g., Gaussian, exponential, Poisson), with approximation quality measured by the 2-Wasserstein or the total variation distance. Unlike many existing approaches, the parameter set is not assumed to be finite; it is modeled as a compact basic semi-algebraic set. We introduce a hierarchy of semidefinite relaxations with asymptotic convergence to the desired optimal value. In addition, when a certain rank condition is satisfied, the convergence is even finite and recovery of an optimal mixing measure is obtained. We also present an application to clustering, where our framework serves either as a stand-alone method or as a preprocessing step that yields both the number of clusters and strong initial parameter estimates, thereby accelerating convergence of standard (local) clustering algorithms.

Srećko Đurašinović, Jean-Bernard Lasserre, Victor Magron

College of Computing and Data Science, NTU, Singapore · LAAS-CNRS, Toulouse, France · Toulouse School of Economics +1

Semidefinite ProgrammingData Mixture Optimization
AskPDF
Jan 16, 2024stat.ML

Semidefinite programming relaxations and debiasing for MAXCUT-based clustering

In this paper, we consider the problem of partitioning a small data sample of size nn drawn from a mixture of 22 sub-gaussian distributions in Rp\mathbb{R}^p. We consider semidefinite programming relaxations of an integer quadratic program that is formulated essentially as finding the maximum cut on a graph, where edge weights in the cut represent dissimilarity scores between two nodes based on their pp features. We define the signal-to-noise ratio (SNR) as s2:=min⁡{npγ2,Δ2}s^2 := \min\{n p γ^2, Δ^2\}, where Δ2:=pγΔ^2 := p γ denotes the ℓ22\ell_2^2 distance between the two cluster centers. Our contributions are twofold. First, we provide a unified framework for analyzing three computationally efficient algorithms: SDP1, BalancedSDP, and Spectral clustering, yielding universal polynomial-rate misclassification guarantees for all three algorithms. Moreover, our theory allows for partial recovery (success rate <100%< 100\%) as long as s2s^2 is lower bounded by a constant. Second, we prove that the misclassification errors for SDP1 and BalancedSDP decay exponentially with respect to the SNR s2s^2 and the BalancedSDP requires no explicit debiasing when the two clusters have equal sizes. To our knowledge, this is the first time such results are obtained for semidefinite relaxations of MAX CUT in population clustering. We provide simulation evidence illuminating the theoretical predictions.

Shuheng Zhou

University of California, Riverside, CA 92521

Semidefinite ProgrammingUnsupervised ClusteringGraph ClusteringSpectral Methods
AskPDF
Date pendingcs.LG

Semidefinite Programming for Quantum Channel Learning

The problem of reconstructing a quantum channel from a sample of classical data is considered. When the total fidelity can be represented as a ratio of two quadratic forms (e.g., in the case of mapping a mixed state to a pure state, projective operators, unitary learning, and others), Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix. A remarkable feature of SDP is that the optimization is convex, which allows the problem to be efficiently solved by a variety of numerical algorithms. We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms. A notable feature is that the Kraus rank of the obtained quantum channel typically comprises less than a few percent of its maximal possible value. This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data. The theory was also applied to the problem of reconstructing projective operators from data. Finally, we discuss a classical computational model based on quantum channel transformation, performed and calculated on a classical computer, possibly hardware-optimized.

Mikhail Gennadievich Belov, Victor Victorovich Dubov, Vadim Konstantinovich Ivanov +3

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

Semidefinite ProgrammingQuantum Machine Learning
AskPDF