Optimization problems with orthogonality constraints have many applications in science and engineering. In these applications, one often deals with large-scale problems which are ill-conditioned near the optimum. Consequently, there is a need for first-order optimization methods which deal with orthogonality constraints, converge rapidly even when the objective is not well-conditioned, and are robust.

In this dissertation we develop a generalization of Nesterov's accelerated gradient descent algorithm for optimization on the manifold of orthonormal matrices. The performance of the algorithm scales with the square root of the condition number. As a result, our method outperforms existing state-of-the-art algorithms on large, ill-conditioned problems. We discuss applications of the method to electronic structure calculations and to the calculation of compressed modes.