W10 id 305373

Wyk lad 11- 2012/2013

Istnienie rozwiazań, c.d.

Definicja 0.1 X - przestrzeń topologiczna. Funkcja f : X → R ∪ {±∞} jest pó lciag la z do lu (p.d.) na

X w punkcie ¯

x ∈ X jeśli f (¯

x) ≤ lim infx→¯x f (x)

f : X → R∪{±∞} jest pó lciag la z do lu na X jeśli

jest pó lciag la z do lu w każdym punkcie ¯

x ∈ X

Lemat 0.1 f : X → R∪{±∞}. Nastepujace warunki

sa równoważne:

• f jest p.d. na X,

• epigraf f , epi f jest domkniety

• dla każdego r ∈ R zbiór poziomicowy L(r) =

{x ∈ X : f (x) ≤ r} jest domkniety

W przestrzeniach metrycznych (X, ρ): f : X →

R ∪ {±∞} jest p.d. w ¯

x ∈ X jeśli dla każdego ciagu

xk → ¯

lim inf f (xk) ≥ f (¯

k→∞

Twierdzenie 0.1 (Weierstrass) Niech f : X → R∪

{±∞} bedzie funkcja pó lciag la z do lu określona

na przestrzeni topologicznej przeliczalnie zwartej X (każdy ciag zawiera podciag zbieżny), np na

przestrzeni metrycznej. Wówczas zbiór minimów (rozwiazań) globalnych

S = {¯

x ∈ X : f (¯

x) ≤ f (x) dla każdego x ∈ X}

jest niepusty.

Dowód. Rozpatrzmy ciag (x

k) ⊂ X taki, że

f (xk) → m := inf f (X)

Ze wzgledu na przeliczalna zwartość X ciag ten

zawiera podciag (x ) zbieżny do pewnego ¯

x ∈ X.

Ze wzgledu na ciagowa pó lciag lość z do lu f

m = lim f (xk ) = lim inf f (x ) ≥ f (¯

m→∞

Z drugiej strony, f (¯

x) ≥ m. Wobec tego f (¯

x) = m.

Koercytywność

Definicja 0.2 Funkcja f : Rn → R jest koercytywna jeśli dla każdego ciagu (x

n) ⊂ Rn dla którego

kxnk → +∞ zachodzi f (xn) → +∞:

lim f (x) = +∞

kxk→+∞

Twierdzenie 0.2 (koercytywność i zwartość) Dana funkcja f : Rn → R ∪ {+∞} ciag la na Rn. f jest

koercytywna wtedy i tylko wtedy gdy dla każdego r ∈ R zbiór L(r) = {x f (x) ≤ r} jest niepusty i zwarty.

Dowód.Pokażemy najpierw, że koercytywność implikuje zwartość zbiorów poziomicowych.

Zauważmy, że ciag lość f implikuje, że zbiory

poziomicowe L(r) = {x : f (x) ≤ r} sa domkniete.

Na mocy tw. Bolzano-Weierstrassa trzeba pokazać, że sa ograniczone. Pokażemy to przez zaprzecze-

nie.

Za lóżmy, że istnieje α ∈ R takie,że zbiór L(α) =

f (x) ≤ α} jest nieograniczony.

Istnieje

wówczas ciag (x

n) ⊂ L(α) taki,

że kxnk → +∞.

Ale xn ∈ L(α), czyli f (xn ≤ α co przeczy koercytywności. Tak wiec L(r) musza być ograniczone.

Za lóżmy teraz, że wszystkie zbiory L(r) sa ogranic-

zone. Pokażemy, że f jest koercytywna. Weźmy ciag (x

n) ⊂ Rn taki, że kxnk → +∞. Gdyby ist-

nia l jakikolwiek podciag (f (x )) ciagu f (x

n) który

by lby ograniczony przez pewna liczbe α ∈ R, to

wówczas xn ∈ L(α) co nie jest mo˙liwe bo L(α) sa k

ograniczone a (xn ) nie jest ograniczony z definicji.

A wiec f (x

n) nie mo że być ograniczony, czyli nie zawiera podciagów ograniczonych, tzn f (x

n) →

+∞.

Twierdzenie 0.3 Dana funkcja f : Rn → R ∪ {+∞}

ciag la na Rn. Jeśli f jest koercytywna to zbiór

X∗ minimów globalnych f jest niepusty.

Dowód Niech m = infx∈Rn f(x). Niech γk ↓ m przy k → +∞. Wówczas

∞

X∗ =

{x ∈ Rn : f (x) ≤ γk}

i=1

Z twierdzenie poprzedniego, każdy zbiór

{x ∈ Rn : f (x) ≤ γk}

jest niepusty i zwarty oraz tworza rodzine zbiorów

wstepujacych, a wiec X∗ jest zwarty i niepusty

Aby znaleźć minima globalne różniczkowalnej funkcji koercytywnej wystarczy znaleźć punkty 3

krytyczne a nastepnie obliczyć wartości f w tych

punktach i wybrać minimalna .

Przypadki szczególne

Najcześciej stosujemy powyższe twierdzenia do

zadania minimalizacji f : Rn → R na zbiorze Ω ⊂

Rn.

f (x) x ∈ Ω

f (x) :=

+∞ x 6∈ Ω

Wniosek: Zbiór minimów globalnych f jest niepusty i zwarty gdy Ω jest domkniety, f jest pó lciag la

z do lu i jeden z warunków zachodzi:

Ω jest ograniczony,

f jest koercytywna

istnieje zbiór poziomicowy f niepusty i zwarty Minima lokalne i globalne

Twierdzenie 0.4 Niech Ω ⊂ Rn bedzie zbiorem wy-

puk lym oraz f : Ω → R ∪ {+∞} w laściwa funkcja wypuk la. Każde minimum lokalne jest globalne.

Jeśli dodatkowo f jest ściśle wypuk la, to istnieje conajwyżej jedno minimum globalne f .

Rzutowanie

Twierdzenie 0.5 Niech C ⊂ Rn bedzie zbiorem wy-

puk lym.

(a) Dla każdego x ∈ Rn istnieje jednoznacznie wyznaczony punkt P (x) nazywany rzutem x na C , który minimalizuje

kz − xk

dla

z ∈ C.

(b) Dla każdego x ∈ Rn wektor z ∈ C jest równy P (x) wtedy i tylko wtedy

(y − z)T (x − z) ≤ 0, ∀ y ∈ C.

W przypadku gdy C jest zbiorem afinicznym warunek ten jest równoważny warunkowi

(x − z) ∈ S⊥

gdzie S jest podprestrzenia równoleg la do C.

jest ciag lym odwzorowaniem zweżajacym

kP (x) − P (y)k ≤ kx − yk

x, y ∈ Rn.

Proof.

(a) Ustalmy x i niech w bedzie elementem z C.

Minimalizacja

kx − zk

po wszystkich z ∈ C

r´’ownoważna jest minimalizacji funkcji ciag lej g(z) =

kz − xk2 po wszystkich z ∈ C takich, że kx − zk ≤ kx − wk

Zbiór

C ∩ {z : kx − zk ≤ kx − wk

jest zwarty, a wiec z twierdzenia Weierstrassa ist-

nieje wektor minimalizujacy, który jest wyznac-

zony jednoznacznie gdyż funkcja kz−xk2 jest ściśle wypuk la.

(b) Dla wszystkich y i z z C mamy

ky − xk2 = ky − zk2 + kz − xk2 − 2(y − z)T (x − z)

≥ kz − xk2 − 2(y − z)T (x − z)

stad z = P (x)

odwrotnie, niech z = P (x), weźmy y ∈ C i dla α > 0 niech yα = αy + (1 − α)z mamy

∂

0 ≤

(kx − y

∂α

αk2)|α=0 = −2(y − z)T (x − z)

Stożki recesji zbiorów poziomicowych funkcji wypuk lej

Dany niepusty zbiór wypuk ly C ⊂ Rn.

Stożek recesji RC zbioru C jest to zbiór wektorów postaci

RC := {d ∈ Rn : x + αd ∈ Cf orall x ∈ C, α > 0}

Proposition 1.1 Niech f : Rn → R∪{+∞} domknieta

w laściwa funkcja wypuk la. Niech zbiór poziomicowy f bedzie postaci

Vγ := {x ∈ Rn : f (x) ≤ γ} γ ∈ R.

Wtedy:

(a) Wszystkie niepuste zbiory poziomicowe Vγ

maja ten sam stożek recesji

(b) Jeśli jeden niepusty zbiór poziomicowy jest zwarty to wszystkie niepuste zbiory poziomicowe sa zwarte.

Istnienie rozwiazań funkcji wypuk lych

Proposition 1.2 Niech Ω ⊂ Rn bedzie niepusty domkniety

wypuk ly i f : Ω → R ∪ {+∞} domknieta w laściwa

funkcja wypuk la z niepusta dziedzina . Wtedy

X∗ zbiór minimów f na Ω jest niepusty i zwarty wtedy i tylko wtedy gdy Ω i f nie maja wspólnych

kierunków recesji.

Dowód uwaga: Zbiór w Rn jest zwarty wtedy i tylko wtedy gdy nie posiada niezerowych kierunków recesji.

Niech m = infx∈Ω f (x) i niech γk ↓

∞

X∗ =

Ω ∩ {x | f (x) ≤ γk}

k=1

Jeśli Ω i {x | f (x) ≤ γk} nie maja wspólnych nieze-

rowych kierunków recesji to sa zwarte, i X∗ jest

zwarty. Odwrotnie jeśli X∗ jest niepusty i zwarty to to ponieważ

X∗ = Ω ∩ {x | f (x) ≤ m}

mamy, że Ω i zbiory poziomicowe nie majawspólnych

kierunków recesji.