Optimization Online


All roads lead to Newton: Feasible second-order methods for equality-constrained optimization

P.-A. Absil(absil***at***inma.ucl.ac.be)
Jochen Trumpf(Jochen.Trumpf***at***anu.edu.au)
Robert Mahony(Robert.Mahony***at***anu.edu.au)
Ben Andrews(Ben.Andrews***at***anu.edu.au)

Abstract: 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.

Keywords: Feasibly-projected sequential quadratic programming (FP-SQP); equality-constrained optimization; Riemannian manifold; Riemannian Newton method; sequential Newton method; retraction; osculating paraboloid; second-order correction; second fundamental form; Weingarten map

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Technical Report UCL-INMA-2009.024, Departement d'ingenierie mathematique, UCLouvain, Belgium.

Download: [PDF]

Entry Submitted: 08/31/2009
Entry Accepted: 08/31/2009
Entry Last Modified: 08/31/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society