5.1. Stożek kierunków stycznych
Rozważmy problem optymalizacyjny
gdzie W⊂Rn i f:W→R. Niech x¯ będzie rozwiązaniem lokalnym. Będziemy chcieli powiązać geometrię lokalną zbioru W w punkcie x¯ z zachowaniem funkcji f, czyli kierunkami spadku jej wartości. Przez lokalną geometrię W rozumiemy zbiór kierunków, w których możemy się poruszyć z punktu x¯ nie opuszczając W.
Definicja 5.1
Stożkiem kierunków stycznych Tx¯ do W w punkcie x¯∈clW nazywamy zbiór wektorów d∈Rn takich że
dla pewnych λk>0, xk∈W i xk→x¯.
Powyższa definicja mówi, iż kierunek d należy do stożka kierunków stycznych Tx¯, jeśli jest on granicą kierunków wyznaczonych przez ciąg punktów dopuszczalnych xk zmierzających to x¯. Zapisać możemy to formalnie w następujący sposób:
| Tx¯=d∈Rn:d=λlimk→∞xk-x¯xk-x¯ dla pewnych λ≥0, xk⊂W oraz xk→x¯, xk≠x¯. | | (5.2) |
Dowód tej tożsamości oraz poniższego lematu pozostawiamy jako ćwiczenie.
Lemat 5.1
-
Zbiór Tx¯ jest stożkiem, tzn. λd∈Tx¯ dla dowolnych d∈Tx¯ i λ≥0. W szczególności, 0∈Tx¯.
-
Jeśli x¯ jest punktem wewnętrznym zbioru W, to Tx¯=Rn.
-
Stożek Tx¯ jest domknięty.
Przykład 5.1
Na rysunku 5.1 znajdują się trzy przykłady zbiorów i stożków do nich stycznych w punkcie x¯. Stożki te są przesunięte o wektor x¯, by pokazać ich zależność od kształtu zbioru. W przykładzie (a) i (c) zakładamy, że brzeg zbioru W jest gładki, więc stożki te są półprzestrzeniami ograniczonymi przez styczną w x¯. W przykładzie (b) zbiór W to środek narysowanego stożka (bez brzegu). Wówczas stożek kierunków stycznych jest domknięciem zbioru W.
Jak już wspomnieliśmy, stożek kierunków stycznych jest ściśle związany z rozwiązaniem zagadnienia (5.1). Jeśli w punkcie x¯∈W funkcja f ma minimum lokalne na W, to wówczas kierunki spadku wartości funkcji f nie mogą należeć do zbioru kierunków stycznych w punkcie x¯. Gdyby tak nie było, to poruszając się w kierunku spadku funkcji f zmniejszalibyśmy jej wartość jednocześnie pozostając w zbiorze W. Intuicje te formalizujemy poniżej.
Definicja 5.2
Niech f:X→R będzie różniczkowalna w x¯∈X. Zbiorem kierunków spadku funkcji f w punkcie x¯ nazywamy
Twierdzenie 5.1
Niech x¯ będzie rozwiązaniem lokalnym problemu (5.1). Jeśli f jest różniczkowalna w x¯, to
Dowód
Weźmy d∈Tx¯. Wówczas d=limk→∞λkxk-x¯ dla pewnego ciągu punktów xk⊂W zbieżnego do x¯ oraz ciągu liczb λk⊂0,∞. Z definicji różniczkowalności f w x¯ mamy
| fxk=fx¯+Dfx¯xk-x¯+oxk-x¯. | |
Z faktu, że x¯ jest rozwiązaniem lokalnym fxk≥fx¯ dla dostatecznie dużych k. W połączeniu z powyższym wzorem daje to następujące oszacowanie:
| 0≤fxk-fx¯=Dfx¯xk-x¯+oxk-x¯. | |
Mnożąc obie strony powyższej nierówności przez λk dostajemy
| 0≤Dfx¯λkxk-x¯+λkoxk-x¯. | |
Zrobimy teraz sztuczkę, aby rozwiązać problem z oxk-x¯ i przejdziemy z k to nieskończoności:
| 0≤Dfx¯λkxk-x¯︸→d+λkxk-x¯︸→doxk-x¯xk-x¯︸→0. | |
Udowodniliśmy zatem, że Dfx¯d≥0, czyli d∉Dx¯. Kończy to dowód twierdzenia.
∎
Przykład 5.2
Rozważmy następujący problem optymalizacyjny:
Oznaczmy fx1,x2=x12+x22 i W=x∈R2:x1+x2≥1. Zbadamy zbiory Tx¯ i Dx¯ w następujących punktach: 1,1T,1,0T,12,12T.
-
x¯=1,1T. Punkt ten leży wewnątrz zbioru W, czyli Tx¯=R2. Zbiór kierunków spadku funkcji f dany jest następująco:
| Dx¯=d∈R2:Dfx¯d<0=d∈R2:2,2d<0=d∈R2:d1+d2<0. | |
W oczywisty sposób część wspólna powyższych zbiorów nie jest pusta, czyli w punkcie 1,1T nie ma minimum.
-
x¯=1,0T. Punkt ten leży na brzegu zbioru W. Łatwo można zauważyć, że
| Tx¯=d∈R2:d1+d2≥0,Dx¯=d∈R2:d1<0. | |
Zbiory te mają niepuste przecięcie (patrz podwójna kratka na rys. 5.2), więc w punkcie 1,0T nie ma minimum.
-
x¯=12,12T. Zauważmy, że
| Tx¯=d∈R2:d1+d2≥0,Dx¯=d∈R2:1,1d<0=d∈R2:d1+d2<0. | |
Zbiory te mają zatem puste przecięcie, więc w punkcie 12,12T może być minimum.
Bezpośrednie wykorzystanie twierdzenia 5.1 do szukania kandydatów na rozwiązania zadań z ograniczeniami nie wygląda zachęcająco. Dlatego postaramy się opisać prościej zbiór Tx¯ oraz warunek Tx¯∩Dx¯=∅.
5.2. Ograniczenia nierównościowe
Zajmiemy się problemem optymalizacyjnym w następującej formie:
| fx→min,gix≤0,i=1,…,m,x∈X, | | (5.3) |
gdzie X⊂Rn jest zbiorem otwartym i f,g1,…,gm:X→R. A zatem
| W=x∈X:g1x≤0,…,gmx≤0. | | (5.4) |
Funkcje gi nazywane są ograniczeniami nierównościowymi, zaś cały problem (5.3) zadaniem optymalizacyjnym z ograniczeniami nierównościowymi.
Ustalmy x¯∈W i załóżmy, że funkcje gi są ciągłe. Wówczas ruch wokół x¯ ograniczają lokalnie tylko te warunki, dla których gix¯=0. W przypadku pozostałych, z ciągłości gi wynika, iż istnieje pewne otoczenie x¯, na którym mamy gi<0. Okazuje się, że ta obserwacja będzie pełnić ważną rolę w procesie optymalizacji z ograniczeniami nierównościowymi.
Definicja 5.3
Zbiorem ograniczeń aktywnych w punkcie x¯∈W nazywamy zbiór
Głównym wynikiem tego rozdziału będzie powiązanie własności ograniczeń aktywnych w danym punkcie x¯∈W z lokalną geometrią tego zbioru wokół x¯. W tym celu wprowadźmy następującą definicję.
Definicja 5.4
Niech x¯∈W i gi różniczkowalne w x¯ dla ograniczeń aktywnych i∈Ix¯. Stożkiem kierunków stycznych dla ograniczeń zlinearyzowanych nazywamy zbiór
| Tlinx¯=d∈Rn:∀i∈Ix¯Dgix¯d≤0. | |
Stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest zbiorem wielościennym, a zatem wypukłym i domkniętym.
Dowód
Dowód przebiega bardzo podobnie do dowodu twierdzenia 5.1. Weźmy d∈Tx¯. Wówczas d=limk→∞λkxk-x¯ dla pewnego ciągu punktów xk⊂W zbieżnego do x¯ oraz ciągu liczb dodatnich λk. Ustalmy i∈Ix¯. Z definicji różniczkowalności gi w x¯ mamy
| gixk=gix¯+Dgix¯xk-x¯+oxk-x¯. | |
Ograniczenie i-te jest aktywne w x¯. Zatem gix¯=0. Oczywiście, gixk≤0, ponieważ xk∈W. W połączeniu w powyższym wzorem daje to następujące oszacowanie:
| 0≥gixk-gix¯=Dgix¯xk-x¯+oxk-x¯. | |
Mnożąc obie strony powyższej nierówności przez λk dostajemy
| 0≥Dgix¯λkxk-x¯+λkoxk-x¯. | |
Zrobimy teraz sztuczkę, aby rozwiązać problem oxk-x¯ i przejdziemy z k to nieskończoności:
| 0≥Dgix¯λkxk-x¯︸→d+λkxk-x¯︸→doxk-x¯xk-x¯︸→0. | |
Udowodniliśmy zatem, że Dgix¯d≤0. Analogicznie wynik otrzymujemy dla każdego ograniczenia aktywnego i∈Ix¯. A zatem d∈Tlinx¯.
∎
Przykład 5.3
Rozważmy zbiór W=x∈R2:x12+x22≤1,x2≥0, patrz rysunek 5.3. Zapiszmy go w kanonicznej formie (5.4):
| X=Rn,g1x1,x2=x12+x22,g2x1,x2=-x2. | |
Zbadajmy trzy punktu tego zbioru 12,12, 0,1 i 1,0.
-
x¯=12,12: Ix¯=∅ i Tx¯=Tlin=Rn.
-
x¯=0,1: Ix¯=1, Tx¯=d∈Rn:d2≤0,
| Tlinx¯=d∈R2:Dg10,1d≤0=d∈R2:0,2d≤0=Tx¯. | |
-
x¯=1,0: Ix¯=1,2, Tx¯=d∈Rn:d1≤0,d2≥0,
| Tlinx¯ | =d∈R2:Dg11,0d≤0,Dg21,0d≤0 | |
| | ={d∈R2:[2,0]d≤0,[0,-1]d≤0}=T(x¯). | |
Przykład 5.4
Rozważmy ten sam zbiór W co w powyższym przykładzie, lecz zapiszmy go nieco inaczej:
| W=x∈R2:x12+x22≤1,x23≥0. | |
Zmianie uległo drugie ograniczenie: z x2≥0 na x23≥0. Nowy opis zbioru W odpowiada ograniczeniom g1x1,x2=x12+x22, g2x1,x2=-x23. Rozważmy zbiory Tx¯ i Tlinx¯ w punkcie x¯=0,1. Stożek kierunków stycznych jest identyczny, gdyż zbiór się nie zmienił:
Natomiast stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest następujący:
| Tlinx¯ | =d∈R2:Dg11,0d≤0,Dg21,0d≤0 | |
| | =d∈R2:2,0d≤0,0,0d≤0 | |
| | =d∈R2:d1≤0. | |
Widzimy zatem, że nie zawsze zachodzi równość pomiędzy Tx¯ i Tlinx¯.
5.3. Warunki konieczne Kuhna-Tuckera
W lemacie 5.2 wykazaliśmy, że Tx¯⊂Tlinx¯. Pokazaliśmy w przykładach, że dość często mamy równość tych dwóch zbiorów. Okazuje się, że to bardzo ważna własność, która będzie punktem wyjścia dla całej teorii optymalizacji nieliniowej Kuhna-Tucker'a. Zanim jednak przejdziemy do głównego twierdzenia dowiedziemy pomocniczy, lecz bardzo ważny lemat.
Lemat 5.3 (Farkas (1901))
Niech A będzie macierzą m×n i d∈Rn. Wówczas dokładnie jeden z układów ma rozwiązanie:
| (1)Ax≤0,dTx>0,x∈Rn,(2)ATy=d,y≥0,y∈Rm. | |
Dowód
Pokażemy najpierw, że jeśli układ (2) ma rozwiązanie, to układ (1) go nie ma. Weźmy zatem y spełniające (2). Zatem d=ATy. Wstawiamy to do układu (1) i otrzymujemy
Pierwsza nierówność oznacza, że każda współrzędna wektora Ax jest niedodatnia. Ponieważ współrzędne y są nieujemne, to iloczyn skalarny yTAx jest niedodatni. Przeczy to drugiej nierówności, a zatem dowodzi, że (1) nie ma rozwiązania.
Załóżmy teraz, że układ (2) nie ma rozwiązania. Zdefiniujmy zbiór
| V=x∈Rn:x=ATy dla pewnego y∈Rm, y≥0. | |
Łatwo sprawdzić, że jest to zbiór wypukły i domknięty. Z faktu, że układ (2) nie ma rozwiązania wynika, że d∉V. Zastosujmy więc mocne twierdzenia o oddzielaniu, tw. 3.2 do zbiorów V i U=d. Istnieje więc wektor a∈Rn taki że
Pokażemy, że x¯=a jest rozwiązaniem układu (1). Oznaczmy α=supx∈Vx¯Tx. Ponieważ 0∈V, to α≥0, co pociąga dTx¯>0. Pozostaje tylko udowodnić, że Ax¯≤0. Przypuśćmy, że i-ta współrzędna Ax¯ jest dodatnia. Z definicji zbioru V wynika, że dla dowolnego y≥0 zachodzi α≥x¯TATy=yTAx¯. Zdefiniujmy ciąg yn=0,…,0,n,0,…,0T, gdzie n jest na i-tej współrzędnej. Na mocy założenia o dodatniości Ax¯i dostajemy
| limn→∞ynTAx¯=limn→∞nAx¯i=∞, | |
co przeczy temu, że ynTAx¯≤α. Sprzeczność ta dowodzi, że Ax¯≤0.
∎
Twierdzenie 5.2 (Twierdzenie Kuhna-Tuckera)
Niech x¯ będzie rozwiązaniem lokalnym (5.3). Jeśli funkcje f oraz gi, i∈Ix¯, są różniczkowalne w x¯ oraz Tx¯=Tlinx¯, to istnieje μ∈0,∞m, takie że
| Dfx¯+∑i∈Ix¯μiDgix¯=0T,μigix¯=0,i=1,2,…,m. | | (5.5) |
Często tezę powyższego twierdzenia zapisuje się biorąc sumę po wszystkich i=1,…,m:
| Dfx¯+∑i=1mμiDgix¯=0T,μigix¯=0,i=1,2,…,m. | |
Jest to naginanie notacji, gdyż funkcje opisujące ograniczenia nieaktywne nie muszą być różniczkowalne w punkcie x¯. Z drugiej strony są one mnożone przez zerowe współczynniki μi. Jest to pewne usprawiedliwienie powyższej notacji, którą należy rozumieć tak, jak zapisane zostało w twierdzeniu 5.2.
Dowód twierdzenia 5.2
Na mocy twierdzenia 5.1 mamy Dx¯∩Tx¯=∅. Dalej, korzystając z założenia, dostajemy Dx¯∩Tlinx¯=∅, co innymi słowy oznacza, że nie istnieje rozwiązanie z∈Rn układu
| Dfx¯z<0,Dgix¯z≤0,i∈Ix¯. | |
Stosujemy lemat Farkasa z d=-Dfx¯T i macierzą A złożoną wierszowo z gradientów ograniczeń aktywnych Dgix¯, i∈Ix¯. Istnieje zatem y∈0,∞Ix¯ takie że yTA=-Dfx¯ lub inaczej
Zdefiniujmy μ∈0,∞m następująco: μii∈Ix¯=y i μii∉Ix¯=0. Wówczas powyższa równość jest równoważna następującej
| Dfx¯+∑i∈Ix¯mμiDgix¯=0T. | |
Z definicji μi oczywiste jest, że μigix¯=0.
∎
Uwaga 5.1
Założenia twierdzenia Kuhna-Tuckera są trywialnie spełnione, gdy x¯∈intW, tzn. gdy Ix¯=∅. Wówczas warunki (5.5) sprowadzają się do
Na zakończenie zwróćmy jeszcze raz uwagę na tezę twierdzenia Kuhna-Tuckera. Warunki (5.5) nazywane są warunkami koniecznymi pierwszego rzędu. Wektor μ będzie pojawiał się jeszcze wiele razy na tym wykładzie. Nadajmy mu zatem nazwę:
Definicja 5.5
Wektor μ spełniający (5.5) nazywa się wektorem mnożników Lagrange'a w punkcie x¯.
5.4. Zadania
Ćwiczenie 5.1
Wykaż, że zbiór Tx¯ dla x¯∈clW jest stożkiem.
Ćwiczenie 5.2
Udowodnij, że stożek kierunków stycznych Tx¯ jest zbiorem domkniętym.
Ćwiczenie 5.3
Udowodnij tożsamość (5.2).
Ćwiczenie 5.4
Znajdź stożek kierunków stycznych do zbioru W w punkcie x¯=0, gdy
-
W
=
x
1
,
x
2
∈
R
2
:
x
2
≥
-
x
1
3
,
-
W
=
x
1
,
x
2
∈
R
2
:
x
1
∈
Z
,
x
2
=
0
,
-
W
=
x
1
,
x
2
∈
R
2
:
x
1
∈
Q
,
x
2
=
0
.
Ćwiczenie 5.5
Udowodnić, że dla zadania
| fx→min,gix≤0,i=1,…,m,xi≥0,i=1,…,n, | |
warunek konieczny pierwszego rzędu przyjmuje postać:
| Dfx+∑i∈IxμiDgix≥0T,Dfx+∑i∈IxμiDgixx=0,μigix=0,i=1,…,m,μi≥0,i=1,…,m. | |
Nierówność dla wektorów oznacza nierówność po współrzędnych.
Rys. 5.2. Stożek kierunków stycznych i stożek kierunków spadku w punkcie
