Simplify $\sup_x y^\top x -\log(\sum_i e^{x_i})$
The first order conditions yield $y_i=\frac{e^{x_i}}{\sum_i e^{x_i}}$. How do I eliminate $x_i$ from the equation? I know the answer to be $\sum y_i \log(y_i)$ and I am able to verify, but how to prove this?
There must be a less messy way of doing this...
Let $\phi(x,y) = \sum_k x_ky_k - \log(\sum_k e^{x_k})$, and $f(y) = \sup_x \phi(x,y)$.
Then $f$ is finite iff $y_k \ge 0$ and $\sum_k y_k = 1$. Furthermore, if these conditions on $y$ hold, we have $f(y) = \sum_k y_k \log y_k$, where we interpret $(0 \log 0) $ as zero.
If $y \in \mathbb{R}^1$, we have $\phi(x,y) = x(y-1)$, from which the result is obvious.
Let $y \in \mathbb{R}^n$, $n >1$ and suppose $y_1 <0$. Consider $\eta(x)=\phi(y,(x,0,...,0))= xy_1-\log(n-1+e^x)$, and note that $\lim_{x \to -\infty} \eta(x) = \infty$.
Now look at $\gamma(x) = \phi(y,(x,...,x)) = x(\sum_ky_k -1) - \log n$. It is clear that if $\sum_ky_k \neq 1$, then either $\lim_{x \to -\infty} \gamma(x) = \infty$ or $\lim_{x \to +\infty} \gamma(x) = \infty$.
Hence if $f(y)$ is finite we have $y_k \ge 0$ and $\sum_k y_k = 1$.
Now suppose $y_k \ge 0$ and $\sum_k y_k = 1$.
Note that $f(y) = \sup_{x_2,...,x_n} \sup_{x_1} \phi(x,y)$, hence if $y_1=0$, we have $f(y) = \sup_{x_2,...,x_n} \sum_{k \neq 1} x_ky_k - \log(\sum_{k \neq 1} e^{x_k}) $. The same reasoning applies to any other index so we may assume that $y_k >0$ for all $k$.
Let $\lambda(x)=\phi(x,y)$ and note that $D\lambda(x) = y^T-{1 \over \sum_k e^{x_k}}(e^{x_1},...,e^{x_n})$. Since $\lambda$ is a concave function, and $D\lambda((\log y_1,...,\log y_n)) = 0$, we see that $\lambda$ is maximized at $(\log y_1,...,\log y_n)$, and so $f(y) = \sum_k y_k \log y_k < \infty$.