A feasible method for optimization with orthogonality constraints

• 成果类型: Article
• 署名作者: Wen, Zaiwen; Yin, Wotao
• 署名单位: Shanghai Jiao Tong University; Shanghai Jiao Tong University; Rice University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0584-1
• 发表日期: 2013
• 页码: 397-434
• 关键词: semidefinite programs; rank reduction; minimization; algorithm; DECOMPOSITION; formulation; barzilai; matrices; FLOWS

摘要

Minimization with orthogonality constraints (e.g., X-inverted perpendicular X = I) and/or spherical constraints (e. g., parallel to x parallel to(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 apply the Cayley transform-a Crank-Nicolson-like update scheme-to preserve the constraints and based on it, develop curvilinear search algorithms with lower flops 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 the quadratic assignment problem, a gap 0.842% to the best known solution on the largest problem tai256c in QAPLIB can be reached in 5 min on a typical laptop.