1
$\begingroup$

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.
$\endgroup$

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.