Convex analysis
Renu M. R.
March 3, 2020
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R.
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
1 0.2
Let v1 = and v2 = . Linear combination?
0.5 3
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
1 0.2
Let v1 = and v2 = . Linear combination? R2 .
0.5 3
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Affine combination for previous example?
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Affine combination for previous example? Line passing
through v1 and v2 .
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
Convex combination for previous example?
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
Convex combination for previous example? Line segment
between v1 and v2 .
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
Conic combination
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
Conic combination α1 , α2 ≥ 0.
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
Conic combination α1 , α2 ≥ 0.
Conic combination?
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
Conic combination α1 , α2 ≥ 0.
Conic combination? Cone contained by the rays containing v1 ,
v2 .
The different ways of combining
vectors
Let v1 and v2 be two vectors in some vector space with R as the
field.
Let v = α1 v1 + α2 v2
Linear combination α1 , α2 ∈ R. No restrictions.
Affine combination α1 + α2 = 1.
Convex combination α1 + α2 = 1, 0 ≤ α1 , α2 ≤ 1.
Conic combination α1 , α2 ≥ 0.
Convex, affine sets and cone
Let C ⊂ Rn .
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C,
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
C is a convex set if for any x1 , x2 ∈ C,
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
C is a convex set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for 0 ≤ α ≤ 1.
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
C is a convex set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for 0 ≤ α ≤ 1.
Examples?
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
C is a convex set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for 0 ≤ α ≤ 1.
Examples?
C is a cone if for any x1 , x2 ∈ C,
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
C is a convex set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for 0 ≤ α ≤ 1.
Examples?
C is a cone if for any x1 , x2 ∈ C, α1 x1 + α2 x2 ∈ C, for
α1 , α2 ≥ 0.
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
C is a convex set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for 0 ≤ α ≤ 1.
Examples?
C is a cone if for any x1 , x2 ∈ C, α1 x1 + α2 x2 ∈ C, for
α1 , α2 ≥ 0.
Examples?
Convex, affine sets and cone
Let C ⊂ Rn .
C is an affine set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for α ∈ R.
Examples?
C is a convex set if for any x1 , x2 ∈ C, αx1 + (1 − α)x2 ∈ C,
for 0 ≤ α ≤ 1.
Examples?
C is a cone if for any x1 , x2 ∈ C, α1 x1 + α2 x2 ∈ C, for
α1 , α2 ≥ 0.
Examples?
Note that all the above cases can be generalized for more than
two points.
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Affine hull Smallest affine set that contains C is the affine hull of C (aff C)
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Affine hull Smallest affine set that contains C is the affine hull of C (aff C)
n
X n
X
aff C = αi xi | xi ∈ C, αi = 1 .
i=1 i=1
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Affine hull Smallest affine set that contains C is the affine hull of C (aff C)
n
X n
X
aff C = αi xi | xi ∈ C, αi = 1 .
i=1 i=1
Convex hull Smallest convex set that contains C (conv C)
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Affine hull Smallest affine set that contains C is the affine hull of C (aff C)
n
X n
X
aff C = αi xi | xi ∈ C, αi = 1 .
i=1 i=1
Convex hull Smallest convex set that contains C (conv C)
n
X n
X
conv C = αi xi | xi ∈ C, αi = 1, αi ≥ 0 .
i=1 i=1
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Affine hull Smallest affine set that contains C is the affine hull of C (aff C)
n
X n
X
aff C = αi xi | xi ∈ C, αi = 1 .
i=1 i=1
Convex hull Smallest convex set that contains C (conv C)
n
X n
X
conv C = αi xi | xi ∈ C, αi = 1, αi ≥ 0 .
i=1 i=1
Conic hull Set of all conic combinations of points in C
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Affine hull Smallest affine set that contains C is the affine hull of C (aff C)
n
X n
X
aff C = αi xi | xi ∈ C, αi = 1 .
i=1 i=1
Convex hull Smallest convex set that contains C (conv C)
n
X n
X
conv C = αi xi | xi ∈ C, αi = 1, αi ≥ 0 .
i=1 i=1
Conic hull Set of all conic combinations of points in C
n
X
αi xi | xi ∈ C, αi ≥ 0 .
i=1
Convex, affine and conic hulls
Let C be an arbitrary subset of Rn .
Affine hull Smallest affine set that contains C is the affine hull of C (aff C)
n
X n
X
aff C = αi xi | xi ∈ C, αi = 1 .
i=1 i=1
Convex hull Smallest convex set that contains C (conv C)
n
X n
X
conv C = αi xi | xi ∈ C, αi = 1, αi ≥ 0 .
i=1 i=1
Conic hull Set of all conic combinations of points in C
n
X
αi xi | xi ∈ C, αi ≥ 0 .
i=1
Examples?
Convex functions
Let C ⊂ Rn , be a convex set.
f : C → R,
is a convex function if for every x, y ∈ C, and 0 ≤ α ≤ 1,
Convex functions
Let C ⊂ Rn , be a convex set.
f : C → R,
is a convex function if for every x, y ∈ C, and 0 ≤ α ≤ 1,
f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y)
Convex functions
Let C ⊂ Rn , be a convex set.
f : C → R,
is a convex function if for every x, y ∈ C, and 0 ≤ α ≤ 1,
f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y)
f is strictly convex if a strict inequality holds for x 6= y and
0 < α < 1.
Convex functions
Let C ⊂ Rn , be a convex set.
f : C → R,
is a convex function if for every x, y ∈ C, and 0 ≤ α ≤ 1,
f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y)
f is strictly convex if a strict inequality holds for x 6= y and
0 < α < 1.
f is concave if −f is convex.
Convex functions
Let C ⊂ Rn , be a convex set.
f : C → R,
is a convex function if for every x, y ∈ C, and 0 ≤ α ≤ 1,
f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y)
f is strictly convex if a strict inequality holds for x 6= y and
0 < α < 1.
f is concave if −f is convex.
Examples?
Convex functions
Let C ⊂ Rn , be a convex set.
f : C → R,
is a convex function if for every x, y ∈ C, and 0 ≤ α ≤ 1,
f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y)
f is strictly convex if a strict inequality holds for x 6= y and
0 < α < 1.
f is concave if −f is convex.
Examples?
How to check for convexity?
