1
$\begingroup$

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 \}$
$\endgroup$
2
  • $\begingroup$ Theorem 3.2.5 does not yield $0\in\partial f(x)$ in this case. In Theorem 3.2.5, $x$ is a global extremum. In Theorem 5.1.6, $x$ is only a local minimum over $G$. $\endgroup$
    – f10w
    Jun 24, 2016 at 19:01
  • $\begingroup$ Yeah, the statement 3.2.5 is kind of vague but i added the proof (Edit 1) which only focuses on local minima. I also added another Theorem (see Edit 2) which is nearly the same statement as of 5.1.6, the Theorem in question, but for local minima not in a subset $G\subset \mathbb R^n$. I dont see a plausible reason to make a difference for such subsets G because anyway everything is focused on local minima which means proofing by $\epsilon$ based subsets, right? Thanks for your time and thoughts $\endgroup$
    – John Doe
    Jun 25, 2016 at 7:53

0

You must log in to answer this question.

Browse other questions tagged .