Twierdzenia o oddzielaniu i podpieraniu

Przejd¹my do omówienia Twierdze« o oddzielaniu i podpieraniu zbiorów wypukªych, które s¡ bardzo istotne w analizie wypukªej i maj¡ szerokie zastosowanie w optymal-izacji. Zacznijmy jednak od

Denicja 1. Hiperpªaszczyn¡ H w n

R

nazywamy ka»dy zbiór postaci

H = {x ∈

n

R : a, x = α},

dla ustalonych 0

n

n 6= a ∈

, α ∈

R

R

R.

Uwaga 1. Zauwa»my, »e w 3

2

R hiperpªaszczyzn¡ jest pªaszczyzna, w R hiperpªaszczyzn¡

jest prosta, a na R hiperpªaszczyzn¡ jest punkt.

Ciekawostka. Chocia» poj¦cie hiperpªaszczyna wygl¡da na sªowo zapo»yczone z science ction, to w rzeczywisto±ci jest odwrotnie, pisarze science ction po»yczyli je od matematyków:)

Oba Twierdzenia o podpieraniu i oddzielaniu s¡ bardzo intuicyjne, jednak»e w ich formalnych dowodach musimy przeksztaªci¢ geometryczn¡ intuicj¦ na form¦ al-begraiczn¡ b¡d¹ analityczn¡. Zacznijmy od Stwierdzenia

Stwierdzenie 1. Je»eli ∅ 6= D ⊂ n

R - domkni¦ty oraz y /

∈ D, to istnieje x? ∈ D takie,

»e ky − x?k = d(y, D) := infx∈Dky − xk.

Dowód. Dowód do samodzielnego przeprowadzenia przez studentów.

Niech C ⊂ n

n

n

R

zbiór wypukªy, x ∈ C ⊂ R oraz y ∈ R \ C. Szukamy wektora

x? ∈ cl C, który realizuje odlegªo±¢ punktu y od zbioru C. kx? − yk = d(y, C) wtedy i tylko wtedy, gdy dla ka»dego x ∈ C k¡t θx mi¦dzy wektorami o pocz¡tku x? i ko«cu x, oraz wektorem o pocz¡tku x? a ko«cu w y musi by¢ k¡tem rozwartym lub prostym, czyli θx ∈ [ π , π] (zrobi¢ rysunek pomocniczy). Ten warunek geometryczny zyskuje sw¡ in-2

terpretacj¦ analityczn¡/algebraiczn¡ przy pomoc iloczynu skalarnego. Przypomnijmy,

»e

u, w = kukkwk cos θ,

θ = ∠(u, w).

Zatem opisany warunek przymuje posta¢ ( y − x?, x − x? = ky −x?kkx−x?k cos θx ≤

0, czyli)

∀ x ∈ C

y − x?, x − x? ≤ 0.

Pomimo, »e nie dla ka»dego zbioru wypukªego istnieje wektor realizuj¡cy odlegªo±¢

zbioru od punktu nienale»¡cego do niego, to daje si¦ udowodni¢ Twierdzenie Twierdzenie 1 (charakteryzacja punktu realizuj¡cego odlegªo±¢ zbioru wypukªego od punktu nienale»¡cego do niego). Niech C ⊂ n

R - wypukªy oraz y /

∈ C.

Wówczas x? ∈ C, taki, »e ky − x?k = d(y, C), wtedy i tylko wtedy, gdy

∀ x ∈ C

y − x?, x − x? ≤ 0.

Dowód. Dowód przeprowadzony na wykªadzie.

1

Wniosek 1. Je»eli C ⊂ n

R

- domkni¦ty, wypukªy oraz y /∈ C, to istnieje dokªadnie

jeden wektor x? ∈ C, taki, »e 0 < ky − x?k = d(y, C).

Dowód. Dowód do samodzielnego przeprowadzenia przez studentów.

Twierdzenie 2 (o oddzielaniu (The Basic Separation Theorem)). Niech C ⊂ n R

wypukªy, domkni¦ty oraz y /∈ C. wówczas istniej¡ a ∈ n

R \ {0} oraz α ∈ R takie, »e

∀ x ∈ C

a, x ≤ α < a, y.

Dowód. Dowód przeprowadzony na wykªadzie.

Nast¦puj¡ce twierdzenie pokazuje, »e operacja domkni¦cia zachowuje wypukªo±¢

Twierdzenie 3. Je»eli C ⊂ n

R

- wypukªy, to cl C jest zbiorem wypukªym.

Dowód. Dowód do samodzielnego przeprowadzenia przez studentów.

Uwaga 2. Zauwa»my, »e otoczka wypukªa zbioru domkni¦tego nie musi by¢ zbiorem domkni¦tym (jest oczywi±cie zbiorem wypukªym) Np. A = {0}×[0, 1]∪[0, +∞)×{0}.

Przejdziemy do dowodu Twierdzenia o podpieraniu w dowodzie, którego wykorzys-tamy Lemat o dost¦pno±ci

Twierdzenie 4 (o podpieraniu (Support Theorem)). Je»eli C ⊂ n R

- wypukªy,

Int C 6= ∅, z ∈ Fr C, to istnieje a ∈ n

R \ {0} taki, »e

∀ x ∈ C

a, x ≤ a, z.

Dowód. Dowód przprowadzony na wykªadzie.

Z geometrycznej interpretacji Twierdzenia o podpieraniu wynika natychmiast Wniosek 2. Domkni¦ty, wypukªy podzbiór n

R jest cz¦±ci¡ wspóln¡ wszystkich domkni¦-

tych póªprzestrzeni zawieraj¡cych go.

Twierdzenie o podpieraniu zastosujemy w dowodzie nast¦puj¡cego Twierdzenia, które b¦dzie odgrywaªo istotn¡ rol¦ w programowaniu wypukªym Twierdzenie 5 (o podpieraniu nadwykresu funkcji wypukªej). Niech C ⊂ n R -

wypukªy, Int C 6= ∅, f : C → R - funkcja wypukªa. Je»eli x0 ∈ Int C, to istnieje wektor d ∈

n

R

taki, »e

∀ x ∈ C

f (x) ≥ f (x

0) + d, x − x0 .

Dowód. Dowód przprowadzony na wykªadzie.

Uwaga 3. Oczywi±cie z Twierdzenia o zwi¡zku mi¦dzy wypukªo±ci¡ i hiperpªaszczyzn¡

styczn¡ funkcji ró»niczkowlanej wiemy, »e w je»eli funkcja wypukªa jest ró»niczkowlana na otwartym, wypukªym podzbiorze n

R , to wektor d z tezy powy»szego Twierdzenia

jest wyznaczony jednoznacznie oraz d = ∇f(x0). W przypadku funkcji wypukªej nieró»niczkowalnej jest wi¦cej ni» jeden wektor d o »¡danej warto±ci np. f(x) = |x|, x0 = 0, wtedy d = [−1, 1].

2