# A good starting position for maximizing a function with Newton-Raphson / Halley's method

I'm attempting to find the maximum of this function:

\begin{align*} h(\mathbf{t}) = -\left\{\sum_{i=1}^{n}\lambda_i e^{\boldsymbol{\theta}_i^\intercal \mathbf{t}}\right\} + \boldsymbol{\alpha}^\intercal \mathbf{t} - \frac{1}{2}\mathbf{t}^\intercal \Gamma \mathbf{t} \end{align*} where $\lambda_i \ge 0$ and $\Gamma$ is symmetric, positive definite (this guarantees $h$ is everywhere concave, and so a unique max exists). I plan to find the solution via Newton-Raphson / Halley's method, which require a sufficiently close starting point $t_0$. If we analyze the derivative, \begin{align*} \nabla h(\mathbf{t}) = -\left\{\sum_{i=1}^{n}\lambda_i \boldsymbol{\theta}_ie^{\boldsymbol{\theta}_i^\intercal \mathbf{t}}\right\} + \boldsymbol{\alpha} - \Gamma \mathbf{t} \end{align*} Now, if $n = 1$, then it turns out the solution is (based off some help from a previous Overflow post): \begin{align*} \widetilde{\mathbf{t}} = \Gamma^{-1}\boldsymbol{\alpha} - \frac{W(\lambda\boldsymbol{\theta}^\intercal\Gamma^{-1}\boldsymbol{\theta} e^{\boldsymbol{\theta}^\intercal \Gamma^{-1}\boldsymbol{\alpha}})}{\boldsymbol{\theta}^\intercal\Gamma^{-1}\boldsymbol{\theta}}\Gamma^{-1}\boldsymbol{\theta} \end{align*} where $W$ is the lambert $W$ function along the zero branch, for which there are great initial approximations for.

I tried adapting the strategy in the above paper to my case, but couldn't proceed further. Please advise a quick, dirty initial approximation to my objective function.

• Hi Tom, I've come across effectively the same optimization problem in my own work, did you ever find a satisfactory solution? – Thoth Jun 29 at 22:09

You can try applying gradient ascent method and run it for a few iterations to get an initial guess for $\mathbf{t}$. As the function is strongly concave, the gradient ascent is sure to converge to its unique global maxima, and so running it for a few iterations will produce a good approximation for the true global maxima. Actually, by analyzing the gradient ascent steps, you can estimate how many iterations you need to run it for the approximation to meet a prespecified approximation error required for the Newton-Raphson/Halley method to succeed. See this for such a discussion.