26.1 Convex sets and functions 291(a) (b) (c)(d) (e) (f)Figure 26.1(a) is a convex set. (b) is a nonconvex set. (c) is the convex hull of a
nonconvex set. (d) is a convex function. (e) is nonconvex, but all local minimums are
global. (f) is not convex.Permitting convex functions to take values of−∞is a convenient standard
because certain operations on proper convex functions result in improper
ones (infimal convolution, for example). These technicalities will never bother
us in this book, however.A consequence of the definition is that for convexfwe have
f(αx+ (1−α)y)≤αf(x) + (1−α)f(y)
for allα∈(0,1) andx,y∈dom(f). (26.1)In fact, the inequality holds for allx,y∈Rd.Some authors use Eq. (26.1) as the definition of a convex function along
with a specification that the domain is convex. IfA⊆Rdis convex, then
f:A→Ris convex if it satisfies Eq. (26.1) withf(x) =∞assumed for
x /∈A.A function isstrictly convexif the inequality in Eq. (26.1) is always strict.
TheFenchel dualof a functionfisf∗(u) =supx〈x,u〉−f(x), which is convex
because the maximum of convex functions is convex. The Fenchel dual has many
nice properties. Most important for us is that for sufficiently nice functions∇f∗
is the inverse of∇f(Theorem 26.6). Another useful property is that whenfis
a proper convex function and its epigraph is closed, thenf=f∗∗. The Fenchel
dual is also called the convex conjugate. Iff:Rd→R ̄is twice differentiable
on the interior of its domain, then convexity offis equivalent to its Hessian
having nonnegative eigenvalues for allx∈int(dom(f)). The field of optimization