I'm reviewing my "numerical optimization" background, and some of the theorems ring bells all over the place. Some of these theorems (for example in "Line search methods") assert validity of convergence etc assuming "Lipschitz" conditions.
However when I read through some of the papers (I'm an engineer by the way) I sometimes see some function to be optimized and no proof at all about such condition, which sometimes is necessary for convergence.
My question is if the formula of the function to be optimized isn't easy to analyse is there any technique (even numerical) that can be used to state "ok the function is Lipschitz"?
Most engineers they just run the method and that's it, if it converges they're happy otherwise they try something else.
Thank you
In many cases, it suffices to check that your function is differentiable with continuous derivatives. Let us be precise. Let $\Omega \subset \mathbb{R}^n$ be open and let $f : \Omega \rightarrow \mathbb{R}^n$ be differentiable with continuous first order partial derivatives. Let $B \subset \Omega$ be a closed ball. Then the restriction of $f$ to $B$ is Lipschitz continuous, i.e., there exists a constant $L > 0$ such that $$\|f(y)-f(x)\|_2 \leq L \|y-x\|_2,$$ for all $x, y \in B$. Proof: Let $x, y \in B$ be given. Since $B$ is convex, we have $(1-t)x+ty \in B$ for all $t \in [0,1]$. It follows that the function $g : [0,1] \rightarrow \mathbb{R^n}$ given by $$g(t) = f((1-t)x+ty)$$ is well-defined. By the chain rule it is also differentiable and the derivative is given by $$g'(t) = Df((1-t)x+ty)\cdot(y-x).$$ Here $Df(z) \in \mathbb{R}^{n \times n}$ denotes the Jacobian of $f$ at the point $z$ and $\cdot$ is the (normal) matrix vector product. It follows that $$f(y) - f(x) = g(1) - g(0) = \int_0^1 g'(t) dt = \int_0^1 Df((1-t)x+ty)\cdot(y-x)dt.$$ This expression allows us to estimate \begin{align} \|f(y) - f(x)\| &\leq \int_0^1 \| Df((1-t)x+ty)\cdot(y-x)dt \|_2 \\ &\leq \left( \int_0^1 \| Df((1-t)x+ty) \|_2 dt \right)\|y-x \|_2.\end{align} Now, since $B$ is a closed and bounded subset of $R^n$ and because $z \rightarrow \|Df(z)\|_2$ is a continuous function there exists a constant $L > \infty$, such that $$ \|Df(z)\|_2 \leq L$$ for all $z \in B$. Returning to our inequalities, we conclude that $$\| f(y)- f(x)\|_2 \leq L \|y-x\|_2$$ This completes the proof.
This is the standard proof of the fact that if $\Omega \in \mathbb{R}^n$ and $f \in C^{1}(\Omega,\mathbb{R}^n)$ then $f$ is locally Lipschitz. In many cases, but not always, this property is enough.
The function $f : \mathbb{R} \rightarrow \mathbb{R}$ given by $f(y) = y^2$, is locally Lipschitz, but it is not globally Lipschitz. Proof: Let $x, y$ be given. Then $$f(y) - f(x) = y^2 - x^2 = (y+x)(y-x)$$ and the only real candidate for $L$ is $L = |x+y|$ which can not be bounded independently of $x, y\in \mathbb{R}$.