A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

Samuel Burer; Kyungchan Park

doi:10.1007/s10957-023-02168-6

Back

A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

Journal article

Peer reviewed

A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

Samuel Burer and Kyungchan Park

Journal of optimization theory and applications, Vol.202(1), pp.320-339

07/2024

DOI: 10.1007/s10957-023-02168-6

View Online

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; and (ii) the use of the Kronecker matrix product to construct SDP relaxations. Using synthetic instances on five problem classes, we show that, in general, our relaxation significantly strengthens existing relaxations, although at the expense of longer solution times.

Mathematics

Physical Sciences

Technology

Mathematics, Applied

Operations Research & Management Science

Science & Technology

Details

Title: Subtitle: A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold
Creators: Samuel Burer - University of Iowa
Kyungchan Park - University of Iowa
Resource Type: Journal article
Publication Details: Journal of optimization theory and applications, Vol.202(1), pp.320-339
DOI: 10.1007/s10957-023-02168-6
ISSN: 0022-3239
eISSN: 1573-2878
Publisher: Springer Nature
Number of pages: 20
Language: English
Electronic publication date: 03/03/2023
Date published: 07/2024
Academic Unit: Business Analytics
Record Identifier: 9984386360102771

Metrics

25 Record Views

1 Times Cited - Web of Science

See more details