1.1. Problem optymalizacji
Niech W⊂Rn będzie niepustym zbiorem, zaś f:W→R dowolną funkcją. Będziemy rozważać problem minimalizacji funkcji f na zbiorze W, przyjmując różne postaci W, w tym:
-
W=Rn (problem optymalizacji bez ograniczeń),
-
W=x∈Rn:g1x=0,…,gmx=0, gdzie g1,…gm:Rn→R pewne funkcje (problem optymalizacji z ograniczeniami równościowymi),
-
W=x∈Rn:g1x≤0,…,gmx≤0, gdzie g1,…gm:Rn→R pewne funkcje (problem optymalizacji z ograniczeniami nierównościowymi).
Zbiór W nosi nazwę zbioru punktów dopuszczalnych.
Definicja 1.1
Punkt x0∈W nazywamy minimum globalnym
funkcji f na zbiorze W jeśli
| fx≥fx0dla każdegox∈W. | |
Definicja 1.2
Punkt x0∈W nazywamy minimum lokalnym
funkcji f jeśli istnieje ε>0 takie, że dla kuli
Bx0,ε o środku w x0 i promieniu ε
zachodzi
| fx≥fx0dla każdegox∈Bx0,ε∩W. | |
Oczywiście, jeśli x0 jest minimum globalnym to jest minimum
lokalnym. Minimum nazywamy ścisłym, jeśli w
powyższych definicjach zachodzi fx>fx0, dla x≠x0.
Analogicznie definiujemy globalne i lokalne maksimum. Punkt x0
nazywamy ekstremum (lokalnym, globalnym) jeśli jest on
maksimum lub minimum (lokalnym, globalnym).
Minimum (globalne, lokalne) nie musi istnieć, tzn. może się
okazać, że nie istnieje x0 spełniające warunek z
definicji 1.1 lub 1.2. W szczególności minimum
globalne f na zbiorze W nie istnieje gdy:
-
-
(b) infx∈Wfx=c∈R, ale ∄x∈U takie, że
fx=c.
Przykład 1.1
Niech W=R,fx=xsinx. Dla tej funkcji
infx∈Wfx=-∞, zatem minimum globalne nie istnieje.
Jeżeli natomiast ograniczymy się do przedziału W=a,b,
to minimum globalne będzie istnieć. Funkcja ta osiąga
minimum lokalne w nieskończonej ilości punktów, dla W=R.
Jeżeli za W przyjmiemy odcinek otwarty, to minimum globalne
istnieje lub nie istnieje, w zależności od tego odcinka.
Ogólnie, funkcja ciągła może nie osiągać kresów na
zbiorze niezwartym, w szczególności na podzbiorze otwartym
W⊂Rn.
1.2. Istnienie minimum funkcji ciągłej
Przypomnijmy, że podzbiór zwarty w Rn to podzbiór domknięty i ograniczony.
Twierdzenie 1.1
Jeśli W jest zbiorem zwartym i f:W→R jest funkcją ciągłą, to f osiąga kresy na W (dolny i górny).
Oznacza to, że istnieją x0, y0∈W takie, że dla dowolnego x∈W zachodzi
Będziemy oznaczali normę euklidesową w Rn przez
Warunek zwartości zbioru w powyższym twierdzeniu możemy osłabić do warunku domkniętości, jeśli funkcja jest koercywna. Koercywność funkcji definiujemy następująco:
Definicja 1.3
Funkcję f:W→R na podzbiorze W⊂Rn nazywamy koercywną, jeśli fx→∞ dla x→∞. Można ten warunek zapisać równoważnie
| ∀r>0∃s>0∀x∈W:x>s⟹fx>r. | |
W szczególności, jeśli W jest ograniczony, to f jest automatycznie koercywna na W.
Twierdzenie 1.2
Jeśli zbiór W jest domknięty oraz funkcja f:W→R jest ciągła i koercywna, to istnieje punkt x0 w którym funkcja f przyjmuje minimum, tzn. istnieje x0∈W taki, że fx0=infx∈Wfx.
Dowód
Niech y będzie ustalonym punktem w zbiorze W⊂Rn. Rozpatrzmy zbiór U=x∈W:fx≤fy. Zauważmy, że U jest zbiorem domkniętym w W, bo funkcja f jest ciągła, a nierówność w warunku nieostra. Z domkniętości W wynika, że U jest domknięty w
Rn. Jest on też ograniczony. Mianowicie, dla r=fy, z koercywności f istnieje s>0 takie, że jeśli x>s,
to fx>r=fy, skąd U jest zawarte w kuli Bs=x:x≤s. Zatem U jest zbiorem zwartym. Wówczas istnieje x0∈U – punkt minimum na zbiorze U. Dla x∉U mamy fx>fy≥fx0, więc x0 jest globalnym minimum na całym W.
∎
Domkniętość W nie jest potrzebna, jeśli f odpowiednio rośnie w pobliżu granicy ∂W.
Twierdzenie 1.3
Niech W⊂Rn będzie dowolnym niepustym
podzbiorem oraz f:W→R – funkcją ciągłą. Jeśli dla pewnego ustalonego punktu y∈W oraz dowolnego ciągu xn∈W, takiego że
zachodzi
to istnieje punkt x0 w którym funkcja f przyjmuje minimum.
Dowód
Zbiór U definiujemy jak w poprzednim dowodzie, U=x∈W:fx≤fy. Aby pokazać domkniętość
U weźmy dowolny ciąg xn⊂U zbieżny do x~. Pokażemy, że x~∈U. Z xn∈U mamy fxn≤fy i
jeśli x~∉W, nierówność ta przeczy założeniu twierdzenia. Wynika stąd, że x~∈W. Korzystając teraz z
ciągłości f na W dostajemy fx~≤fy, skąd x~∈U. Ograniczoność zbioru U wynika z założonej w
twierdzeniu implikacji xn→∞⇒lim infn→∞fxn>fy. Pozostała część dowodu jest identyczna jak
w dowodzie poprzedniego twierdzenia.
∎
Przykład 1.2
Funkcja fx,y=xy-lnxy jest ciągła i spełnia
założenia Twierdzenia 1.3 na zbiorze W=x,y∈Rn:x>0,y>0,x+y≤4, osiąga więc minimum na W.
1.3. Minima lokalne funkcji jednej zmiennej
Niech W⊂R - podzbiór otwarty. Przypomnimy elementarne fakty.
Twierdzenie 1.4 (Warunek konieczny I rzędu)
Jeśli x0∈W jest punktem lokalnego minimum lub maksimum funkcji f:W→R oraz f posiada pochodną w punkcie x0, to
Dowód twierdzenia 1.4
Niech x0 - minimum lokalne. Dla dostatecznie małych h zachodzi fx0+h≥fx0. Zatem dla h>0 mamy
| fx0+h-fx0h≥0⟹limh→0fx0+h-fx0h≥0⟹f′x0≥0. | |
Dla h<0
| fx0+h-fx0h≤0⟹limh→0fx0+h-fx0h≤0⟹f′x0≤0. | |
Stąd f′x0=0.
∎
Twierdzenie 1.5 (Warunek konieczny II rzędu)
Jeśli f:W→R jest klasy C2 na zbiorze W i x0 jest punktem lokalnego minimum, to
Twierdzenie 1.6 (Warunek dostateczny II rzędu)
Jeśli f:W→R jest klasy C2 na zbiorze W oraz f′x0=0, f′′x0>0 dla pewnego x0∈W, to f ma ścisłe
lokalne minimum w punkcie x0.
Uwaga 1.1
Twierdzenie 1.5 pozostaje prawdziwe przy zamianie lokalnego minimum na maksimum, jeśli znak znak drugiej pochodnej zmienimy na przeciwny.
Uwaga 1.2
Jeśli W nie jest otwarty, to Twierdzenia 1.4 i 1.5 nie są prawdziwe dla x0∈∂W (brzeg W), np. funkcja fx=-x2 przyjmuje minimum na odcinku 0,2 w punkcie x0=2, ale żaden z warunków koniecznych tych twierdzeń nie zachodzi. Natomiast Twierdzenie 1.6 zachodzi również dla W będącego odcinkiem domkniętym i x0∈∂W.
Poniższe twierdzenie uogólnia warunek dostateczny II rzędu.
Twierdzenie 1.7
Jeśli funkcja f jest klasy Ck na podzbiorze otwartym W⊂R i zachodzi f′x0=f′′x0=⋯=fk-1x0=0 oraz fkx0≠0 w pewnym x0∈W, to:
-
I) Jeśli k jest nieparzyste, to funkcja f nie posiada w punkcie x0 ekstremum
lokalnego.
-
II) Jeśli k jest parzyste oraz:
-
(a) fkx0>0, to punkt x0 jest ścisłym minimum lokalnym f,
-
(b) fkx0<0, to punkt x0 jest ścisłym maksimum lokalnym f.
Dowody twierdzeń 1.5-1.7 podamy w podrozdziale 1.5.
1.4. Wzory Taylora
W tym podrozdziale przypomnimy wyniki, których będziemy używać w wielu dowodach w trakcie tego wykładu. Skorzystamy z nich również, aby przedstawić zwięzłe dowody twierdzeń 1.5-1.7.
Twierdzenie 1.8 (Twierdzenie o wartości średniej)
Jeśli funkcja f:a,b→R jest ciągła na a,b i różniczkowalna na a,b, to istnieje taki punkt x∈a,b, że
Zauważmy, że do prawdziwości powyższego twierdzenia nie jest konieczna ciągłość pierwszej pochodnej (w zadaniu 1.7 pokazujemy, że różnicznowalność nie musi pociągać ciągłości pochodnej).
Dowód twierdzenia 1.8
Niech gx=fb-fax-b-afx dla x∈a,b. Wówczas g jest ciągła na a,b, różniczkowalna w a,b oraz
Pokażemy teraz, że istnieje punkt x0∈a,b, w którym pochodna g się zeruje. Jeśli g jest funkcją stałą, to dla dowolnego x0∈a,b mamy g′x0=0. W przeciwnym przypadku, na mocy twierdzenia 1.1 funkcja g przyjmuje swoje kresy na a,b. Jeden z kresów jest różny od ga=gb. Zatem jest on przyjmowany w punkcie x0 we wnętrzu przedziału a,b. Korzystając z twierdzenia 1.4 wnioskujemy, że g′x0=0. Różniczkując g otrzymujemy:
| 0=g′x0=fb-fa-b-af′x. | |
Po prostych przekształceniach otrzymujemy poszukiwany wzór.
∎
Twierdzenie 1.9 (Twierdzenie Taylora z resztą w postaci Peano)
Niech f:a,b→R będzie funkcją klasy C1 na a,b oraz dwukrotnie różniczkowalna w pewnym x0∈a,b. Wówczas dla x∈a,b zachodzi następujący wzór:
| fx=fx0+f′x0x-x0+f′′x02x-x02+ox-x02. | |
Uwaga 1.3
W sformułowaniu powyższego twierdzenia użyliśmy notacji małe o. Rozumieć ją należy następująco:
| Rx=fx-fx0-f′x0x-x0-f′′x02x-x02 | |
jest rządu mniejszego niż x-x02, tzn.
Przykład 1.3
Innym zastosowaniem powyższej notacji jest definicja pochodnej. Pochodną funkcji f w punkcie x0 nazywamy taką liczbę α∈R, że
Dowód twierdzenia 1.9
Bez straty ogólności możemy założyć x0=0. Musimy wykazać, że Rx:=fx-f0-f′0x-f′′02x2 jest niższego rzędu niż x2, tzn. Rx=ox2. Z ciągłości pierwszej pochodnej f dostajemy
Wiemy, że f′ jest różniczkowalna w 0. Zatem f′y=f′0+f′′0y+ry, gdzie ry=oy. Oznacza to, że
Dla dowolnego ε>0 istnieje zatem δ>0, taka że y<δ pociąga ry<εy.
Ustalmy zatem dowolny ε>0 i związaną z nim δ>0. Weźmy x<δ i scałkujmy pochodną f′y. Otrzymamy wówczas:
| fx-f0=∫0xf′0+f′′0y+rydy=f′0x+f′′02x2+∫0xrydy, | |
czyli Rx=∫0xrydy. Korzystając z oszacowania ry<εy dla y<δ dostajemy
| Rx≤∫0xrydy<∫0xεydy=εx22. | |
A zatem
Z dowolności ε>0 wynika, iż Rx=ox2.
∎
Uwaga 1.4
Twierdzenie 1.9 można uogólnić do dowolnie długiej aproksymacji Taylora. Dowód przebiega wówczas podobnie, lecz jest nieznacznie dłuższy.
Zakładając większą gładkość funkcji f możemy opisać dokładniej błąd aproksymacji we wzorze Taylora.
Twierdzenie 1.10 (Twierdzenie Taylora z resztą w postaci Lagrange'a)
Niech f:a,b→R będzie funkcją klasy Ck-1 na a,b oraz k-krotnie różniczkowalna na a,b. Wtedy dla ustalonego x0∈a,b i x∈a,b zachodzi następujący wzór:
| fx=fx0+∑i=1k-1fix0i!x-x0i+fkx~k!x-x0k, | |
gdzie x~ jest pewnym punktem pomiędzy x0 i x.
W szczególności dla k=2 dostajemy
| fx=fx0+f′x0x-x0+12f′′x~x-x02. | |
Dowód twierdzenia 1.10
Niech liczba M spełnia równanie
| fx=fx0+∑i=1k-1fix0i!x-x0i+Mx-x0k. | |
Celem dowodu jest pokazanie, że M=fkx~k! dla pewnego punktu x~ pomiędzy x0 i x. Określmy funkcję
| gy=fy-∑i=1k-1fix0i!y-x0i-My-x0k,y∈x0,x. | |
Zauważmy, że
Ponieważ gx=0, to na podstawie twierdzenia 1.8 istnieje x1∈x0,x, taki że g′x1=0. Stosując jeszcze raz tw. 1.8 do funkcji g′y dla y∈x0,x1 dostajemy x2∈x0,x1, w którym g′′x2=0. Postępując w ten sposób dostajemy ciąg punktów x>x1>x2>⋯>xk>x0, takich że gjxj=0, j=1,…,k. Z warunku dla punktu xk otrzymujemy
Szukanym punktem x~ w twierdzeniu jest więc xk.
∎
1.5. Dowody twierdzeń 1.5-1.7
Dowód twierdzenia 1.5
Z twierdzenia 1.4 wiemy, że jeśli x0 jest punktem minimum to f′x0=0. Zatem korzystając ze wzoru Taylora, tw. 1.10, uzyskujemy
dla pewnego punktu x~ leżącego pomiędzy x0 i x.
Z założenia, że x0 jest minimum lokalnym, otrzymujemy fx-fx0≥0. Stąd i z x-x02≥0 wnioskujemy, że
Jeśli x→x0, to również x~→x0. Wykorzystując ciągłość f′′ dostajemy f′′x0≥0.
∎
Dowód twierdzenia 1.6
Z ciągłości drugiej pochodnej f wynika, że istnieje kula Bx0,ε, na której f′′>0. Zatem dla x∈Bx0,ε, x≠x0, wnioskujemy ze wzoru Taylora, tw. 1.10, że fx>fx0:
| fx-fx0=f′x0x-x0︸=0+12f′′x~x-x02︸>0. | |
Oznacza to, że f ma ścisłe minimum lokalne w x0.
∎
Dowód twierdzenia 1.7
Z ciągłości f i otwartości W wynika, że istnieje kula Bx0,ε⊂W, na której fk jest niezerowa (tzn. fk nie zmienia znaku z ciągłości). Korzystając ze wzoru Taylora, tw. 1.10 i z założeń twierdzenia otrzymujemy
dla dowolnego x∈Bx0,ε oraz x~, zależnego od x, należącego do przedziału o końcach x0 i x.
Aby zbadać, czy zachodzi jedna z nierówności fx>fx0 lub fx<fx0 dla wszystkich x≠x0, x∈Bx0,ε
należy zbadać znak członu z potęgą x-x0k. Człon ten zmienia znak dla k nieparzystego, stąd teza (I). Dla k
parzystego znak różnicy fx-fx0 zależy od znaku pochodnej fk na Bx0,ε.
∎
1.6. Ekstrema globalne
Uzupełnimy jeszcze twierdzenie 1.6 o wynik dotyczący ekstremów globalnych.
Niech I⊂R będzie odcinkiem otwartym, domkniętym, lub jednostronnie domkniętym (być może nieograniczonym) i niech f:I→R będzie funkcją klasy C1 na I i klasy C2 na intI. Zachodzi następujące
Twierdzenie 1.11
Przy powyższych założeniach, jeśli f′x0=0 oraz:
-
(a) f′′x≥0∀x∈I⟹x0 jest globalnym minimum na I,
-
(b) f′′x≤0∀x∈I⟹x0 jest globalnym maksimum na I.
Jeśli założenia powyższe uzupełnimy o warunek f′′x0>0 (odpowiednio f′′x0<0), to x0 będzie ścisłym
globalnym minimum (maksimum).
Dowód
Wzór Taylora, tw. 1.10, daje
| fx=fx0+12f′′x~x-x02, | |
gdzie x~ jest pewnym punktem pomiędzy x0 i x. Stąd drugi człon wzoru Taylora decyduje o nierówności pomiędzy fx a fx0 i otrzymujemy obie implikacje w twierdzeniu dotyczące słabych ekstremów.
Załóżmy dodatkowo w pierwszym stwierdzeniu, że f′′x0>0. Z założenia f′′x≥0 i warunku f′x0=0 dostajemy
| f′x=f′x-f′x0=∫x0xf′′ydy≥0, | |
gdy x>x0. Podobnie pokazujemy, że f′x=-∫xx0f′′ydy≤0, gdy x<x0. Z faktu, że
f′′x0>0 i ciągłości drugiej pochodnej dostajemy dodatkowo, że ta pochodna jest ściśle dodatnia w otoczeniu x0. Zatem
całki są dodatnie, co pociąga nierówności f′x>0, gdy x>x0, oraz f′x<0, gdy x<x0. Wynika stąd, że funkcja f jest ściśle rosnąca na prawo od x0 i ściśle malejąca na lewo od x0, a więc x0 jest ścisłym minimum. Przypadek ścisłego maksimum dowodzimy analogicznie.
∎
1.7. Zadania
Ćwiczenie 1.1
Czy funkcja fx,y=x4+x2-xy+2y2 osiąga minimum na zbiorze x,y∈R2:x≥-1.
Ćwiczenie 1.2
Znajdź minimum funkcji fx,y=2x+3y na zbiorze W=x,y∈R2:x2+y2=1.
Ćwiczenie 1.3
Znajdź maksimum funkcji fx,y=x2-4y2 na zbiorze W=x,y∈R2: 2x2+y=1.
Ćwiczenie 1.4
Znajdź minimum funkcji fx,y=ex2-y2 na zbiorze W=x,y∈R2:x2+y2=1.
Ćwiczenie 1.5
Rozważmy następujący nieliniowy problem optymalizacyjny:
| x1-42+x2-22→min,4x12+9x22≤36,x12+4x2=4,2x1+3≥0. | |
-
Naszkicuj zbiór punktów dopuszczalnych, czyli punktów spełniających wszystkie ograniczenia.
-
Znajdź graficznie rozwiązanie powyższego problemu optymalizacyjnego.
-
Znajdź następnie rozwiązanie w przypadku, gdy minimalizacja zamieniona zostanie na maksymalizację.
Ćwiczenie 1.6
Niech g będzie funkcją spełniającą: 0≤gy, y∈0,1, oraz ∫01gydy=1.
Znajdź x∈0,1, dla którego następująca całka jest minimalna:
Ćwiczenie 1.7
Wykaż, że funkcja
| fx=x2sin1x,x≠0,0,x=0, | |
jest różniczkowalna w R, lecz jej pochodna nie jest ciągła.
Ćwiczenie 1.8
Udowodnij, że poniższe definicje pochodnej funkcji f:a,b→R w punkcie x0∈a,b są równoważne:
-
(a) f′x0=limh→0fx0+h-fx0h,
-
(b) fx=fx0+αx-x0+ox-x0 dla x∈a,b i α∈R niezależnego od x.
Przez równoważność rozumiemy to, że jeśli granica w (a) istnieje, to zależność (b) jest spełniona z α=f′x0; i odwrotnie, jeśli (b) zachodzi dla pewnego α, to granica w (a) istnieje i jest równa α.