7
$\begingroup$

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:

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Commented May 4, 2021 at 16:15
  • 2
    $\begingroup$ @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.) $\endgroup$ Commented May 4, 2021 at 17:14
  • 2
    $\begingroup$ 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). doi.org/10.1145/3123939.3124550. $\endgroup$ Commented May 4, 2021 at 17:55
  • $\begingroup$ Thanks @KyleMandli, the citations there pointed me in the right direction! Also, that paper is totally insane and wonderful. $\endgroup$ Commented May 4, 2021 at 21:25
  • $\begingroup$ Was a fun paper to work on! $\endgroup$ Commented May 4, 2021 at 23:20

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.