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}$.

Thank you for all answers, constructive comments and useful references.

My question is related to the following topics:

  1. Is a smooth function convex near a local minimum?
  2. Local minimum implies local convexity?
  3. Does a unique global and local minimum imply (strict) convexity?
  • 1
    $\begingroup$ It's not true that $\nabla ^2 f(\overline{x})>0$. Take for instance $f(x) = x^4$. $\endgroup$
    – user587377
    Sep 7 '18 at 18:05
  • $\begingroup$ @CVdeFire Thanks for your comment. I change a little in my question. $\endgroup$
    – Blind
    Sep 7 '18 at 18:19
  • 1
    $\begingroup$ @Blind -- i am not an expert (by a long shot) so i have a few potentially dumb questions :) -- [1] i think we continue to assume $f$ is differentiable (or even twice differentiable), right? [2] 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? $\endgroup$
    – antkam
    Sep 29 '18 at 4:07
  • $\begingroup$ @antkam one dimensional is deserved to be posted if your solution is interesting. $\endgroup$
    – Blind
    Sep 29 '18 at 4:33
  • $\begingroup$ 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. $\endgroup$ Oct 1 '18 at 0:01

I was thinking this has a chance in $\mathbb R$ but once you step in $\mathbb R^2$ there should be counterexamples. Let us have a look at the polynomial function: $f\colon (x,y)\in \mathbb R^2 \longmapsto x^4 + 12 x^2 y^2 + y^4 + (x+2y)^2$. You can factor it as $f(x,y) = (x^2+y^2)^2 + 10x^2y^2 + (x+2y)^2$, this establishes that $f(0,0) = 0$ is the unique minimum.

We should note that $f$ is not locally convex around $(0,0)$. For example you can check that, \begin{equation} \begin{bmatrix} 2 \\ -1 \end{bmatrix}^\top \nabla^2 f(t,t) \begin{bmatrix} 2 \\ -1 \end{bmatrix} = -12t^2 < 0, \end{equation} for all $t \neq 0$, no matter how small.

It seemed that there existed a unique minimum for a small enough linear perturbation, however upon closer inspection the gradient map is not injective. I have plotted (rotated and resized) $\nabla f(r\cos \theta, r\sin\theta)$ with $r$ fixed smaller and smaller, and with $\theta$ varying from $0$ to $2 \pi$. It seems to describe a deformed circle around $(0,0)$ (it actually becomes close to a segment) but those circles actually overlap (see the attached plot). In any case the equation is, \begin{equation} \begin{bmatrix} 4 x^3 + 24 x y^2 + 2 (x + 2 y) \\ 24 x^2 y + 4 y^3 + 4 (x + 2 y) \end{bmatrix} = \begin{bmatrix} -u \\ -v \end{bmatrix}. \end{equation}

Arcs of the gradient are drawn, $\nabla f(r \cos t, r \sin t)$, for $r=10^{-7}(1+n/4)$ with $n=1,\dots,10$ and $t = 0 \dots 2\pi$. The picture has been rotated and stretched to show clearly the overlap.

Plot of the arc of the gradients for small and varying radius.


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!

  • 1
    $\begingroup$ 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$. $\endgroup$
    – Ѕааԁ
    Sep 29 '18 at 8:16
  • 1
    $\begingroup$ @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). $\endgroup$
    – antkam
    Sep 29 '18 at 14:28
  • 1
    $\begingroup$ 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... $\endgroup$
    – antkam
    Sep 29 '18 at 14:34
  • $\begingroup$ @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}$. $\endgroup$
    – Blind
    Sep 30 '18 at 3:14
  • $\begingroup$ @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}$. $\endgroup$
    – 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|<r\}$ 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<r$. Then for any $0<\delta<h(d)$ there exists $v<\delta$ and $b<c<d$ with $0<h(b)<h(d)$ and $h(c)<v<h(b)$. 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<b$ with $h(a)<v$. Thus we have shown the existence of $0<a<b<c<d$ for which $h(a)<v<h(b)$ and $h(c)<v<h(d)$. The graph of $h$ in $[a,d]$ is depicted below.

enter image description here

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]$.

  • $\begingroup$ @Blind:Thoughts? $\endgroup$
    – MathManM
    Oct 6 '18 at 20:08
  • $\begingroup$ @Blind: There was some hand-waving in the original, which I cleaned up. Also added a graph for clarity. $\endgroup$
    – MathManM
    Oct 8 '18 at 1:28
  • $\begingroup$ 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$? $\endgroup$
    – Blind
    Oct 8 '18 at 13:29
  • $\begingroup$ @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. $\endgroup$
    – MathManM
    Oct 8 '18 at 18:04
  • $\begingroup$ @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]$. $\endgroup$
    – MathManM
    Oct 8 '18 at 18:08

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.