2
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ Can you please elaborate on how you were able to say $\max\{x_1,\ldots,x_n\} = \max_{y \in \Delta_n}x^Ty$? $\endgroup$
    – MAS
    Apr 2 '17 at 19:03
  • $\begingroup$ 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 $\endgroup$
    – MAS
    Apr 3 '17 at 11:45
  • $\begingroup$ @MAS sorry, I'm seeing your requests just now. Please see updated answer. $\endgroup$
    – dohmatob
    May 7 '18 at 0:13
  • $\begingroup$ The devil is in the details. The Fact relies on the Biconjugate Theorem which in turn is not so easy (separation of epigraphs etc.) $\endgroup$
    – max_zorn
    May 7 '18 at 4:35
  • $\begingroup$ 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... $\endgroup$
    – dohmatob
    May 7 '18 at 9:01
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – MAS
    Mar 16 '17 at 10:44
  • $\begingroup$ @MAS Hmm I don't see the typo, can you elaborate? $\endgroup$
    – littleO
    Mar 16 '17 at 10:45
  • $\begingroup$ @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. $\endgroup$
    – littleO
    Mar 16 '17 at 12:34
  • $\begingroup$ 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. $\endgroup$ Mar 16 '17 at 17:37
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.