# Stable strict local minimum implies local convexity

Let $\bar{x}\in\mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a $C^2$ function.

We have known that if $\nabla f(\bar{x})=0$ and $\nabla^2f(\bar{x})>0$, i.e. $\nabla^2f(\bar{x})$ is positive definite, then $\bar{x}$ is a strict local minimum of $f$ and moreover the linear perturbation of $f$, the function $f_v(x):=f(x)+v^Tx$ also has a strict local minimum point for each $v$ with sufficiently small norm. Moreover the condition $\nabla^2f(\bar{x})>0$ implies $f$ is locally convex around $\bar{x}$. This fact motivates us to the following question:

Suppose that $\bar{x}$ satisfies the following properties.

There exists $r>0$ such that:

• $\bar{x}$ is unique local minimum of $f$ on $\overline{B}(\bar{x},r)$;
• The linear perturbation function $f_v(x):=f(x)+v^Tx$ has a unique local minimum in $\overline{B}(\bar{x},r)$ for each $v$ with sufficiently small norm.

Here $\overline{B}(\bar{x},r)$ is the closed ball with center $\bar{x}$ and radius $r$.

Could we conclude that $f$ is locally convex around $\bar{x}$.

My question is related to the following topics:

• It's not true that $\nabla ^2 f(\overline{x})>0$. Take for instance $f(x) = x^4$. – user587377 Sep 7 '18 at 18:05
• @CVdeFire Thanks for your comment. I change a little in my question. – Blind Sep 7 '18 at 18:19
• @Blind -- i am not an expert (by a long shot) so i have a few potentially dumb questions :) --  i think we continue to assume $f$ is differentiable (or even twice differentiable), right?  i am working on a proof that might work for the limited case of $n=1$. would that be interesting to post? or is that obvious and you're only interested in the general multi-dimensional $n>1$ case? – antkam Sep 29 '18 at 4:07
• @antkam one dimensional is deserved to be posted if your solution is interesting. – Blind Sep 29 '18 at 4:33
• I would perhaps try to characterize whether or not the gradient of $f$ is (locally) cyclically monotone as that fully characterizes whether or not $f$ is convex. – Pete Caradonna Oct 1 '18 at 0:01

BUGGY proof of $$n=1$$ special case There is a bug in the proof, which I am trying to fix when I have more time...

Disclaimer: I am not an expert (by a long shot), so you're most welcome to point out errors, loopholes, clarifications, etc. Thanks!

First, some simple "pre-processing" of the antecedents:

• For clarity I will write $$B(l) = B(\bar{x}, l) = [\bar{x} - l, \bar{x} + l]$$, i.e. the center of the neighborhood will always (implicitly) be $$\bar{x}$$.

• Assume $$f$$ is differentiable. Since $$\bar{x}$$ is a local minimum, $$f'(\bar{x}) = 0$$.

• Let $$\epsilon > 0$$ denote the upperbound for a "sufficiently small norm". I.e. $$\forall v \in (-\epsilon, \epsilon)$$ (equivalently, $$|v| < \epsilon$$): $$f_v(x) = f(x) + vx$$ has a unique local minimum in $$B(r)$$.

Lemma 1: there exists a neighborhood $$B(a) = [\bar{x} - a, \bar{x} + a]$$ for some $$a > 0$$ s.t. $$\forall x \in B(a), | { f(x) - f(\bar{x}) \over x - \bar{x}} | < \epsilon$$. Note that $${ f(x) - f(\bar{x}) \over x - \bar{x}}$$ is the slope from $$(x, f(x))$$ to $$(\bar{x}, f(\bar{x}))$$. So this claim says there is a neighborhood where the absolute slope (from $$\bar{x}$$ to any other point) is bounded below $$\epsilon$$.

Proof of Lemma 1: (I think) this follows directly from the definition of derivative $$f'(\bar{x}) = \lim_{x \rightarrow \bar{x}} { f(x) - f(\bar{x}) \over x - \bar{x}}$$. Specifically, for any positive constant (here we choose $$\epsilon$$) there must be a neighborhood $$B(a)$$ s.t. the fraction $${ f(x) - f(\bar{x}) \over x - \bar{x}}$$ stays entirely within $$(f'(\bar{x}) -\epsilon, f'(\bar{x}) + \epsilon)$$, which equals $$(-\epsilon, \epsilon)$$ because $$f'(\bar{x}) = 0$$. $$\square$$

At this point, we are dealing with two neighborhoods. The given $$B(r)$$ where the "unique local minimum" conditions apply, and the new $$B(a)$$ where the absolute slopes $$< \epsilon$$. Let $$b = \min(r, a)$$, s.t. $$B(b)$$ is the smaller of the two neighborhoods $$B(r)$$ and $$B(a)$$.

Main Result: $$f$$ is locally convex in $$B(b)$$.

Main Proof: Assume for later contradiction that $$f$$ is not locally convex in $$B(b)$$. This means $$\exists c, d$$ s.t. $$\bar{x} - b \le c < \bar{x} < d \le \bar{x} + b$$ and the line segment $$L$$ connecting $$(c, f(c))$$ and $$(d, f(d))$$ does not lie entirely above $$f$$. [Bug alert: it is not OK to assume $$c,d$$ lie on different sides of $$\bar{x}$$.] Let the equation of the line segment $$L$$ be $$L(x) = mx + q$$ where $$m$$ is the slope and $$q$$ the intercept.

Lemma 2: $$|m| = | {f(d) - f(c) \over d - c} | < \epsilon$$.

Proof of Lemma 2: Since $$\bar{x}$$ is a unique local minimum in $$B(r)$$, it is also a unique local minimum in $$B(b)$$. Without loss, assume $$f(d) > f(c)$$. Then:

• $$|f(d) - f(c)| < |f(d) - f(\bar{x})|$$ since $$f(d) > f(c) > f(\bar{x})$$, and,

• $$|d - c| > |d - \bar{x}|$$ since $$d > \bar{x} > c$$,

• therefore: $${ |f(d) - f(c)| \over |d - c| } < { |f(d) - f(\bar{x})| \over |d - \bar{x}| } < \epsilon$$ since $$d \in B(b) \subset B(a)$$.

For the case of $$f(c) > f(d)$$, simply swap $$c$$ and $$d$$ in all 3 bullets above. $$\square$$

Continuing the main proof, we apply the perturbation antecedent condition with $$v = -m$$. Note that Lemma 2 proves that $$|v| = |m| < \epsilon$$, i.e. this chosen $$v$$ is of sufficiently small norm. Therefore, $$f_v(x) = f(x) - mx$$ has a unique local minimum in $$B(r)$$, which means it has 0 or 1 local minimum in $$B(b) \subset B(r)$$.

Recall that $$L(x)$$ does not lie entirely above $$f(x)$$ in the interval $$[c,d]$$, i.e. $$\exists e \in (c,d)$$ s.t. $$f(e) > L(e)$$. Consider $$g(x) = f(x) - L(x)$$. We have $$g(c) = g(d) = 0$$ and $$g(e) > 0$$. Since $$f, L$$ are continuous, so is $$g$$. Now, by the extreme value theorem:

• $$g$$ has a minimum in $$[c,e]$$, and since $$g(e) > g(c)$$, the minimum is actually in $$[c,e)$$.

• Similarly, $$g$$ has a minimum in $$(e,d]$$.

Therefore, $$g$$ has two minima in $$[c,d]$$. Since $$f_v$$ and $$g$$ only differ by a constant $$q$$, this means $$f_v$$ also has two minima in $$[c,d] \subset B(b) \subset B(r)$$. This is the desired contradiction.

Author's note: Again, I am no expert, so suggestions, comments, corrections most welcome!

• Many results in real analysis state different conclusions for $\mathbb R$ and $\mathbb R^n$. It would be better if you could prove it for at least $\mathbb R^2$. – Saad Sep 29 '18 at 8:16
• @AlexFrancisco (1) first of all, do you think my $n=1$ proof is valid? analysis is not really my area, so i'm afraid i might have hidden assumptions that are invalid. (2) i completely agree that this proof doesnt generalize, and in fact i am undecided whether the conjecture is true for $n=2$. something like Claim 1 should still be true, but what would the assumed violating non-convex example look like? it cannot be said to satisfy $c < \bar{x} < d$ any more, and the slope of $L$ is no longer bounded by $\epsilon$ (assuming some version of Claim 1 still true). – antkam Sep 29 '18 at 14:28
• in fact, one doubt i had about my own proof is: can i really assume $c < \bar{x} < d$? my thinking was that if $c, d$ are on the same side of $\bar{x}$, then we can shrink $b$ to exclude both, so any "true" violating example "must" have $c,d$ on different sides of $\bar{x}$. but this line of thinking might be problematic... – antkam Sep 29 '18 at 14:34
• @antkam Thanks your contribution. You are right, i am confused why you can find two points $c,d$ such that $c<\bar{x}<d$ when $f$ is not locally convex around $\bar{x}$ since $c,d$ can be lied on the same direction with $\bar{x}$. – Blind Sep 30 '18 at 3:14
• @antkam Thanks for your contribution and attemption. You are right, i am confused why you can find two points $c,d$ such that $c<\bar{x}<d$ when $f$ is not locally convex around $\bar{x}$ since $c,d$ can be lied on the same side of $\bar{x}$. – Blind Sep 30 '18 at 3:25

Here is a proof for $$n=1$$. Let $$f:\mathbb{R}\to\mathbb{R}$$ be in $$C^2$$, and assume (without loss of generality) that $$\bar{x}=0$$ is a unique local minimum of $$f$$ in $$B_r :=\{x\in\mathbb{R}:|x| and that $$f(0)=0$$. Assume furthermore that there exists $$\epsilon>0$$ such that any $$f_v(x):=f(x) + v\cdot x$$ has a unique local minimum in $$B_r$$ for all $$|v|<\epsilon$$.

We will show that the first derivative $$h:=f'$$ is non-decreasing in some neighborhood of $$0$$, which implies that $$f$$ is convex in that neighborhood, the desired result. The proof is by contradiction: we show that if $$h$$ is NOT non-decreasing near $$0$$, then it must contain infinitely many dog-leg turns converging on $$0$$. This contradicts the condition that $$f_v$$ has a unique solution near $$0$$ for small $$v$$.

First we prove that $$h$$ is non-decreasing on some small interval $$[0,s]$$. If $$h$$ is identically zero in a neighborhood of $$0$$, then $$f\equiv 0$$ in this neighborhood and is convex. So we may assume that $$h$$ is not identically zero near $$0$$. Note that $$h$$ cannot be uniformly $$\leq 0$$ in any interval $$[0,s]$$ since $$0$$ is a unique local minimum of $$f$$ in $$[0,r]$$ and $$h$$ is continuous. Thus, we may choose $$d>0$$ for which $$h(d)>0$$.

Assume to the contrary that $$h$$ is NOT non-decreasing in any interval $$[0,s]$$ for $$s. Then for any $$0<\delta there exists $$v<\delta$$ and $$b with $$0 and $$h(c). This follows from the previous paragraph, the assumption about $$h$$ together with its continuity, and the fact that $$h(0)=0$$. For the same reason we may also choose $$a with $$h(a). Thus we have shown the existence of $$0 for which $$h(a) and $$h(c). The graph of $$h$$ in $$[a,d]$$ is depicted below. It follows we may choose $$\epsilon>0$$ for which $$I:=[v-\epsilon, v+\epsilon]$$ is contained in $$[h(a),h(b)]\cap [h(c),h(d)]$$. Define the sets

$$P:=h(\{x\in[a,b]:h'(x)>0\})$$ $$P':=h(\{x\in[c,d]:h'(x)>0\})$$

Lemma $$(I\cap P)\cap(I\cap P')$$ is non-empty.
(Proof forthcoming. It proceeds by showing that $$|I\cap P| = |I|$$ where $$|\cdot|$$ is Lebesgue measure.)

The Lemma implies that there exists $$y\in(I\cap P)\cap(I\cap P')$$. Thus there exist $$x_1\in[a,b]$$ and $$x_2\in[c,d]$$ for which $$h(x_1)=h(x_2)=y$$ and $$h'(x_1)>0, h'(x_2)>0$$.

Since $$f_v'(x) = h(x) + v$$, we have shown that for any $$s$$ and sufficiently small $$v$$ there exists $$x_1 \neq x_2$$ for which $$f_v'(x_j)=0$$ and $$f_v''(x_j)>0$$. This contradicts the requirement that $$f_v$$ has a unique local minimum in $$B_r$$ for sufficiently small $$v$$.

Thus, $$h$$ is non-decreasing in $$[0,s]$$. A similar argument shows that $$h$$ is non-decreasing in $$[t,0]$$ for some $$t<0$$. It follows that $$f$$ is convex in $$[t,s]$$.

• @Blind:Thoughts? – MathManM Oct 6 '18 at 20:08
• @Blind: There was some hand-waving in the original, which I cleaned up. Also added a graph for clarity. – MathManM Oct 8 '18 at 1:28
• Could you explain the following questions: Why $f=0$ in case h is identically zero in a neighborhood of 0? What is uniformly $\leq 0$? Could you make clear the way of choosing $a,b,c,d$? – Blind Oct 8 '18 at 13:29
• @Blind: My proof assumes that $f(0)=0$ in the first sentence. So if $h=0$ in a neighborhood of $0$, then $f=0$ in that same neighborhood, since $h=f'$. "By uniformly $\leq 0$" I simply meant that $h\leq 0$ in some neighborhood of $0$; 'uniformly' was an unnecessary adjective. – MathManM Oct 8 '18 at 18:04
• @Blind: On choosing $a,b,c,d$. The existence of $b<c<d$ with the prescribed properties follows from the assumption made that $h$ is not non-decreasing on any interval $[0,s]$. – MathManM Oct 8 '18 at 18:08