Let $1 \leq r \leq n$ be an integer. Define $\|x\|=\max_{1 \leq i_1 \leq \dots \leq i_r \leq n} |x_{i_1}| + \cdots + |x_{i_r}|$ as a norm on $\mathbb{R}^n$.
My question is why $\|x\|$ can be computed as the optimal value of the following problem $$ \max_y \quad x^Ty \\ \text{subject to} \quad \|y\|_{\infty} \leq 1 \\ \quad \quad \quad \quad \|y\|_1 \leq r $$
I'm very stuck on this question and would appreciate any help on it. Thanks!
To solve the original problem, we just have to sort the entries of $x$ and take the first $r$ elements with the largest elements and sum the magnitude up. Hence, we can just focus on the magnitude of $x$ and the optimization problem is equivalent to
$$\max_y \sum_i |x_i|y_i$$
subject to
$$0 \le y_i \le 1, i \in \{1,\ldots, n\}$$
$$\sum_i y_i \le r$$
of which we know an optimal solution is attained at BFS, that is there is an optimal solution where there will be $n$ independent constraints that are active.
Suppose the last constraint is not active, that is sum of $y_i$ is less than $r$, notice that we can always make one more $y_i$ to take value $1$ and it remaisn feasible and the solution won't be worse. Hence, we can assume that the last constraint is active. If the last constraint is active, and suppose we let at least $n-1$ of the $y_i$ takes value $\{0,1\}$. Since the sum is an integer, each $y_i$ must be integer as well and hence the last $y_i$ will also take value from $\{0,1\}$, that is exactly $r$ components will take value $1$. In the original formulation, it means that there is an optimal solution with exactly $r$ of them will take value with magnitude $1$.