I wish to minimize the quantity $$W=1/2x^TAx-x^Tg(y)$$ with respect to $x$ and $y$, which are vectors of unknowns. $A$ is a sparse square symmetric positive definite matrix and $g(y)$ is a vector with non-linear dependence on $y$. Everything is real-valued. Finding $x$ given $y$ is straight forward: $$Ax-g=0$$ $$x=A^{-1}g$$ To find the optimal value of $y$, I am trying to use gradient descent (I have analytic expressions for the derivatives of $g$):

$$\nabla W(y)=-\nabla g^Tx - g^T \nabla x$$

  1. Is the correct approach to substitute in an expression for $x$, and try the usual gradient descent tools (line searches, etc) to update $y$? $$\nabla W(y)=-\nabla g^TA^{-1}g - g^T A^{-1}\nabla g=-2\nabla g^TA^{-1}g$$
  2. Because I can calculate the derivatives of $g$ quite easily, I would like to try to use this information for Newton's method, or something similar. I can calculate the components of $\nabla^2g$, which I suppose is an order-3 tensor. However, I am unsure how to apply this object to a matrix or vector. I know there must be some contraction that doesn't require me to form the tensor explicitly. Is this block matrix expression correct? $$(\nabla (\nabla g)^T)x= \left( \begin{matrix} \nabla^2_1g^T\ x & \nabla^2_2g^T\ x \dots \nabla^2_kg^T\ x \end{matrix} \right)$$ where column k is $\nabla^2_kg^T\ x=(\frac{\partial }{\partial y_k}\nabla g^T)x$. The dimensions seem to be compatible, though I can't tell if the simplicity is the product of my wishful thinking.

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.