7

Suppose we want to minimize some convex functional $J(u)$ where $u$ lives in some Banach space $V$. The classical Newton method

$$\mathrm d^2J(u_n)(u_{n + 1} - u_n) = -\mathrm dJ(u_n)$$

can be viewed as an explicit Euler discretization of the dynamical system

$$\tau\;\mathrm d^2J(u)\frac{\mathrm du}{\mathrm dt} = -\mathrm dJ(u),$$

that takes a constant timestep $\tau$ at every step. You can think of a primitive damped Newton method as taking a timestep that is some fraction of $\tau$, and a globally-convergent Newton line search method as using a variable timestep that is tuned to make sure that the objective decreases. Several papers have remarked on this (see below).

Are there improved, practical solution methods based on viewing Newton's method as a dynamical system? For example, what happens if, instead of doing a line search at every iteration, you were to use a classical adaptive Runge Kutta method with stepsize control like RK-1/2 or similar? More generally, is there some respect in which this dynamical systems viewpoint is practically relevant, or is it just a mathematical curiosity?

References:

Daniel Shapero
  • 10,263
  • 1
  • 28
  • 59
  • it's no longer relevant for practical solutions, but i remember a professor once told me that they used to solve nonlinear systems by realising the continuous system and letting it converge. – Thijs Steel May 04 '21 at 16:15
  • 2
    @ThijsSteel That would be a pseudo-timestepping approach to solving nonlinear problems. (As in "pseudo-time" stepping, not pseudo-"time stepping" -- it's an artificial time variable.) – Wolfgang Bangerth May 04 '21 at 17:14
  • 2
    I was involved in using an analog computing chip that used a continuous version of Newton's method Huang, Y., Guo, N., Seok, M., Tsividis, Y., Mandli, K., & Sethumadhavan, S. (2017). Hybrid analog-digital solution of nonlinear partial differential equations (pp. 665–678). https://doi.org/10.1145/3123939.3124550. – Kyle Mandli May 04 '21 at 17:55
  • Thanks @KyleMandli, the citations there pointed me in the right direction! Also, that paper is totally insane and wonderful. – Daniel Shapero May 04 '21 at 21:25
  • Was a fun paper to work on! – Kyle Mandli May 04 '21 at 23:20

1 Answers1

5

No, it is not possible to use higher-order ODE integration methods on the Newton dynamical system to do better than vanilla Newton with some globalization strategy. Brezinski (2001) gives a negative result in Theorem 2 and the discussion after it, showing that only the explicit Euler scheme has superlinear convergence.

Daniel Shapero
  • 10,263
  • 1
  • 28
  • 59