Optimization and Systems Theory Seminar
Friday December 4, 2009, 11.00-12.00, Room 3733, Lindstedtsvägen 25
Anders Forsgren, Optimization and Systems Theory, Department of Mathematics, KTH
E-mail: andersf@kth.se
A sufficiently exact inexact Newton step based on
reusing matrix information
Newton's method is a classical method for solving a nonlinear
equation. We derive inexact Newton steps that lead to an
inexact Nwton method, applicable near a solution. The method is
based on solving for a fixed Jacobian during p
consecutive iterations. One such p-cycle
requires 2^p-1 solves with the fixed Jacobian. If matrix
factorization is used, it is typically more computationally
expensive to factorize than to solve, and we envisage that the
proposed inexact method would be useful as the iterates
converge. The inexact method is shown to be p-step convergent with
Q-factor 2^p under standard assumptions where Newton's method
has quadratic rate of convergence. The method is thus sufficiently
exact in the sense that it mimics the convergence rate of Newton's
method. It may interpreted as a way of performing iterative
refinement by solving the linear subproblem
sufficiently exactly by a simplified Newton method. The method is
contrasted to a simplified Newton method, where it is known that a
cycle of 2^p-1 iterations gives the same type of convergence. We
present some numerical results and also discuss how this method
might be used in the context of interior methods for linear
programming.
Calendar of seminars
Last update: November 30, 2009.