A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

2022/08/05 by Samuel Burer, Burer, Samuel, Kyungchan Park +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #RNA Interference and Gene Delivery

paper · pdf · doi:10.48550/arxiv.2208.03125

openalex publication_date 2022/08/05 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

We study semidefinite programming (SDP) relaxations for the NP-hard problem of globally optimizing a quadratic function over the Stiefel manifold. We introduce a strengthened relaxation based on two recent ideas in the literature: (i) a tailored SDP for objectives with a block-diagonal Hessian; (ii) and the use of the Kronecker matrix product to construct SDP relaxations. Using synthetic instances on four problem classes, we show that, in general, our relaxation significantly strengthens existing relaxations, although at the expense of longer solution times.

Related

• A Semidefinite Relaxation for Sums of Heterogeneous Quadratic Forms on the Stiefel Manifold
• Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
• Sequential subspace methods on Stiefel manifold optimization
• Solving Low-Rank Semidefinite Programs via Manifold Optimization
• Stiefel optimization is NP-hard