23 November 2010 / Accepted: 26 July 2012 / Published online: 29 August 2012 | Zaiwen Wen · Wotao Yin
The paper "A feasible method for optimization with orthogonality constraints" by Zaiwen Wen and Wotao Yin addresses the challenges of minimizing functions subject to orthogonality and spherical constraints. These constraints, such as \(X^\top X = I\) and \(\|x\|_2 = 1\), are common in various applications including polynomial optimization, combinatorial optimization, eigenvalue problems, and matrix rank minimization. The authors propose a novel approach using the Cayley transform, a Crank-Nicolson-like update scheme, to efficiently preserve these constraints. This method is compared with existing techniques based on projections and geodesics, showing lower computational costs. The proposed algorithms are demonstrated to be effective on a variety of test problems, including the maxcut problem, polynomial optimization, nearest correlation matrix estimation, and extreme eigenvalue problems. For the quadratic assignment problem, the algorithms achieve a gap of 0.842% to the best known solution on the largest problem "tai256c" in QAPLIB within 5 minutes on a typical laptop. The work is supported by grants from the National Science Foundation (NSF) and the National Natural Science Foundation of China (NSFC).The paper "A feasible method for optimization with orthogonality constraints" by Zaiwen Wen and Wotao Yin addresses the challenges of minimizing functions subject to orthogonality and spherical constraints. These constraints, such as \(X^\top X = I\) and \(\|x\|_2 = 1\), are common in various applications including polynomial optimization, combinatorial optimization, eigenvalue problems, and matrix rank minimization. The authors propose a novel approach using the Cayley transform, a Crank-Nicolson-like update scheme, to efficiently preserve these constraints. This method is compared with existing techniques based on projections and geodesics, showing lower computational costs. The proposed algorithms are demonstrated to be effective on a variety of test problems, including the maxcut problem, polynomial optimization, nearest correlation matrix estimation, and extreme eigenvalue problems. For the quadratic assignment problem, the algorithms achieve a gap of 0.842% to the best known solution on the largest problem "tai256c" in QAPLIB within 5 minutes on a typical laptop. The work is supported by grants from the National Science Foundation (NSF) and the National Natural Science Foundation of China (NSFC).