This material will be published by Cambridge University Press as Bandit
Algorithms by Tor Lattimore and Csaba Szepesvari. This pre-publication version
is free to view and download for personal use only. Not for re-distribution, sale,
or use in derivative works.©Tor Lattimore and Csaba Szepesvari 2017.
The latest version is available athttp://banditalgs.com. Feedback on any
aspect is very welcome: [email protected]
26 Foundations of Convex Analysis ( )
Our coverage of convex analysis is necessarily extremely brief. We introduce only
what is necessary and refer the reader to standard texts for the proofs.
26.1 Convex sets and functions
A setA⊆Rdis convex if for anyx,y∈Ait holds thatαx+ (1−α)y∈Afor all
α∈(0,1). Theconvex hullof a collection of pointsx 1 ,x 2 ,...,xn∈Rdis the
smallest convex set containing the points, which also happens to satisfy
co(x 1 ,x 2 ,...,xn) =
{
x∈Rd:x=
∑n
i=1
pixifor somep∈Pn− 1
}
.
The convex hull is also defined for an arbitrary setA⊂Rd:co(A), the convex hull
ofA, is defined to be the smallest convex set containingA(see (c) in Figure 26.1).
For the rest of the section we letA⊆Rdbe convex. LetR ̄=R∪{−∞,∞}be
the extended real number system and define operations involving infinities in the
natural way (see notes).
Definition26.1.An extended real-valued functionf:Rd→R ̄isconvexif its
epigraphEf={(x,y)∈Rd×R:y≥f(x)}⊂Rd+1is a convex set.
Thedomainof an extended real-valued function onRdisdom(f) ={x∈Rd:
f(x)<∞}. ForS⊂Rd, a functionf:S→R ̄is identified with the function
f ̄:Rd→R ̄which coincides withfonSand is defined to take the value +∞
outside ofS. It follows that iff:S→Rthendom(f) =S. A convex function is
properif its range does not include−∞and its domain is nonempty.
For the rest of the chapter we will write “letfbe a convex” to mean that
f:Rd→R ̄is a proper convex function.
