1
$\begingroup$

I'm reading through the deepest descent method, and I'm struggling to understand a specific bound. I'll try to be as much clear as I can, but the notation used is a bit messy.

It is basically explained what the deepest descent is, as a generalization of the Gauss-Seidel method. It is also said that it's NOT a good algorithm, but it is worth keep looking into its properties. You can assume we have to solve the problem

$$ \min_{x \in \mathbb{R}^n} f(x) $$

where $f(x) : \mathbb{R}^n \rightarrow \mathbb{R}$.

Theorem 2.11. in this book states the following

enter image description here

the (i) and (iii) are the followings:

enter image description here enter image description here

Where $q(t)$ is defined as $f(x_k + td_k)$, so it's a parametric version of the next iteration, and for given direction we wish to find the best "step". The theorem is proved, and it make sense, however after such proof (that basically converges to a minima, or it keeps going further down) it is stated something else about the "convergence speed" and there's specifically the following bound I don't quite understand:

enter image description here

I don't get the bound

$$ f(x) \leq f^* + \frac{1}{2}\text{dist}^2(x,X^*) $$

can anyone tell me why is that? My guess is probably related to the mean value theorem and lipshitz conditions, but I can't really figure out why that's the bound.

$\endgroup$
0
$\begingroup$

A well-known property of convex functions with $L$-Lipschitz continuous gradient is that

$$ 0 \leq f(y) - f(x) - \langle \nabla f(x), y-x\rangle \leq \tfrac{L}{2}\|x-y\|^2. $$

See, for instance [Thm. 2.1.5, 1].

Suppose that $X^*$ is the set of optimizers of $f$ and it is nonempty and closed. Then, in the above inequality simply set $y\leftarrow x$ and $x\leftarrow \Pi_{X^*}x$, where $\Pi_{X^*}$ is the projection on $X^*$.

We obtain: $$ f(x) - f^* \leq \tfrac{L}{2}\|x-\Pi_{X^*}x\|^2 \leq \tfrac{L}{2}\mathrm{dist}^2(x,X^*). $$

This is exactly the bound mentioned on page 33 of the book of Bonnans et al.

References:

  1. Y. Nesterov, Introductory lectures on convex optimization: a basic course, Kluwer Academin Publishers, 2004.
$\endgroup$

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.