Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
From MaRDI portal
Publication:1785193
DOI10.1007/S10107-017-1169-9zbMath1405.90098arXiv1408.4685OpenAlexW3124734834MaRDI QIDQ1785193
Frank Permenter, Pablo A. Parrilo
Publication date: 28 September 2018
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.4685
dual solution recoverymaximum rank matricessemidefinite programming (SDP) facial reduction procedure
Semidefinite programming (90C22) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (37)
CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices ⋮ A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms ⋮ Evaluating approximations of the semidefinite cone with trace normalized distance ⋮ A new perspective on low-rank optimization ⋮ Dimension reduction for semidefinite programs via Jordan algebras ⋮ On eigenvalues of symmetric matrices with PSD principal submatrices ⋮ A simplified treatment of Ramana's exact dual for semidefinite programming ⋮ Subset Selection and the Cone of Factor-Width-k Matrices ⋮ Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming ⋮ Characterization of the dual problem of linear matrix inequality for H-infinity output feedback control problem via facial reduction ⋮ DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ⋮ Amenable cones: error bounds without constraint qualifications ⋮ On sums of squares of \(K\)-nomials ⋮ Numerical algebraic geometry and semidefinite programming ⋮ Stability and performance verification of optimization-based controllers ⋮ An improved semidefinite programming hierarchy for testing entanglement ⋮ Penalized semidefinite programming for quadratically-constrained quadratic optimization ⋮ Validating numerical semidefinite programming solvers for polynomial invariants ⋮ Polyhedral approximations of the semidefinite cone and their application ⋮ Douglas-Rachford splitting and ADMM for pathological convex optimization ⋮ Facial reduction for exact polynomial sum of squares decomposition ⋮ Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs ⋮ On polyhedral and second-order cone decompositions of semidefinite optimization problems ⋮ Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices ⋮ frlib ⋮ A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs ⋮ Facially Dual Complete (Nice) Cones and Lexicographic Tangents ⋮ Exact Semidefinite Programming Bounds for Packing Problems ⋮ Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs ⋮ Solving SDP completely with an interior point oracle ⋮ Unnamed Item ⋮ Error Bounds and Singularity Degree in Semidefinite Programming ⋮ Coordinate Shadows of Semidefinite and Euclidean Distance Matrices ⋮ Sparse PSD approximation of the PSD cone ⋮ Solving Conic Optimization Problems via Self-Dual Embedding and Facial Reduction: A Unified Approach
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions
- Facial reduction algorithms for conic optimization problems
- A facial reduction algorithm for finding sparse SOS representations
- A criterion for the half-plane property
- Regularizing the abstract convex program
- Initialization in semidefinite programming via a self-dual skew-symmetric embedding
- An exact duality theory for semidefinite programming and its complexity implications
- Semidefinite programming relaxations for the quadratic assignment problem
- An independent benchmarking of SDP and SOCP solvers
- Homogeneous multivariate polynomials with the half-plane property
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Cones of diagonally dominant matrices
- Combinatorial characterization of the null spaces of symmetric H-matrices
- Presolving in linear programming
- How to generate weakly infeasible semidefinite programs via Lasserre's relaxations for polynomial optimization
- Strong duality and minimal representations for cone optimization
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Semidefinite programming relaxations for the graph partitioning problem
- Polynomials with the half-plane property and matroid theory
- On factor width and symmetric \(H\)-matrices
- Efficient Use of Semidefinite Programming for Selection of Rotamers in Protein Conformations
- Bad Semidefinite Programs: They All Look the Same
- Lyapunov analysis of rigid body systems with impacts and friction via sums-of-squares
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Linear Matrix Inequalities in System and Control Theory
- Strong Duality for Semidefinite Programming
- Copositive realxation for genera quadratic programming
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Error Bounds for Linear Matrix Inequalities
- Semidefinite Optimization and Convex Algebraic Geometry
- Pre- and Post-Processing Sum-of-Squares Programs in Practice
- Extreme copositive quadratic forms
- Preprocessing and Regularization for Degenerate Semidefinite Programs
- Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals
- Handbook of semidefinite programming. Theory, algorithms, and applications
This page was built for publication: Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
