What is the convex conjugate of $f=\max_{i=1\dots n}x_i$?

Question

What is the convex conjugate of $f=\max_{i=1\dots n}x_i$ on $\mathbb{R}^n$?

My attempt: $$f^*(y)=\sup_{x\in\mathbb{R}^n}\left(y^Tx-f(x)\right)$$ $$f^*(y)=\sup_{x\in\mathbb{R}^n}\left(y^Tx-\max_{i=1\dots n}x_i\right)$$ let the max occur at index $t$ then, $$f^*(y)=\sup_{x\in\mathbb{R}^n}\left(y^Tx-x_t\right)=\sup_{x\in\mathbb{R}^n}\left(\sum_{i\ne t}^ny_ix_i+y_tx_t-x_t\right)$$

I am not sure how to proceed.

Answer 1

If $y_i < 0$ for some $i$, then you can choose $x_i$ to be very negative and let the other components of $x$ be zero to see that the supremum is $\infty$. If $y \geq 0$ and $\sum_i y_i > 1$, you can choose $x$ to have very positive components of equal magnitude to see that the supremum is $\infty$. If $y \geq 0$ and $\sum_i y_i < 1$, you can choose $x$ to have very negative components of equal magnitude to see that the supremum is $\infty$. Finally, if $y \geq 0$ and $\sum_i y_i = 1$, then $y^T x \leq \max_i x_i$ for all $x$ and so the supremum is at most $0$. So, $f^*$ is the indicator function of the set $S = \{ y \geq 0 \mid \sum_i y_i = 1 \}$.

Answer 2

Fact: The support function and indicator function of a closed convex nonempty set are convex conjugates of one another.

Proof. Let $ C$ be a closed convex nonempty subset of a Hilbert space $\mathcal H$. For any $x \in \mathcal H$ One computes $$i_C^*(x) := \sup_{y \in \mathcal H}x^Ty - i_C(y) = \sup_{y \in C}x^Ty,$$ which is precisely the support function $\sigma_C$ of $C$ evaluated at $x$. Finally, $\sigma_C^* = i_C^{**} = i_C$, since $i_C$ is a is convex lower semi-continuous function. $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \Box$

Now, $f(x):= \max\{x_1,\ldots,x_n\} = \max_{y \in \Delta_n}x^Ty = \sigma_{\Delta_n}(x)$, where $\Delta_n$ is the unit n-simplex. Thus $f^* = i_{\Delta_n}$.

Update

As bonus, OP requests a proof for the fact that

the maximum of a linear function on a simplex is indeed attained on a vertex!

This result is well-known to game-theorists, and should have been first stated and proved by Nash, if I'm not mistaken. It says that

in a best-response mixed-strategy, every pure component is also optimal!

Proof. Let's show that if $y^* \in \Delta_n$ maximizes $x^Ty$ then so does every vertex in its support. For this, it suffices to show that $x_i = x_j$ for all $i,j \in \operatorname{supp}(y^*)$. Indeed, by way of contradiction, suppose $x_i > x_j$ for some $i,j \in \operatorname{supp}(y^*)$. Then $x^Ty^* > x^Ty^*(j \rightarrow i)$ where $y^*(i \rightarrow j) \in \Delta_n$ is formed from $y^*$ by replacing the $j$th coordinate $y^*_j$ with $y^*_i + y^*_j$ and the $i$th coordinate with $0$. But this contradicts the optimality of $y^*$. $\quad\quad\quad\Box$