We prove that a "first-order" Sequential Quadratic Programming (SQP) algorithm for equality constrained optimization has local linear convergence with rate @math , where @math is the condition number of the Riemannian Hessian, and global convergence with rate @math . 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.
Though analyses are well-established for both the Riemannian and the SQP approach (even by the same author in @cite_3 for the Riemannian approach and @cite_6 for the SQP approach), the connection between them did not receive much attention until the past 10 years. Such connection is re-emphasized in @cite_4 : the authors pointed out that the feasibly-projected sequential quadratic programming (FP-SQP) method in @cite_7 gives the same update as the Riemannian Newton update. used this connection to provide a framework for selecting a preconditioning metric for Riemannian optimization, in particular when the Riemannian structure is sought on a quotient manifold. However, these connections are established for second-order methods between the Riemannian and the SQP approaches, and such connection for first-order methods are not---we believe---explicitly pointed out yet.
@cite_7 @cite_4 @cite_6 @cite_3
2107502531 2131901022 1974824893
An algorithm for smooth nonlinear constrained optimization problems is described, in which a sequence of feasible iterates is generated by solving a trust-region sequential quadratic programming (SQP) subproblem at each iteration and by perturbing the resulting step to retain feasibility of each iterate. By retaining feasibility, the algorithm avoids several complications of other trust-region SQP approaches: the objective function can be used as a merit function, and the SQP subproblems are feasible for all choices of the trust-region radius. Global convergence properties are analyzed under various assumptions on the approximate Hessian. Under additional assumptions, superlinear convergence to points satisfying second-order sufficient conditions is proved. This paper considers the connection between the intrinsic Riemannian Newton method and other more classically inspired optimization algorithms for equality-constrained optimization problems. We consider the feasibly-projected sequential quadratic programming (FP-SQP) method and show that it yields the same update step as the Riemannian Newton, subject to a minor assumption on the choice of multiplier vector. We also consider Newton update steps computed in various ‘natural’ local coordinate systems on the constraint manifold and find simple conditions that guarantee that the update step is the Riemannian Newton update. In particular, we show that this is the case for projective local coordinates, one of the most natural choices that have been proposed in the literature. Finally we consider the case where the full constraints are approximated to simplify the computation of the update step. We show that if this approximation is good at least to second-order then the resulting update step is the Riemannian Newton update. The conclusion of this study is that the intrinsic Riemannian Newton algorithm is the archetypal feasible second order update for non-degenerate equality constrained optimisation problems. To generalize the descent methods of unconstrained optimization to the constrained case, we define intrinsically the gradient field of the objective function on the constraint manifold and analyze descent methods along geodesics, including the gradient projection and reduced gradient methods for special choices of coordinate systems. In particular, we generalize the quasi-Newton methods and establish their superlinear convergence; we show that they only require the updating of a reduced size matrix. In practice, the geodesic search is approximated by a tangent step followed by a constraints restoration or by a simple arc search again followed by a restoration step.