I'm reading about nonsmooth optimization and specially the book 'Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control' by Marko M. Mäkelä, Pekka Neittaanmäki.
At page 72 one finds the following Theorem 5.1.6:
If $f$ is locally Lipschitz at $x$ and attains its local minimum over the set $G \subset \mathbb R^n$ at $x$, then $0\in\delta f(x)+N_G(x)$.
The proof uses an open set $x\in G\cap S \subset S$ and a function $g(y)=f(y)+K d_{G\cap S}(y)$ where K is the lipschitz constant such that x is the minimum over S regarding this function g(y) and argues $0\in \delta(f(x)+K d_{G\cap S}(x))\subset \delta f(x)+K \delta d_{G\cap S}(x) \subset \delta f(x)+N_{G\cap S}(x) = \delta f(x)+N_G(x)$ where $d_G(x)=\inf_{y \in G} \|x-y\|$.
What i find curious about this theorem is that the book also has theorem 3.2.5, if f is locally Lipschits at x and attains its extremum at x, then $0\in \delta f(x)$ and theorem 4.1.4, the normal cone $N_G(x)$ of the set G is a closed convex cone containing zero.
I assume that the sum of two sets is meant to be $\delta f(x)+N_G(x)=\{z+y \in \mathbb R^n | z\in \delta f(x), y \in N_G(x) \}$.
Now, thats where i dont get the point of the theorem in question (5.1.6). Given x is a local minimum Thm 3.2.5 shows that $0\in \delta f(x)$ and since $N_G(x)$ is a closed cone containing zero its not very surprising that $0\in \delta f(x)+N_G(x)$, right?
So what's the point of this theorem? As i understand it, 5.1.6 gives a criteria where one can search for local minima given a feasable set G by examinig the set $\delta f(x)+N_G(x)$, but why would i wanna increase the size of the search set $\delta f(x)$ by $N_G(x)$ altough i can be sure that there must be $0\in \delta f(x)$ which should contain fewer vectors than the sum?
Edit 1: Proof of Theorem 3.2.5:
Suppose first that f attains a local minimum at $x$. Then there exists $\epsilon>0$ such that $f(x+tv)-f(x)\ge 0$ for all $0<t<\epsilon$ and $v\in \mathbb R^n$. Now we have $$f^°(x;v)=\limsup_{y\rightarrow x, t\downarrow 0}\frac{f(y+tv)-f(y)}{t}\ge \limsup_{t\downarrow 0}\frac{f(x+tv)-f(x)}{t}\ge 0$$ and so $$f^°(x;v)\ge 0=0^\intercal v\ for\ all\ v\in \mathbb R^n,$$ which means by definition of subdifferential that $0\in \delta f(x)$. Suppose next that f attains a local maximum at $x$. Then $-f$ attains a local minimum at $x$ and as above $0\in\delta (-f)(x)$. The statement follows from Thereom 3.2.4.
Edit 2: The book also states Theorem 5.1.1: If $f:\mathbb R^n\rightarrow \mathbb R$ is locally Lipschitz at $x$ and attains its local minimum at $x$, then $0\in \delta f(x)$ and $f^°(x;v)\ge 0$ for all $v\in \mathbb R^n$.
The proof follows directly from Theorem 3.2.5.
Remarks:
- $f$ is meant to as a function $f:\mathbb R^n \rightarrow \mathbb R$
- $\delta f(x):=\{\xi \in \mathbb R^n | f^°(x;v)\ge \xi ^\intercal v\ for \ all\ v\in \mathbb R^n\}$ is the clarke subdifferential
- $f^°(x;v) = \limsup_{y\rightarrow x,\ t\downarrow 0} \frac{f(y+tv)-f(y)}{t}$ is the clarke directional derivative
- the normal cone for an arbitrary set G is defined as $N_G(x)=\{y \in \mathbb R^n | y^\intercal z \le 0\ for\ all\ z\in T_G(x) \}$
- the tangent cone for a set G is defined as $T_G(x)=\{ z \in \mathbb R^n | \exists t_i \downarrow 0, y_i \rightarrow y, x_i\rightarrow x\ :\ x_i+t_iy_i \in G\ as\ i\rightarrow \infty \}$
