Convex Sets and Functions
Nicholas Ruozzi
University of Texas at Dallas
Where We’re Going
• Multivariable calculus tells us where to look for global optima,
but our goal is to design algorithms that can actually find one!
• This is inherently different than combinatorial optimization,
the true solution may be given by a real number, e.g., , which
we might not even be able to represent in closed form!
• Our notions of what it means to solve these problems needs
to be different
• What makes an optimization problem easy? What makes an
optimization problem hard?
2
Convex Sets
• A set of points is convex if for every pair of points , any point on
the line segment between and is also in
• That is, if , then for all
Convex Set Not a Convex Set
3
Convex Sets
• A set of points is convex if for every pair of points , any point on
the line segment between and is also in
• That is, if , then for all
Convex Set Not a Convex Set
4
Examples of Convex Sets
• Line Segments: for some
𝑦
• Lines, planes, hyperplanes, etc. also define convex sets
5
Examples of Convex Sets
• Half spaces: for some and
𝑇
𝑤 𝑥 +𝑏=0
6
Examples of Convex Sets
• Balls of Radius : for some
• This is called the Euclidean norm or Euclidean distance
because is equal to the length of the line segment between
the points and
7
Examples of Convex Sets
• Balls of Radius : for some
8
Convex Combinations
• We say that is a convex combination of the points if for some
choice of such that
• Let be the set of all points that can be obtained as a convex
combination of the
• In the special case , is just a line segment
• is a convex set called the convex hull of the
where and
9
Convex Combinations
• We say that is a convex combination of the points if for some
choice of such that
• Let be the set of all points that can be obtained as a convex
combination of the
• is a convex set called the convex hull of the
10
Convex Functions
• A function is convex if is a convex set and
for all and
• is called concave if is convex
Convex Functions
• A function is convex if is a convex set and
for all and
Convex Functions
• A twice continuously differentiable function with is convex if is
a convex set and
for all
• This is likely the definition that you saw in high school
Calculus
Convex Functions
• Which of the following functions are convex?
14
Convex Functions
• Which of the following functions are convex?
15
Operations Preserving Convexity
• Nonnegative weighted sums of convex functions are convex,
i.e., if and are convex functions and then
is a convex function.
16
Operations Preserving Convexity
• Composition with an affine function, i.e., if is a convex function
and , then given by
is a convex function.
17
Operations Preserving Convexity
• Pointwise maximum of convex functions are convex, i.e., if and
are convex functions then
is a convex function.
18
Operations Preserving Convexity
• Pointwise supremum, i.e., if is convex in for each fixed then
is a convex function.
19
Operations Preserving Convexity
• Minimization of a convex function, i.e., if is jointly convex in
and for some convex set , then
is a convex function.
20
Other Characterizations of Convexity
• A differentiable function is convex on a convex set if and only if
for all
• Proof: see Boyd 3.3.1
21
Other Characterizations of Convexity
• A differentiable function is convex on a convex set if and only if
for all
First order Taylor
expansion: this is the best
linear approximator of at
the point
22
Other Characterizations of Convexity
• A differentiable function is convex on a convex set if and only if
for all
𝑓 ( 𝑥)
′
𝑓 ( 𝑦 )+ 𝑓 ( 𝑦 )(𝑥 − 𝑦 )
23
Other Characterizations of Convexity
• A differentiable function is convex on a convex set if and only if
for all
Image: Lane Vosbury, Seminole State
College
24
Other Characterizations of Convexity
• A twice continuously differentiable function is convex on a
convex set if and only if its Hessian matrix is positive
semidefinite at all
• is positive semidefinite if all of its eigenvalues are
nonnegative
• Equivalently, for all vectors
Note: we will have a more formal refresher of
eigenvalues/eigenvectors later in the course
25
