Given the problem $\max x^Ty$
s.t $e^Ty=k$
$0\leq y\leq \mathbb{e}$
Prove that the optimal value is $f(x)=\sum_{i=1}^{k}x_{[i]}$ where $x_{[i]}$ is the ith largest values in the vector $x$
I've tried at first with lagrangian but it didn't work(if someone can prove it like this I would like to see).
So I tried the following assume that $y^*$ is optimal vector of the given problem where $y_i^*,y_j^*<1$(wlog only 2 indices) such that $y_i^*+y_j^*=1$ and $x_j\geq x_i$
Looking at the optimal value only at the two coordiants $i,j$ we get $x_iy_i^*+x_jy_j^*\leq(y_i^*+y_j^*)x_j=x_j$ and therefore the optimal value is $f(x)$.
I'm not sure if the way I've done it is right
Note-this excerise is given from duality section
Since the constraint set is compact we know there is a maximiser. We must have that the dimension $n \ge k$ otherwise there are no solutions. I am assuming that $k$ is a natural number.
We can assume that $x_1 \ge x_2 \ge \cdots $.
Suppose $y$ is an optimal solution.
If $y_1 <1$ then $\sum_{i>1} y_k = k-y_1 > k-1 \ge 1$ and so we can reduce $y_n, y_{n-1},...$ and add the combined reduction to $y_1$ so that $y_1 = 1$ without increasing the cost. (There must be enough non zero elements in $y_2,...$ so that we can do that and the cost does not decrease because of the ordering of the $x_i$.)
We can see that $y'=(y_2,...,y_n)$ must solve the problem $\max_{e^T y'=k', \ 0 \le y' \le e} (x')^T y'$, where $x' = (x_2,...)$ and $k'=k-1$.
We can repeat as long as $k' >0$.
Hence we can take a maximiser to be $(1,....,1,0,...,0)$ where there are $k$ ones and hence the optimal value is $x_1+\cdots + x_k$.