Stiefel optimization is NP-hard

DOI10.1007/S11590-025-02271-9MaRDI QIDQ7289114zbMATH OpenFDO

Authors Zehua Lai, Lek-Heng Lim, Tianyun Tang

Publication date 2 July 2026

Published in Optimization Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S11590-025-02271-9

Mathematics Subject Classification ID

Manifolds and cell complexes (57-XX) Operations research, mathematical programming (90-XX)

Cites work

• Computational Complexity
• Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix
• Grassmannian optimization is NP-hard
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 429516 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear Programming on the Stiefel Manifold
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Optimization on flag manifolds
• Some optimal inapproximability results
• Sums of random symmetric matrices and quadratic optimization under orthogonality constraints
• Sums of squares, moment matrices and optimization over polynomials
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• The Geometry of Algorithms with Orthogonality Constraints

Cited in

(1)

• Parareal algorithm for gradient flow arising from orthogonality-constrained matrix optimization problems

This page was built for publication: Stiefel optimization is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7289114)