6
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

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

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.