Optimization Online


A Feasible method for Optimization with Orthogonality Constraints

Zaiwen Wen (zw2109***at***sjtu.edu.cn)
Wotao Yin (wotao.yin***at***rice.edu)

Abstract: Minimization with orthogonality constraints (e.g., $X^\top X = I$) and/or spherical constraints (e.g., $\|x\|_2 = 1$) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these difficulties, we propose to use a Crank-Nicholson-like update scheme to preserve the constraints and based on it, develop curvilinear search algorithms with lower per-iteration cost compared to those based on projections and geodesics. The efficiency of the proposed algorithms is demonstrated on a variety of test problems. In particular, for the maxcut problem, it exactly solves a decomposition formulation for the SDP relaxation. For polynomial optimization, nearest correlation matrix estimation and extreme eigenvalue problems, the proposed algorithms run very fast and return solutions no worse than those from their state-of-the-art algorithms. For quadratic assignment problem, a gap 0.842\% to the best known solution on the largest problem ``tai256c" in QAPLIB can be reached in 5 minutes on a typical laptop.

Keywords: Orthogonality constraint, spherical constraint, Stiefel manifold, Cayley transformation, curvilinear search, polynomial optimization, maxcut SDP, nearest correlation matrix, eigenvalue and eigenvector, invariant subspace, quadratic assignment problem

Category 1: Nonlinear Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: @TECHREPORT{OptM-Wen-Yin-2010, author = {Wen, Zaiwen and Yin, Wotao}, title = {A Feasible method for Optimization with Orthogonality Constraints}, institution = {Rice University}, year = {2010} }

Download: [PDF]

Entry Submitted: 11/08/2010
Entry Accepted: 11/08/2010
Entry Last Modified: 11/15/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society