Show that the exact step length in the line search

Question

Given a positive definite matrix Q, consider the steepest descent method with exact line search for the quadratic function:

$$f(x) = \frac{1}{2}x^TQx + q^tx-\beta $$

with

$$x^{k+1} = x^k +\alpha_ks^k, s^k= - \nabla f(x^k), a_k=argmin_{\alpha > 0}f(x^k+\alpha s^k)$$

Show that $$\alpha_k = \frac {-\nabla f(x^k)^Ts^k}{(s^k)^TQs^k}$$

The only idea I have for solving this is to plug $x^k+\alpha s^k$ into $f$, and taking the gradient and hoping this equals the second definition of $\alpha_k$ .

So from my understanding I have to find the derivative of $$ \frac{1}{2}(x^k +\alpha s^k)^TQ(x^k +\alpha s^k) + q^t(x^k +\alpha s^k)-\beta $$

And set it to equal $0$ and isolate for $\alpha$, can anyone give me any tips as to how to differentiate involving a Matrix?

I'm confused by $argmin_{ \alpha > 0}$ there is no a in the second definition of $\alpha_k$ so do I assum a = 1? — 73est, Nov 02 '16 at 18:38
$\operatorname{arg min}_{\alpha > 0}$ means finding the (positive) minimizer $\alpha$ of the term that follows. — user251257, Nov 02 '16 at 18:39
What do you mean that follows. So the positive $\alpha$ that will minimize $f(x^k + \alpha s^k)$? — 73est, Nov 02 '16 at 18:47
yes. just like you said, differentiate $g_k(\alpha) = f(x^k + \alpha s^k)$ and find it's zero. — user251257, Nov 02 '16 at 18:49
So how does $\frac{1}{2}( x^k+\alpha s^k)^TQ(x^k+\alpha s^k)$ distribute and differentiate for example. The transposes are confusing me. — 73est, Nov 02 '16 at 18:58
So would I get $\frac{1}{2} Q( (x^k)^T(x^k)+\alpha (x^k)^T (s^k) +\alpha (x^k) (s^k)^T + \alpha^2 (s^k)^T (s^k))?$ — 73est, Nov 02 '16 at 19:07

score 1 · Answer 1 · answered May 06 '22 at 07:27

\begin{align} f\big(\boldsymbol x^{k+1} \big) = f\big(\boldsymbol x^k + \alpha_k \boldsymbol s^{k}\big) &= \frac12 \big(\boldsymbol x^k + \alpha_k \boldsymbol s^{k}\big)^T Q \big(\boldsymbol x^k + \alpha_k \boldsymbol s^{k}\big) + \boldsymbol q^T \big(\boldsymbol x^k + \alpha_k \boldsymbol s^{k}\big) -\beta\\ &= \frac12 \big(\boldsymbol x^k\big)^T Q \boldsymbol x^k + \frac12 \alpha_k^2 \big(\boldsymbol s^{k}\big)^T Q \boldsymbol s^{k} + \alpha_k \big( \boldsymbol s^k \big)^T Q \boldsymbol x^{k} + \boldsymbol q^T \boldsymbol x^k + \alpha_k\boldsymbol q^T \boldsymbol s^{k} -\beta \\ &= f\big(\boldsymbol x^k \big) + \frac12 \alpha_k^2 \big(\boldsymbol s^{k}\big)^T Q \boldsymbol s^{k}+ \alpha_k \big( \boldsymbol s^k \big)^T Q \boldsymbol x^{k} + \alpha_k \big( \boldsymbol s^{k}\big)^T \boldsymbol q\\ &= f\big(\boldsymbol x^k \big) + \frac12 \alpha_k^2 \big(\boldsymbol s^{k}\big)^T Q \boldsymbol s^{k}+ \alpha_k \big( \boldsymbol s^k \big)^T \Big[Q \boldsymbol x^{k} + \boldsymbol q\Big] =: g(\alpha_k) \end{align}

Assuming a fixed $\boldsymbol x^{k}$, $g(\alpha_k) $ is essentially a univariate, scalar parabola with unique minimum (recall that this is what we want) at $g'(\alpha_k) = 0$. Performing the derivative, one obtains

\begin{align} 0 &\overset{!}{=} \alpha_k \big( \boldsymbol s^k \big)^T Q \boldsymbol s^{k}+ \big( \boldsymbol s^k \big)^T \Big[Q \boldsymbol x^{k} + \boldsymbol q\Big] \\ \Rightarrow \alpha_k &= -\frac{ \big( \boldsymbol s^k \big)^T \Big[Q \boldsymbol x^{k} + \boldsymbol q\Big]}{\big( \boldsymbol s^k \big)^T Q \boldsymbol s^{k}}\end{align}

By definition of $f\big(\boldsymbol x^k\big)$, $$\nabla f\big(\boldsymbol x^k\big) = Q \boldsymbol x^k + \boldsymbol q$$ and thus \begin{align} \alpha_k &= -\frac{ \big( \boldsymbol s^k \big)^T \nabla f\big(\boldsymbol x^k\big)}{\big( \boldsymbol s^k \big)^T Q \boldsymbol s^{k}} = -\frac{ \nabla f\big(\boldsymbol x^k\big)^T \boldsymbol s^k }{\big( \boldsymbol s^k \big)^T Q \boldsymbol s^{k}} \end{align} as desired.

Show that the exact step length in the line search

1 Answers1

Linked