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

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.

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$

• Can you please elaborate on how you were able to say $\max\{x_1,\ldots,x_n\} = \max_{y \in \Delta_n}x^Ty$?
– MAS
Apr 2 '17 at 19:03
• Can you please elaborate on how you were able to say $\max\{x_1,\ldots,x_n\} = \max_{y \in \Delta_n}x^Ty$? @dohmatob
– MAS
Apr 3 '17 at 11:45
• @MAS sorry, I'm seeing your requests just now. Please see updated answer. May 7 '18 at 0:13
• The devil is in the details. The Fact relies on the Biconjugate Theorem which in turn is not so easy (separation of epigraphs etc.) May 7 '18 at 4:35
• Yes, the Fenchel-Moreau (aka Biconjugate Theorem) fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Fenchel-Moreau is definitely not the simplest thing to prove... May 7 '18 at 9:01

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 \}$.

• Is there a typo here: "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$." @littleO
– MAS
Mar 16 '17 at 10:44
• @MAS Hmm I don't see the typo, can you elaborate? Mar 16 '17 at 10:45
• @MAS After seeing dohmatob's answer I realized my answer was wrong! I think I corrected it now, but you should accept dohmatob's answer instead of this one because it's a more clean solution. Mar 16 '17 at 12:34
• Both derivations are certainly worthwhile. But given that it's such a pain in the butt to derive conjugates, it's really handy to have principles like the one @dohmatob has offered. Mar 16 '17 at 17:37

Another answer is using Holder's inequality. Since $$l1$$ in the Holder's inequality is paired with $$l\infty$$, we can use this to our advantage. We have $$x^Ty\le ||x||_q||y||_p \quad: \quad \frac{1}{p}+\frac{1}{q}=1$$ by setting $$p=1$$ we have $$q=\infty$$ and the infinity norm is the largest value of the vector. So $$||x||_{\infty} = \max_{\forall i} |x_i|$$. Therefore we can say $$f(x)=||x||_{\infty}$$ and for the convex conjugate function, we have

$$f^*(y) = \sup_{x\in\mathbb{R}^n} \left(y^Tx-f(x)\right) \le \sup_{x\in\mathbb{R}^n}\left(||x||_{\infty}||y||_{1}-f(x)\right) = \sup_{x\in\mathbb{R}^n}\left(f(x)||y||_{1}-f(x)\right)=\sup_{x\in\mathbb{R}^n}\left(f(x)\times(||y||_{1}-1)\right)$$ Apparently this function is unbounded above for an arbitrary choice of $$x$$ unless the factored term be equal to zero. so we have this solution: $$f^*(y) = \begin{cases} 0 \qquad ||y||_{1}=1 \\ \infty \qquad O.W.\end{cases}$$