# 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
show 2 more comments

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 50, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9300405383110046, "perplexity_flag": "head"}