A feasible method for optimization with orthogonality constraints
- PDF / 587,620 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 225 Views
A feasible method for optimization with orthogonality constraints Zaiwen Wen · Wotao Yin
Received: 23 November 2010 / Accepted: 26 July 2012 / Published online: 29 August 2012 © Springer and Mathematical Optimization Society 2012
Abstract Minimization with orthogonality constraints (e.g., X X = I ) and/or spherical constraints (e.g., x2 = 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-ofthe-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.
The work of Z. Wen was supported in part by NSF DMS-0439872 through UCLA IPAM and NSFC grant 11101274. The work of W. Yin was supported in part by NSF grants DMS-07-48839 and ECCS-10-28790, and ONR Grant N00014-08-1-1101. Z. Wen (B) Department of Mathematics and Institute of Natural Sciences, Shanghai Jiaotong University, Shanghai, China e-mail: [email protected]; [email protected] W. Yin Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005, USA e-mail: [email protected]
123
398
Z. Wen, W. Yin
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 Mathematics Subject Classification (2010) 90C27 · 90C30
49Q99 · 65K05 · 90C22 · 90C26 ·
1 Introduction Matrix orthogonality constraints play an important role in many applications of science and engineering. In this paper, we consider optimization with orthogonality constraints: min
X ∈Rn× p
F(X ), s.t. X X = I,
(1)
where I is the identity matrix and F(X ) : Rn× p → R is a differentiable function. p The feasible set Mn := {X ∈ Rn× p : X X = I } is often referred to as the Stiefel manifold, which reduces to the unit-sphere manifold Spn−1 := {x ∈ Rn : x2 = 1} when p = 1. We also consider the generalized orthogonality constraints X ∗ M X = K , where X ∈ Cn× p , M ∈ Rn×n is a symmetric positive definite matrix, and K ∈ C p× p is a n
Data Loading...
