Semidefinite Programming
1996/03/01 by Lieven Vandenberghe, Stephen Boyd · 4,108 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Affine transformation #Computer science #Conic optimization #Convex analysis #Convex optimization #Interior point method #Linear matrix inequality #Linear programming #Mathematical optimization #Mathematics #Matrix Theory and Algorithms #Nonlinear programming #Nonlinear system #Pure mathematics #Quadratic programming #Quadratically constrained quadratic program #Regular polygon #Second-order cone programming #Semidefinite embedding #Semidefinite programming #Sparse and Compressive Sensing Techniques
paper · doi:10.1137/1038003
published in SIAM Review 38(1), 49-95 (Society for Industrial and Applied Mathematics)
openalex publication_date 1996/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25
Abstract
In semidefinite programming one minimizes a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so semidefinite programs are convex optimization problems. Semidefinite programming unifies several standard problems (e.g., linear and quadratic programming) and finds many applications in engineering and combinatorial optimization. Although semidefinite programs are much more general than linear programs, they are not much harder to solve. Most interior-point methods for linear programming have been generalized to semidefinite programs. As in linear programming, these methods have polynomial worst-case complexity, and perform very well in practice. This paper gives a survey of the theory and applications of semidefinite programs, and an introduction to primal-dual interior-point methods for their solution.
Cited by
- Theory and Applications of Robust Optimization
- Estimating Finite Source Properties of Small Earthquake Ruptures
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Interior Methods for Nonlinear Optimization
- Fast quantum measurement tomography with optimal error bounds
- Algorithm 950
- Fastest Distributed Consensus Problem on Fusion of Two Star Networks
- Noise-Tolerant Quantum Tokens for MAC
- A Newton-bracketing method for a simple conic optimization problem
- Principles of Quantum Communication Theory: A Modern Approach
- Duality of optimization problems with gauge functions
- Resource Allocation for Simultaneous Wireless Information and Power Transfer Systems: A Tutorial Overview
- Capitalizing Backscatter-Aided Hybrid Relay Communications with Wireless Energy Harvesting
- Semidefinite programs for completely bounded norms
- Fastest Distributed Consensus Averaging Problem on Chain of Rhombus Networks
- A direct formulation for sparse PCA using semidefinite programming
- Asymptotic Analysis of Objectives based on Fisher Information in Active Learning
- Nonlocality and Entanglement for Symmetric States
- A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming
- Flexible numerical optimization with ensmallen
- Semidefinite Relaxation of Quadratic Optimization Problems
- Phase Retrieval with Application to Optical Imaging: A contemporary overview
- Linear precoding via conic optimization for fixed MIMO receivers
- Super-Resolution DOA Estimation for Arbitrary Array Geometries Using a Single Noisy Snapshot
- Refined Asymptotics for Multigraded Sums of Squares
- Quantifying Dynamical Total Coherence in a Resource Non-increasing Framework
- Design of Privacy-Preserving Dynamic Controllers
- Joint Transmit Beamforming for Multiuser MIMO Communication and MIMO Radar
- Exact solutions of infinite dimensional total-variation regularized\n problems
- Convex Maneuver Planning for Spacecraft Collision Avoidance
- Estimation of (near) low-rank matrices with noise and high-dimensional scaling
- The Interplay between Quantum Contextuality and Wigner Negativity
- Semidefinite Programming and Nash Equilibria in Bimatrix Games
- On the Semidefinite Duality of Finite-Horizon LQG Problem
- On Positive Duality Gaps in Semidefinite Programming
- T-positive semidefiniteness of third-order symmetric tensors and T-semidefinite programming
- Structural Analysis of Viral Spreading Processes in Social and\n Communication Networks Using Egonets
- Matrix best approximation in the spectral norm
- Conic optimization techniques yield sufficient conditions for set-completely positive matrix completion under arrowhead specification pattern
- Secure Dual-Functional Radar-Communication System via Exploiting Known Interference in the Presence of Clutter
- Almost-rigidity of frameworks
- Distinguishing Separable and Entangled States
- Robust Markov Decision Processes
- A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
- Generically globally rigid graphs have generic universally rigid frameworks
- Regions of Attraction Approximation Using Individual Invariance
- Fastest Mixing Markov Chain on Symmetric K-Partite Network
- Bayesian Inference using the Proximal Mapping: Uncertainty Quantification under Varying Dimensionality
- Phase Retrieval with Application to Optical Imaging
- Efficient Reward Identification In Max Entropy Reinforcement Learning with Sparsity and Rank Priors
- Fastest Distributed Consensus Problem on Branches of an Arbitrary Connected Sensor Network
- Nonequilibrium Phase Transitions in Large N Matrix Quantum Mechanics
- A Faster Interior Point Method for Semidefinite Programming
- Minimizing rational functions: a hierarchy of approximations via pushforward measures
- Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
- Analytic Studies of Fermions in the Conformal Bootstrap
- On the Power of Entangled Quantum Provers
- Certified Roundoff Error Bounds Using Semidefinite Programming
- Funnel Libraries for Real-Time Robust Feedback Motion Planning
- Peregrine: Network Localization and Navigation with Scalable Inference and Efficient Operation
- On the complexity of Putinar-Vasilescu's Positivstellensatz
- Computing finite-dimensional bipartite quantum separability
- Scalable Combinatorial Bayesian Optimization with Tractable Statistical models
- Discrete-Aware Matrix Completion via Proximal Gradient
- Approximate Dynamic Programming For Linear Systems with State and Input Constraints
- Nullspace Property for Optimality of Minimum Frame Angle Under Invertible Linear Operators
- Low Rank Forecasting
- MPLAPACK version 2.0.1 user manual
- Approximating the order 2 quantum Wasserstein distance using the moment-SOS hierarchy
- Complexity aspects of local minima and related notions
- Universal and Efficient Quantum State Verification via Schmidt Decomposition and Mutually Unbiased Bases
- A Comprehensive Survey on Transfer Learning
- A sequential semidefinite programming method and an application in passive reduced-order modeling
- Best ℓ1-approximation of nonnegative polynomials by sums of squares
- Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity
- Complete family of separability criteria
- Mean-Reverting Portfolios: Tradeoffs Between Sparsity and Volatility
- Sum-of-square-of-rational-function based representations of positive semidefinite polynomial matrices
- Detecting multipartite entanglement
- Measurement incompatibility and quantum steering via linear programming
- A Triangle Algorithm for Semidefinite Version of Convex Hull Membership Problem
- A Sparse Flat Extension Theorem for Moment Matrices
- Experiment design and parameter estimation of Pauli channels using convex optimization
- Entanglement detection
- Stability of Polynomial Differential Equations: Complexity and Converse\n Lyapunov Questions
- Energy as an entanglement witness for quantum many-body systems
- Unambiguous State Discrimination of two density matrices in Quantum Information Theory
- Geometric remarks on Kalman filtering with intermittent observations
- A proximal DC approach for quadratic assignment problem
- On the Equivalence of SDP Feasibility and a Convex Hull Relaxation for System of Quadratic Equations
- Prove Costa's Entropy Power Inequality and High Order Inequality for Differential Entropy with Semidefinite Programming
- Correlations, Bell Inequality Violation & Quantum Entanglement
- A Distributed Method for Fitting Laplacian Regularized Stratified Models
- Non-Negative Matrix Factorization, Convexity and Isometry
- Universal quantum data compression via nondestructive tomography
- Bounds on quantum correlations in Bell-inequality experiments
- Testing quantum devices: Practical entanglement verification in bipartite optical systems
- Convertibility between two-qubit states using stochastic local quantum operations assisted by classical communication
- Phase-covariant quantum benchmarks
- Polynomial mathematical programs with equilibrium constraints and semidefinite programming relaxations
- Bounding the Set of Quantum Correlations
- Cryptography in a Quantum World
- Mutually unbiased bases and semi-definite programming
- Better Bell-inequality violation by collective measurements
- Optimal tracking for pairs of qubit states
- Mixed-quantum-state detection with inconclusive results
- A quasipolynomial-time algorithm for the quantum separability problem
- Nonlinear entanglement witnesses, covariance matrices and the geometry of separable states
- Tensor optimization for optical-interferometric imaging
- Upper bound on the secret key rate distillable from effective quantum correlations with imperfect detectors
- Pure-state transformations and catalysis under operations that completely preserve positivity of partial transpose
- Quantum algorithms for the ordered search problem via semidefinite programming
- Unifying several separability conditions using the covariance matrix criterion
- Local Discrimination of Mixed States
- Multiparticle covariance matrices and the impossibility of detecting graph-state entanglement with two-particle correlations
- Squashing model for detectors and applications to quantum-key-distribution protocols
- Optimal quantum detectors for unambiguous detection of mixed states
- Computing quantum discord is NP-complete
- The Nature of Computation
- A tutorial on linear and bilinear matrix inequalities
- Synchronization overZ2and community detection in signed multiplex networks with constraints
- Exact solvability, non-integrability, and genuine multipartite entanglement dynamics of the Dicke model
- Evaluating Convex Roof Entanglement Measures
- Lagrangian Relaxation
- Quantum benchmarks for the storage or transmission of quantum light from minimal resources
- The ubiquitous Kronecker product
- Information causality and noisy computations
- Activation of Nonlocal Quantum Resources
- Optimal multicopy asymmetric Gaussian cloning of coherent states
- Single-photon quantum key distribution in the presence of loss
- Manipulating multiqudit entanglement witnesses by using linear programming
- Second-Order Conic and Polyhedral Approximations of the Exponential Cone: Application to Mixed-Integer Exponential Conic Programs
- Optimal entanglement witnesses for continuous-variable systems
- Maximally genuine multipartite entangled mixed X-states ofN-qubits
- Characterizing quantum microwave radiation and its entanglement with superconducting qubits using linear detectors
- Entanglement verification for quantum-key-distribution systems with an underlying bipartite qubit-mode structure
- Unsupervised Learning of Image Manifolds by Semidefinite Programming
- A rewriting system for convex optimization problems
- Improved semidefinite programming upper bound on distillable entanglement
- Optimal distortion embeddings of distance regular graphs into Euclidean spaces
- Solving Euclidean Distance Matrix Completion Problems Via Semidefinite Programming
- Random unitary maps for quantum state reconstruction
- Concave Quadratic Cuts for Mixed-Integer Quadratic Problems
- Lower bounds for ground states of condensed matter systems
- New and updated semidefinite programming bounds for subspace codes
- Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number
- Entanglement detection with scrambled data
- Optimal unambiguous state discrimination of two density matrices: A second class of exact solutions
- One-shot entanglement distillation beyond local operations and classical communication
- Symmetric Extensions of Quantum States and Local Hidden Variable Theories
- Optical implementation of the encoding of two qubits to a single qutrit
- Detected the steerability bounds of the generalized Werner states via BackPropagation neural network
- Sudden change in dynamics of genuine multipartite entanglement of cavity-reservoir qubits
- Fastest Distributed Consensus Averaging Problem on Perfect and Complete n-ary Tree networks
- Einstein-Podolsky-Rosen steering: Its geometric quantification and witness
- Loop equations and bootstrap methods in the lattice
- Parameter estimation of quantum processes using convex optimization
- Finite Quantum Tomography and Semidefinite Programming
- Qudit hypergraph states
- A quantum interior-point predictor–corrector algorithm for linear programming
- Semidefinite Programming Converse Bounds for Quantum Communication
- Quantum optics of chiral spin networks
- Joint Measurability of Generalized Measurements Implies Classicality
- Optimal violation of the Leggett–Garg inequality for arbitrary spin and emergence of classicality through unsharp measurements
- Relaxations of the Satisfiability Problem Using Semidefinite Programming
- Supervised Metric Learning with Generalization Guarantees
- Ultimate precision of joint quadrature parameter estimation with a Gaussian probe
- A glance beyond the quantum model
- Complex portfolio selection via convex mixed‐integer quadratic programming: a survey
- Optimal positive-operator-valued measures for unambiguous state discrimination
- Absolutely classical spin states
- Method for making 2-electron response reduced density matrices approximately N-representable
- Analysis of Transmission of Methicillin-resistant Staphylococcus Aureus in an Intensive Care Unit by Pulsed-field Gel Electrophoresis
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Demonstration of Einstein-Podolsky-Rosen Steering Using Hybrid Continuous- and Discrete-Variable Entanglement of Light
- Bounding Temporal Quantum Correlations
- A Complete Characterization of the Gap between Convexity and SOS-Convexity
- No-Signalling-Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovász Number
- Synthesizing Robust Domains of Attraction for State-Constrained Perturbed Polynomial Systems
- Efficient classification of complete parameter regions based on semidefinite programming. [europepmc]
- Validation of a model of the GAL regulatory system via robustness analysis of its bistability characteristics. [europepmc]
- The use of genomic coancestry matrices in the optimisation of contributions to maintain genetic diversity at specific regions of the genome. [europepmc]
- Spatio-Temporal Steering for Testing Nonclassical Correlations in Quantum Networks. [europepmc]
- Quantum machine learning: a classical perspective. [europepmc]
- Two-dimensional translation-invariant probability distributions: approximations, characterizations and no-go theorems. [europepmc]
- Dynamic Behavior Analysis via Structured Rank Minimization. [europepmc]
- Robust Statistical Frontalization of Human and Animal Faces. [europepmc]
- Solving the Time- and Frequency-Multiplexed Problem of Constrained Radiofrequency Induced Hyperthermia. [europepmc]
- Light-Matter Hybrid-Orbital-Based First-Principles Methods: The Influence of Polariton Statistics. [europepmc]
- Quantum Process Fidelity Bounds from Sets of Input States. [europepmc]
- Online Learning Approach for Predictive Real-Time Energy Trading in Cloud-RANs. [europepmc]
- Analysis and optimization of quantum adaptive measurement protocols with the framework of preparation games. [europepmc]
- A Relaxed Interior Point Method for Low-Rank Semidefinite Programming Problems with Applications to Matrix Completion. [europepmc]
- ORTHOGONAL TRACE-SUM MAXIMIZATION: APPLICATIONS, LOCAL ALGORITHMS, AND GLOBAL OPTIMALITY. [europepmc]
- Lower Bounds on Multivariate Higher Order Derivatives of Differential Entropy. [europepmc]
- An Improved TDOA Method for Land-Based Long-Range HF Skywave Source Geolocation and Experimental Results. [europepmc]
- Square Root Convexity of Fisher Information along Heat Flow in Dimension Two. [europepmc]
- Demonstration of quantum-digital payments. [europepmc]
- Tapping into Permutation Symmetry for Improved Detection of k -Symmetric Extensions. [europepmc]
- Multimodal subspace identification for modeling discrete-continuous spiking and field potential population activity. [europepmc]
- A proactive/reactive mass screening approach with uncertain symptomatic cases. [europepmc]
- Fundamental limits to multi-functional and tunable nanophotonic response. [europepmc]
- Inverse design in photonic crystals. [europepmc]
- Semidefinite programming for manipulating acoustic traps in real time (SMART). [europepmc]
Related