Linear Programming on the Stiefel Manifold

DOI10.1137/23M1552243MaRDI QIDQ6202765FDOQ6202765

Authors Mengmeng Song, Yong Xia

Publication date 27 February 2024

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

Full work available at URL https://arxiv.org/abs/2301.06918

zbMATH Keywords

linear programmingStiefel manifoldsemidefinite programmingoptimality conditionsquadratically constrained quadratic optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)

Abstract: The extended linear Stiefel Manifold optimization (ELS) is studied in the first time. It aims at minimizing a linear objective function over the set of all $p$-tuples of orthonormal vectors in ${mathbbR}^n$ satisfying $k$ additional linear constraints. Despite the classical polynomial-time solvable case $k=0$, (ELS) is in general NP-hard. According to the Shapiro-Barvinok-Pataki theorem, (ELS) admits an exact semidefinite programming (SDP) relaxation when $p(p+1)/2len-k$, which is tight when $p=1$. Surprisingly, we can greatly strengthen this sufficient exactness condition to be $plen-k$, which covers the extreme case $n-p=0=k$. Regarding (ELS) as a smooth nonlinear programming problem, we reveal a nice property that under LICQ, the standard first- and second-order {it local} necessary optimality conditions are sufficient for {it global} optimality when $p+1len-k$.

Recommendations

• On minimization on Stiefel manifolds
• scientific article; zbMATH DE number 1795207
• A Procrustes problem on the Stiefel manifold
• Some global optimization problems on Stiefel manifolds
• Generic optimality conditions for semialgebraic convex programs

Cites work

• scientific article; zbMATH DE number 6118218 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 681023 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• A generalized solution of the orthogonal Procrustes problem
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A nonlinear programming technique for the optimization of continuous processing systems
• A note on lack of strong duality for quadratic problems with orthogonal constraints
• A remark on the convexity and positive definiteness concerning Hermitian matrices
• A survey of hidden convex optimization
• An optimal variant of Kelley's cutting-plane method
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• Cauchy's Interlace Theorem for Eigenvalues of Hermitian Matrices
• Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem
• Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Hadamard matrices and their applications
• Linear and nonlinear programming.
• Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
• On Local Minimizers of Nonconvex Homogeneous Quadratically Constrained Quadratic Optimization with at Most Two Constraints
• On equivalence of semidefinite relaxations for quadratic matrix programming
• On minimization on Stiefel manifolds
• On some applications of Hadamard matrices
• On the ball-constrained weighted maximin dispersion problem
• On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
• On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
• Optimality conditions for the nonlinear programming problems on Riemannian manifolds
• Optimization algorithms exploiting unitary constraints
• Partial Lagrangian relaxation for the unbalanced orthogonal Procrustes problem
• Problems of distance geometry and convex properties of quadratic maps
• Proximal gradient method for nonsmooth optimization over the Stiefel manifold
• Quadratic Matrix Programming
• Rank optimality for the Burer-Monteiro factorization
• Rank-reducibility of a symmetric matrix and sampling theory of minimum trace factor analysis
• Richtungsfelder und Fernparallelismus in \(n\)-dimensionalen Mannigfaltigkeiten
• Riemannian optimization via Frank-Wolfe methods
• Simple algorithms for optimization on Riemannian manifolds with constraints
• The Cutting-Plane Method for Solving Convex Programs
• The orthogonal approximation of an oblique structure in factor analysis

This page was built for publication: Linear Programming on the Stiefel Manifold

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