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
2131901022 2139313686 2022144657 2768546550
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. This paper studies Newton-type methods for minimization of partly smooth convex functions. Sequential Newton methods are provided using local parameterizations obtained from **-Lagrangian theory and from Riemannian geometry. The Hessian based on the **-Lagrangian depends on the selection of a dual parameter g; by revealing the connection to Riemannian geometry, a natural choice of g emerges for which the two Newton directions coincide. This choice of g is also shown to be related to the least-squares multiplier estimate from a sequential quadratic programming (SQP) approach, and with this multiplier, SQP gives the same search direction as the Newton methods. Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality constraints (linear and nonlinear). We assume that first derivatives are available and that the constraint gradients are sparse. We discuss an SQP algorithm that uses a smooth augmented Lagrangian merit function and makes explicit provision for infeasibility in the original problem and the QP subproblems. SNOPT is a particular implementation that makes use of a semidefinite QP solver. It is based on a limited-memory quasi-Newton approximation to the Hessian of the Lagrangian and uses a reduced-Hessian algorithm (SQOPT) for solving the QP subproblems. It is designed for problems with many thousands of constraints and variables but a moderate number of degrees of freedom (say, up to 2000). An important application is to trajectory optimization in the aerospace industry. Numerical results are given for most problems in the CUTE and COPS test collections (about 900 examples). First-order methods have been popularly used for solving large-scale problems. However, many existing works only consider unconstrained problems or those with simple constraint. In this paper, we develop two first-order methods for constrained convex programs, for which the constraint set is represented by affine equations and smooth nonlinear inequalities. Both methods are based on the classic augmented Lagrangian function. They update the multipliers in the same way as the augmented Lagrangian method (ALM) but employ different primal variable updates. The first method, at each iteration, performs a single proximal gradient step to the primal variable, and the second method is a block update version of the first one. For the first method, we establish its global iterate convergence as well as global sublinear and local linear convergence, and for the second method, we show a global sublinear convergence result in expectation. Numerical experiments are carried out on the basis pursuit denoising and a convex quadratically constrained quadratic program to show the empirical performance of the proposed methods. Their numerical behaviors closely match the established theoretical results.