Fast root finding algorithm for a special function

Question

My question follows from

Fast root finding for strictly decreasing function

I am a bit surprised from the above page that there is even no efficient root finding algorithm (RFA) for a strictly monotonic function. Consider $f: \mathbb R\to\mathbb R$ defined by $f(z)=\sum_{k=1}^n p_k y_k e^{z y_k} -x$, where $p_k>0$ for all $k=1,\ldots, n\ge 2$. Assume further $y_1<y_2<\cdots<y_n$, and there exists a root $z_*$ for $f$, i.e. $f(z_*)=0$. Then it follows from the assumptions that $f$ is strictly increasing and thus $z^*$ is unique. My concern is to find a numerical approximation of $z^*$.

A straightforward computation yields that

$$f'(z)=\sum_{k=1}^n p_k y_k^2 e^{z y_k}~>~0,\quad \mbox{for all } z\in\mathbb R.$$

Is there any competitive computational method designed for $f$? Comments or remarks are highly appreciated!

PS: My first attempt is to apply Newton's method. Actually, it is easy to remark that

1. if $y_1\ge 0$, then $f$ is convex;
2. if $y_n\le 0$, then $f$ is concave;

For these two cases, I think Newton's method may work. As for $y_1< 0<y_n$, I think it holds $\inf_{z\in\mathbb R}f'(z)>0$.

Answer 1

Before any algorithm is applied, I recommend rescaling by letting $t=e^z$ and considering $t\in(0,\infty)$. This will make the function more "linear", which will likely prove to be beneficial. If the root is very large, it may even be beneficial to take the log of the function to make it even more linear. If $y_k$ are integers (I assume they are positive since $f$ is supposed to be increasing), then you end up with a polynomial in $t$, of which there are many root-finding algorithms for.

The algorithm fedja mentions in the comments is known as the Newt-safe algorithm. Oscar Veliz has a nice explanation of the method on YouTube. Asymptotically the convergence is the same as Newton's method. The only difference is that it's "safe" to use, provided you have a bound on $z^\star$. A simple bound can be obtained by requiring all terms be greater (less) than $x/n$.

Although I do not think there should be any issues with Newt-safe for this problem, since it is increasing and convex, some other algorithms such as Brent's method or Chandrupatla's method may be of interest to you. Unlike Newt-safe, they are more likely to use bisection for faster initial convergence when the function may not be very linear, causing something such as Newton's method to progress very slowly. They also require no evaluation of the derivative, which, if $n$ is very large, may save enough time per iteration to be faster than Newt-safe.