# 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
Commented Apr 2, 2017 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
Commented Apr 3, 2017 at 11:45
• @MAS sorry, I'm seeing your requests just now. Please see updated answer. Commented May 7, 2018 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.) Commented May 7, 2018 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... Commented May 7, 2018 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
Commented Mar 16, 2017 at 10:44
• @MAS Hmm I don't see the typo, can you elaborate? Commented Mar 16, 2017 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. Commented Mar 16, 2017 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. Commented Mar 16, 2017 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}$$

You can solve this with some linear programming duality theory. Indeed, finding $$f^*(y)$$ in that case means computing the optimum of: $$\begin{matrix} \max & y^Tx & - & t & \\ s.t. & x_i & \leq & t &\forall i \in \{1,\dots,n\}\\ & x & \in & \mathbb{R}^n & \\ & t & \in & \mathbb{R} & \end{matrix}$$ Its dual can be worked out to be: $$\begin{matrix} \min & 0 & &\\ s.t. & \lambda_i & = & y_i & \forall i \in \{1,\dots,n\}\\ & 1^T \lambda & = & 1 & \\ & \lambda & \in & \mathbb{R}_{\geq 0}^n \end{matrix}$$ Now, we have that the LP above is infeasible whenever $$y \notin \{x\in \mathbb{R}_{\geq 0}^n :\ 1^T x = 1\}$$ and is feasible with optimum value zero otherwise. When the dual is infeasible it means that the primal is unbounded, while for the other case we just have strong duality that holds automatically, hence: $$f^*(y) = \begin{cases} 0 &if\ y\in \mathbb{R}_{\geq 0}^n & 1^T y = 1\\ +\infty &otherwise. \end{cases}$$