# A property of the minimum of a sum of convex functions

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?

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

• Yes-thank you! I just posted a follow-up question; I'd appreciate if you could look at it if you have time. – robinson Apr 13 '13 at 6:00