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!

  • $\begingroup$ @Tim: I think you wanted $\nabla$ when you typed \grad, correct? The LaTeX code is \nabla. $\endgroup$ – Arturo Magidin Mar 12 '11 at 22:04
  • $\begingroup$ @Arturo: Thanks! Yes, and nice to learn about that. $\endgroup$ – Tim Mar 12 '11 at 22:11
  • $\begingroup$ 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. $\endgroup$ – cardinal Mar 12 '11 at 22:13
  • $\begingroup$ @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. $\endgroup$ – Tim Mar 12 '11 at 22:22
  • $\begingroup$ @Tim, if your (sub)space is $X = [0,1]$, then what are the open sets over $X$? Then, what are the neighborhoods? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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