A framework of constraint preserving update schemes for optimization on Stiefel manifold

DOI10.1007/S10107-014-0816-7zbMATH Open1325.49037arXiv1301.0172OpenAlexW2106173883MaRDI QIDQ747775FDOQ747775

Bo Jiang, Yuhong Dai

Publication date: 19 October 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: This paper considers optimization problems on the Stiefel manifold $X^{mathsfT}X=I_p$, where $Xinmathbb{R}^{nimesp}$ is the variable and $I_p$ is the $p$-by-$p$ identity matrix. A framework of constraint preserving update schemes is proposed by decomposing each feasible point into the range space of $X$ and the null space of $X^{mathsfT}$. While this general framework can unify many existing schemes, a new update scheme with low complexity cost is also discovered. Then we study a feasible Barzilai-Borwein-like method under the new update scheme. The global convergence of the method is established with an adaptive nonmonotone line search. The numerical tests on the nearest low-rank correlation matrix problem, the Kohn-Sham total energy minimization and a specific problem from statistics demonstrate the efficiency of the new method. In particular, the new method performs remarkably well for the nearest low-rank correlation matrix problem in terms of speed and solution quality and is considerably competitive with the widely used SCF iteration for the Kohn-Sham total energy minimization.

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

Recommendations

• A Riemannian conjugate gradient method for optimization on the Stiefel manifold
• Global optimization on Stiefel manifolds: a computational approach
• Transportless conjugate gradient for optimization on Stiefel manifold
• Two adaptive scaled gradient projection methods for Stiefel manifold constrained optimization
• Riemannian optimization with a preconditioning scheme on the generalized Stiefel manifold
• scientific article; zbMATH DE number 2130662
• Global optimization on Stiefel manifolds -- an interesting results of discretization
• Simple algorithms for optimization on Riemannian manifolds with constraints
• Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
• Some global optimization problems on Stiefel manifolds

zbMATH Keywords

optimizationorthogonality constraintStiefel manifoldfeasibilitylow-rank correlation matrixadaptive nonmonotone line searchBarzilai-Borwein-like methodheterogeneous quadratic functionsKohn-Sham total energy minimizationsphere constraintupdate schemes

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Manifolds and measure-geometric topics (49Q99)

Cites Work

• KSSOLV—a MATLAB toolbox for solving the Kohn-Sham equations
• The university of Florida sparse matrix collection
• A feasible method for optimization with orthogonality constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized power method for sparse principal component analysis
• Title not available (Why is that?)
• The Geometry of Algorithms with Orthogonality Constraints
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• Title not available (Why is that?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming
• Optimization theory and methods. Nonlinear programming
• A constrained optimization algorithm for total energy minimization in electronic structure calculations
• The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem
• Two-Point Step Size Gradient Methods
• Rank reduction of correlation matrices by majorization
• A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization
• Efficient rank reduction of correlation matrices
• A generalized solution of the orthogonal Procrustes problem
• A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
• On Augmented Lagrangian Methods with General Lower-Level Constraints
• A Nonmonotone Line Search Technique for Newton’s Method
• An Inexact Accelerated Proximal Gradient Method for Large Scale Linearly Constrained Convex SDP
• The cyclic Barzilai-–Borwein method for unconstrained optimization
• Extrema of sums of heterogeneous quadratic forms
• An inexact interior point method for \(L_{1}\)-regularized sparse covariance selection
• Numerical methods for large eigenvalue problems
• Feasible Barzilai–Borwein-like methods for extreme symmetric eigenvalue problems
• A Sequential Semismooth Newton Method for the Nearest Low-rank Correlation Matrix Problem
• Gradient methods with adaptive step-sizes
• New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds
• \(R\)-linear convergence of the Barzilai and Borwein gradient method
• A framework of constraint preserving update schemes for optimization on Stiefel manifold
• On the Barzilai and Borwein choice of steplength for the gradient method
• Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints
• On minimization on Stiefel manifolds
• Optimization algorithms exploiting unitary constraints
• Title not available (Why is that?)
• Projection-like retractions on matrix manifolds
• A Procrustes problem on the Stiefel manifold
• Quasi-Newton Methods on Grassmannians and Multilinear Approximations of Tensors
• A Trust Region Direct Constrained Minimization Algorithm for the Kohn–Sham Equation
• Adaptive two-point stepsize gradient algorithm
• An alternating variable method for the maximal correlation problem
• Some global optimization problems on Stiefel manifolds
• Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization
• Conjugate gradient algorithm for optimization under unitary matrix constraint
• Richtungsfelder und Fernparallelismus in \(n\)-dimensionalen Mannigfaltigkeiten
• Title not available (Why is that?)
• Steepest Descent Algorithms for Optimization Under Unitary Matrix Constraint

Cited In (49)

• A New First-Order Algorithmic Framework for Optimization Problems with Orthogonality Constraints
• Stochastic consensus dynamics for nonconvex optimization on the Stiefel manifold: Mean-field limit and convergence
• On the generalized essential matrix correction: an efficient solution to the problem and its applications
• A Conjugate Gradient Method for Electronic Structure Calculations
• Jacobi-type algorithms for homogeneous polynomial optimization on Stiefel manifolds with applications to tensor approximations
• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• Hypergraph Clustering Using a New Laplacian Tensor with Applications in Image Processing
• A communication-efficient and privacy-aware distributed algorithm for sparse PCA
• A Block Lanczos Method for Large-Scale Quadratic Minimization Problems with Orthogonality Constraints
• A collection of efficient retractions for the symplectic Stiefel manifold
• Solving the discrete Euler-Arnold equations for the generalized rigid body motion
• Convergence and worst-case complexity of adaptive Riemannian trust-region methods for optimization on manifolds
• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• First order optimality conditions and steepest descent algorithm on orthogonal Stiefel manifolds
• Nonmonotone inexact restoration approach for minimization with orthogonality constraints
• Orthogonal nonnegative matrix factorization problems for clustering: a new formulation and a competitive algorithm
• A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron
• A brief introduction to manifold optimization
• A competitive optimization approach for data clustering and orthogonal non-negative matrix factorization
• On matrix exponentials and their approximations related to optimization on the Stiefel manifold
• A framework of constraint preserving update schemes for optimization on Stiefel manifold
• Exact Penalty Function for $\ell_{2,1}$ Norm Minimization over the Stiefel Manifold
• Multiple graphs clustering by gradient flow method
• Riemannian conjugate gradient methods for computing the extreme eigenvalues of symmetric tensors
• Generalized left-localized Cayley parametrization for optimization with orthogonality constraints
• Gradient Flow Based Kohn--Sham Density Functional Theory Model
• An Eigenvalue-Based Method for the Unbalanced Procrustes Problem
• A Filter Active-Set Algorithm for Ball/Sphere Constrained Optimization Problem
• Implicit steepest descent algorithm for optimization with orthogonality constraints
• The abstract Laplacian tensor of a hypergraph with applications in clustering
• Orthogonal canonical correlation analysis and applications
• An alternate gradient method for optimization problems with orthogonality constraints
• Nonconvex and nonsmooth optimization with generalized orthogonality constraints: an approximate augmented Lagrangian method
• Adaptive Quadratically Regularized Newton Method for Riemannian Optimization
• Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization
• A Riemannian conjugate gradient method for optimization on the Stiefel manifold
• A class of smooth exact penalty function methods for optimization problems with orthogonality constraints
• Nonmonotone feasible arc search algorithm for minimization on Stiefel manifold
• The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning
• Optimization schemes on manifolds for structured matrices with fixed eigenvalues
• Delta invariant for Eulerian digraphs
• Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
• Practical gradient and conjugate gradient methods on flag manifolds
• A regularized Newton method for computing ground states of Bose-Einstein condensates
• A penalty-free infeasible approach for a class of nonsmooth optimization problems over the Stiefel manifold
• Non-monotone inexact restoration method for nonlinear programming
• Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints
• An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors

Uses Software

• SparseMatrix
• KSSOLV

This page was built for publication: A framework of constraint preserving update schemes for optimization on Stiefel manifold

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