3
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\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.