Linear Programming on the Stiefel Manifold

DOI10.1137/23M1552243arXiv2301.06918MaRDI QIDQ6202765FDOQ6202765

Authors: Mengmeng Song, Yong Xia 

Publication date: 27 February 2024

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

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$.

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)

Cites Work

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

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)