2
$\begingroup$

Is there any algorithm (or tricks) for rootfinding to take advantages of automatic differentiation (AD)?

Rootfinding algorithms typically solve $$ \mathbf{f}(\mathbf{y}) = \mathbf{0} $$ where $\mathbf{f}:\mathbb{R}^n\rightarrow\mathbb{R}^n$ and $\mathbf{y}:\mathbb{R}^n$.

Newton's method is not applicable in my case because the whole Jacobian does not fit in my memory while Broyden's method (one of the most popular method) usually doesn't converge.

I wonder if there's any way to take advantage of automatic differentiation in making root finder algorithm more stable or faster to converge (e.g. initializing the inverse of Jacobian with AD maybe?).

$\endgroup$
5
  • 1
    $\begingroup$ How large is $n$? Is the Jacobian sparse or dense? $\endgroup$ – Brian Borchers Sep 28 '20 at 14:46
  • 1
    $\begingroup$ $n$ is typically 10^4-10^5 and constructing the full Jacobian is expensive. I'm not sure if it's sparse or dense, but the AD engine can provide the vector-Jacobian and Jacobian-vector product automatically. $\endgroup$ – Firman Sep 28 '20 at 14:55
  • $\begingroup$ I haven't used AD, but it sounds like you can form the entries of the Jacobian on the fly as they are needed. If this is true, you could use this to express the Jacobian as an operator on a vector, which would let you use "matrix-free" iterative solver methods that rely on matrix-vector products (conjugate gradient, GMRES, etc). Not sure if this is what @BrianBorchers meant by "interactive methods" $\endgroup$ – Charlie S Sep 28 '20 at 17:55
  • $\begingroup$ Sorry for the typo. "interactive" should have been "iterative" in my answer. $\endgroup$ – Brian Borchers Sep 28 '20 at 18:01
  • 2
    $\begingroup$ @BrianBorchers Didn't mean to be snooty, I actually googled "interactive methods" as I assumed it was some state of the art concept! $\endgroup$ – Charlie S Sep 28 '20 at 19:28
1
$\begingroup$

There's a good discussion of globalization strategies for Newton's method root finding in Numerical Methods for Unconstrained Optimization and Nonlinear Equations by J. E. Dennis, Jr. and Robert B. Schnabel. See section 6.5 in particular.

Dennis and Schnabel advocate treating the problem of finding a root of $f(p)=0$ as a nonlinear least squares problem:

$\min \sum_{i=1}^{n} f_{i}(p)^{2}$

You can apply Newton's method for minimization of this least squares problem with a globalization strategy (line search, trust region, Levenberg-Marquardt, etc.) These globalization strategies make sense when the problem is converted to least squares form. You could solve the Newton's method equations in each iteration using an iterative method based on the Jacobian-vector multiplications provided by your AD tool. For example, the Newton-Krylov method uses a Krylov subspace method to solve the equations.

Another approach would be to directly solve the nonlinear least-squares problem using an iterative method for unconstrained nonlinear minimization such as conjugate gradients, limited memory BFGS, etc. All of these require gradient computations, which in turn boil down to multiplying the Jacobian times $f(p)$. Your AD tool should be able to help with that.

$\endgroup$

Your Answer

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

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