6.1. Warunki regularności
Sformułujemy teraz trzy warunki dostateczne równości Tx¯=Tlinx¯, zwane warunkami regularności. Dowody dostateczności podamy w kolejnych twierdzeniach.
Definicja 6.1
W punkcie x¯∈W spełniony jest:
-
warunek liniowej niezależności, jeśli funkcje gi, i∉Ix¯, są ciągłe w x¯ oraz wektory Dgix¯, dla i∈Ix¯, są liniowo niezależne,
-
warunek afiniczności, jeśli funkcje gi, i∈Ix¯, są afiniczne oraz funkcje gi, i∉Ix¯, są ciągłe w x¯,
-
warunek Slatera, jeśli funkcje gi, i∈Ix¯ są pseudowypukłe w x¯, funkcje gi, i∉Ix¯, są ciągłe w x¯ oraz istnieje x∈X, dla którego gix<0 dla i∈Ix¯.
Zauważmy, że w warunku Slatera nie wymagamy, aby punkt x spełniał warunki ograniczeń nieaktywnych, tzn. x nie musi być w zbiorze W.
Twierdzenie 6.1
Jeśli w punkcie x¯∈W spełniony jest warunek afiniczności, to Tx¯=Tlinx¯.
Dowód
Zawieranie Tx¯⊂Tlinx¯ wynika z lematu 5.2. Wystarczy zatem wykazać zawieranie w drugą stronę.
Niech d∈Tlinx¯. Udowodnimy, że istnieje λ*>0, taka że cały odcinek x¯+λd, λ∈0,λ*, zawarty jest w W:
Zauważmy, że gix¯<0 dla i∉Ix¯. Z ciągłości tych funkcji w x¯ wynika, że istnieje λ*>0, dla której gix¯+λd≤0, i∉Ix¯, λ∈0,λ*. Pozostaje jeszcze wykazać, że nierówność taka zachodzi dla ograniczeń aktywnych. Ustalmy i∈Ix¯. Z definicji d wiemy, że Dgix¯d≤0. Ograniczenie gi jest afiniczne, czyli postaci gix=aiTx+bi, gdzie ai∈Rn, bi∈R. Zatem Dgix¯d=aiTd. Z faktu, że gi jest aktywne w x¯ dostajemy również 0=gix¯=aiTx¯+bi. Stąd dla dowolnego λ≥0 mamy
| 0≥λaiTd=λaiTd+aiTx¯+bi︸0=aiTx¯+λd+bi=gix¯+λd. | |
Dowodzi to (6.1).
Pozostaje już tylko skonstruować ciąg xk⊂W, xk→x¯ i λk⊂0,∞. Kładziemy
Wówczas xk∈W, xk→x oraz λkxk-x=d, czyli trywialnie
a zatem d∈Tx¯.
∎
Przed przystąpieniem do dowodu analogicznych twierdzeń dla pozostałych warunków regularności sformułujemy pomocniczy lemat.
Wprowadźmy zbiór
| Tintx¯=d∈Rn:∀i∈Ix¯Dgix¯d<0. | |
Uwaga 6.1
Zauważmy, że jeśli w punkcie x¯∈W funkcje gi, i∈Ix¯, są różniczkowalne w x¯, zaś funkcje gi, i∉Ix¯ są ciągłe w x¯, to d∈Tintx¯ oznacza, że x¯+λd∈intW dla dostatecznie małych λ>0.
Lemat 6.1
Niech x¯∈W oraz funkcje gi, i∈Ix¯, są różniczkowalne w x¯, zaś funkcje gi, i∉Ix¯ są ciągłe w x¯.
Wówczas
-
-
II) Jeśli Tintx¯≠∅, to clTintx¯=Tlinx¯.
Dowód
Dowód (I) zostawiamy jako ćwiczenie. Do dowodu (II) zauważmy, że Tintx¯ jest wnętrzem zbioru Tlinx¯. Ponadto Tlinx¯ jest zbiorem wielościennym, a zatem wypukłym (patrz lemat 4.5). Zastosowanie lematu 3.2 kończy dowód.
∎
Twierdzenie 6.2
Jeśli w punkcie x¯∈W spełniony jest warunek Slatera, to Tx¯=Tlinx¯.
Dowód
Pokażemy najpierw, że Tintx¯≠∅. Niech x∈X taki że gix<0 dla i∈Ix¯. Z pseudowypukłości gi w punkcie x¯ dostajemy Dgix¯x-x¯<0 dla i∈Ix¯, czyli x-x¯∈Tintx¯.
Na mocy lematu 6.1 mamy Tlinx¯=clTintx¯. Udowodniliśmy także, że Tintx¯⊂Tx¯⊂Tlinx¯ oraz, że Tx¯ jest domknięty. A zatem Tlinx¯=Tx¯.
∎
Dowód analogicznego twierdzenia dla warunku liniowej niezależności wymaga pomocniczego lematu w stylu lematu Farkasa. Wynik ten jest jednak wcześniejszy i został uzyskany przez Paul'a Gordana w 1873 roku.
Lemat 6.2 (Gordan, 1873)
Niech A będzie macierzą m×n. Wówczas dokładnie jeden z układów ma rozwiązanie:
| (1)Ax<0,x∈Rn,(2)ATy=0,y≥0,y≠0y∈Rm. | |
Dowód
Dowód rozpoczniemy od uzasadnienia, że oba te układy nie mogą mieć rozwiązania jednocześnie. Załóżmy więc przez sprzeczność, że istnieją x,y spełniające (1)-(2). Z faktu, że y rozwiązuje (2), dostajemy, że yTAx=0. Z drugiej strony x rozwiązuje (1), czyli Axi<0 dla każdego i=1,…,n. Pamiętając, że yj≥0, j=1,…,m, i y≠0 mamy yTAx<0. Dostaliśmy więc sprzeczność, co dowodzi, że nie może istnieć jednocześnie rozwiązanie (1) i (2).
Następnym krokiem dowodu będzie wykazanie, że zawsze któryś z układów ma rozwiązanie. W tym celu udowodnimy, że jeśli układ (1) nie ma rozwiązania, to układ (2) ma rozwiązanie. W tym celu zdefiniujmy następujące zbiory wypukłe:
| U=-∞,0m,V=z∈Rm:z=Ax dla pewnego x∈Rn. | |
Z faktu, że układ (1) nie ma rozwiązania, wynika, iż zbiory te są rozłączne. Słabe twierdzenie o oddzielaniu implikuje istnienie wektora a∈Rm, a≠0, takiego że
Wykażemy, że a≥0. Przypuśćmy przeciwnie, że istnieje współrzędna ai<0. Rozważmy ciąg zn=-1n,-1n,…,-n,…,-1nT, gdzie -n jest na i-tej pozycji. Wówczas zn∈U oraz limn→∞aTzn=∞, a zatem dostaliśmy sprzeczność, gdyż supz∈UaTz jest skończone.
Wiemy zatem, że wektor a ma wszystkie współrzędne nieujemne. Pociąga to supz∈UaTz=0. Weźmy z=A-ATa. Wówczas z∈V, czyli aTz≥0. A zatem
| 0≤aTz=aTA-ATa=-ATa2, | |
co implikuje, że ATa=0, czyli ATa=0. Rozwiązaniem układu (2) jest zatem y=a.
∎
Twierdzenie 6.3
Jeśli w punkcie x¯∈W spełniony jest warunek liniowej niezależności, to Tx¯=Tlinx¯.
Dowód
Identycznie jak w dowodzie tw. 6.2 wystarczy pokazać, że Tintx¯≠∅. Niech A będzie macierzą składającą się z gradientów Dgix¯ ograniczeń aktywnych (jako rzędów). Na mocy liniowej niezależności nie istnieje wektor μ∈RIx¯, μ≠0, o tej własności, że ATμ=0. Nie istnieje więc rozwiązanie układu (2) w lemacie 6.2. A zatem ma rozwiązanie układ (1), czyli istnieje d∈Rn, takie że Ad<0:
Stąd d∈Tintx¯.
∎
6.2. Przykłady
Przykład 6.1
Rozważmy problem optymalizacji na zbiorze:
| W=x∈R2:x12+x22≤1,x1+2x2≤1,x1-3x2≤1. | |
Zbiór X=R2. Ograniczenia są opisane przez trójkę funkcji
| g1x1,x2=x12+x22-1,g2x1,x2=x1+2x2-1,g3x1,x2=x1-3x2-1. | |
W punkcie x¯=1,0T wszystkie ograniczenia są aktywne i mamy
| Dg1x¯=2,0,Dg2x¯=1,2,Dg3x¯=1,-3. | |
Warunek liniowej niezależności ograniczeń nie jest spełniony w x¯. Ograniczenia aktywne nie są również afiniczne. Pozostaje zatem sprawdzić warunek Slatera. Wszystkie funkcje ograniczeń są wypukłe, a więc także pseudowypukłe. W punkcie x=0,0T mamy gix=-1<0 dla i=1,2,3. Zachodzi więc warunek Slatera.
Przykład 6.2 (Kuhn, Tucker (1951))
Rozważmy zadanie optymalizacyjne:
Zbiór punktów dopuszczalnych W naszkicowany jest na rysunku 6.1. Zapiszmy funkcje opisujące ograniczenia:
| g1x1,x2=-x13+x2,g2x1,x2=-x2. | |
Zauważmy, że w każdym punkcie dopuszczalnym, poza 0,0T, spełniony jest warunek liniowej niezależności. Widać jednak, że rozwiązaniem powyższego problemu optymalizacyjnego jest x¯=0,0T. Niestety w tym punkcie Tx¯≠Tlinx¯:
| Tx¯=d∈R2:d1≥0,d2=0,Tlinx¯=d∈R2:d2=0. | |
Przykład 6.3
Niech A będzie macierzą symetryczną n×n. Rozważmy zadanie optymalizacyjne:
Zapiszmy najpierw problem optymalizacyjny w kanonicznej formie. Zauważmy przy tym, że warunek x≤1 jest równoważny x2=xTx≤1.
| -xTAx→min,xTx-1≤0,x∈Rn. | |
Oznaczmy przez W zbiór punktów dopuszczalnych. Zauważmy, że w każdym punkcie dopuszczalnym spełnione są warunki liniowej niezależności i Slatera. Wynika stąd, że rozwiązanie powyższego zadania spełnia warunki konieczne pierwszego rzędu (warunki Kuhna-Tuckera (5.5)). Znajdziemy teraz wszystkie punkty ,,podejrzane”.
Warunki Kuhna-Tuckera mają następującą postać:
| -2xTA+2μxT=0T,μxTx-1=0,μ≥0,x∈Rn. | |
Przypadek xTx-1<0. Wówczas μ=0 (z powodu drugiego równania) i pierwsze równanie przyjmuje postać xTA=0T, którą poprzez transponowanie obu stron sprowadzamy do
Równanie to spełnione jest przez wszystkie x∈kerA, x<1. W szczególności ma ono co najmniej jedno rozwiązanie (x=0).
Przypadek xTx-1=0. Teraz nic nie możemy powiedzieć o μ. Może być zerowe lub dodatnie. Pierwsze równanie przyjmuje jednak postać
μxT=xTA, które po stransponowaniu wygląda następująco:
Rozwiązaniami są zatem wektory własne (x) odpowiadające nieujemnym wartościom własnym (μ). Zbiór rozwiązań może być pusty, jeśli wszystkie wartości własne są ujemne.
Podsumowując, zbiór punktów podejrzanych, czyli punktów, w których spełniony jest warunek konieczny pierwszego rzędu, ma postać:
| x∈kerA:x<1∪x∈R2:x=1 oraz x jest wektorem własnym A dla nieujemnej wartości własnej. | |
Na obecnym etapie nie mamy żadnej techniki pozwalającej na znalezienie rozwiązania. Możemy tylko posłużyć się zdrowym rozsądkiem. Otóż, jeśli x∈kerA, to wartość funkcji celu xTAx jest zerowa. Dla dowolnego elementu drugiego zbioru, wartość funkcji celu jest równa wartości własnej. Możemy zatem wyciągnąć następujący wniosek: jeśli maksymalna wartość własna jest dodatnia, to każdy wektor jej odpowiadający jest rozwiązaniem globalnym. Jeśli macierz A nie ma wartości własnych większych od zera, to rozwiązaniem jest dowolny punkt z jądra A o normie nie większej niż 1.
6.3. Zadania
Ćwiczenie 6.1
Uzasadnij prawdziwość stwierdzenia umieszczonego w uwadze 6.1, by później udowodnić, że Tintx¯⊂Tx¯, gdzie Tintx¯ zdefiniowane jest w lemacie 6.1.
Ćwiczenie 6.2
Przez ”punkty podejrzane” problemu optymalizacyjnego rozumiemy takie punkty dopuszczalne, w których nie są spełnione warunki regularności albo spełnione są warunki konieczne pierwszego rzędu. Znajdź wszystkie punkty podejrzane dla następującego problemu optymalizacyjnego:
| x2-6x+y2+2y→min,x+2y-10=0,25-x2-y2≥0. | |
Czy w którymś z nich jest rozwiązanie? Jeśli tak, to w którym? Odpowiedź uzasadnij.
Ćwiczenie 6.3
Znajdź zbiór rozwiązań problemu optymalizacyjnego
| ∑i=1ncixi2→min,∑i=1nxi=b, | |
gdzie b,ci>0. Uzasadnij, że są to wszystkie rozwiązania.
Ćwiczenie 6.4
Znajdź rozwiązania globalne problemu optymalizacyjnego
| x12+3x22-x1→min,x12-x2≤1,x1+x2≥1. | |
Ćwiczenie 6.5
Znajdź minima i maksima globalne funkcji
| fx1,x2=4x12+2x22-6x1x2+x1 | |
na zbiorze
| W=x1,x2∈R2:-2x1+2x2≥1, 2x1-x2≤0,x1≤0,x2≥0. | |
