Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is achieved, denoting $$x_i = \arg \min_{x \in \mathbb{R}^n} g_i(x).$$ It seems natural to guess that all minima of $$ g_1(x) + g_2(x) + \cdots + g_k(x)$$ will lie in the convex hull of $\{x_1, \ldots, x_k\}$. Is this true?
[Math] A property of the minimum of a sum of convex functions
convex optimizationconvex-analysisoptimization
Best Answer
False, consider the functions
$$g_1(x,y) = \frac19(x-1)^2 + y^4 \quad\text{ and }\quad g_2(x,y) = x^4 + \frac19 (y-1)^2$$
Their global minima are achieved at $x_1 = (1,0)$ and $x_2 = (0,1)$ respectively.
However
$$g_1(x,y) + g_2(x,y) = \frac19 (x-1)^2 + x^4 + \frac19 (y-1)^2 + y^4$$
Notice $$\frac{d}{dx} \left( \frac19 (x-1)^2 + x^4 \right) = \frac{2\,\left( 3\,x-1\right) \,\left( 6\,{x}^{2}+2\,x+1\right) }{9}$$
The global minimum of $g_1(x,y) + g_2(x,y)$ is achieved at $(x,y) = (\frac13,\frac13)$, outside the convex hull of $(0,1)$ and $(1,0)$.