Operations that preserve convexity of sets

Proposition 3 (Intersection). If X1 , X2 , . . . , Xm are convex sets, then \i2[m] Xi

is a convex set.

Example: Polyhedron {x 2 Rn |Ax  b} for some A 2 Rm⇥n , b 2 Rm which is

an intersection of half-spaces.

28
 Operations that preserve convexity of sets

Proposition 4 (Affine Image). If X is a convex set, f (x) = Ax + b with

A 2 Rm⇥n , b 2 Rm , then the set f (X) := {y|y = Ax + b for some x 2 X}
is a convex set.

Ellipsoid:
Proposition 5. Let A be a symmetric positive definite matrix. Then, the set
E := {x 2 Rn |(x c)> A 1 (x c)  1} is convex.

29
 Operations that preserve convexity of sets

Proposition 6 (Product). If X1 , X2 , . . . , Xm are convex sets, then

X := X1 ⇥ X2 ⇥ . . . ⇥ Xm := {(x1 , x2 , . . . , xm ) | xi 2 Xi , i 2 [m]}

is a convex set.
Example:

Proposition
P 7 (Weighted
P Sum). If X1 , X2 , . . . , Xm are convex sets, then
i2[m] ↵i Xi := {y | y = i2[m] ↵i xi , xi 2 Xi } is a convex set.

Example:

30
 Operations that preserve convexity of sets

Proposition 8 (Inverse Affine Image). Let X 2 Rn be a convex set and

A : Rm ! Rn be an affine map with A(y) = Ay + b for matrix A and vector
b of suitable dimension. Then, the set A 1 (X) := {y 2 Rm | Ay + b 2 X} is
a convex set.

31
 Convex Combination

Given a collection of points x1 , x2 , . . . P

, xk , the combination 1 x1 + 2 x2 +...+
k xk is called Convex if i 0 and ni=1 i = 1.

Equivalent Definition:
Definition 4 (Convex Set). A set is convex if it contains all convex combi-
nations of its points.

Definition 5 (Convex Hull). The convex hull of a set X 2 Rn is the set of

all convex combinations of its elements, i.e.,
8 9
< X X =
n
conv(X) := y 2 R | y = i xi , where i 0, i = 1, xi 2 X8i 2 [k], k 2 N .
: ;
i2[k] i2[k]

Proposition 9 (Convex Hull). The following are true.

conv(X) is a convex set (even when X is not).
If X is convex, then conv(X) = X.
For any set X, conv(X) is the smallest convex set containing X.

Example:

32
 Combination of points

Given a collection of points x1 , x2 , . . . , xk , the combination 1 x1 + 2 x2 +...+

k xk is called

Pn
Convex if i 0 and i=1 i = 1.

Conic if i 0,
Pn
Affine if i=1 i = 1,

Linear if i 2 R.

A set is convex/ convex cone/ affine subspace/linear subspace if it contains all

convex/conic/affine/linear combinations of its elements.

Definition 6. A set X is a cone if for any x 2 X, ↵ 0, we have ↵x 2 X.

33
 Projection

Definition 7 (Projection). The projection of a point x0 on a set X, denoted

projX (x0 ) is defined as

projX (x0 ) := argminx2X ||x x0 ||22 .

Theorem 4: Projection Theorem

If X is closed and convex, then projX (x0 ) exists and is unique.

Main idea:
Existence due to Weierstrass Theorem
Uniqueness via contradiction exploiting convexity

34
 Separating Hyperplane

Definition 8 (Separating Hyperplane). Let X1 and X2 be two nonempty

convex sets in Rn . A hyperplane H = {x 2 Rn | a> x = b} with a 6= 0 is said
to separate X1 and X2 if
X1 ⇢ H := {x 2 Rn | a> x  b},
X2 ⇢ H + := {x 2 Rn | a> x b},
X1 \ X2 6⇢ H.

Separation is said to be strict if X1 ⇢ {x 2 Rn | a> x  b0 }, X2 ⇢ {x 2 Rn |

a> x b00 } with b0 < b00 .

Equivalently
sup a> x  inf a> x
x2X1 x2X2

with the inequality being strict for strict separation.

35
 Separating Hyperplane Theorem

Theorem 5: Separating Hyperplane Theorem

Let X be a closed convex set and x0 2

/ X. Then, there exists a hyperplane
that strictly separates x0 and X.

Main Idea:
||a||22
1. Let H = {x 2 Rn | a> x = b} with a = x0 projX (x0 ) and b = a> x0 2 .

2. Use properties of projection and convexity of X to verify that H is indeed

the separating hyperplane.

36
 Theorem of the Alternative (Farkas’ Lemma)

Lemma 1 (Farkas’ Lemma). Let A 2 Rm⇥n and b 2 Rm . Then, exactly one

of the following sets must be empty:
1. {x 2 Rn | Ax = b, x 0}
2. {y 2 Rm | A> y  0, b> y > 0}.

Insight: If unable to show a system of linear inequalities does not have a solution,
try to show that its alternative system does.

Main Idea:
1. Easy to show that if (2) is feasible, (1) is infeasible.
2. For the converse, suppose (1) is infeasible. Then, b 2 / cone(a1 , a2 , . . . , an )
where ai is the i-th column of A. Find a hyperplane separating b from
cone(a1 , a2 , . . . , an ) and show that (2) is feasible.

37
 Application: Linear Programming Duality

Consider the following pair of linear optimization problems.

minn c> x
x2R
s.t. Ax = b, (P)
x 0.

max
m
b> y
y2R

s.t. A> y  c, (D)

Theorem 6: LP Duality

If (P) has a finite optimal value, then (D) also has a finite optimal value
and both optimal values are equal to each other.

38
 Domain of a Function

We consider extended real-valued functions f : Rn ! R [ {1} =: R̄.

The (e↵ective) domain of f , denoted dom(f ), is the set {x 2 Rn | |f (x)| <

+1}.

Example: f (x) = x1 . What is dom(f )?

Pn
f (x) = i=1 xi log(xi ). What is dom(f )?

When dom(f ) 6= , we say that the function f is proper.

39
 Convex Functions

Definition 9 (Convex Function). A function f : Rn ! R̄ is convex if

1. dom(f ) ✓ Rn is a convex set, and
2. for every x, y 2 dom(f ), 2 [0, 1], we have f ( x + (1 )y)  f (x) +
(1 )f (y).

The Line segment joining (x, f (x)) and (y, f (y)) lies “above” the function.

Examples:
f (x) = x2
f (x) = ex
f (x) = a> x + b for x 2 Rn

40
 Example: Norms

Definition 10 (Norms). A function ⇡ : Rn ! R̄ is a norm if

⇡(x) 0, 8x and ⇡(x) = 0 if and only if x = 0,
⇡(↵x) = |↵|⇡(x) for all ↵ 2 R,
⇡(x + y)  ⇡(x) + ⇡(y).

Examples:
P 1
||x||p := ( ni=1 |xi |p ) p for p 1.
p
||x||Q := x> Qx where Q is a positive definite matrix.
P Pn
||A||F := ( m i=1
2 1/2
j=1 |Ai,j | ) Frobenius norm on Rm⇥n .

Proposition 10. A Norm is a convex function.

41
 Example: Indicator Function

Definition 11. Indicator function IC (x) of a set C is defined as

(
0, x 2 C,
IC (x) :=
1, x2 / C.

Proposition 11. Indicator function IC (x) is convex if the set C is a convex

set.

42
 Example: Support Function

Proposition 12. Support function of a set C is defined as IC⇤ (x) := supy2C x> y.
Support function of a set is always a convex function.

43
 Special Types of Convex Functions

Definition 12. A function f : Rn ! R̄ is

strictly convex if property (2) above holds with strict inequality for
2 (0, 1),
2
µ-strongly convex if f (x) µ ||x||
2 is convex, and
2

concave if f (x) is convex.

44
 Jensen’s Inequality

Pk f : R ! PkR̄, for any collection of

n
Proposition 13. For a convex function
Pk{x1 , x2 , . . . , xk }, we have f ( i=1 i xi ) 
points i=1 i f (xi ) when i 0
and i=1 i = 1.

Proof is straightforward via induction.

45
 Epigraph Characterization

Definition 13. A epigraph of a function f : Rn ! R̄ is defined as the set

epi(f ) := {(x, t) 2 Rn+1 |f (x)  t}.

Example: Norm cone: {(x, t)|||x||  t} is a convex set.

Proposition 14. Function f : Rn ! R̄ is convex in Rn if and only if its

epigraph is a convex set in Rn+1 .

46
 Level-set Characterization

Definition 14. For any ↵ 2 R, the level set of function f : Rn ! R̄ at level

↵ is defined as
lev↵ (f ) := {x 2 dom(f )|f (x)  ↵}.

Proposition 15. If a function f is a convex function, then every level set

of f is a convex set.

Converse is not true. A function is called quasi-convex if its domain and all level
sets are convex sets.

HW: Give an example of a function which is quasi-convex but not convex.

47
 Restriction of a Convex Function on a Line

Proposition 16. If a function f is convex if and only if for any x, h 2 Rn ,

the function (t) = f (x + th) is a convex function on R.

If we know how to check convexity of functions defined on R, then we can check

convexity of functions defined on Rn .

48
 First Order Condition

Proposition 17. If a function f is di↵erentiable, then it is convex if and

only if dom(f ) is a convex set and for any x, y 2 dom(f ), we have

f (y) f (x) + rf (x)> (y x).

A global lower bound on the function can be obtained at any point based on local
information (f (x), rf (x)).

49
 Second Order Condition

Proposition 18. If a function f is twice di↵erentiable, then it is convex if

and only if dom(f ) is a convex set and r2 f (y) ⌫ 0 for every y 2 dom(f ).

50
 Convexity Preserving Operations

Proposition 19 (Conic Combination). Let {fi (x)}i2I be a P

collection of con-
vex functions and let ↵i 0 for all i 2 I. Then, g(x) := i2I ↵i fi (x) is a
convex function.

Proposition 20 (Affine Composition). If f : Rm ! R is a convex function,

then g(x) := f (Ax + b) is also a convex function where A 2 Rm⇥n , b 2 Rm .

51
 Convexity Preserving Operations

Proposition 21 (Pointwise Maximum). Let {fi (x)}i2I is a collection of con-

vex functions, then g(x) := maxi2I fi (x) is a convex function.

The set I need not be a finite set.

Proposition 22 (Pointwise Supremum). Let f (x, !) is convex in x for any

! 2 ⌦, then g(x) := sup!2⌦ f (x, !) is convex in x.

52
 Convexity Preserving Operations

Proposition 23 (Scalar Composition). If a function f is convex in Rn , and

F is a convex non-decreasing function on R, then g(x) := F (f (x)) is convex.

Proposition 24 (Vector Composition). Let {fi }i2{1,2,...m} are convex func-

tions on Rn , and F : Rm ! R is a convex function and non-decreasing in
each argument, then the function g(x) = F (f (x)) is convex.

53