Is the max-min a convex combination of the minima?

Question

Let $f_1,\ldots,f_n$ be convex continuous functions defined in a convex compact domain $C\subseteq \mathbb{R}^d$, and let $$ x_i := \arg\min_{x\in C} f_i(x). $$

Let $g$ be a convex function defined by $g(x) := \max_{i}f_i(x)$, and let $$ y := \arg\min_{x\in C} g(x). $$

Is $y$ a convex combination of $x_1,\ldots,x_n$?

Here is an illustration of the question for $n=2$ functions in dimension $d=1$:

EDIT: We can assume that $C$ is compact and the functions $f_i$ are continuous.

Do we have any other asusmptions on $C$ or the $f_i$? e.g. is $C$ closed or compact? are $f_i$ lower semicontinuous or coercive? — Zim, Jun 06 '22 at 08:50
@Zim we can assume that $C$ is compact and that the $f_i$ are continuous. Edited. — Erel Segal-Halevi, Jun 07 '22 at 05:07

score 1 · Accepted Answer · answered Jun 07 '22 at 06:39

The minimiser of the maximum $y$ does not have to be a convex combination of the $x_i$. Take $f_1(u,v)=(u-v)^2+\frac{v^2}{100}$, $f_2(u,v)=(u+v-1)^2+\frac{v^2}{100}$. That is, $f_1$ and $f_2$ are elongated valleys in different directions, where the floor of each valley has a slight depression on the $u$-axis. The minimum of $\max\{f_1,f_2\}$ lies in the intersection of the 'valleys', off the $u$-axis.

Is the max-min a convex combination of the minima?

1 Answers1