Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
@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 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.