0

I started reading Güler's Foundations of Optimization today, and I'm having trouble with the proof of Lemma 1.17. I've already found errors in the book, so I'm particularly suspicious at this point.

Lemma 1.17. Let $f : I \to \mathbb{R}^m$ be a map on an interval $I = (a, b)$. If $f$ is differentiable at every point in $I$, then

$\lVert f(y) - f(x) \rVert \leq |y - x| \cdot \displaystyle \sup_{0 \leq t \leq 1} \lVert Df(x + t(y - x)) \rVert, \;\;\;\; x, y \in I$

Proof. Let $M > \sup_{0 \leq t \leq 1} \lVert Df(x + t(y - x)) \rVert$ and set

$K := \{t : 0 \leq t \leq 1, \lVert f(x + t(y - x)) - f(x) \rVert \leq M t |y - x| \}$.

The set $K$ is closed, since $f$ is continuous, and $0 \in K$. Let $s$ be the largest element of $K$. We claim that $s = 1$. Otherwise, $s < 1$, and choosing $t \in (s, 1)$ such that $t - s$ is small enough, we have

$\lVert f(x + t(y-x)) - f(x) \rVert \\ \leq \lVert f(x + t(y-x)) - f(x + s(y-x)) \rVert + \lVert f(x + s(y-x)) - f(x) \rVert \\ \leq \lVert Df(x + s(y-x))(t-s)(y-x) + o((t-s)|y-x|) \rVert + M s |y - x| \\ \leq M(t - s)|y - x| + M s |y - x| \\ = M t |y - x|$

that is, $t \in K$, a contradiction. This proves the claim and the lemma.

I have several issues with the above proof. All of them are located in the last equation block.

  1. Couldn't it be $o((t-s)(y-x))$?
    This is a minor detail and not all that relevant, except that it appears you would need to drop the absolute values to do the substitution that it looks like the author attempts. Seems weird.

  2. Shouldn't it be $Df(x)(t-s)(y-x)$?
    This looks like a typo to me. By Taylor, we have $f(x + t(y-x)) = f(x) + Df(x)t(y-x) + o(t(y-x))$ and similarly $f(x + s(y-x)) = f(x) + Df(x)s(y-x) + o(s(y-x))$. Subtracting, we get $f(x + t(y-x)) - f(x + s(y-x)) = Df(x)(t-s)(y-x) + o((t-s)(y-x))$.

  3. How do we justify the inequality with $M(t-s)|y-x|$?
    This is the main point that has me stuck. Again by Taylor, we have $\lVert f(x + (t-s)(y-x)) - f(x) \rVert = \lVert Df(x)(t-s)(y-x) + o((t-s)(y-x)) \rVert \leq M(t-s)|y-x|$
    and everything seems great, except for the fact that this $o((t-s)(y-x))$ and the other $o((t-s)(y-x))$ from the previous line are not necessarily equal. It seems like the author is trying to justify it by taking $t-s$ "small enough," but I can't predict how the different values of $o((t-s)(y-x))$ compare as $t-s \to 0$. I see no easy fix to this problem.

Questions: Is this proof broken? If so, can it be easily mended? If not, should I just read the corresponding theorem and proof in Rudin and pretend this one never existed? Furthermore, are errors like this frequent throughout this book, and should I look for another source to self-study optimization?

Remark: If we assume the function is smooth instead of differentiable, then it would seem we have $o((t-s)(y-x)) = \sum_{j=2}^\infty d_j (t^j - s^j)$ in the earlier line while $o((t-s)(y-x)) = \sum_{j=2}^\infty d_j (t-s)^j$ in the later line, where $d_j$ is (the big mess of) everything the two terms have in common. However, $(t-s)^j \leq t^j - s^j$ for all $j \geq 2$, which makes this method seem fundamentally flawed.

  • He starts by assuming that $M$ is strictly greater than $\sup | Df(x+t(y-x)) |$. This strictly greater than is the key. If you made $M$ equal to the sup, that would break the proof. – Brian Borchers Dec 12 '16 at 04:35
  • @BrianBorchers I don't see how that resolves the issue. Could you possibly elaborate? –  Dec 12 '16 at 04:47
  • If $\sup | A(t) | < M$ then $| A(t)x + \delta x | \leq M | x |$ for $\delta$ small enough. – Brian Borchers Dec 12 '16 at 04:55

1 Answers1

0

In the second and third line of the block above he does the following:

We have that \begin{align*} f(x + t(y-x)) - f(x + s(y-x)) &= f(x+s(y-x) + (t-s)(y-x))-f(x+s(y-x)) \\ &= D(f)(x+s(y-x))((t-s)(y-x)) + o((t-s)(y-x)). \end{align*}

By taking $s$ small enough, and by the definition of $M$ we can then conclude that: \begin{align*} ||f(x + t(y-x)) - f(x + s(y-x))|| &\leq M |(t-s)(y-x)|. \end{align*} In particular, by the triangle inequality we have that \begin{align*} ||f(x + t(y-x)) - f(x + s(y-x))|| &\leq ||D(f)(x+s(y-x))((t-s)(y-x))|| + ||o((t-s)(y-x))|| \end{align*} where $||o((t-s)(y-x))|| \to 0$ as $s\to t$.

By the definition of $M$, we have that $M(t-s)|y-x|> ||D(f)(x+s(y-x))((t-s)(y-x))||$ and so by taking $s$ small enough we get the above inequality.

Personally I think the notation used is atrocious and this might be where the difficulty is.

Leon Sot
  • 1,293