Zagadnienia

1. Wiadomości wstępne

1.1. Problem optymalizacji

Niech WRn będzie niepustym zbiorem, zaś f:WR 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=xRn:g1x=0,,gmx=0, gdzie g1,gm:RnR pewne funkcje (problem optymalizacji z ograniczeniami równościowymi),

  • W=xRn:g1x0,,gmx0, gdzie g1,gm:RnR pewne funkcje (problem optymalizacji z ograniczeniami nierównościowymi).

Zbiór W nosi nazwę zbioru punktów dopuszczalnych.

Definicja 1.1

Punkt x0W nazywamy minimum globalnym funkcji f na zbiorze W jeśli

fxfx0dla każdegoxW.
Definicja 1.2

Punkt x0W nazywamy minimum lokalnym funkcji f jeśli istnieje ε>0 takie, że dla kuli Bx0,ε o środku w x0 i promieniu ε zachodzi

fxfx0dla każdegoxBx0,ε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 xx0. 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:

  • (a) infxWfx=-, lub

  • (b) infxWfx=cR, ale xU takie, że fx=c.

Przykład 1.1

Niech W=R,fx=xsinx. Dla tej funkcji infxWfx=-, 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 WRn.

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:WR jest funkcją ciągłą, to f osiąga kresy na W (dolny i górny). Oznacza to, że istnieją x0, y0W takie, że dla dowolnego xW zachodzi

fx0fxfy0.

Będziemy oznaczali normę euklidesową w Rn przez

x=x12+x22++xn2.

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:WR na podzbiorze WRn nazywamy koercywną, jeśli fx dla x. Można ten warunek zapisać równoważnie

r>0s>0xW:x>sfx>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:WR jest ciągła i koercywna, to istnieje punkt x0 w którym funkcja f przyjmuje minimum, tzn. istnieje x0W taki, że fx0=infxWfx.

Dowód

Niech y będzie ustalonym punktem w zbiorze WRn. Rozpatrzmy zbiór U=xW:fxfy. 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:xs. Zatem U jest zbiorem zwartym. Wówczas istnieje x0U – punkt minimum na zbiorze U. Dla xU mamy fx>fyfx0, 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 WRn będzie dowolnym niepustym podzbiorem oraz f:WR – funkcją ciągłą. Jeśli dla pewnego ustalonego punktu yW oraz dowolnego ciągu xnW, takiego że

xnclWWlubxn

zachodzi

lim infnfxn>fy,

to istnieje punkt x0 w którym funkcja f przyjmuje minimum.

Dowód

Zbiór U definiujemy jak w poprzednim dowodzie, U=xW:fxfy. Aby pokazać domkniętość U weźmy dowolny ciąg xnU zbieżny do x~. Pokażemy, że x~U. Z xnU mamy fxnfy 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 xnlim infnfxn>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,yRn:x>0,y>0,x+y4, osiąga więc minimum na W.

1.3. Minima lokalne funkcji jednej zmiennej

Niech WR - podzbiór otwarty. Przypomnimy elementarne fakty.

Twierdzenie 1.4 (Warunek konieczny I rzędu)

Jeśli x0W jest punktem lokalnego minimum lub maksimum funkcji f:WR oraz f posiada pochodną w punkcie x0, to

fx0=0.
Dowód twierdzenia 1.4

Niech x0 - minimum lokalne. Dla dostatecznie małych h zachodzi fx0+hfx0. Zatem dla h>0 mamy

fx0+h-fx0h0limh0fx0+h-fx0h0fx00.

Dla h<0

fx0+h-fx0h0limh0fx0+h-fx0h0fx00.

Stąd fx0=0.

Twierdzenie 1.5 (Warunek konieczny II rzędu)

Jeśli f:WR jest klasy C2 na zbiorze W i x0 jest punktem lokalnego minimum, to

f′′x00.
Twierdzenie 1.6 (Warunek dostateczny II rzędu)

Jeśli f:WR jest klasy C2 na zbiorze W oraz fx0=0, f′′x0>0 dla pewnego x0W, 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 x0W (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 x0W.

Poniższe twierdzenie uogólnia warunek dostateczny II rzędu.

Twierdzenie 1.7

Jeśli funkcja f jest klasy Ck na podzbiorze otwartym WR i zachodzi fx0=f′′x0==fk-1x0=0 oraz fkx00 w pewnym x0W, 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,bR jest ciągła na a,b i różniczkowalna na a,b, to istnieje taki punkt xa,b, że

fb-fa=fxb-a.

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 xa,b. Wówczas g jest ciągła na a,b, różniczkowalna w a,b oraz

ga=fba-fab=gb.

Pokażemy teraz, że istnieje punkt x0a,b, w którym pochodna g się zeruje. Jeśli g jest funkcją stałą, to dla dowolnego x0a,b mamy gx0=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 gx0=0. Różniczkując g otrzymujemy:

0=gx0=fb-fa-b-afx.

Po prostych przekształceniach otrzymujemy poszukiwany wzór.

Twierdzenie 1.9 (Twierdzenie Taylora z resztą w postaci Peano)

Niech f:a,bR będzie funkcją klasy C1 na a,b oraz dwukrotnie różniczkowalna w pewnym x0a,b. Wówczas dla xa,b zachodzi następujący wzór:

fx=fx0+fx0x-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-fx0x-x0-f′′x02x-x02

jest rządu mniejszego niż x-x02, tzn.

limxx0Rxx-x02=0.
Przykład 1.3

Innym zastosowaniem powyższej notacji jest definicja pochodnej. Pochodną funkcji f w punkcie x0 nazywamy taką liczbę αR, że

fx=fx0+αx-x0+ox-x0.
Dowód twierdzenia 1.9

Bez straty ogólności możemy założyć x0=0. Musimy wykazać, że Rx:=fx-f0-f0x-f′′02x2 jest niższego rzędu niż x2, tzn. Rx=ox2. Z ciągłości pierwszej pochodnej f dostajemy

fx-f0=0xfydy.

Wiemy, że f jest różniczkowalna w 0. Zatem fy=f0+f′′0y+ry, gdzie ry=oy. Oznacza to, że

limy0ryy=0.

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ą fy. Otrzymamy wówczas:

fx-f0=0xf0+f′′0y+rydy=f0x+f′′02x2+0xrydy,

czyli Rx=0xrydy. Korzystając z oszacowania ry<εy dla y<δ dostajemy

Rx0xrydy<0xεydy=εx22.

A zatem

Rxx2<ε2.

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,bR będzie funkcją klasy Ck-1 na a,b oraz k-krotnie różniczkowalna na a,b. Wtedy dla ustalonego x0a,b i xa,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+fx0x-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,yx0,x.

Zauważmy, że

gx0=gx0==gk-1x0=0.

Ponieważ gx=0, to na podstawie twierdzenia 1.8 istnieje x1x0,x, taki że gx1=0. Stosując jeszcze raz tw. 1.8 do funkcji gy dla yx0,x1 dostajemy x2x0,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

0=gkxk=fkxk-k!M.

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 fx0=0. Zatem korzystając ze wzoru Taylora, tw. 1.10, uzyskujemy

fx-fx0=12f′′x~x-x02

dla pewnego punktu x~ leżącego pomiędzy x0 i x. Z założenia, że x0 jest minimum lokalnym, otrzymujemy fx-fx00. Stąd i z x-x020 wnioskujemy, że

f′′x~0.

Jeśli xx0, to również x~x0. Wykorzystując ciągłość f′′ dostajemy f′′x00.

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 xBx0,ε, xx0, wnioskujemy ze wzoru Taylora, tw. 1.10, że fx>fx0:

fx-fx0=fx0x-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

fx=fx0+fkx~k!x-x0k

dla dowolnego xBx0,ε 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 xx0, xBx0,ε 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 IR będzie odcinkiem otwartym, domkniętym, lub jednostronnie domkniętym (być może nieograniczonym) i niech f:IR 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 fx0=0 oraz:

  • (a) f′′x0xIx0 jest globalnym minimum na I,

  • (b) f′′x0xIx0 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′′x0 i warunku fx0=0 dostajemy

fx=fx-fx0=x0xf′′ydy0,

gdy x>x0. Podobnie pokazujemy, że fx=-xx0f′′ydy0, 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 fx>0, gdy x>x0, oraz fx<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,yR2:x-1.

Ćwiczenie 1.2

Znajdź minimum funkcji fx,y=2x+3y na zbiorze W=x,yR2:x2+y2=1.

Ćwiczenie 1.3

Znajdź maksimum funkcji fx,y=x2-4y2 na zbiorze W=x,yR2: 2x2+y=1.

Ćwiczenie 1.4

Znajdź minimum funkcji fx,y=ex2-y2 na zbiorze W=x,yR2:x2+y2=1.

Ćwiczenie 1.5

Rozważmy następujący nieliniowy problem optymalizacyjny:

x1-42+x2-22min,4x12+9x2236,x12+4x2=4,2x1+30.
  1. Naszkicuj zbiór punktów dopuszczalnych, czyli punktów spełniających wszystkie ograniczenia.

  2. Znajdź graficznie rozwiązanie powyższego problemu optymalizacyjnego.

  3. Znajdź następnie rozwiązanie w przypadku, gdy minimalizacja zamieniona zostanie na maksymalizację.

Ćwiczenie 1.6

Niech g będzie funkcją spełniającą: 0gy, y0,1, oraz 01gydy=1. Znajdź x0,1, dla którego następująca całka jest minimalna:

01x-y2gydy.
Ćwiczenie 1.7

Wykaż, że funkcja

fx=x2sin1x,x0,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,bR w punkcie x0a,b są równoważne:

  • (a) fx0=limh0fx0+h-fx0h,

  • (b) fx=fx0+αx-x0+ox-x0 dla xa,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 α=fx0; i odwrotnie, jeśli (b) zachodzi dla pewnego α, to granica w (a) istnieje i jest równa α.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.