Basics of Convex Optimization - Convex Sets and
Convex Functions
IE643
Lecture 3
05 August 2019
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 1 / 29
Outline
1 Convex sets
2 Convex Functions
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 2 / 29
Convex sets
Convex Sets
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 3 / 29
Convex sets
Points in a 2D space
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 4 / 29
Convex sets
Affine combination of two points
z is an arbitrary point on the line passing through x and y .
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 5 / 29
Convex sets
Convex combination of two points
z is an arbitrary point on the line segment connecting x and y .
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 6 / 29
Convex sets
Convex Sets
A set C is convex if λx + (1 − λ)y ∈ C, ∀x, y ∈ C, ∀λ ∈ [0, 1].
The line segment connecting x and y in C lies entirely within C.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 7 / 29
Convex sets
Convex Sets
A set C is convex if λx + (1 − λ)y ∈ C, ∀x, y ∈ C, λ ∈ [0, 1].
The line segment connecting x and y in C lies entirely within C.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 8 / 29
Convex sets
Non-convex Sets
A set C is not convex if there exist two points x and y in C such that
λx + (1 − λ)y ∈ / C, for some λ ∈ [0, 1].
The line segment connecting x and y in C does not entirely lie within
C.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 9 / 29
Convex sets
Convex Sets and Convex Combination
Going beyond two points
Let x, y , z be points in a set C.
We need to extend the definition of convex combination to these
three points.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 10 / 29
Convex sets
Convex sets and Convex combination
Going beyond two points
Let x, y , z be points in a set C.
We need to extend the definition of convex combination to these
three points.
Recall: We defined convex combination of two points x and y as
λx + (1 − λ)y , λ ∈ [0, 1].
Equivalent representation
λ1 x + λ2 y , λ1 ≥ 0, λ2 ≥ 0, λ1 + λ2 = 1.
Natural extension to three points x1 , x2 and x3
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 11 / 29
Convex sets
Convex sets and Convex combination
Going beyond two points
Let x, y , z be points in a set C.
We need to extend the definition of convex combination to these
three points.
Recall: We defined convex combination of two points x and y as
λx + (1 − λ)y , λ ∈ [0, 1].
Equivalent representation
λ1 x + λ2 y , λ1 ≥ 0, λ2 ≥ 0, λ1 + λ2 = 1.
Natural extension to three points x1 , x2 and x3
λ1 x + λ2 y + λ3 z, λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0, λ1 + λ2 + λ3 = 1.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 12 / 29
Convex sets
Convex sets and Convex combination
Going beyond two points
Convex combination of m points
Let x 1 , x 2 , . . . , x m be points in a set C. Then m i
P
i=1 λi x , λi ≥ 0,
P m 1 2 m
i=1 λi = 1 is called a convex combination of x , x , . . . , x .
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 13 / 29
Convex sets
Convex Sets and Convex combination
Going beyond two points
Convex combination of m points
Let x 1 , x 2 , . . . , x m be points in a set C. Then m i
P
i=1 λi x , λi ≥ 0,
P m 1 2 m
i=1 λi = 1 is called a convex combination of x , x , . . . , x .
A set C is convex if and only if it contains all convex combinations of
its elements.
Proof: Try yourself
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 14 / 29
Convex sets
Properties of Convex Sets
Let Ci , i ∈ I be a collection of convex sets. Then
T
Ci is convex.
i∈I
Pk
Let C1 , C2 , . . . Ck be convex sets. Then i=1 Ci is convex.
Exercise: Prove these results.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 15 / 29
Convex Functions
Convex Functions
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 16 / 29
Convex Functions
Convex Function - Definition
A function f : C → R, defined over a convex set C is called convex if
f (λy + (1 − λ)z) ≤ λf (y ) + (1 − λ)f (z), ∀y , z ∈ C, ∀λ ∈ [0, 1].
We always consider R = (−∞, +∞].
Non-empty convex set C on R is always an interval. (Exercise!)
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 17 / 29
Convex Functions
Convex Function - Definition
A function f : C → R, defined over a convex set C is called convex if
f (λy + (1 − λ)z) ≤ λf (y ) + (1 − λ)f (z), ∀y , z ∈ C, ∀λ ∈ [0, 1].
Chord over-estimates the graph of function.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 18 / 29
Convex Functions
Convex Function - Definition
A function f : C → R, defined over a convex set C is called convex if
f (λy + (1 − λ)z) ≤ λf (y ) + (1 − λ)f (z), ∀y , z ∈ C, ∀λ ∈ [0, 1].
Chord over-estimates the graph of function.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 19 / 29
Convex Functions
Convex Function - Definition
A function f : C → R, defined over a convex set C is called convex if
f (λy + (1 − λ)z) ≤ λf (y ) + (1 − λ)f (z), ∀y , z ∈ C, ∀λ ∈ [0, 1].
Chord over-estimates the graph of function.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 20 / 29
Convex Functions
Concave Function
Concave function is a close relative of convex function.
A function f : C → R, defined over a convex set C is called concave if
-f is convex over C.
Note: Concave functions are also defined over convex sets.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 21 / 29
Convex Functions
Convex Function - Characterization
Extending convex function definition to more than two points.
Jensen’s inequality
Let a function f : C → R, defined over a convex set C be convex. Let
x 1 , x 2 , . . . , x m ∈ C. Then
m
X m
X
f( λi x i ) ≤ λi f (x i ), λi ≥ 0 ∀i = 1, . . . , m; λi = 1.
i=1 i=1
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 22 / 29
Convex Functions
Convex Function - Characterization
Jensen’s inequality
Let a function f : C → R, defined over a convex set C be convex. Let
x 1 , x 2 , . . . , x m ∈ C. Then
m
X m
X
f( λi x i ) ≤ λi f (x i ), λi ≥ 0 ∀i = 1, . . . , m; λi = 1.
i=1 i=1
Proof: Try yourself!
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 23 / 29
Convex Functions
Convex Function - Characterization
Jensen’s inequality
Let a function f : C → R, defined over a convex set C be convex. Let
x 1 , x 2 , . . . , x m ∈ C. Then
m
X m
X
f( λi x i ) ≤ λi f (x i ), λi ≥ 0 ∀i = 1, . . . , m; λi = 1.
i=1 i=1
Application in probability
Consider x i to be realizations of a random variable X and λi to be
the corresponding discrete probabilities of observing x i .
Then Jensen’s inequality says: If f is a convex function,
f (EX ) ≤ Ef (X ).
Useful to obtain upper or lower bounds.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 24 / 29
Convex Functions
Convex Function - First Order Characterization
For differentiable convex functions, the tangent lines under-estimate
the graph of function.
Recall: Tangent at a point is a first-order approximation of a function.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 25 / 29
Convex Functions
Convex Function - First Order Characterization
Recall: First order approximation of a function f at a point y :
I f (y ) ≈ f (z) + (y − z)f 0 (z).
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 26 / 29
Convex Functions
Convex Function - First Order Characterization
Let C ⊆ R be an open interval. Let f : C → R be a continuously
differentiable function. Then f is convex if and only if
f (y ) ≥ f (z) + (y − z)f 0 (z), ∀y , z ∈ C.
f 0 (z) is the derivative of f at z.
Note: C ⊆ R is assumed to be an open interval.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 27 / 29
Convex Functions
Convex Function - Second Order Characterization
Let C ⊆ R be an open interval. Let f : C → R be a twice
continuously differentiable function. Then f is convex if and only if
f 00 (x) ≥ 0, ∀x ∈ C.
f 00 (x) is the double derivative of f at x.
f 00 (x) ≥ 0 indicates non-negative curvature.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 28 / 29
Convex Functions
Convex Function - Is Differentiability Required?
Question: Does a convex function need to be differentiable or
twice-differentiable ?
Answer: No, not necessarily.
Absolute value function |x| is convex but not differentiable at x = 0.
(
x, if x ≥ 0
|x| =
−x, otherwise.
P. Balamurugan (IE643 Lecture 3) Basics of Convex Optimization - Convex Sets and Convex Functions
05 August 2019 29 / 29
