A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

Samuel Burer; Kyungchan Park

doi:10.48550/arXiv.2208.03125

Back

A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

Preprint

Open access

A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

Samuel Burer and Kyungchan Park

arXiv.org

Cornell University Library, arXiv.org

08/05/2022

DOI: 10.48550/arXiv.2208.03125

Files and links (1)

url

https://doi.org/10.48550/arXiv.2208.03125View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

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.

Optimization

Manifolds (mathematics)

Mathematical programming

Quadratic equations

Details

Title: Subtitle: A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold
Creators: Samuel Burer
Kyungchan Park
Resource Type: Preprint
Publication Details: arXiv.org
DOI: 10.48550/arXiv.2208.03125
eISSN: 2331-8422
Publisher: Cornell University Library, arXiv.org; Ithaca
Language: English
Date posted: 08/05/2022
Academic Unit: Business Analytics
Record Identifier: 9984380545902771

Metrics

21 Record Views