The University of Texas at Austin

Department of Electrical and Computer Engineering

EE381K: Convex Optimization — Fall 2020

Lecture 2

Aryan Mokhtari Monday, August 31, 2020

Goal: In this lecture we focus on extreme points and their properties.

1 Extreme Points
Definition 1. Let C ∈ Rn be a non-empty, closed convex set. Then, x̂ is an extreme point of C if
there are not two points y, z ∈ C and scalar λ ∈ (0, 1) such that x̂ = λy + (1 − λ)z.

This definition means that a point x̂ is an extreme point of a set if it is not between any two other
points of that set.
Can we say every polyhedron has at least one extreme point? The answer is no! For instance a
half-space is a polyhedron, but it does not have an extreme point.

Now there are two questions that we aim to answer in this lecture:

• How do we check if a point x̂ is an extreme point of a polyhedron P?

• How do we ensure if a polyhedron P has extreme points?

To answer the first question we need to first define Face and Minimal Face of a polyhedron.

Definition 2. Consider a polyhedron P = {x | Ax ≤ b, Dx = e}, where A ∈ Rm×n . For a given

set of indices J ⊂ {1, . . . , m}, define FJ as FJ = {x ∈ P | a>
i x = bi , for i ∈ J}. If FJ is nonempty
it is called a face of polyhedron P.

Note that for the points in set FJ (if it is non-empty) we have

a>
i x ≤ bi , for i ∈
/ J, a>
i x = bi , for i ∈ J, Dx = e. (1)

A few remarks follows:

• Remark 1. Faces of FJ are also faces of P.

• Remark 2. All faces of P have the same lineality space as P.

• Remark 3. The number of faces is finite and at least one. (P is a face of P for J = ∅.)

Definition 3. A face of polyhedron P is a minimal face if it does not contain another face of P.

1
Theorem 1. Consider a pointed polyhedron P = {x | Ax ≤ b, Dx = e} and a point x̂ which
belongs to P. Define J(x̂) = {i1 , . . . , ik } as the indices of the active constraints at x̂, i.e.,

a>
i x < bi , for i ∈
/ J(x̂), a>
i x = bi , for i ∈ J(x̂). (2)
 
AJ(x̂)
Then, x̂ is a minimal face of the pointed polyhedron P if and only if rank = n, where
D
 >
ai1
 .. 
AJ(x̂) is a sub-matrix of A defined as AJ(x̂) =  . .
a>ik

Proof. Note that according to the definition of a face, we can define the face FJ(x̂) as the set of
points that satisfy the following conditions:

a>
i x ≤ bi , for i ∈
/ J(x̂), a>
i x = bi , for i ∈ J(x̂), Dx = e. (3)

By definition and according to the expressions in (2), the point x̂ belongs to the face FJ(x̂) and
satisfies the conditions in (3).
(a) Now we prove (< −−) [If the rank condition holds, then x̂ is a minimal face].
If the rank condition holds, then x̂ is the only point that satisfies the conditions in (3), cause if
there was another pointz 6= x̂ that satisfies these conditions then their difference x − x̂ belongs to
AJ(x̂)
the nullspace of which would be a contradiction. Hence, x̂ is the only point in the face
D
FJ(x̂) and therefore the dimension of FJ(x̂) is zero and as a result it is a minimal face.
(b) Now we prove (−− >) [If x̂ is a minimal face, then the rank condition holds]. We prove the
equivalent statement [If the rank condition does not hold, then x̂ is not a minimal face]. If the
rank condition does not hold then there exists a vector v 6= 0 such that AJ(x̂) v = 0 and Dv = 0.
Note that for x̂ we have a> i x̂ < bi when i ∈/ J(x̂). Hence, for a sufficiently small t we can show
that a>i (x̂ + tv) ≤ bi and a > (x̂ − tv) ≤ b when i ∈
i i / J(x̂). Indeed, it is easy to verify that for both
x̂ + tv and x̂ − tv the second and third conditions in (3) are also satisfied. Hence, points x̂ + tv
and x̂ − tv also belong to the face FJ(x̂) and as a result the face FJ(x̂) is not minimal and the proof
is complete.

Theorem 2. A point is an extreme point if and only if it is a minimal face of a pointed polyhedron.

Proof. Considering the result of Theorem 1, we need to prove that for a polyhedron P = {x|Ax ≤
b, Dx = e} the following statements for a point x are equivalent.

 
AJ(x)
rank( )=n ⇐⇒ there are no y, z ∈ P and λ ∈ (0, 1) s.t. x = λy + (1 − λ)z
D

First we prove (→) Suppose the claim does not hold and there exist y and z in P such that
x = λy + (1 − λ)z where λ ∈ (0, 1). (we will show that it will lead to a contradiction.)
Now note that a>i x = bi for all i ∈ J(x). This implies that

λa> >
i y + (1 − λ)ai z = bi

At the same time we know that

a>
i y ≤ bi , a>
i z ≤ bi

2
Therefore, these conditions are satisfied if and only if

a>
i y = bi , a>
i z = bi

Therefore, for any ai where i ∈ Jx we can show that

a>
i (y − z) = 0

Hence, y − z belongs to the null space of AJ(x) . It is also easy to check that D(y − z) = 0 and
 
AJ(x)
y − z also belongs to the null space of D. Hence, y − z belongs to the null space of which
D
 
A
contradicts with the fact that rank( J(x) ) = n. Hence, the proof for (→) is complete.
D
Now we proceed to prove (←)  
A
Suppose the claim does not hold and rank( J(x) ) < n which means that there exists a vector v
D
such that AJ(x) v = 0 and Dv = 0. Remember that for x we know that

a>
i x = bi for i ∈ J(x), a>
i x < bi for i ∈
/ J(x), Dx = e

We also know that

a>
i v = 0 if i ∈ J(x), Dv = 0.

Then, it can be shown that for sufficiently small  we can show that y = x ± v satisfy the following
conditions

a>
i y = bi if i ∈ J(x), a>
i y ≤ bi if i ∈
/ J(x), Dx = e.

Therefore, both y1 = x + v and y2 = x − v are in P. But, note that it can be checked that x can
be written as a convex combination of y1 and y2 , i.e, x = 0.5y1 + 0.5y2 which is a contradiction.
The proof is complete.

Corollary 1. Consider x̂ which belongs  polyhedron P = {x | Ax ≤ b, Dx = e}. x̂ is an

 to the
A
extreme point of P if and only if rank( J(x̂) ) = n.
D

2 How should one check if a point is an extreme point? (Rank

Test)
 us a way to check if a given point x̂ is an extreme point of a polyhedron P is to
Corollary 1 gives
A
check if rank( J(x̂) ) = n holds or not. If it holds then x̂ is an extreme point of P, and if not
D
then x̂ is not an extreme point.

Example: Consider the polyhedron P = {(x1 , x2 , x3 ) | x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x1 + x2 + x3 = 1}.

   
AJ(x̂) 0 0 −1
Question 1 : Is (0.5, 0.5, 0) an extreme point? rank( ) = rank( ) = 2 < 3. Hence,
D 1 1 1
it’s not.

3
  
  0 −1 0
A
Question 2 : Is (1, 0, 0) an extreme point? rank( J(x̂) ) = rank(0 0 −1) = 3. Hence, it’s
D
1 1 1
an extreme point.

Proposition 1. Consider the polyhedron P = {x | x ≥ 0, Dx = e}. The following statements

hold:

• (a) If x̂ ∈ P and rank([di1 , . . . , dik ]) = k, where dj is column j of D and {i1 , . . . , ik } =

{i | x̂i > 0}, then x̂ is an extreme point.

• (b) An extreme point x̂ has at most rank(D) nonzero elements.

Proof. (a) WLOG we assume that the first k inequalities that are not active x̂, and the last n − k
are active. Hence, we can write
 
0 ... 0 −1 0 ... 0
   0 ... 0
 0 −1 ... 0
AJ(x̂)

 .. .
.. .
..
rank( ) = rank( . )=n

D  0 ... ... 0
 0 ... 0 0 0 ... −1 
d1 . . . dk dk+1 . . . ... dn

Note that the rank is n is due to the following observations: 1) The first k columns are linearly
independent, 2) The last n − k columns are linear independent, 3) any column of the last n − k
columns is linearly independent from the first k columns. Hence, all the columns are linearly
independent. As a result, x̂ is an extreme point.
(b) We prove this claim by contradiction. Let’s call rank(D) = k. This means that k rows of D are
linearly independent. If the number of nonzero elements of x̂ is more than k, then it means that
the number of active constraints at x̂ is strictly less than n − k. Hence, rank of AJ(x̂) is strictly
 
AJ(x̂)
less than n − k which means that the rank of is strictly less than n. This contradicts with
D
the fact that x̂ is an extreme point. Hence, the proof is complete.

Theorem 3. Consider the set of doubly stochastic matrices

P = {X ∈ Rn×n | xij ≥ 0 for all i, j, X1 = 1, X> 1 = 1}.

Show that any extreme point of this polyhedron is a permutation matrix and any permutation matrix
is an extreme point of this polyhedron.

(a permutation matrix is a doubly stochastic matrix with elements 0 or 1.)

Proof. Homework.

3 When does a polyhedron have extreme points?

As we mentioned earlier, not all polyhedrons have extreme points. For, instance a half space does
not have any extreme point. In fact, if a polyhedron contains a line it doesn’t have any extreme
point. Only pointed polyhedrons have extreme points. We prove this in the following theorem.

4
Theorem 4. Consider a polyhedron P = {x | Ax ≤ b, Dx = e}. The following statements are
equivalent:

• (a) P has at least one extreme point.

• (b) P does not contain a line.

 
A
• (c) P is a pointed polyhedron. (rank = n)
D

Proof. We prove these statements are equivalent by showing (a) ⇒ (c) ⇒ (b) ⇒ (a)

(a) ⇒ (c) : Note that if (a) holds then P has at least one extreme point which  we denote by x̂.
AJ(x̂)
According to Theorem 1 and Theorem 2, if x̂ is an extreme point then rank = n. Since
D
     
A AJ(x̂) A
rank ≥ rank then we obtain that rank = n and hence P is a pointed
D D D
polyhedron.
 
A
(c) ⇒ (b) : If P is a pointed polyhedron, then n rows of are linearly independent. Let’s
D
 
A
denote {â1 , . . . , âk , d̂k+1 , . . . , d̂n } as the set of n linearly independent rows of . Suppose the
D
polyhedron P contains a line of the form x0 + λv0 , where v0 6= 0. Then, for any λ ∈ R we have

â>
i (x0 + λv0 ) ≤ b̂i for i = 1, . . . , k

This condition only holds if â> >

i x0 ≤ b̂i and âi v0 = 0 for i = 1, . . . , k.
Further, for any λ ∈ R we have

d̂>
i (x0 + λv0 ) = êi for i = k + 1, . . . , n

This condition only holds if d̂> >

i x0 = êi and d̂i v0 = 0 for i = 1, . . . , k.
Note that vectors {â1 , . . . , âk , d̂k+1 , . . . , d̂n } are linearly independent (create a basis for Rn ), but
their inner product with vector v0 is zero. This implies that vector v0 should be 0 which is a
contradiction.

(b) ⇒ (a) : Assume that P does not contain a line. Pick a point x0 in the polyhedron. Define
J(x0 ) as the indices of active constraints at x0 , i.e., J(x0 ) = {i | a> i x0 = bi }. If span({ai | i ∈
J(x )} ∪ {d , . . . , d }) = R n then the proof is complete, since the span of a subset of rows of matrix
 0 1 p
A n
is R , hence, it has n linearly independent rows and hence its rank is n and therefore x0 is an
D
extreme point. Now suppose span({ai | i ∈ J(x0 )} ∪ {d1 , . . . , dp }) 6= Rn , then there exists a vector
v such that its inner product with all of the vectors {ai | i ∈ J(x0 )} and {d1 , . . . , dp } is zero. Now
consider the following line: {y | y = x0 + λv, for any λ ∈ R}. Note that for the points on this line
we have
a>i y = bi , for i ∈ J(x0 ), d>
j y = ej , for j = 1, . . . , p.

Hence, all active constraints remain active for any. point in this line, but since polyhedron P does
not contain any line, there should be a λ∗ such that x0 + λ∗ v hits a new constraint a> k x ≤ bk
> ∗
meaning ak (x0 + λ v) = bk , where k ∈ / J(x0 ). It can be shown that ak does not belong to

5
span({ai | i ∈ J(x0 )} ∪ {d1 , . . . , dp }), since if it belongs to it then we have a> k v = 0 which
implies a>
k x 0 = bk and it contradicts with the fact that k ∈
/ J(x 0 ). Hence, a k does not belong to
span({ai | i ∈ J(x0 )} ∪ {d1 , . . . , dp }). Therefore, if we define a new point in the polyhedron x1 as
x1 = x0 + λ∗ v, we can conclude that

dim (span({ai | i ∈ J(x0 )} ∪ {d1 , . . . , dp })) < dim (span({ai | i ∈ J(x1 )} ∪ {d1 , . . . , dp }))

If we do this process at most n times then we reach a point x̂ such that dim (span({ai | i ∈ J(x0 )})) =
n and therefore x̂ is an extreme point.

Remark 1. According to the above theorem for any polyhedron P = {x | Ax ≤ b, Dx  =  e}, we

A
can easily check if it has extreme points or not by following the rank test of matrix . If the
D
rank of this matrix is n, then it has at least one extreme point. If the rank is smaller than n, then
it does not have any extreme point.