Paper ID sheet UCLINMA2009.024
 Title

All roads lead to Newton: Feasible secondorder methods for equalityconstrained optimization
 Authors
 P.A. Absil, Jochen Trumpf, Robert Mahony, Ben Andrews
 Abstract

This paper considers the connection between the intrinsic
Riemannian Newton method and other more classically inspired
optimization algorithms for equalityconstrained optimization
problems. We consider the feasiblyprojected sequential quadratic
programming (FPSQP) 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 secondorder
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
nondegenerate equality constrained optimisation problems.
 Key words
 Feasiblyprojected sequential quadratic programming (FPSQP); equalityconstrained optimization; Riemannian manifold; Riemannian Newton method; sequential Newton method; retraction; osculating paraboloid; secondorder correction; second fundamental form; Weingarten map
 Status
 Technical report UCLINMA2009.024, registered 31 August 2009
 Download

[Home]