Przykład 8.1
Rozważmy następujący problem optymalizacyjny:
dla pewnego a∈Rn i b∈R. Ograniczenie równościowe możemy zamienić na dwa ograniczenia nierównościowe:
| fx→min,aTx+b≤0,-aTx-b≤0,x∈Rn. | |
Ograniczenia są afiniczne, czyli w każdym punkcie spełniony jest warunek afiniczności. Jeśli x¯ jest rozwiązaniem lokalnym, to istnieje wektor mnożników Lagrange'a μ=μ1,μ2T i spełnione są warunki Kuhna-Tuckera (5.5):
| Dfx¯+μ1aT+μ2-aT=0T,μ1aTx+b=0,μ2-aTx-b=0,μ1,μ2≥0. | |
Punkt x¯ jest dopuszczalny (jako że jest rozwiązaniem), czyli spełnia ograniczenia: aTx+b=0. Stąd trywialnie spełnione są druga i trzecia równość. Możemy zatem powyższe warunki równoważnie zapisać jako:
| Dfx¯+μ1-μ2aT=0T,μ1,μ2≥0. | |
Oznaczmy λ=μ1-μ2. Warunki nieujemności μ1,μ2 implikują, że λ∈R. Dostajemy więc finalnie:
Jest to warunek Kuhna-Tuckera dla ograniczeń równościowych.
8.1. Warunek konieczny pierwszego rzędu
Teoria wprowadzana w tym podrozdziale jest prostym rozszerzeniem tego, co już zrobiliśmy dla problemu optymalizacyjnego z ograniczeniami nierównościowymi. Rozpoczniemy od rozszerzenia Tlin:
Definicja 8.1
Niech x¯∈W, gi różniczkowalne w x¯ dla ograniczeń aktywnych i∈Ix¯ oraz hj są różniczkowalne w x¯ dla j=1,…,l. Stożkiem kierunków stycznych dla ograniczeń zlinearyzowanych nazywamy zbiór
| Tlinx¯=d∈Rn:∀i∈Ix¯Dgix¯d≤0,∀j=1,…,lDhjx¯d=0. | |
Podobnie jak poprzednio zauważmy, że stożek kierunków stycznych dla ograniczeń zlinearyzowanych jest zbiorem wielościennym, a zatem wypukłym i domkniętym. Jeśli jest choć jedno ograniczenie równościowe, to ma on puste wnętrze.
Warunek konieczny istnienia rozwiązania lokalnego problemu z ograniczeniami mieszanymi jest sformułowany poniżej. Identycznie jak w twierdzeniu 5.2 zakładamy równość stożka kierunków stycznych dla ograniczeń oryginalnych i zlinearyzowanych. Później uogólnimy warunki regularności, które będą taką równość pociągały.
Twierdzenie 8.1 (Twierdzenia Kuhna-Tuckera)
Niech x¯ będzie rozwiązaniem lokalnym (8.1). Jeśli funkcje f, gi, i∈Ix¯, oraz hj, j=1,…,l, są różniczkowalne w x¯ oraz Tx¯=Tlinx¯, to istnieją μ∈0,∞m oraz λ∈Rl takie że
| Dfx¯+∑i∈Ix¯μiDgix¯+∑j=1lλjDhjx¯=0T,μigix¯=0,i=1,2,…,m. | | (8.3) |
Dowód
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¯.Dhjx¯z≤0,j=1,…,l,-Dhjx¯z≤0,j=1,…,l. | | (8.4) |
Stosujemy lemat Farkasa, lemat 5.3, z d=-Dfx¯ i macierzą A następującej postaci:
| A=Dhjx¯,j=1,…,l-Dhjx¯,j=1,…,lDgix¯,i∈Ix¯ | |
Istnieje zatem y∈0,∞Ix¯+2l takie że yTA=-Dfx¯ lub inaczej
Zdefiniujmy λj=yj-yl+j, j=1,…,l. Przypiszmy współrzędnym μ odpowiadającym ograniczeniom aktywnym, i∈Ix¯, ostatnie Ix¯ wartości wektora y. Na pozostałych współrzędnych połóżmy zera. Wówczas równość (8.5) jest równoważna następującej
| Dfx¯+∑i∈Ix¯mμiDgix¯+∑j=1lλjDhjx¯=0T. | |
Z definicji μi oczywiste jest, że μigix¯=0.
∎
8.2. Warunki regularności
Sformułujemy teraz trzy warunki dostateczne równości Tx¯=Tlinx¯, zwane warunkami regularności.
Definicja 8.2
W punkcie x¯∈W spełniony jest:
-
warunek liniowej niezależności, jeśli funkcje gi, i∉Ix¯, są ciągłe w x¯, pozostałe ograniczenia nierównościowe i wszystkie równościowe są klasy C1 na otoczeniu x¯ oraz wektory Dgix¯ dla i∈Ix¯ i Dhjx¯ dla j=1,…,l są liniowo niezależne,
-
warunek afiniczności, jeśli funkcje gi, i∈Ix¯, oraz hj, j=1,…,l, są afiniczne,
-
warunek Slatera, jeśli
-
funkcje gi, i∈Ix¯ są pseudowypukłe w x¯, funkcje gi, i∉Ix¯, są ciągłe w x¯,
-
funkcje hj, j=1,…,l, są afiniczne,
-
istnieje x∈X, dla którego gix<0 dla i∈Ix¯ oraz hjx=0 dla j=1,…,l.
Zaczniemy od najprostszego przypadku.
Twierdzenie 8.2
Jeśli w punkcie x¯∈W spełniony jest warunek afiniczności, to zachodzi równość Tx¯=Tlinx¯.
Dowód
Postępując jak w przykładzie 8.1 zamieniamy ograniczenia afiniczne równościowe na ograniczenia afiniczne nierównościowe. Teza wynika z twierdzenia 6.1.
∎
Twierdzenie 8.3
Jeśli w punkcie x¯∈W spełniony jest warunek Slatera, to zachodzi równość Tx¯=Tlinx¯.
Dowód
Zapiszmy najpierw funkcje hj dla j=1,…,l:
| hjy=ajTy+bj,aj∈Rn,bj∈R. | |
Wprowadźmy uogólnienie zbioru Tintx¯ do przypadku ograniczeń mieszanych:
| Tintx¯=d∈Rn:∀i∈Ix¯Dgix¯d<0,∀j=1,…,lDhjx¯d=0. | |
(1) Tintx¯≠∅. Weźmy punkt x z warunku Slatera. Na mocy pseudowypukłości, patrz uwaga 4.3, mamy
| Dgix¯x-x¯<0,∀i∈Ix¯. | |
Dla każdego j mamy także
| ajTx-x¯=ajTx+bj-ajTx¯-bj=hjx-hjx¯=0. | |
Wnioskujemy więc, że wektor x-x¯∈Tintx¯.
(2) Tintx¯⊂Tx¯. W tym celu weźmy dowolny d∈Tintx¯. Wystarczy pokazać, że pewien odcinek o końcu x¯ i kierunku d zawiera się w całości w zbiorze W. Rozważmy w tym celu funkcję yλ=x+λd. Na mocy ciągłości funkcji opisujących ograniczenia nieaktywne istnieje ε>0 taki że giyλ≤0 dla λ∈0,ε oraz i∉Ix¯. Z faktu, że d∈Tintx¯ dostajemy również, że hjyλ=0 dla j=1,…,l i dowolnego λ. Pozostaje tylko zająć się ograniczeniami aktywnymi. Z faktu, że gi są różniczkowalne w x¯ dla i∈Ix¯ mamy
| limλ↓0giyλ-gix¯λ=Dgix¯d<0, | |
gdzie ostatnia nierówność wynika z tego, że d∈Tintx¯. A zatem giyλ-gix¯<0 dla dostatecznie małych λ.
(3) clTintx¯=Tlinx¯. Zbiory Tintx¯ i Tlinx¯ leżą na hiperpłaszczyźnie H wyznaczonej przez afiniczne ograniczenia liniowe. Możemy zatem znaleźć przekształcenie liniowe P o pełnym rzędzie przekształcające tą hiperpłaszczyznę w przestrzeń Rn′, gdzie n′ jest wymiarem rzeczonej hiperpłaszczyzny (jeśli funkcje hj są parami różne, to n′=n-l). Przekształcenie to jest wzajemnie jednoznaczne rozpatrywane jako funkcja określona na H. A zatem topologie w Rn′ i na H są identyczne. Wystarczy więc udowodnić tezę tego podpunktu na obrazach Tint′x¯ i Tlin′x¯ zbiorów Tintx¯ i Tlinx¯. Zauważmy, że zbiór Tint′x¯ jest otwarty. Wykazaliśmy, że jest niepusty. Jest również wnętrzem zbioru Tlin′x¯. Na mocy lematu 6.1 mamy clTint′x¯=Tlin′x¯.
(4) Tx¯⊂Tlinx¯. Identycznie jak dowód lematu 5.2.
Pozostaje już tylko przypomnieć, że Tx¯ jest zbiorem domkniętym. A zatem
| clTintx¯⊂Tx¯⊂Tlin=clTintx¯. | |
∎
Zanim przejdziemy do rozważań nad trzecim warunkiem regularności, warunkiem liniowej niezależności, przypomnijmy twierdzenie o funkcji uwikłanej, by, korzystając z niego, podać opis stożka kierunków stycznych do powierzchni zadanej przez ograniczenia równościowe.
Twierdzenie 8.4 (Twierdzenie o funkcji uwikłanej)
Niech f:X→Rn, gdzie X⊂Rn+m otwarty, będzie odwzorowaniem klasy Ck. Załóżmy, że fa,b=0, gdzie a,b∈X. Przyjmujemy tutaj notację, że a∈Rn, zaś b∈Rm. Oznaczmy przez Ax macierz pochodnych cząstkowych, w punkcie a,b, względem pierwszych n zmiennych: Ax∈Rn×n zadana jest wzorem Axij=∂fi∂uja,b.
Jeśli macierz Ax jest odwracalna, to istnieje zbiór otwarty W⊂Rm zawierający b oraz funkcja g:W→Rn klasy Ck, taka że gy,y∈X dla y∈W, gb=a oraz fgy,y=0 dla y∈W. Ponadto, Dgb=-Ax-1Ay, gdzie Ay jest pochodną f w punkcie a,b względem ostatnich m zmiennych: Ay∈Rn×m zadana jest wzorem Ayij=∂fi∂un+ja,b.
Rozważmy powierzchnię opisaną przez układ m* równań:
gdzie X⊂Rn otwarty. Przez TSx¯ oznaczmy stożek kierunków stycznych do S punkcie x¯∈S.
Twierdzenie 8.5
Załóżmy, że funkcje ci, i=1,…,m*, są klasy Ck, k≥1, na otoczeniu x¯ oraz gradienty Dcix¯, i=1,…,m*, są liniowo niezależne. Wówczas
| TSx¯=TlinSx¯:=d∈Rn:Dcix¯d=0,i=1,…,m*. | |
Ponadto, dla każdego d∈TSx¯ istnieje ε>0 i krzywa y:-ε,ε→S klasy Ck o tej własności, że y0=x¯ oraz y′0=d.
Dowód
Pokażemy najpierw, że TSx¯⊂TlinSx¯. Niech d∈TSx¯. Wówczas d=limk→∞λkxk-x¯ dla xk⊂S, xk≠x. Z definicji pochodnej dostajemy dla każdego i=1,…,m*:
| cixk︸=0=cix¯︸=0+Dcix¯λnxk-x¯︸→d+λkxk-x¯︸→doxk-x¯xk-x¯︸→0, | |
czyli Dcix¯d=0. Stąd wynika, że d∈TlinSx¯.
Pozostało jeszcze zawieranie w drugą stronę. Dowód tej części będzie zdecydowanie trudniejszy. Ustalmy d∈TlinSx¯. Skonstruujemy krzywą przechodzącą przez x¯ i zawartą w S, której pochodna w punkcie x¯ jest równa d. Oznaczmy cx=c1x,…,cm*x i zdefiniujmy funkcję Φ:Rm*×R→Rm* wzorem
| Φu,t=cx¯+td+Dcx¯Tu. | |
Zauważmy, że Φ0,0=0. Oznaczmy przez DuΦ macierz pochodnych cząstkowych względem zmiennych wektora u: DuΦ=∂Φi∂uji,j=1m*. W 0,0 mamy DuΦ0,0=Dcx¯Dcx¯T. Przypomnijmy, że zgodnie z założeniem macierz Dcx¯ ma maksymalny rząd (równy m*), czyli DuΦ0,0 jest odwracalna. Na mocy twierdzenia o funkcji uwikłanej istnieje zatem ε>0 oraz funkcja u:-ε,ε→Rm* klasy Ck, taka że Φut,t=0. Połóżmy
Krzywa ta, zgodnie z konstrukcją, leży na powierzchni S, tzn. cyt=0 dla t∈-ε,ε oraz y0=x¯. Różniczkując złożenie cyt dostajemy
| ddtcyt=Dcytd+Dcx¯Tu′t. | |
czyli w t=0 mamy
| ddtcytt=0=Dcx¯d+Dcx¯Tu′0. | |
Z drugiej strony wiemy, że cyt=0, czyli powyższa pochodna jest równa zero: Dcx¯d+Dcx¯Tu′0=0. Przypomnijmy, że d∈TlinSx¯, co w naszym zapisie oznacza Dcx¯d=0. Wynika stąd, że Dcx¯Dcx¯Tu′0=0. Korzystając z faktu, że Dcx¯ ma rząd m* dostajemy u′0=0. Jesteśmy już teraz gotowi, aby dokończyć dowód. Różniczkując funkcję y dostajemy
co w t=0 daje y′0=d. Możemy stąd już łatwo wywnioskować, że d∈TSx¯.
∎
Uwaga 8.1
Powyższe twierdzenie dowodzi powszechnie znanego faktu dotyczącego przestrzeni stycznej do rozmaitości. Otóż, z założeń wynika, że S jest lokalnie wokół punktu x¯ rozmaitością różniczkową klasy Ck. Przestrzeń styczna do rozmaitości w punkcie x¯ definiowana jest jako zbiór wektorów, które są pochodnymi (w punkcie x¯) krzywych leżących na tej rozmaitości i przechodzących przez x¯ (jest to równoważne definicji Tx¯). Równość Tlinx¯=Tx¯ oznacza, że przestrzeń styczna jest jądrem przekształcenia liniowego Dcx¯.
Z powyższego twierdzenia będziemy wielokrotnie korzystać w następnych rozdziałach. Będzie ono głównym narzędziem przy dowodzeniu warunku koniecznego drugiego rzędu. W tym rozdziale pozwoli łatwo wykazać równość Tx¯=Tlinx¯ przy założeniu warunku liniowej niezależności.
Twierdzenie 8.6
Jeśli w punkcie x¯∈W spełniony jest warunek liniowej niezależności, to zachodzi równość Tx¯=Tlinx¯.
Dowód
Ustalmy d∈Tlinx¯. Niech I⌃x¯=i∈Ix¯:Dgix¯d=0. Na mocy twierdzenia 8.5 istnieje krzywa y:-ε,ε→Rn, taka że y0=x¯, y′0=d oraz giyt=0, i∈I⌃x¯, i hjyt=0, j=1,…,l. Ustalmy i∈Ix¯∖I⌃x¯. Połóżmy g⌃it=giyt, t∈-ε,ε. Wówczas g⌃i′0=Dgix¯d<0, czyli istnieje εi>0, takie że g⌃it<0 dla t∈0,εi. Z ciągłości, giyt<0 na pewnym otoczeniu 0 dla i∉Ix¯. Podsumowując, istnieje ε¯>0, takie że yt∈W dla t∈0,ε¯. Stąd trywialnie d∈Tx¯.
Dowód zawierania Tx¯⊂Tlinx¯ jest identyczny do dowodu lematu 5.2.
∎
Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.
