Image for a strict local minimizer that is not an isolated minimizer

Question

From Numerical Optimization by Nocedal and Wright:

A point $x^*$ is a strict local minimizer if there is a neighborhood $N$ of $x^*$ such that $f(x^*)<f(x)$ for all $x \in N$ with $x \neq > x^*$.

A point $x^*$ is an isolated local minimizer if there is a neighborhood $N$ of $x^*$ such that $x^*$ş is the only local minimizer in $N$.

...

While strict local minimizers are not always isolated, it is true that all isolated local minimizers are strict.

I just could not draw an image of a strict local minimizer that is not isolated in my mind. Neither could I find in the web.

Can you draw one for me, so that I can see the different between strict and isolated local minimizers visually?

By the way authors give following function as an example: $f(x)=x^4cos(1/x)+2x^4, 0 $ being the minimizer. Though you do not need to show on this function. A hand drawn image is OK, if it shows the difference.

Answer 1

As others have pointed out correctly, this happens when you have a series of local minimizers that converge to a minimizer that has a better value than what they have.

So, this is something that is not very easy to draw knowing that the local minimizers should get very close to each other when converging to the final point. Having said that I tried my best to depict it (it is actually easier to imagine it instead of drawing it)

The key to understanding the difference is the term "only local minimizer in N" in the definition of the isolated local minimizer. A point could be the global minimizer in a neighbourhood (as the origin is in the image above), but there might be infinitely many local minimizers in that neighbourhood which are not as good as this point, but they are still local minimizers. In that sense, although this point is strict local minimizer as no other point can beat its value, but is not an isolated local minimizer (there is a sequence of local minimizers converging to it with strictly higher function value).

Note: you could think of much simpler examples if you do not limit yourself to the continuous functions: $f(x) = 1$ if $x\neq 0$ and $f(0) = 0$ at zero has this property. In any neighbourhood around 0, 0 is the strict local minimizer, but any other point in the neighbourhood is also a local minimizer. So, 0 is not an isolated local minimum.

Answer 2

To get some function that looks like the graph in Maziar Sanjabi's answer, we can

1. Find a function that has a basic shape like that, such as $f(x)=x^2$;
2. Multiply $f(x)$ with a periodic function that has infinitely small period as it approaches $x=0$, which is the local minimizer of $f(x)$, one such function is $g(x)=2-\cos(30/x)$.

We have $h(x)=f(x)g(x)$, which looks like:

It oscillates between $x^2$ and $3x^2$.

Answer 3

This is a good question. The idea is to build a function whit a set of local minimizers converging to some local minimizer. To that end, consider the sequence $\{x_n\}$ with $x_n=\frac{1}{n}.$ Define $f:\Bbb R\to \Bbb R$ as follows:

$$f(x)= -x,\;x\leq 0,\;\; f(x)=1,\;x>1,\;\; f\left(\frac{1}{2k+1}\right)=1,\;\; f\left(\frac{1}{2k}\right)=\frac{1}{2k},$$ and if $\frac{1}{2k}< x< \frac{1}{2k+1},$ take $f(x)$ as the point $y$ such that $(x,y)$ belongs to the line passing through $\left(\frac{1}{2k},\frac{1}{2k}\right)$ and $\left(\frac{1}{2k+1},1\right).$ Then, it is easy to see that $x=\frac{1}{2k}$ is a local minimum of $f$ and $x=0$ also. Furthermore, $x=0$ is also a strict local minimum. However, there is no neighborhood of $x=0$ in which it is the only local minimizer.

Hope this helps

Answer 4

Bertsekas's book "Nonlinear Programming" 1999 version (version 2), practice problem 1.1.11, gives another example that isolated local mininum is not strict local minimum (due to a paper [Dun87]).

Importantly, it also proves that non-singular isolated local minimum must be strict local minimum. Thus the example only happens to the singular case. This might help a bit on understanding when this would happen.