Grassmannian optimization is NP-hard

DOI10.1137/24M1672596MaRDI QIDQ6931479zbMATH OpenFDO

Authors Zehua Lai, Lek-Heng Lim, Ke Ye

Publication date 10 September 2025

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1672596

zbMATH Keywords

Grassmannianmanifold optimizationNP-hardpositive definite coneStiefel manifold

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Analysis of algorithms and problem complexity (68Q25) Polynomial optimization (90C23) Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)

Cites work

• A group-theoretic framework for the construction of packings in Grassmannian spaces
• Basic Convex Analysis in Metric Spaces with Bounded Curvature
• Degree of the Grassmannian as an affine variety
• Differential geometry, Lie groups, and symmetric spaces.
• Doubly Stochastic Matrices and the Diagonal of a Rotation Matrix
• Geometric algorithms and combinatorial optimization
• Geometric Invariant Theory
• Groupes simples clos et ouverts et géométrie riemannienne.
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 429516 (Why is no real title available?)
• scientific article; zbMATH DE number 3909256 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 1246686 (Why is no real title available?)
• scientific article; zbMATH DE number 1321168 (Why is no real title available?)
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• scientific article; zbMATH DE number 739280 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1007086 (Why is no real title available?)
• scientific article; zbMATH DE number 4119142 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 3109468 (Why is no real title available?)
• Introduction to Smooth Manifolds
• Isometries of Grassmann spaces
• Lectures on convex optimization
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Non-existence of continuous convex functions on certain Riemannian manifolds
• On cones of nonnegative quartic forms
• On the complexity of following the central path of linear programs by linear extrapolation. II
• On the tightness of SDP relaxations of QCQPs
• Packing Lines, Planes, etc.: Packings in Grassmannian Spaces
• Quadratic programming is in NP
• Reducibility among combinatorial problems
• Representing the space of linear programs as the Grassmann manifold
• Reproducing kernels for the irreducible components of polynomial spaces on unions of Grassmannians
• Richtungsfelder und Fernparallelismus in \(n\)-dimensionalen Mannigfaltigkeiten
• Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
• Some NP-complete problems in quadratic and nonlinear programming
• Statistics on special manifolds
• Strong Rigidity of Locally Symmetric Spaces. (AM-78)
• Sums of random symmetric matrices and quadratic optimization under orthogonality constraints
• Sur certaines formes Riemanniennes remarquables des géométries à groupe fondamental simple.
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• The Geometry of Algorithms with Orthogonality Constraints
• Unitäre Transformationen großer Matrizen

Cited in

(4)

• Euclidean distance degree in manifold optimization
• Stiefel optimization is NP-hard
• Special orthogonal, special unitary, and symplectic groups as products of Grassmannians
• Parareal algorithm for gradient flow arising from orthogonality-constrained matrix optimization problems

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

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