convex optimizationconvex-analysis
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?
No, take the function $f: (1, 2) \to \mathbb{R}$, $x \mapsto x^2$. Alternatively, you can consider $\exp: \mathbb{R} \to \mathbb{R}$.
This statement can even fail when the domain is compact, take for example the function $f: [0, 1] \to \mathbb{R}$ that is defined by $f(x) = \begin{cases} 1 & x = 0 \\ x^2 & x > 0\end{cases}$.
If the domain is compact and $f$ is continuous, the statement holds. The existence of a minimum follows directly from the compactness of the domain and the continuity of the function. If $f$ assumes its minimum at two different points $x \ne y$, then by definition of strict convexity $f\left(\frac{x + y}{2}\right) < \frac{1}{2}(f(x) + f(y)) = f(x)$, in contradiction to the choice of $x$.
I found a counterexample as I was trying to construct a proof. Let me explain my thought process.
Let $x'$ be on the boundary and assume $x'\not\in C$. Since $x'$ is on the boundary, it has a separating hyperplane. Let $c$ be perpendicular to that plane and consider the function $f(x)=c^Tx$. Since $x'$ is on the boundary, function values can get arbitrarily close to $c^Tx'$, but by construction, cannot exceed $c^Tx'$ (the separating hyperplane is an isocurve). Since $f$ attains its maximum on $C$, there is a point $x^* \in C$ for which $c^Tx' = c^Tx^*$. So, $x^*$ and $x'$ share the same separating hyperplane.
The next step in my proof would be to construct a point on the other side of $x'$ that is in $C$ and reach a contradiction with convexity. This is where I had the aha moment.
Consider the following set, which is a closed rectangle and the first quadrant of a closed circle, minus the point where the rectangle meets the circle.
Best Answer
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$.