4.1. Problem minimalizacyjny
Niech W będzie niepustym wypukłym podzbiorem Rn, zaś f:W→R będzie funkcją wypukłą. Rozważmy problem minimalizacji funkcji f na zbiorze W:
Przypomnijmy, że punktami dopuszczalnymi nazywamy elementy zbioru W. Rozwiązaniem globalnym nazywamy taki punkt x¯∈W, że fx¯≤fx dla każdego x∈W. Rozwiązaniem lokalnym jest taki punkt x¯∈W, że istnieje ε>0, dla którego fx¯≤fx, jeśli x∈W∩Bx¯,ε. Rozwiązanie jest ścisłe, jeśli fx¯<fx dla x∈W∩Bx¯,ε i x≠x¯. Innymi słowy, x¯ jest rozwiązaniem lokalnym, jeśli x¯ jest minimum funkcji f na pewnym otoczeniu x¯.
Twierdzenie 4.1
Niech W⊂Rn wypukły, f:W→R wypukła. Jeśli x¯∈W będzie rozwiązaniem lokalnym (4.1), to:
-
I) x¯ jest rozwiązaniem globalnym,
-
II) Zbiór rozwiązań globalnych jest wypukły.
-
III) Jeśli f jest ściśle wypukła, to x¯ jest ścisłym rozwiązaniem lokalnym.
-
IV) Jeśli x¯ jest ścisłym rozwiązaniem lokalnym, to x¯ jest jedynym rozwiązaniem globalnym.
Zauważmy, że w powyższym twierdzeniu nie zakładamy różniczkowalności funkcji f.
Dowód twierdzenia 4.1
(I): Dowód przez sprzeczność. Przypuśćmy, że istnieje x*∈W takie że fx*<fx¯. Ponieważ x¯ jest rozwiązaniem lokalnym, to fx¯≤fx dla x∈W∩Bx¯,ε i ε>0. Z wypukłości zbioru W wynika, iż odcinek łączący x¯ i x* znajduje się w zbiorze W. Ma on więc niepuste przecięcie z kulą Bx¯,ε: dla pewnego λ∈0,1 mamy λx¯+1-λx*∈Bx¯,ε. Z wypukłości f dostajemy
| fλx¯+1-λx*≤λfx¯+1-λfx*<fx¯, | |
co przeczy lokalnej optymalności x¯.
(II) Pozostawione jako ćwiczenie.
(III) Wynika wprost z definicji ścisłej wypukłości.
(IV) Pozostawione jako ćwiczenie.
∎
Dotychczas pokazaliśmy, że warunkiem koniecznym i dostatecznym minimum funkcji wypukłej na zbiorze wypukłym i otwartym jest zerowanie się pochodnej/gradientu. Uogólnimy teraz te wyniki na przypadek dowolnych zbiorów wypukłych.
Twierdzenie 4.2
Niech W⊂Rn wypukły, f:W→R wypukła. Jeśli f jest różniczkowalna w punkcie x¯∈W, to mamy następującą równoważność:
x¯ jest rozwiązaniem (4.1) wtw, gdy Dfx¯x-x¯≥0 dla każdego x∈W.
Uwaga 4.1
W sformułowaniu powyższego twierdzenia, jak i w wielu miejscach w dalszej części tych notatek, zastosowany jest następujący skrót myślowy. Aby mówić o różniczkowalności funkcji f w punkcie x¯∈W, musi być ona określona w pewnym otoczeniu x¯, czyli w kuli Bx¯,ε dla pewnego ε>0. Jeśli x¯ jest na brzegu W, to zakładać będziemy, że f jest określona na W∪Bx¯,ε mimo, że jest to pominięte, dla prostoty notacji, w założeniach twierdzenia.
Uwaga 4.2
Jeśli x¯∈intW, to warunek powyższy sprowadza się do warunku zerowania się pochodnej Dfx¯=0.
Dowód tw. 4.2
Załóżmy, że Dfx¯x-x¯≥0 dla każdego x∈W. Ustalmy x∈W. Na mocy twierdzenia 3.8
Z założenia, drugi składnik jest nieujemny, co pociąga fx≥fx¯. Z dowolności x∈W dostajemy tezę.
Załóżmy teraz, że x¯ jest rozwiązaniem (4.1). Ustalmy x∈W. Zauważmy, że wypukłość W implikuje x¯+λx-x¯=1-λx¯+λx∈W dla λ∈0,1. Z definicji pochodnej mamy
| Dfx¯x-x¯=limλ↓0,λ<1fx¯+λx-x¯-fx¯λ. | |
Ponieważ w punkcie x¯ jest minimum, to fx¯+λx-x¯≥fx¯. Stąd Dfx¯x-x¯≥0.
∎
Z dowodu powyższego twierdzenia dostajemy użyteczny wniosek.
Wniosek 4.1
Jeśli x¯∈W, gdzie W⊂Rn jest wypukły, jest rozwiązaniem lokalnym (4.1) dla funkcji f:W→R (niekoniecznie wypukłej) różniczkowalnej w x¯, to Dfx¯x-x¯≥0 dla każdego x∈W.
Przykład 4.1
Rozważmy problem minimalizacyjny:
| x1-322+x2-52⟶min,-x1+x2≤2,2x1+3x2≤11,x1,x2≥0, | |
Zbiór W zadany jest przez ograniczenia liniowe (patrz rysunek 4.1):
| W=x1,x2∈R2:x1,x2≥0,-x1+x2≤2, 2x1+3x2≤11. | |
Łatwo sprawdzić, że jest on wypukły. Funkcja fx1,x2=x1-322+x2-52 jest ściśle wypukła: jej hesjan wynosi
Na mocy tw. 4.1 minimum jest jednoznaczne. Policzmy gradient f:
| Dfx1,x2=2x1-3,2x2-10. | |
Gradient zeruje się w punkcie 32,5, który jest poza zbiorem W. Minimum należy zatem szukać na brzegu W. Nie mamy jeszcze narzędzi ułatwiających znalezienie tego punktu. Zgadujemy… Sprawdźmy wierzchołek x¯=1,3. Gradient w tym punkcie wynosi -1,-4. Zauważmy, że wektory x-x¯ są kombinacjami liniowymi dodatnimi wektorów x1=0,2-1,3=-1,-1 i x2=112,0-1,3=92,-3, tzn. x-x¯=a1x1+a2x2 dla pewnych a1,a2≥0. Wystarczy zatem sprawdzić, że Dfx¯x1≥0 i Dfx¯x2≥0:
| | Dfx¯x1=-1,-4-1-1=5, | |
| | Dfx¯x2=-1,-49/2-3=1612. | |
Na mocy tw. 4.2 minimum jest rzeczywiście w punkcie 1,3.
Rozszerzymy teraz twierdzenie 4.2 na klasę funkcji wypukłych nieróżniczkowalnych – skorzystamy z wprowadzonego w poprzednim rozdziale pojęcia subróżniczki.
Twierdzenie 4.3
Niech W~⊂Rn wypukły otwarty, f:W~→R wypukła. Załóżmy, że zbiór punktów dopuszczalnych W jest wypukłym podzbiorem W~. Mamy następującą równoważność:
x¯ jest rozwiązaniem (4.1) wtw, gdy istnieje ξ∈∂fx¯, takie że ξTx-x¯≥0 dla każdego x∈W.
Wniosek 4.2
Niech W⊂Rn wypukły otwarty, f:W~→R wypukła. Wówczas f ma w x¯∈W minimum globalne wtw, gdy 0∈∂fx¯.
Dowód twierdzenia 4.3
Zacznijmy od łatwiejszej implikacji. Załóżmy, że istnieje ξ∈∂fx¯, takie że ξTx-x¯≥0 dla każdego x∈W. Z faktu, że ξ jest subgradientem wynika, że
Wystarczy teraz skorzystać z założenia, żeby zauważyć, że fx≥fx¯ dla x∈W, czyli x¯ jest rozwiązaniem (4.1).
Załóżmy teraz, że x¯∈W jest rozwiązaniem (4.1). Zdefiniujmy dwa zbiory
| C1 | =x,z∈Rn×R:x∈W~,z>fx-fx¯, | |
| C2 | =x,z∈Rn×R:x∈W,z≤0. | |
Oba zbiory są wypukłe, C1 ma niepuste wnętrze (zbiór C2 ma puste wnętrze, jeśli W ma puste wnętrze). Z faktu, że punkt x¯ jest rozwiązaniem (4.1) wynika, że C1∩C2=∅. Stosujemy słabe twierdzenie o oddzielaniu: istnieje niezerowy wektor μ,γ∈Rn×R i stała b∈R, takie że
| μTx+γz≤b,∀x∈W~,z>fx-fx¯μTx+γz≥b,∀x∈W,z≤0. | | (4.2) |
Zanim przejdziemy do analitycznych rozważań popatrzmy na geometryczny obraz. Zauważmy, że zbiory C1 i C2 ,,stykają” się w punkcie x¯,0. Hiperpłaszczyzna oddzielająca te zbiory musi zatem przechodzić przez ten punkt. Jest ona styczna do wykresu funkcji x↦fx-fx¯ – pierwsza grupa współrzędnych μ wektora μ,γ do niej normalnego, z dokładnością do długości i zwrotu, wyznacza subgradient tego odwzorowania w punkcie x¯ (a zatem także subgradient f). Z faktu, że ta hiperpłaszczyzna jest również styczna do C2 dostajemy μTx-x¯≥0.
Udowodnijmy to teraz analitycznie. Odejmijmy od obu stron nierówności (4.2) μTx¯:
| | μTx-x¯+γz≤b~,∀x∈W~,z>fx-fx¯ | | (4.3) |
| | μTx-x¯+γz≥b~,∀x∈W,z≤0, | | (4.4) |
gdzie b~=b-μTx¯. Zauważmy najpierw, że γ nie może być większa od zera. Wówczas, wykorzystując dowolność z≤0, dostajemy sprzeczność z (4.4). Kładąc w (4.4) x=x¯ i z=0, otrzymujemy b~≤0. Wnioskujemy stąd, że niedopuszczalne jest γ=0: z nierówności (4.3) (pamiętając o otwartości W~) dostalibyśmy bowiem μ=0, co przeczyłoby niezerowości wektora μ,γ. Wykazaliśmy więc, że
Biorąc x=x¯, nierówność (4.3) upraszcza się do γz≤b~ dla z>0. Stąd b~≥0. Łącząc to z poprzednio otrzymaną nierównością b~≤0 dostajemy
Przechodząc w (4.3) z z do fx-fx¯ mamy
Dzieląc obie strony przez γ i pamiętając, że γ<0 dostajemy
co dowodzi, że -μγ∈∂fx¯. Kładąc z=0 w (4.4) otrzymujemy μTx-x¯≥0. Dzielimy obie strony przez -γ>0:
co kończy dowód.
∎
4.2. Funkcje pseudowypukłe
W tym podrozdziale wprowadzimy rodzinę funkcji, dla której spełniony jest warunek:
| Dfx¯=0⟺w x¯ jest minimum globalne. | |
Okazuje się, że rodzina ta obejmuje nie tylko funkcje wypukłe.
Definicja 4.1
Niech W⊂Rn będzie otwarty i niepusty, zaś f:W→R – różniczkowalna w W. Funkcja f jest pseudowypukła w x¯∈W, jeśli
| ∀y∈W:Dfx¯y-x¯≥0⟹fy≥fx¯. | |
Funkcja f jest ściśle pseudowypukła w x¯∈W, jeśli
| ∀y∈W:Dfx¯y-x¯≥0,x¯≠y⟹fy>fx¯. | |
Funkcja f jest (ściśle) pseudowypukła, jeśli jest ona (ściśle) pseudowypukła w każdym punkcie x¯∈W.
Funkcja f jest (ściśle) pseudowklęsła, jeśli -f jest (ściśle) pseudowypukła.
Uwaga 4.3
Implikacja w definicji pseudowypukłości ma równoważną postać:
| ∀y∈W:fy<fx¯⟹Dfx¯y-x¯<0. | |
Na rysunku 4.2 znajdują się przykłady jednowymiarowych funkcji pseudowypukłych i pseudowklęsłych.
Lemat 4.1
Niech f:W→R, gdzie W⊂Rn wypukły, otwarty i niepusty. Jeśli f jest (ściśle) wypukła i różniczkowalna na W, to f jest (ściśle) pseudowypukła.
Dowód
Załóżmy, że f wypukła. Na mocy tw. 3.8 dla dowolnych x¯,x∈W mamy
Jeśli zatem Dfx¯x-x¯≥0, to fx≥fx¯ i f jest pseudowypukła. W analogiczny sposób dowodzimy, że ścisła wypukłość pociąga ścisłą pseudowypukłość.
∎
Lemat 4.2
Niech f:W→R, gdzie W⊂Rn, otwarty, niepusty, będzie funkcją pseudowypukłą w x¯∈W. Wówczas x¯ jest minimum globalnym wtw, gdy Dfx¯=0.
Dowód
Identyczny jak dowód wniosku 3.2.
∎
Dowód poniższego lematu jest identyczny jak dowód twierdzenia 4.2.
Lemat 4.3
Niech W⊂Rn wypukły, f:W→R pseudowypukła. Mamy następującą równoważność:
x¯ jest rozwiązaniem (4.1) wtw, gdy Dfx¯x-x¯≥0 dla każdego x∈W.
4.3. Maksymalizacja funkcji wypukłej
Definicja 4.2
Punktem ekstremalnym zbioru wypukłego W⊂Rn nazwiemy taki punkt x¯∈W, który nie jest punktem wewnętrznym żadnego odcinka zawartego w W, tj. jeśli x¯=λx1+1-λx2 dla pewnych λ∈0,1 i x1,x2∈W, to x1=x2=x¯.
Definicja 4.3
Otoczką wypukłą punktów xii∈I nazywamy zbiór punktów będących kombinacją wypukłą skończonej liczby spośród punktów xi.
Otoczkę wypukłą można równoważnie definiować jako najmniejszy zbiór wypukły zawierający punkty xii∈I.
Przedstawimy teraz prostą wersję twierdzenia Kreina-Milmana.
Twierdzenie 4.4
Niech U⊂Rn będzie zbiorem wypukłym i zwartym. Jest on wówczas otoczką wypukłą swoich punktów ekstremalnych.
Przed przejściem do dowodu powyższego twierdzenia wprowadzimy niezbędne pojęcia. Przypomnijmy, że przestrzenią afiniczną nazywamy zbiór A, taki że ∑i=1kλixi∈A dla dowolnych xi⊂A i λi⊂R takich że ∑i=1kλi=1. Każda podprzestrzeń afiniczna Rn może zostać przesunięta tak, aby zawierała 0. Staje się ona wówczas podprzestrzenią liniową. Wymiarem podprzestrzeni afinicznej nazywamy wymiar związanej z nią podprzestrzeni liniowej.
Definicja 4.4
Wymiarem zbioru wypukłego U⊂Rn nazywamy wymiar otoczki afinicznej U, tzn. podprzestrzeni afinicznej generowanej przez U:
| affU=∑i=1kλixi:x1,…,xk∈U,∑i=1kλi=1. | |
Zapiszmy łatwe wnioski z powyższej definicji i rozważań ją poprzedzających:
Wniosek 4.3
-
Zbiór wypukły o wymiarze m<n możemy traktować jako podzbiór przestrzeni Rm.
-
Zbiór wypukły w przestrzeni Rn ma niepuste wnętrze wtw, gdy jego wymiar wynosi n.
Dotychczas rozważaliśmy hiperpłaszczyzny podpierające epigraf funkcji wypukłej. Teraz uogólnimy to pojęcie na dowolny zbiór wypukły.
Lemat 4.4
Niech U⊂Rn będzie zbiorem wypukłym o niepustym wnętrzu. Przez punkt brzegowy x¯∈U przechodzi wówczas hiperpłaszczyzna, taka że zbiór U leży w jednej z wyznaczonych przez nią półprzestrzeni. Hiperpłaszczyznę tą nazywamy hiperpłaszczyzną podpierającą zbiór U w punkcie x¯.
Dowód
Na mocy słabego twierdzenia o oddzielaniu zastosowanego do U i V=x¯ (zauważmy, że intU∩V=∅) istnieje a∈Rn, takie że aTx≤aTx¯ dla każdego x∈U. Szukaną hiperpłaszczyzną jest
Zbiór U zawarty jest w półprzestrzeni x∈Rn:aTx≤aTx¯.
∎
Dowód twierdzenia 4.4
Przeprowadzimy indukcję po wymiarze m zbioru zwartego i wypukłego U. Przypadki m=0 (U jest punktem) i m=1 (U jest odcinkiem) są trywialne. Czas na krok indukcyjny. Załóżmy, że każdy zbiór wypukły i zwarty o wymiarze nie większym od m jest otoczką wypukłą swoich punktów ekstremalnych. Weźmy zbiór wypukły i zwarty U o wymiarze m+1. Zbiór ten traktujemy jako podzbiór Rm+1. Ma on wówczas niepuste wnętrze. Niech x¯∈U.
Przypadek (I): x¯ leży na brzegu U. Na mocy lematu 4.4 istnieje hiperpłaszczyzna podpierająca H przechodząca przez x¯. Zbiór Ux¯=U∩H jest wypukły, zwarty i o wymiarze co najwyżej m. Na mocy założenia indukcyjnego punkt x¯ jest kombinacją wypukłą punktów ekstremalnych Ux¯. Pozostaje już tylko wykazać, że punkty ekstremalne Ux¯ są punktami ekstremalnymi U. Wynika to stąd, że żaden punkt x∈Ux¯ nie może być przedstawiony jako kombinacja wypukła punktów, z których jeden lub oba nie należą do Ux¯.
Przypadek (II): x¯ leży we wnętrzu U. Przeprowadźmy przez x¯ dowolną prostą. Przecina ona brzeg U w dwóch punktach x1,x2. Z przypadku (I) wiemy, że każdy z punktów x1,x2 może zostać przedstawiony jako kombinacja wypukła skończonej liczby punktów ekstremalnych U. Punkt x¯ może być zapisany jako kombinacja wypukła x1,x2, a więc należy do otoczki wypukłej punktów ekstremalnych U.
∎
Poniżej prezentujemy inny dowód twierdzenia 4.4 bazujący częściowo na pomysłach wykorzystywanych w dowodzie ogólnej wersji twierdzenia Kreina-Milmana. W przeciwieństwie do powyższego rozumowania, dowód ten nie jest konstruktywny.
Alternatywny dowód twierdzenia 4.4
Jeśli zbiór U zawarty jest w R1, to teza twierdzenia jest trywialna. Załóżmy więc, że każdy wypukły zwarty podzbiór Rm jest otoczką wypukłą swoich punktów ekstremalnych. Udowodnimy prawdziwość tego stwierdzenia dla U⊂Rm+1. Niech W będzie otoczką wypukłą punktów ekstremalnych U. Oczywiście W⊂U. Przypuśćmy, że istnieje x¯∈U∖W. Wówczas możemy znaleźć kulę o środku w x¯ i dostatecznie małym promieniu, która nie przecina W. Na mocy mocnego twierdzenia o oddzielaniu, tw. 3.2, istnieje wektor a∈Rm+1, taki że aTx≤α dla x∈W i aTx¯>α. Niech β=supx∈UaTx. Supremum to jest po całym zbiorze U i jest skończone ze zwartości U. Hiperpłaszczyzna P=x∈Rm+1:aTx=β nie przecina W (bo α<aTx¯≤β), ale ma punkt wspólny z U. Rzeczywiście, PU:=P∩U jest niepusty, gdyż ze zwartości U wynika, że supremum definiujące β jest osiągane, czyli istnieje x∈U, dla którego aTx=β. Pokażemy, że PU zawiera punkt ekstremalny U, co będzie sprzeczne z definicją zbioru W. Zbiór PU jest niepustym, zwartym zbiorem wypukłym w przestrzeni afinicznej o wymiarze m. Zbiór PU możemy traktować jako podzbiór Rm, czyli na mocy założenia indukcyjnego jest on otoczką wypukłą swoich punktów ekstremalnych. Niech y¯ będzie jednym z punktów ekstremalnych PU i załóżmy, że jest on kombinacją wypukłą y1,y2∈U, y¯=λy1+1-λy2 dla λ∈0,1. Wówczas β=aTy¯=λaTy1+1-λaTy2. Z konstrukcji β wynika, że zarówno aTy1 jak i aTy2 muszą być równe β, czyli y1,y2∈PU. Z faktu, że y¯ jest punktem ekstremalnym PU wnioskujemy, że y1=y2=y¯, czyli y¯ jest punktem ekstremalnym U.
∎
Twierdzenie 4.5
Niech f:W→R wypukła, ciągła, określona na wypukłym i zwartym zbiorze W⊂Rn. Wówczas punkt ekstremalny zbioru W jest jednym z rozwiązań globalnych problemu
Dowód
Funkcja ciągła osiąga swoje kresy na zbiorze zwartym. Powyższy problem maksymalizacyjny ma zatem rozwiązanie x¯∈W. Na mocy tw. 4.4 punkt x¯ jest kombinacją wypukłą skończonej liczby punktów ekstremalnych, x1,…,xm, zbioru W, tzn.
dla liczb a1,…,am>0 takich że a1+…+am=1. Z wypukłości f dostajemy
Z faktu, że x¯ jest maksimum f na zbiorze W wynika, że fx1=…=fxm=fx¯.
∎
Przykład 4.2
Rozważmy następujące zadanie optymalizacyjne:
| x1+x22→max,x12+x22≤1,x1+x2≥0. | |
Funkcja celu jest wypukła, więc na mocy twierdzenia 4.5 punkt ekstremalny jest rozwiązaniem. Zbiór punktów dopuszczalnych jest kołem przeciętym z półprzestrzenią, czyli zbiorem wypukłym. Zbiór punktów ekstremalnych zaznaczony jest pogrubioną linią na rysunku 4.3. Jest to fragment okręgu. Zmaksymalizujmy więc funkcję celu na całym okręgu i zobaczmy, czy rozwiązanie należy do tego fragmentu okręgu. Podstawiając x22=1-x12 do funkcji celu dostajemy
Rozwiązaniem tego problemu jest x1=1/2. Stąd x2=±3/2. Para 1/2,3/2 należy do półokręgu punktów ekstremalnych, więc jest rozwiązaniem, lecz niekoniecznie jedynym. Para 1/2,-3/2 nie należy do zbioru punktów dopuszczalnych.
Twierdzenie 4.5 jest szczególnie użyteczne przy maksymalizacji funkcji wypukłej na zbiorach wielościennych:
Definicja 4.5
Zbiór W⊂Rn nazwiemy zbiorem wielościennym, jeśli jest przecięciem skończonej rodziny półprzestrzeni, tzn.
| W=x∈Rn:piTx≤αi,i=1,…,m, | |
gdzie pi∈Rn, pi≠0 i αi∈R.
Łatwo można zauważyć, że punktami ekstremalnymi ograniczonych zbiorów wielościennych są ,,wierzchołki” (patrz rys. 4.4).
Lemat 4.5
Zbiór wielościenny jest domknięty i wypukły.
Dowód
Zbiór wielościenny jest domknięty i wypukły jako przecięcie rodziny zbiorów domkniętych i wypukłych.
∎
Przykład 4.3
Rozważmy problem optymalizacyjny
| x12+x22→max,x1+3x2≤12,5x1+x2≤18,3x1+2x2≥8. | |
Funkcja celu jest wypukła, zaś zbiór punktów dopuszczalnych jest wielościenny. Jego punkty ekstremalne to 0,4T, 3,3T i 4,-2T, patrz rysunek 4.5. Wartość funkcji celu w tych punktach wynosi odpowiednio: 16, 18 i 20. Rozwiązaniem jest zatem punkt 4,-2T. Można łatwo dowieść, że jest to jedyne rozwiązanie tego problemu.
4.4. Zadania
Ćwiczenie 4.1
Udowodnij, że zbiór rozwiązań globalnych zagadnienia (4.1) jest wypukły dla wypukłego zbioru W⊂Rn i wypukłej funkcji f:W→R.
Ćwiczenie 4.2
Rozważmy zagadnienie (4.1) dla wypukłego zbioru W⊂Rn i wypukłej funkcji f:W→R. Wykaż, że ścisłe rozwiązanie lokalne jest jedynym rozwiązaniem globalnym.
Ćwiczenie 4.3
Udowodnij: Niech W⊂Rn wypukły oraz g,h:W→R różniczkowalne. Jeśli zachodzi jeden z poniższych warunków:
-
g jest wypukła, g≥0, oraz h jest wklęsła, h>0,
-
g jest wypukła, g≤0, oraz h jest wypukła, h>0,
to f=g/h jest pseudowypukła. Podaj przykład, że f nie jest wypukła.
Ćwiczenie 4.4
Udowodnij: Niech W⊂Rn wypukły oraz g,h:W→R różniczkowalne. Jeśli g jest wypukła i g≤0 oraz h jest wklęsła, h>0, to f=gh jest pseudowypukła.
Ćwiczenie 4.5
Udowodnij, że zbiór minimów funkcji pseudowypukłej f:W→R, gdzie W⊂Rn wypukły, jest zbiorem wypukłym.
Ćwiczenie 4.6
Odpowiedz na następujące pytania:
-
Czy suma funkcji pseudowypukłych jest pseudowypukła?
-
Czy jeśli funkcje g1,g2 są pseudowypukłe w punkcie x oraz Dg1x=Dg2x=0T, to funkcja g1+g2 jest pseudowypukła w x?
-
Czy suma funkcji pseudowypukłej i wypukłej jest pseudowypukła?
Odpowiedzi uzasadnij kontrprzykładami lub dowodami.
Ćwiczenie 4.7
Korzystając z tw. 4.2 rozwiąż zadanie
Ćwiczenie 4.8
Znaleźć rozwiązania zadania
| logx1+4+x2→max,x2≥2x1,x2≤4. | |
Ćwiczenie 4.9
Rozwiąż zadanie
| ex1-32+x2logx2→min,x2>1,x1∈1,100. | |
Ćwiczenie 4.10
Udowodnij, że x¯∈W jest punktem ekstremalnym zbioru wypukłego W⊂Rn wtw, gdy W∖x¯ jest zbiorem wypukłym.
Ćwiczenie 4.11
Wykaż, że jeśli w punkcie brzegowym x¯ zbioru wypukłego U istnieje hiperpłaszczyzna podpierająca H, taka że H∩U=x¯, to punkt x¯ jest punktem ekstremalnym U.
Ćwiczenie 4.12
Zbadaj związek pomiędzy subróżniczką funkcji wypukłej w punkcie x¯ a hiperpłaszczyznami podpierającymi epigraf tej funkcji w tym punkcie.
Ćwiczenie 4.13
Znaleźć rozwiązanie zadania
| log1x1+4+x2→max,x2≥2x1,x2≤4. | |
Ćwiczenie 4.14
Rozwiąż problem programowania nieliniowego z ograniczeniami:
| log2x1+x2-2x2-2x1-x22+2x2→min,x1≥0,x2≥0,x1+x2≥1,x1-x2+x1≤4. | |
Ćwiczenie 4.15
([3, Zadania 3.28, 3.29])
Zdefiniujmy f:0,∞n→R najstępująco:
| fx=mincTy+xTAy-b:y∈W, | |
gdzie W jest zbiorem wielościennym, b,c∈Rn, A∈Rn×n.
-
Wykaż, że f jest wklęsła.
-
Scharakteryzuj subróżniczkę f.
-
Znajdź subróżniczkę w punktach x≥0 dla
Ćwiczenie 4.16
Korzystając z tw. 4.3 rozwiąż następujący problem optymalizacyjny:
| x2-6x+y2+2y→min,x+2y-10=0,25-x2-y2≥0. | |
