0
$\begingroup$

Let be $$f(x) = \frac{1}{2}x^TAx +b^Tx$$

where $A$ is a symmetric positive definite matrix and $b \in \mathbb{R}^d$. We know that such a function is systematically twice (and even infinitely) differentiable with

$$ \begin{cases} \nabla f(x) = Ax + b \\ \nabla^2 f(x) = A \\ \end{cases} $$

Let us note $g_k:=\nabla f(x^{(k)})$, so that here $g_k = Ax^{(k)}+b$. In this case, the optimal step size in direction $-g_k$ can be obtained analytically by solving

$$ \begin{align} 0 &= \frac{d}{d\lambda}f(x^{(k)}-\lambda g_k)\tag{1}\label{eq1} \\ &= \langle A(x^{(k)}-\lambda g_k) + b, - g_k\rangle\tag{2}\label{eq2} \\ &= - \|g_k\|^2 + \lambda \langle Ag_k, g_k\rangle\tag{3}\label{eq3}\ \end{align} $$

Here are my questions:

  1. how do you get from (\ref{eq1}) to (\ref{eq2}):

if $\nabla f(x) = Ax + b$ then $\frac{d}{d\lambda}f(x^{(k)}-\lambda g_k) = A(x^{(k)}-\lambda g_k) + b$. However, how do you get the dot product notation $\langle\cdot, \cdot \rangle$ notation as well as the additional $-g_k$

  1. how do you get from (\ref{eq2}) to (\ref{eq3})
$\endgroup$
0
$\begingroup$

Q1

(1) to (2) is followed from the below property of a multivariate function$${d\over dt}f(u+t v)=\nabla f(u+t v)^T\cdot v$$which has a simple and elementary proof using only the fact that $$f(u+t v)=f\Big(u_1+tv_1,u_2+tv_2,\cdots,u_n+tv_n\Big)$$

proof

Note that using calculus:$${d\over dt }f(u+t v){=\sum_{k=1}^n {\partial f\over \partial x_k}\Bigg|_{x=u+tv}\cdot {\partial u_k+tv_k\over \partial t}\\=\sum_{k=1}^n {\partial f\over \partial x_k}\Bigg|_{x=u+tv}\cdot v_k\\=\nabla f(u+t v)^T\cdot v}$$

Q2

(2) to (3) is followed so easily$$\langle A(x^{(k)}-\lambda g_k) + b, - g_k\rangle{=\langle Ax^{(k)}-\lambda A g_k + b, - g_k\rangle\\=\langle g_k-\lambda A g_k , - g_k\rangle\\=-||g_k||^2+\lambda \langle Ag_k,g_k\rangle}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you for your comment @Mostafaayaz. Q2 is clear. I also understand $f(u+t v)=f\Big(u_1+tv_1,u_2+tv_2,\cdots,u_n+tv_n\Big)$. However, I still don't understand how this proves that ${d\over dt}f(u+t v)=\nabla f(u+t v)^T\cdot v$. Could you recommend a specific reference? $\endgroup$ – ecjb Mar 25 '19 at 6:31

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.