$f(x^* + h) \ge f(x^*) \Rightarrow \frac{h^2}{2} f''(x^*) \ge 0$

Question

My textbook, Algorithms for Optimization, by Kochenderfer and Wheeler, says the following:

A point can also be at a local minimum if it has a zero derivative and the second derivative is merely nonnegative:

1. $f'(x^∗) = 0$, the first-order necessary condition (FONC)
2. $f''(x^∗) \ge 0$, the second-order necessary condition (SONC)

These conditions are referred to as necessary because all local minima obey these two rules. Unfortunately, not all points with a zero derivative and a zero second derivative are local minima, as demonstrated in figure 1.7.

The first necessary condition can be derived using the Taylor expansion about our candidate point $x^*$:

$$f(x^∗ + h) = f(x^∗) + hf'(x^∗) + O(h^2)$$ $$f(x^∗ − h) = f(x^∗) − hf'(x^∗) + O(h^2)$$ $$f(x^∗ + h) \ge f(x^∗) \Rightarrow hf'(x^∗) \ge 0$$ $$f(x^∗ − h) \ge f(x^∗) \Rightarrow hf'(x^∗) \le 0$$ $$\Rightarrow f'(x^∗)=0$$

The second-order necessary condition can also be obtained from the Taylor expansion:

$$f(x^∗ + h) = f(x^∗) + \underbrace{hf'(x^∗)}_{\text{$=0$}} + \dfrac{h^2}{2} f''(x^∗) + O(h^3)$$

We know that the first-order necessary condition must apply:

$$f(x^* + h) \ge f(x^*) \Rightarrow \dfrac{h^2}{2} f''(x^*) \ge 0$$

since $h > 0$. It follows that $f''(x^*) \ge 0$ must hold for $x^*$ to be at a local minimum.

I don't see how $f(x^* + h) \ge f(x^*) \Rightarrow \dfrac{h^2}{2} f''(x^*) \ge 0$ is true? For instance, take the case of a positive and increasing function just after its inflection point. It would be true that $f(x^* + h) \ge f(x^*)$ for $h > 0$, and it would also be true that $f'(x^*) > 0$. However, it would not be true that $f''(x^*) \ge 0$, since the function at this point (since it is just after its inflection point) is concave down, meaning that $f''(x^*) < 0$.

So how can it be said that $f(x^* + h) \ge f(x^*) \Rightarrow \dfrac{h^2}{2} f''(x^*) \ge 0$? I would greatly appreciate it if people would please take the time to clarify this.

Answer 1

Since $f'(x^*) = 0$ $$f(x^* + h ) \ge f(x^*) \implies \frac{h^2f''(x^*)}{2} + O(h^3) \ge 0$$

By the defintion of $O(h^3)$ we have

$$\frac{h^2f''(x^*)}{2} + Mh^3 \ge 0$$

for some $M>0$.

This means $$f''(x^*) \ge -2Mh$$ for arbitrarily small $h$. This means $f''(x^*) \ge 0$