Iterative Minimization lemma proof

[rayge]

Homework Statement

$f(x)$ is the function we want to minimize. Beyond being real-valued, there are no other conditions on it. (I'm surprised it's not at least continuous, but the book doesn't say that's a condition.) We choose the next $x^k$ through the relation $x^k = x^{k-1} + \alpha_{k}d^k$. We assume $d^k$ is a descent direction. That is, for small positive $\alpha$, $f(x^{k-1} + \alpha d^k)$ is decreasing.

Here's the lemma we want to prove:
When $x^k$ is constructed using the optimal $\alpha$, we have $\nabla f(x^k) \cdot d^k = 0$

The Attempt at a Solution

It's suggested in the book that we should differentiate the function $f(x^{k-1} + \alpha d^k)$ with respect to $\alpha$. My problem is that I don't know how to differentiate a function that isn't defined. My first guess went something like this, but I don't see how I'm any closer to a solution.

$$\frac{\partial}{\partial \alpha} f(x^{k-1} + \alpha d^k) = \frac{\partial}{\partial \alpha} f(x^k)$$
$$f'(x^{k-1} + \alpha d^k)d^k = f'(x^k)(0)$$
$$f'(x^{k-1} + \alpha d^k)d^k = 0$$

I'm really not looking for an answer, but if someone could point me to where I could learn about taking differentials of undefined functions that would be helpful. I'm guessing that somehow I can extract a gradient out of this, and a dot product, but I'm feeling pretty confused.

 

[Stephen Tashi]

Homework Statement

$f(x)$ is the function we want to minimize. Beyond being real-valued, there are no other conditions on it. (I'm surprised it's not at least continuous, but the book doesn't say that's a condition.)

If you're expected to differentiate $f$ it would have to be differentiable, hence continuous.

We choose the next $x^k$ through the relation $x^k = x^{k-1} + \alpha_{k}d^k$.

You didn't say what $x^k$ is. I assume it is a vector. For example, $x^k = ( {x^k}_1, {x^k}_2 )$

We assume $d^k$ is a descent direction. That is, for small positive $\alpha$, $f(x^{k-1} + \alpha d^k)$ is decreasing.

Here's the lemma we want to prove:
When $x^k$ is constructed using the optimal $\alpha$, we have $\nabla f(x^k) \cdot d^k = 0$

The Attempt at a Solution

It's suggested in the book that we should differentiate the function $f(x^{k-1} + \alpha d^k)$ with respect to $\alpha$. My problem is that I don't know how to differentiate a function that isn't defined.

Visualize all the arguments of $f$ . For example $f( {x^{k-1}}_1 + \alpha {d^k}_1, {x^{k-1}}_2 + \alpha {d^k}_2)$

Things might look more familiar In different notation. If we have a real valued function $f(x,y)$ of two real variables $x,y$ and $X(\alpha), \ Y(\alpha)$ are real valued functions of $\alpha$ then
$\frac{df}{d\alpha} = \frac{\partial df}{dx}\frac{dX}{d\alpha} + \frac{\partial df}{dy} \frac{dY}{d\alpha}$
$= \nabla f \cdot (\frac{dX}{d\alpha},\frac{dY}{d\alpha})$

 

[Ray Vickson]

Homework Statement

$f(x)$ is the function we want to minimize. Beyond being real-valued, there are no other conditions on it. (I'm surprised it's not at least continuous, but the book doesn't say that's a condition.) We choose the next $x^k$ through the relation $x^k = x^{k-1} + \alpha_{k}d^k$. We assume $d^k$ is a descent direction. That is, for small positive $\alpha$, $f(x^{k-1} + \alpha d^k)$ is decreasing.

Here's the lemma we want to prove:
When $x^k$ is constructed using the optimal $\alpha$, we have $\nabla f(x^k) \cdot d^k = 0$

The Attempt at a Solution

It's suggested in the book that we should differentiate the function $f(x^{k-1} + \alpha d^k)$ with respect to $\alpha$. My problem is that I don't know how to differentiate a function that isn't defined. My first guess went something like this, but I don't see how I'm any closer to a solution.

$$\frac{\partial}{\partial \alpha} f(x^{k-1} + \alpha d^k) = \frac{\partial}{\partial \alpha} f(x^k)$$
$$f'(x^{k-1} + \alpha d^k)d^k = f'(x^k)(0)$$
$$f'(x^{k-1} + \alpha d^k)d^k = 0$$

I'm really not looking for an answer, but if someone could point me to where I could learn about taking differentials of undefined functions that would be helpful. I'm guessing that somehow I can extract a gradient out of this, and a dot product, but I'm feeling pretty confused.

Taking derivatives does not make sense unless $f$ is differentiable, so automatically continuous---in fact, even smoother than continuous. Maybe the book does not say that, but it is part of the reader's assumed background. Furthermore (just to be picky), expressions like $\nabla f(x^k) \cdot d^k$ depend on even more smoothness: $f$ must be continuously differentiable (not just plain differentiable). If the book does not make this clear, that is a flaw; it should definitely cover these points somewhere.

BTW: the stated result is false if $f$ is not continuously differentiable; there are some easy counterexamples.

 

[rayge]

Actually it is made clear in the beginning on the chapter that we're dealing with quadratic functions of the form $f(x) = \frac{1}{2}\|Ax - b\|^2_2$. My fault for not reading closely enough.

 

[Ray Vickson]

Actually it is made clear in the beginning on the chapter that we're dealing with quadratic functions of the form $f(x) = \frac{1}{2}\|Ax - b\|^2_2$. My fault for not reading closely enough.

OK, but the result is actually true for any continuously-differentiable $f$.

 

[rayge]

Good to know, thanks. I applied the chain rule as suggested, and got:
$$\frac{d f(x^{k-1} + \alpha d^k)}{d\alpha} = \nabla f \cdot d^k$$
From here, it seems reasonable that $\frac{d f(x^{k-1} + \alpha d^k)}{d\alpha} = 0$ is our optimal value but I don't know how to prove that from our assumptions. For small $\alpha$, $f(x^{k-1} + \alpha d^k)$ is decreasing. For large enough $\alpha$, I think $f(x^{k-1} + \alpha d^k)$ is increasing (i.e. we pass by the optimal point). I just don't have a solid grasp on how the function works, and assuming it's increasing for large $\alpha$, why that is the case.

Thanks again.

 

[Ray Vickson]

Good to know, thanks. I applied the chain rule as suggested, and got:
$$\frac{d f(x^{k-1} + \alpha d^k)}{d\alpha} = \nabla f \cdot d^k$$
From here, it seems reasonable that $\frac{d f(x^{k-1} + \alpha d^k)}{d\alpha} = 0$ is our optimal value but I don't know how to prove that from our assumptions. For small $\alpha$, $f(x^{k-1} + \alpha d^k)$ is decreasing. For large enough $\alpha$, I think $f(x^{k-1} + \alpha d^k)$ is increasing (i.e. we pass by the optimal point). I just don't have a solid grasp on how the function works, and assuming it's increasing for large $\alpha$, why that is the case.

Thanks again.

You are searching for a minimum along a line, so you are trying to minimize a univariate function $\phi(\alpha)$, which just happens to be of the form
$$\phi(\alpha) = f(x^{k-1} + \alpha d^k)$$
for some vector constants $x^{k-1}, d^k$. How do you minimize functions of one variable?

 

[Ray Vickson]

Good to know, thanks. I applied the chain rule as suggested, and got:
$$\frac{d f(x^{k-1} + \alpha d^k)}{d\alpha} = \nabla f \cdot d^k$$
From here, it seems reasonable that $\frac{d f(x^{k-1} + \alpha d^k)}{d\alpha} = 0$ is our optimal value but I don't know how to prove that from our assumptions. For small $\alpha$, $f(x^{k-1} + \alpha d^k)$ is decreasing. For large enough $\alpha$, I think $f(x^{k-1} + \alpha d^k)$ is increasing (i.e. we pass by the optimal point). I just don't have a solid grasp on how the function works, and assuming it's increasing for large $\alpha$, why that is the case.

Thanks again.

I see that my previous response did not deal with all of your question. I cannot supply too many details without violating PF helping policies, but I can give a hint. In your specific case you have $f(\vec{x}) = || A \vec{x} - \vec{b}||^2$. So letting $\vec{y} = A \vec{x}^k - \vec{b}$ and $\vec{p} = A \vec{d}^k$, we have that $\phi(\alpha) = f(\vec{x}^k + \vec{d}^k \alpha)$ has the form $\phi(\alpha) = ||\vec{y} + \alpha \vec{p}||^2 = a + b \alpha + c \alpha^2$. How do you find $a, b, c$? Given that $\vec{d}^k$ is a descent direction, what does this say about the values or signs of $a,b,c$? What do these signs say about the behavior of $\phi(\alpha)$?