Dimension reduction for semidefinite programs via Jordan algebras

DOI10.1007/S10107-019-01372-5MaRDI QIDQ2188241zbMATH OpenOpenAlexWikidataFDO

Authors Frank Permenter, Pablo A. Parrilo

Publication date 10 June 2020

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.02090

zbMATH Keywords

block diagonalizationJordan algebrasrank minimizationsemidefinite programmingsymmetric cones

Mathematics Subject Classification ID

Semidefinite programming (90C22)

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.

Review text

A new approach for simplifying semidefinite optimization problems inspired by the technique of symmetry reduction is proposed, where if an orthogonal projection map satisfies certain invariance conditions, an equivalent primal-dual pair of optimization problems over a lower-dimensional symmetric cone is derived. An algorithm for minimizing the rank of this projection and hence the dimension of the involved subalgebra is proposed and implemented as well. By means of Jordan algebras, the proposed method can be easily extended to linear, second-order cone and even symmetric cone optimization. Moreover, it is proven that rank minimization has a beneficial effect on the direct-sum decomposition of the algebra into simple ideals, leading to an optimal ``block-diagonalization of the initial semidefinite optimization problem. Combinatorial versions of the proposed algorithm illustrate its effectiveness on concrete examples.

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

• A comparison of the Delsarte and Lovász bounds
• A new library of structured semidefinite programming instances
• A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with general irreducible components
• Algebras of linear transformations
• An independent benchmarking of SDP and SOCP solvers
• Coherent algebras
• Dimension reduction via colour refinement
• Exploiting orbits in symmetric ILP
• Exploiting special structure in semidefinite programming: a survey of theory and applications
• Exploiting symmetry in copositive programs via semidefinite hierarchies
• scientific article; zbMATH DE number 1254290 (Why is no real title available?)
• scientific article; zbMATH DE number 715155 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1534294 (Why is no real title available?)
• scientific article; zbMATH DE number 3893796 (Why is no real title available?)
• Improving the Semidefinite Programming Bound for the Kissing Number by Exploiting Polynomial Symmetry
• Invariant Semidefinite Programs
• Lattice-like subsets of Euclidean Jordan algebras
• Linear systems in Jordan algebras and primal-dual interior-point algorithms
• Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• Positive linear maps of operator algebras
• Positive projections and Jordan structure in operator algebras.
• Regularizing the abstract convex program
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Strong duality in conic linear programming: facial reduction and extended duals
• Symmetry groups, semidefinite programs, and sums of squares
• Symmetry in semidefinite programs
• The complex structured singular value
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(7)

• The geometries of Jordan nets and Jordan webs
• Minimum energy configurations on a toric lattice as a quadratic assignment problem
• Jordan algebras of symmetric matrices
• Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
• An exceptionally difficult binary quadratic optimization problem with symmetry: a challenge for the largest unsolved QAP instance Tai256c
• Symmetry detection in mixed-integer conic programming

Describes a project that uses

Uses Software

• SeDuMi
• Sostools
• SDPA
• SOSOPT

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)