5
$\begingroup$

I am reading through the paper

In appendix A.3 Numerical entropy minimization, there is a derivation for dual problem. I am trying to understand how to find the gradient and hessian matrix for equation 92.

My education is not in mathematics and I have picked up math on the way. So, I am finding it hard to follow on how to derive the gradient and hessian matrices for optimization.

Edit: The following is from the paper:

enter image description here

$\endgroup$
  • $\begingroup$ It might be helpful to write the primal and dual problems in your question so people don't have to search through the paper. $\endgroup$ – littleO Dec 21 '16 at 3:20
  • $\begingroup$ I think that there is something wrong with the accented letters, in the equations (89), (90) ...in (88) it should be $x$ not $x'$, isn't it? $\endgroup$ – MattG88 Dec 24 '16 at 3:14
  • $\begingroup$ x being a column vector you have to have x' for matrix multiplication. $\endgroup$ – user1243255 Dec 24 '16 at 13:16
  • $\begingroup$ I think it's awesome when a question earns its own bounty in upvotes ;-) There should be a badge for that. $\endgroup$ – Michael Grant Dec 29 '16 at 15:42
4
+25
$\begingroup$

Ah, OK, I was finally able to look at the paper. Note that $$\mathcal{G}(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu)$$ For fixed values of $\lambda,\nu$, (90) gives us a formula for $x(\lambda,\nu)$ which attains that minimization. I'm going to adopt the author's slight abuse of notation and allow logarithms and exponentiation to be applied elementwise to vectors.

The paper talks about using the envelope theorem. In a convex case such as this, Danskin's theorem is a simpler and more powerful result. For our purposes, Danskin's theorem says this: whenever $\bar{x} = x(\lambda,\nu)$ is a unique minimizer of $\inf_x\mathcal{L}(x,\lambda,\nu)$, then $$\nabla \mathcal{G}(\lambda,\nu) = \nabla_{\lambda,\nu}\, \mathcal{L}(\bar{x},\lambda,\nu)$$ In English: to compute the partial derivatives of $\mathcal{G}$ with respect to $\lambda$ and $\nu$, we are allowed take the partial derivatives of $\mathcal{L}$ instead, and then substitute in $\bar{x}=x(\lambda,\nu)$ after that. We get to "pretend" $x$ is constant, even though its value does depend on $\lambda$ and $\nu$.

Using Danskin's theorem is much easier than trying to eliminate $x$ by substitution first. After all, the partial derivatives of $\mathcal{L}$ are obvious: $$\nabla_\lambda \mathcal{L}(x,\lambda,\nu) = Fx-f, \quad \nabla_\nu \mathcal{L}(x,\lambda,\nu) = Hx-h$$ Thus Danskin's theorem gives us an exceedingly simple result: $$\nabla_\lambda \mathcal{G}(\lambda,\nu) = F x(\lambda,\nu)-f, \quad \nabla_\nu \mathcal{G}(\lambda,\nu) = H x(\lambda, \nu)-h$$ where $x(\lambda,\nu)$ is given by (90) above. So the gradient is $$\nabla \mathcal{G}(\lambda,\nu) = \begin{bmatrix} \nabla_\lambda \mathcal{G} \\ \nabla_\nu \mathcal{G} \end{bmatrix} = \begin{bmatrix} F \\ H \end{bmatrix} e^{\log(p)-\vec{1}-F^T\lambda-H^T\nu} - \begin{bmatrix} f \\ h \end{bmatrix}$$ The Hessian follows with a little vector calculus: $$\nabla^2 \mathcal{G}(\lambda,\nu) = \begin{bmatrix} \nabla_{\lambda,\lambda} \mathcal{G} & \nabla_{\lambda,\nu} \mathcal{G} \\ \nabla_{\nu,\lambda} \mathcal{G} & \nabla_{\nu,\nu} \mathcal{G} \end{bmatrix} = -\begin{bmatrix} F \\ H \end{bmatrix} \mathop{\textrm{diag}}\left( e^{\log(p)-\vec{1}-F^T\lambda-H^T\nu}\right) \begin{bmatrix} F^T & H^T \end{bmatrix} $$

$\endgroup$
  • $\begingroup$ @littleO, we should have known this already... I had to do some Googling ;-) $\endgroup$ – Michael Grant Dec 29 '16 at 6:21
  • $\begingroup$ In equation ∇G(λ,ν)=∇λ,νF(x¯,λ,ν) what is F? I tried reading the wikipedia link but couldn't translate to English and further flow into your derivation. $\endgroup$ – user1243255 Dec 29 '16 at 20:40
  • $\begingroup$ Sorry, typo. It should be $\mathcal{L}$. $\endgroup$ – Michael Grant Dec 29 '16 at 20:41
  • $\begingroup$ Thanks for clarification. I was looking to understand derivation of Hessian also. Should I start a new thread for that or would you mind expanding on "The Hessian follows with a little vector calculus:". $\endgroup$ – user1243255 Dec 29 '16 at 20:58
  • $\begingroup$ Let me gently suggest that if that is a struggle then decoding papers like this is a bit premature. Or at least, you should be reading them with other references in hand! I would definitely suggest, for instance, The Matrix Cookbook. You don't need to digest the whole thing. This may sound like a cop-out on my part---it is; I don't think I can offer a sufficient tutorial in a reasonable amount of time, and I don't think this is the forum for it anyway. $\endgroup$ – Michael Grant Dec 29 '16 at 21:03

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.