1
$\begingroup$

I would like to find the roots of a multi-variate, vector-valued, non-linear, real function $ \vec f(\vec x)$. If the system has multiple solutions (I haven't seen that case yet though its possible), I don't care as long as I have some solution that works. The system has $n$ variables and $n$ equations, of which the derivatives and second derivatives are well defined. I have successfully implemented the Newton-Raphson method which leads to convergence for many scenarios and initial conditions, but not all. In one particular scenario, I know there is a valid solution but the Newton-Raphson algorithm can't seem to find that -- or any -- solution (iterates forever).

I have implemented this method with the Eigen linear algebra library with a customized multi-precision scalar (MPIR -- a fork of GMP/MPFR). As such, I don't think floating point precision is the issue since I have as much precision as I want. Likewise, I have tried many different initial guesses, all of which have failed. Not saying there isn't a better way to feed in an initial guess, but I haven't found it yet.

One avenue I am exploring is to extend the idea of the Newton-Raphson method to include second derivative information. Specifically, I would like to solve for $\Delta \vec x$ in the following system of equations:

$$f_i +\sum_j \frac{\partial f_i}{\partial x_j} \Delta x_j + \frac{1}{2} \sum_j\sum_k \frac{\partial^2 f_i}{\partial x_j \partial x_k} \Delta x_j \Delta x_k = 0$$

This is a Taylor series truncated at the quadratic term. I use this notation since the tensor notation tends to confuse me more than help. Anyway, I am painfully aware that this a nonlinear system of quadratic equations. I have investigated a technique called Relinearization without success. Does anyone have an idea on how to approach this system of quadratic equations? Is there another method that utilizes this second derivative information to improve on the Newton-Raphson method?

Another stupid idea is to reformulate the problem from a root-finding exercise into a minimization problem, in which the norm of $ \vec f(\vec x)$ is minimized. The way I see it, a minimum of the squared norm is a root, correct?

$$ \frac{\partial}{\partial \Delta x_l} [|f^2| + 2 \sum_i \sum_j\ f_i \frac{\partial f_i}{\partial x_j}\Delta x_j + \sum_i \sum_j \sum_k (\frac{\partial f_i}{\partial x_j}\frac{\partial f_i}{\partial x_k}+\frac{\partial^2 f_i}{\partial x_j \partial x_k}) \Delta x_j \Delta x_k] =0 $$

Because I am assuming each of the $\Delta x_i$ are independent: $$\frac{\partial \Delta x_i}{\partial \Delta x_l} = \delta_{il} $$

Because the terms in the triple summation are symmetric with respect to the summation indices, the following should be true. (The 2's are left in for clarity).
$$ 2 \sum_i f_i \frac{\partial f_i}{\partial x_l}\ + 2 \sum_i \sum_j (\frac{\partial f_i}{\partial x_j}\frac{\partial f_i}{\partial x_l}+\frac{\partial^2 f_i}{\partial x_j \partial x_l}) \Delta x_j =0 $$

This formulation gives me a problem in the form of $Ax=b$, with $n$ unknowns and $n$ equations, which I can solve. However, I can't get any semblance of convergence. I may be doing something stupid like calculating the second derivatives incorrectly, but think there's something else going on. Is this formulation correct? Is this doomed to not converge even in situations where the Newton-Raphson converged without a problem?

Thanks!

$\endgroup$
  • $\begingroup$ What is the value of $n$? Even with 2 variables, it is common for Newton's method to get lost wandering about. You should first perform a rough search of the landscape to find the likely regions containing a root, eg a bisection method. $\endgroup$ – Chrystomath Dec 7 '17 at 18:26
  • $\begingroup$ @MMS Thanks for your suggestion. I like that idea as I have very little confidence in my method of generating initial guesses. Not like it matters, but 'n' is a triangular number (1, 3, 6, 10, 15...). The most maddening aspect of this is that I can have fast convergence when n = 15, and no convergence after thousands of iterations when n = 6! I have not encountered a situation in which n = 3 fails. $\endgroup$ – Charlie S Dec 7 '17 at 18:47

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.