Dimension reduction for semidefinite programs via Jordan algebras

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.

References in corpus (7)

• Symmetry groups, semidefinite programs, and sums of squares
• SOSTOOLS Version 4.00 Sum of Squares Optimization Toolbox for MATLAB
• Symmetry in semidefinite programs
• Matrix Algebras and Semidefinite Programming Techniques for Codes
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. II. Program Implementation of the Weisfeiler-Leman Algorithm
• Lattice-like subsets of Euclidean Jordan algebras

Cited by in corpus (8)

• Semidefinite programming relaxations for quantum correlations
• Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
• Uncertainty relations from state polynomial optimization
• SymDPoly: symmetry-adapted moment relaxations for noncommutative polynomial optimization
• 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
• Certifying Numerical Decompositions of Compact Group Representations