Minimizing maximum is equivalent to minimizing sum over strictly convex set?

62 Views Asked by At

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a strictly concave function. Consider the following quantity $\mathbf{a} \in \mathbb{R^n}$

\begin{align} \DeclareMathOperator{\argmin}{argmin} \mathbf{a} = \argmin\limits_{\mathbf{x} : f(\mathbf{x}) \geq 1} \max_{i= 1, \dots, n} x_i \end{align}

and the following quantity $\mathbf{b} \in \mathbb{R}^n$:

\begin{align} \DeclareMathOperator{\argmin}{argmin} \mathbf{b} = \argmin\limits_{\mathbf{x} : f(\mathbf{x}) \geq 1} \sum_{i=1}^n x_i \end{align}

Is it true that $\mathbf{a} = \mathbf{b}$? I tried to come up with a few counter examples but I could not find any so I feel like $\mathbf{a} = \mathbf{b}$. Any hints?

1

There are 1 best solutions below

2
On BEST ANSWER

Take $f(x) = 2-x^Tx$ on $\mathbb{R}^2$, so $\{x \in \mathbb{R}^2 : f(x) \geq 1\} = \{ x \in \mathbb{R}^2 : x^Tx \leq 1 \}$. You get $a=\{(1,0),(0,1)\}$ and $b=\{(1/\sqrt{2}, 1/\sqrt{2})\}$.