# Local min and differentiability of a function

Suppose there is a function $f: X \rightarrow \mathbb{R}$, where $X \subseteq \mathbb{R}^n$.

1. If $x^*$ is a local minimizer of $f$ over $X$, must $x^*$ be either of the two cases:

• if $f$ is differentiable at $x^*$, then $x^*$ must be a stationary point i.e. $\nabla{f}(x^*)=0$
• $f$ is non-differentiable at $x^*$?

In other words, are there other possible cases for a local minimizer besides the two? I seem to have seen this as a conclusion from somewhere that I now cannot recall. However the following proposition seems to challenge this.

2. From p194 on Nonlinear Programming by Dimitri P. Bertsekas:

If $X$ is a convex set.

Proposition 2.1.2: (Optimality Condition)

(a) If $x^*$ is a local minimum of $f$ over $X$. then $$\nabla{f}(x^*)'(x - x^*) > 0, \forall x \in X.$$

(b) If $f$ is convex over $X$, then the necessary condition of part (a) is also sufficient for $x^*$ to minimize $f$ over $X$.

If the conclusion in Part 1 is true, then if $f$ is differentiable at $x^*$, we will have $\nabla{f}(x^*)=0$. Under this logic, I was confused why we have the proposition (a) as above in the book?

How to interpret the proposition geometrically?

Thanks and regards!

-
@Tim: I think you wanted $\nabla$ when you typed \grad, correct? The LaTeX code is \nabla. –  Arturo Magidin Mar 12 '11 at 22:04
@Arturo: Thanks! Yes, and nice to learn about that. –  Tim Mar 12 '11 at 22:11
I think it depends on how "local minimum" is defined. In general, a further condition is needed, e.g., that the local minimum be in the interior of $X$. Take $X = [0,1]$ and the function $f(x) = x$ to see why. –  cardinal Mar 12 '11 at 22:13
@cardinal: The definition for a point to be a local minimizer of a function is that there exists a neighbourhood of the point s.t. the function value at any point in the neighbourhood is always greater than or equal to that at the point. This implies that a local minimizer must be in the interior of the domain of the function. –  Tim Mar 12 '11 at 22:22
@Tim, if your (sub)space is $X = [0,1]$, then what are the open sets over $X$? Then, what are the neighborhoods? –  cardinal Mar 12 '11 at 22:46

Dimitri Bertsekas is right. Your conclusion 1 cannot hold in general because when $X \subset \mathbb{R}^n$, and $x$ lies on the boundary of $X$, you are talking about a constrained minimizer. Note that $X$ must be closed for optimization to make sense. Consider for instance $X=[0,1] \subset \mathbb{R}$ and $f(x) = -e^x$.
The condition given in part (a) of Proposition 2.1.2 is that there exist no (first-order) feasible descent direction for $f$ from $X$. Note that the convexity of $X$ is assumed here.
In general, $x \in X$ is a constrained minimizer if, by definition, there is $\epsilon > 0$ such that for all $y \in X$ such that $\|x-y\| < \epsilon$, you have $f(x) \leq f(y)$. This applies even if $f$ is not differentiable.
It's not difficult to show that if $f$ is differentiable, this implies that $-\nabla f(x)$ lies in the cone normal to $X$ at $x$. You'll find the definition of the normal and tangent cones, e.g., in the book by Bazaraa, Sherali and Shetty or pretty much any good optimization book. When $X$ is convex, this is exactly what part (a) of Proposition 2.1.2 says.