4
$\begingroup$

Is the following statement true? If so, how can I find a proof?

Suppose that $f_1$ and $f_2$ are strictly convex functions on a convex set $X \subseteq \mathbb{R}^n$. If $f_1$ and $f_2$ have minimum, then $f = f_1+f_2$ has a minimum.

I understand that $f$ is strictly convex and bounded from below, because $f_1$ and $f_2$ have a unique minimum. But can it happen that $f$ will never attain its infimum?

$\endgroup$
  • $\begingroup$ I had an answer but deleted it when I realized the subtle point here. I guess a counterexample would require $X$ to be open, and for $f$ to obtain its minimum on the boundary of $X$. If $X$ is closed, it certainly can't happen. $\endgroup$ – Michael Grant Jul 21 '16 at 15:44
4
$\begingroup$

Here is a counter-example for $n=2$.

Take $f_1(x) = x_1^2 + x_2^2$, $f_2(x) = 10(x_1-1)^2 + (x_2-1)^2$, both are clearly strictly convex with global minima at $p_1:=(0,0)$ and $p_2:=(1,1)$, respectively. The global minimum of $f_1+f_2$ is at $p_3:=(10/11, 1/2)$, which is not a convex combination of the minima of $f_1$ and $f_2$.

Now define $X$ to be an $\epsilon$-neigborhood of the convex hull of the global minima of $f_1$ and $f_2$: $$ X = \{ (x_1,x_2): \ |x_1-x_2| < \epsilon\}. $$ For $\epsilon < 9/22$ the point $p_3$ is not in $X$. This is the only point in $\mathbb R^2$, where the gradient of $f_1+f_2$ is zero. Hence, $f_1+f_2$ has no minimum in the open set $X$.


The claim is true for $n=1$, though. Let $X$ be convex, hence an interval. Let $x_1$ and $x_2$ denote the minima of $f_1$ and $f_2$, respectively. Let me assume that $f_1$ and $f_2$ are continuously differentiable. I am sure that the claim is true in the general case as well.

Suppose $x_1<x_2$. By strict monotonicity of the gradient of strictly convex functions it follows $f_1'(x_2)>0$ and $f_2'(x_1)<0$. Hence, the derivative of $f_1+f_2$ changes sign on $X$. Thus there is a zero, which is the minimum of $x_1+x_2$.

$\endgroup$
  • $\begingroup$ Perfect. Well done! $\endgroup$ – Michael Grant Jul 24 '16 at 19:06

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.