26.4 Legendre functions 294
26.4 Legendre functions
0 1 2 3
− 1
− 0. 5
0
xlog(x)−x
Figure 26.3f(x) =xlog(x)−x: the
archetypical Legendre function
In this section we use various topological
notions such as the interior, closed set and
boundary. The definitions of these terms are
given in the notes. Letfbe a convex function
andA=dom(f) andC=int(A). Thenfis
Legendreif
(a)Cis nonempty;
(b)fis differentiable and strictly convex on
C;
(c) limn→∞‖∇f(xn)‖ 2 = ∞ for any se-
quence (xn)nwithxn∈Cfor allnand
limn→∞xn=xand somex∈∂C.
The intuition is that the set{(x,f(x)) : x∈dom(A)}is a ‘dish’ with ever-
steepening edges towards the boundary of the domain. Legendre functions have
some very convenient properties:
Theorem26.6.Letf:Rd→R ̄be a Legendre function. Then:
(a)∇fis a bijection betweenint(dom(f))andint(dom(f∗))with the inverse
(∇f)−^1 =∇f∗.
(b)Df(x,y) =Df∗(∇f(y),∇f(x))for allx,y∈int(dom(f)).
The next corollary formalizes the ‘dish’ intuition by showing the directional
derivative along any straight path from a point in the interior to the boundary
blows up.
Corollary26.7.Letfbe Legendre andx∈int(dom(f))andy∈∂int(dom(f)),
thenlimα→ 1 〈∇f((1−α)x+αy),y−x〉=∞.
Example26.8. Letfbe the Legendre function given byf(x) =^12 ‖x‖^22 , which
has domaindom(f) =Rd. Thenf∗(x) =f(x) and∇fand∇f∗are the identity
functions.
Example26.9.Letf(x) =− 2
∑d
i=1
√x
iwhenxi≥0 for alliand∞otherwise,
which has dom(f) = [0,∞)d and int(dom(f)) = (0,∞)d. The gradient is
∇f(x) =− 1 /
√
x, which blows up (in norm) on any sequence (xn) approaching
∂int(dom(f)) ={x∈[0,∞)d:xi= 0for somei∈[d]}. Here,
√
xstands for the
vector (
√
xi)i. In what follows we will often use the underlying convention of
extending univariate functions to vector by applying them componentwise. Note
that‖∇f(x)‖ →0 as‖x‖ → ∞: ‘+∞’ is not part of the boundary ofdom(f).
Strict convexity is also obvious sofis Legendre. In Exercise 26.7 we ask you
to calculate the Bregman divergences with respect tofandf∗and verify the
results of Theorem 26.6.
