Existence of saddle points

Printable View

December 12th 2011, 02:45 PM
jens

Existence of saddle points

Hi,

Let me clarify a definition first: A saddle point of a function $f$ occurs wherever two conditions are fulfilled:
1) the gradient $\nabla f$ vanishes
2) the Hesse matrix $\nabla\nabla^T f$ is indefinite

I conjecture the following theorem:

Let $f \colon \mathcal{D} \subset \mathbb{R}^n \to \mathbb{R}$ with $n \geq 2$ be a twice differentiable function defined on a compact and convex $n$ -manifold $\mathcal{D}$ . We have $f = 0$ on the border $\partial\mathcal{D}$ and $f > 0$ on the interior of $\mathcal{D}$ . Then we have the following implication:

$f$ has at least two local maxima $\Rightarrow$ $f$ has at least one saddle point

Do you know if this is true? And how it can be proven?

Jens
December 13th 2011, 07:46 AM
xxp9

Re: Existence of saddle points

Suppose the pre-images of the two maxima are isolated this would be true and the proof involves using the Morse theory I think.
The idea is, define $D^a = f^{-1}(-\infty, a]$ , then $D^0$ is nothing but $\partial{D}$ , suppose $x \le y$ are the two local maximal values , then with a small positive number $\varepsilon$ , $D^{x-\varepsilon}$ has at least two holes around $f^{-1}(x)$ and $f^{-1}(y)$ , for that $\forall p \in f^{-1}(x)\cup f^{-1}(y), p \notin D^{x-\varepsilon}$ , and since the critical points are isolated, by choosing $\varepsilon$ sufficiently small, those holes will not connect each other to merge to a single hole. So the (n-1)th homology group of $D^{x-\varepsilon}$ has at least dimension 2.
However since D is connected $D^0$ has only one hole inside, represented by a homology group of dimension 1.
According to Morse theory, between 0 and x, there must be other critical value z, so that the homotopic type of $D^{z+\varepsilon}$ is got by gluing one or more (n-1) cells to $D^{z-\varepsilon}$ , to increase the dimension of the (n-1)th homology group.
Then the theory says that the critical point z must have an index of (n-1), so it has an indefinite Hessian, with a signature of (1, -1, -1, ..., -1).
December 13th 2011, 09:03 PM
Jose27

Re: Existence of saddle points

Quote:

Originally Posted by xxp9

Suppose the pre-images of the two maxima are isolated this would be true and the proof involves using the Morse theory I think.
The idea is, define $D^a = f^{-1}(-\infty, a]$ , then $D^0$ is nothing but $\partial{D}$ , suppose $x \le y$ are the two local maximal values , then with a small positive number $\varepsilon$ , $D^{x-\varepsilon}$ has at least two holes around $f^{-1}(x)$ and $f^{-1}(y)$ , for that $\forall p \in f^{-1}(x)\cup f^{-1}(y), p \notin D^{x-\varepsilon}$ , and since the critical points are isolated, by choosing $\varepsilon$ sufficiently small, those holes will not connect each other to merge to a single hole. So the (n-1)th homology group of $D^{x-\varepsilon}$ has at least dimension 2.
However since D is connected $D^0$ has only one hole inside, represented by a homology group of dimension 1.
According to Morse theory, between 0 and x, there must be other critical value z, so that the homotopic type of $D^{z+\varepsilon}$ is got by gluing one or more (n-1) cells to $D^{z-\varepsilon}$ , to increase the dimension of the (n-1)th homology group.
Then the theory says that the critical point z must have an index of (n-1), so it has an indefinite Hessian, with a signature of (1, -1, -1, ..., -1).

I don't know algebraic topology so I can't comment on the answer, but what would you say of this (very, very informal) example:

Basically a flan with two bumps. Take the usual smooth function on $[-1,1]$ such that $f|_{[-1/2,1/2]}=1$ , $0\leq f\leq 1$ and $f|_{\mathbb{R}\setminus (-1,1)}=0$ (think the profile of a flan). Rotate this $f$ to obtain $g$ in $C_c^{\infty}(\mathbb{R}^2 )$ with $g|_{B_{1/2}(0)}=1$ , $0\leq g\leq 1$ and $g|_{\mathbb{R}^2\setminus B_1(0)}=0$ . Take now $h_1,h_2$ two other positive bump functions (the scaled and translated classical mollifiers would do perfectly) such that their supports are contained in $B_{1/2}(0)$ (hence compactly contained in this ball, ie. a positive distance away form the boundary of the ball) and are (the supports) a positive distance appart from each other. Then take your function $F=g+h_1+h_2$ . It has two strict local maxima, but no saddle point.
December 14th 2011, 02:14 AM
jens

Re: Existence of saddle points

Thanks xxp9 for this knowledgeable answer, and for confirming my intuition!

I had roughly the same idea as you for a proof: to think of the topology of contour sets. But you seem to know more about topology than I do. I'm an engineer and don't know about Morse theory. You seem to invoke some theorem from "Morse theory" (?) to directly conclude that the Hessian is indefinite at the critical point. Does your theory also conclude that the gradient vanishes at this critical point?
December 14th 2011, 02:23 AM
jens

Re: Existence of saddle points

Quote:

Originally Posted by Jose27

I don't know algebraic topology so I can't comment on the answer, but what would you say of this (very, very informal) example:

Basically a flan with two bumps. Take the usual smooth function on $[-1,1]$ such that $f|_{[-1/2,1/2]}=1$ , $0\leq f\leq 1$ and $f|_{\mathbb{R}\setminus (-1,1)}=0$ (think the profile of a flan). Rotate this $f$ to obtain $g$ in $C_c^{\infty}(\mathbb{R}^2 )$ with $g|_{B_{1/2}(0)}=1$ , $0\leq g\leq 1$ and $g|_{\mathbb{R}^2\setminus B_1(0)}=0$ . Take now $h_1,h_2$ two other positive bump functions (the scaled and translated classical mollifiers would do perfectly) such that their supports are contained in $B_{1/2}(0)$ (hence compactly contained in this ball, ie. a positive distance away form the boundary of the ball) and are (the supports) a positive distance appart from each other. Then take your function $F=g+h_1+h_2$ . It has two strict local maxima, but no saddle point.

You're right, there is a slight problem in my setup. Actually, what characterizes your counterexample is that your function has plateaus (flat portions). Probably, I should require that all stationary points are isolated, or some condition of this kind. Or that the function be $\mathcal{C}^\infty$ in the interior of $\mathcal{D}$ , from which follows that stationary points are isolated.
December 14th 2011, 07:10 AM
xxp9

Re: Existence of saddle points

You're right. Morse theory only deals with nondegenerate Hessian. We need to add assumptions that all critical points are nondegenerate.

Quote:

Originally Posted by Jose27

I don't know algebraic topology so I can't comment on the answer, but what would you say of this (very, very informal) example:

Basically a flan with two bumps. Take the usual smooth function on $[-1,1]$ such that $f|_{[-1/2,1/2]}=1$ , $0\leq f\leq 1$ and $f|_{\mathbb{R}\setminus (-1,1)}=0$ (think the profile of a flan). Rotate this $f$ to obtain $g$ in $C_c^{\infty}(\mathbb{R}^2 )$ with $g|_{B_{1/2}(0)}=1$ , $0\leq g\leq 1$ and $g|_{\mathbb{R}^2\setminus B_1(0)}=0$ . Take now $h_1,h_2$ two other positive bump functions (the scaled and translated classical mollifiers would do perfectly) such that their supports are contained in $B_{1/2}(0)$ (hence compactly contained in this ball, ie. a positive distance away form the boundary of the ball) and are (the supports) a positive distance appart from each other. Then take your function $F=g+h_1+h_2$ . It has two strict local maxima, but no saddle point.
December 14th 2011, 07:18 AM
xxp9

Re: Existence of saddle points

Gradient vanishes at critical points because this is as defined.
Morse theory studies the topology of a manifold from the information of Hessian signatures of all critical points of a smooth function.
Milnor has a great book <Morse theory> on that topic. You need only read the first chapter to grasp the idea. It's one of the best books I have ever read.

Quote:

Originally Posted by jens

Thanks xxp9 for this knowledgeable answer, and for confirming my intuition!

I had roughly the same idea as you for a proof: to think of the topology of contour sets. But you seem to know more about topology than I do. I'm an engineer and don't know about Morse theory. You seem to invoke some theorem from "Morse theory" (?) to directly conclude that the Hessian is indefinite at the critical point. Does your theory also conclude that the gradient vanishes at this critical point?