Back to Search
Start Over
Dimension reduction for semidefinite programs via Jordan algebras
- Source :
- Springer Berlin Heidelberg
- Publication Year :
- 2019
- Publisher :
- Springer Science and Business Media LLC, 2019.
-
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.
- Subjects :
- 021103 operations research
Rank (linear algebra)
General Mathematics
Dimensionality reduction
Orthographic projection
Subalgebra
MathematicsofComputing_NUMERICALANALYSIS
0211 other engineering and technologies
010103 numerical & computational mathematics
02 engineering and technology
01 natural sciences
Projection (linear algebra)
Algebra
Dimension (vector space)
Optimization and Control (math.OC)
Simple (abstract algebra)
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
FOS: Mathematics
Symmetric matrix
0101 mathematics
Mathematics - Optimization and Control
Software
Mathematics
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 181
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....7e226cd8bf06303d222221795538d371