Any order-reversing involution on convex functions is, up to linear terms, Legendre transform

Analysis 2 Minutes

You need to know: Euclidean space {\mathbb R}^n, scalar product \langle x,y \rangle=\sum\limits_{i=1}^n x_iy_i in {\mathbb R}^n, extended real line \bar{\mathbb R} = {\mathbb R}\cup\{\pm \infty\}, convex function \phi: {\mathbb R}^n \to \bar{\mathbb R}, lower-semi-continuous function \phi: {\mathbb R}^n \to \bar{\mathbb R}, supremum.

Background: A map B:{\mathbb R}^n \to {\mathbb R}^n is called linear if B(x+y)=B(x)+B(y) and B(\alpha x)=\alpha B(x) for all x,y \in {\mathbb R}^n and \alpha\in{\mathbb R}, symmetric if \langle Ax,y \rangle = \langle x,Ay \rangle for all x,y \in {\mathbb R}^n, and invertible if B(x)\neq 0 whenever x \neq 0. Let {\cal C}({\mathbb R}^n) denote the set of all lower-semi-continuous convex functions \phi: {\mathbb R}^n \to \bar{\mathbb R}. Map {\cal L}:{\cal C}({\mathbb R}^n) \to {\cal C}({\mathbb R}^n) given by ({\cal L}\phi)(x) = \sup\limits_{y \in {\mathbb R}^n}(\langle x,y \rangle -\phi(y)) is called the Legendre transform.

The Theorem: On 1st May 2007, Shiri Artstein-Avidan and Vitali Milman submitted to the Annals of Mathematics a paper in which they proved that for every map T :{\cal C}({\mathbb R}^n) \to {\cal C}({\mathbb R}^n) (defined on the whole domain {\cal C}({\mathbb R}^n)) satisfying (P1) TTf=f and (P2) f \leq g implies Tf \geq Tg, there exists a constant C_0 \in {\mathbb R}, a vector v_0\in {\mathbb R}^n, and an invertible symmetric linear map B such that (T f)(x) = ({\cal L}f)(Bx+v_0) + \langle x, v_0 \rangle + C_0 for all x \in {\mathbb R}^n.

Short context: The Legendre transform is a central tool in convex analysis and optimisation, with numerous applications. Map T satisfying properties (P1) and (P2) in the Theorem is called an order-reversing involution. Is it easy to check that the Legendre transform satisfies these properties. The Theorem states a somewhat surprising converse: any order-reversing involution must in fact be the Legendre transform, up to linear terms.

Links: The original paper is available here. See also Section 9.5 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment