Dimension reduction for semidefinite programs via Jordan algebras
From MaRDI portal
Publication:2188241
DOI10.1007/S10107-019-01372-5zbMATH Open1468.90080arXiv1608.02090OpenAlexW2524488792WikidataQ128276840 ScholiaQ128276840MaRDI QIDQ2188241FDOQ2188241
Pablo A. Parrilo, Frank Permenter
Publication date: 10 June 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal-dual pair over a lower-dimensional symmetric cone---namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We present a simple algorithm for minimizing the rank of this projection and hence the dimension of this subalgebra. We also show that minimizing rank optimizes the direct-sum decomposition of the algebra into simple ideals, yielding an optimal "block-diagonalization" of the SDP. Finally, we give combinatorial versions of our algorithm that execute at reduced computational cost and illustrate effectiveness of an implementation on examples. Through the theory of Jordan algebras, the proposed method easily extends to linear and second-order-cone programming and, more generally, symmetric cone optimization.
Full work available at URL: https://arxiv.org/abs/1608.02090
Recommendations
- Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
- Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software
- Symmetry in semidefinite programs
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- Dimensionality reduction of SDPs through sketching
Cites Work
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exploiting special structure in semidefinite programming: a survey of theory and applications
- Symmetry groups, semidefinite programs, and sums of squares
- Title not available (Why is that?)
- Linear systems in Jordan algebras and primal-dual interior-point algorithms
- An independent benchmarking of SDP and SOCP solvers
- Positive projections and Jordan structure in operator algebras.
- Lattice-like Subsets of Euclidean Jordan Algebras
- Positive Linear Maps of Operator Algebras
- A comparison of the Delsarte and Lovász bounds
- Worst-case CVaR based portfolio optimization models with applications to scenario planning
- Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
- Regularizing the abstract convex program
- The complex structured singular value
- Invariant Semidefinite Programs
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Coherent algebras
- Title not available (Why is that?)
- Exploiting orbits in symmetric ILP
- Title not available (Why is that?)
- Dimension Reduction via Colour Refinement
- Strong Duality in Conic Linear Programming: Facial Reduction and Extended Duals
- A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with general irreducible components
- Symmetry in semidefinite programs
- Improving the Semidefinite Programming Bound for the Kissing Number by Exploiting Polynomial Symmetry
- Exploiting symmetry in copositive programs via semidefinite hierarchies
- Algebras of linear transformations
Cited In (5)
- Jordan Algebras of Symmetric Matrices
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software
- Minimum energy configurations on a toric lattice as a quadratic assignment problem
- The geometries of Jordan nets and Jordan webs
Uses Software
This page was built for publication: Dimension reduction for semidefinite programs via Jordan algebras
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188241)
