Analysis of Sequential Quadratic Programming through the Lens of Riemannian Optimization

Abstract

We prove that a "first-order" Sequential Quadratic Programming (SQP) algorithm for equality constrained optimization has local linear convergence with rate $(1-1/{\kappa }_R{)}^k$, where ${\kappa }_R$ is the condition number of the Riemannian Hessian, and global convergence with rate $k^{-1/4}$. Our analysis builds on insights from Riemannian optimization -- we show that the SQP and Riemannian gradient methods have nearly identical behavior near the constraint manifold, which could be of broader interest for understanding constrained optimization.