1
$\begingroup$

This question is migrated from MathStackExchange where it seemed to be too hard. I wonder does anyone here have any ideas?

Suppose $f: K \to \mathbb R$ is $\mathcal C^2$ and strictly convex on some compact convex $K \subset \mathbb R^n$. That means $f(a x + by) < a f(x) + bf(y)$ for all $x,y \in K$ and $a,b \in (0,1)$ with $a+b=1$.

Strict convexity implies $f$ has a unique minimum over $K$. In all examples I have found, this minimum also coincides with the minimum of $\|\nabla f\|$. I wonder if it is always true but am unable to find or invent a proof unless $n=1$.

For $n = 1$ the gradient $\nabla f(x)=f'(x)$ is just the derivative and strict convexity is equivalent to $f'$ being strictly increasing. In that case we can show $\min f$ occurs at the minimiser of $|f'|$.

Consider first the case that $f'(a) = 0$ for some $a \in K$. By strict convexity there is only one such $a$. Clearly $a$ is the unique minimiser of $|f'|$. But $f'(a) = 0$ also means $a$ is a local minimum, and then convexity implies $a$ is the global minimum.

Otherwise $f'$ is strictly positive or negative negative. First assume the former. Without loss of generality we have $K =[0,1]$. Then since $f'$ is strictly increasing $|f'(x)| = f'(x)$ has unique minimum at $0$. Also by writing $f(x) = f(0) + \int_0^x f'(y) \, dy$ as the integral of a strictly positive function we see $f$ is also strictly increasing hence also has unique minimum at $0$. A symmetric argument shows for $f'$ strictly negative both functions have unique minimum at $1$.

Of course for $n>1$ there is no notion of the gradient vector being positive and the proof fails to generalise. Also the higher-dimensional analogue of $f(x) = \int_0^x f'(y) \, dy$ is Stoke's theorem which does not recover values of $f$ at a point. Rather the left-hand-side becomes the integral over the boundary of whatever region we're integrating over on the right.

One fact I imagine is useful is the function $F(x) = \|\nabla f(x)\|^2$ is differentiable with gradient $\nabla F(x) = H(x) \nabla f(x)$ where $H(x)$ is the Hessian of $f$ at $x$. By strict convexity the Hessian is positive definite.

Now $F(x)$ achieves its minimum at some $a \in K$. Without loss of generality $a=0$. Unless $F(a) = 0$ we know the gradient vector $\nabla F(a)$ is normal to $K$. That means $K$ is contained in the halfspace $\{x \in \mathbb R^n: H(x) \nabla f(x) \cdot x\ge 0\}$. That tells us moving in the direction $\nabla f$ a small amount will increase $F$ since the directional derivative is $H(x) \nabla f(x) \cdot \nabla f(x) = \nabla f(x) ^T H(x) \nabla f(x) > 0$ by positive definiteness.

If $H(x) \nabla f(x) $ was parallel to $\nabla f(x) $ we would be done but in general this doesn't occur. For example consider the function $f(x) = x^2 + 2y^2$ over $K=[1,2]^2$. Clearly $f$ is minimised at $(1,1)$ where the gradient is $\nabla f(1) = (2,4)$. We can compute $F(x) = (2x)^2 + (4y)^2 = 4x^2 + 16y^2$. This is also minimised at $(1,1)$ where the gradient is $\nabla F(1) =(8,32)$. In this case the gradients are not parallel but they are both normal to $K$.

Note: There is something perverse about the statement that $f$ has the same minimiser as $\|\nabla f \|$ because $f$ is coordinate-independent (obviously) but $\|\nabla f \|$ is not -- it depends on some choice of inner-product to define. However I don't think this should be a problem since changing the inner product should only amount to skewing the domain. That transform takes straight lines to straight lines so it should preserve convexity and take the points we're interested to onto each other.

$\endgroup$
5
$\begingroup$

Consider $f(x,y)=x^3+ay^3$ ($a>0$) on $K=\{x,y\ge 0,x+y=1\}$ (or in a thin convex set around this interval). The minimum of $f$ is at the point where $x^2=ay^2$ or $x=a^{1/2}y$. The square of the gradient is (up to a constant) $x^4+a^2y^4$ and its minimum is attained when $x^3=a^2y^3$ or $x=a^{2/3}y$, which is a different point for $a\ne 1$.

$\endgroup$
3
  • $\begingroup$ Note also that the same example works on $K = \{ 0 \leq x,y,\ x+y \leq 1 \}$, so requiring that $K$ be full dimensional doesn't help. $\endgroup$ – David E Speyer Dec 13 '18 at 14:42
  • $\begingroup$ @DavidESpeyer You meant $1\le x+y \le 2$, right? $\endgroup$ – fedja Dec 13 '18 at 15:11
  • $\begingroup$ Whoops! You are right, of course. $\endgroup$ – David E Speyer Dec 13 '18 at 15:19

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.