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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.