Analyse Convexe approfondie Année 2013/14

Analyse Convexe approfondie
M1MMD
Ann´ee 2013/14
Partiel du mercredi 12 mars 2014
Always motivate your answers.
The quality of redaction matters.
Problem
Part A. A subset of Rn is called a polytope if it is the convex hull of a finite
number of points.
1. Show that the set of x = (x1 , . . . , xn ) ∈ Rn satisfying
x1 + · · · + xn = 1
xi ≥ 0, ∀i = 1, . . . , n.
is a polytope.
2. Let C be the set of x = (x1 , . . . , xn ) ∈ Rn satisfying
0 ≤ xi ≤ 1,
∀i = 1, . . . , n.
Show that
C = conv({0, 1}n ).
Hint for the difficult inclusion: given x ∈ C, set y = x/xi (for some
appropriate choice of i) and use induction.
Part B. Let K be a convex subset of Rn , let us recall a couple of definitions:
• z ∈ K is called an extreme point of K if for every v ∈ Rn one has
(z + v ∈ K and z − v ∈ K)
⇒
v = 0.
• H is called a support hyperplane of K if H = φ−1 ({α}) for some non-zero
linear form φ and some α ∈ R such that
α = sup {φ(x)}
x∈K
The purpose of this part is to show that if K ⊂ Rn is convex and compact then
K is the convex hull of its extreme points. In other words, any element of K is
a convex combination of the extreme points of K.
1
3. Show that this holds true in dimension 1.
We now assume that n ≥ 2, and that the result holds true in any dimension no
larger than n − 1. Let K be a convex and compact subset of Rn .
4. Show that K can be assumed to have non-empty interior without loss of
generality.
5. Show that if H is a support hyperplane of K and z is an extreme point of
K ∩ H, then z is an extreme point of K as well.
6. Let x ∈ K and let D be a line passing through x. Show that D ∩ K is a
closed segment.
7. Let y be one of the extreme points of this segment, show that there is a
support hyperplane for K passing through y.
8. Use the induction hypothesis to prove that x is a convex combination of
the extreme points of K.
Part C. A subset P of Rn is called a polyhedron if P is a finite intersection of
closed halfspaces. The purpose of this part is to show that a bounded polyhedron
is a polytope. Let
m
\
P =
{x ∈ Rn ; hx, yi i ≤ ai } .
i=1
be a polyhedron of Rn . Let x ∈ P . Let
I = {i ∈ {1, . . . , m}; hx, yi i = ai }
be the set of indices of constraints that are saturated by x. Let
E = vect{yi , i ∈ I}.
9. Let v ∈ Rn such that x + v and x − v belong to P , show that v ∈ E ⊥ .
10. Show that if v ∈ E ⊥ is small enough (in euclidean norm, say) then x + v ∈
P.
11. Deduce a necessary and sufficient condition on E for x to be an extreme
point of P .
12. Deduce that P has only finitely many extreme points.
13. Conclude.
14. Show that the Euclidean ball
(
B=
x ∈ Rn ;
n
X
i=1
is not a polyhedron.
2
)
x2i ≤ 1

Download Report