Zagadnienia

6. Warunki regularności i przykłady

W tym rozdziale podamy warunki dostateczne równości stożka kierunków stycznych T⁢x¯ i stożka kierunków stycznych dla ograniczeń zlinearyzowanych Tl⁢i⁢n⁢x¯. Przypomnijmy, że jest to główne założenie twierdzenia Kuhna-Tuckera, tw. 5.2, opisującego warunek konieczny pierwszego rzędu dla lokalnego rozwiązania problemu optymalizacyjnego z ograniczeniami nierównościowymi (5.3).

6.1. Warunki regularności

Sformułujemy teraz trzy warunki dostateczne równości T⁢x¯=Tl⁢i⁢n⁢x¯, 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∉I⁢x¯, są ciągłe w x¯ oraz wektory D⁢gi⁢x¯, dla i∈I⁢x¯, są liniowo niezależne,

  • warunek afiniczności, jeśli funkcje gi, i∈I⁢x¯, są afiniczne oraz funkcje gi, i∉I⁢x¯, są ciągłe w x¯,

  • warunek Slatera, jeśli funkcje gi, i∈I⁢x¯ są pseudowypukłe w x¯, funkcje gi, i∉I⁢x¯, są ciągłe w x¯ oraz istnieje x∈X, dla którego gi⁢x<0 dla i∈I⁢x¯.

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 T⁢x¯=Tl⁢i⁢n⁢x¯.

Dowód

Zawieranie T⁢x¯⊂Tl⁢i⁢n⁢x¯ wynika z lematu 5.2. Wystarczy zatem wykazać zawieranie w drugą stronę.

Niech d∈Tl⁢i⁢n⁢x¯. Udowodnimy, że istnieje λ*>0, taka że cały odcinek x¯+λ⁢d, λ∈0,λ*, zawarty jest w W:

x¯+λ⁢d:λ∈0,λ*⊂W.(6.1)

Zauważmy, że gi⁢x¯<0 dla i∉I⁢x¯. Z ciągłości tych funkcji w x¯ wynika, że istnieje λ*>0, dla której gi⁢x¯+λ⁢d≤0, i∉I⁢x¯, λ∈0,λ*. Pozostaje jeszcze wykazać, że nierówność taka zachodzi dla ograniczeń aktywnych. Ustalmy i∈I⁢x¯. Z definicji d wiemy, że D⁢gi⁢x¯⁢d≤0. Ograniczenie gi jest afiniczne, czyli postaci gi⁢x=aiT⁢x+bi, gdzie ai∈Rn, bi∈R. Zatem D⁢gi⁢x¯⁢d=aiT⁢d. Z faktu, że gi jest aktywne w x¯ dostajemy również 0=gi⁢x¯=aiT⁢x¯+bi. Stąd dla dowolnego λ≥0 mamy

0≥λ⁢aiT⁢d=λ⁢aiT⁢d+aiT⁢x¯+bi︸0=aiT⁢x¯+λ⁢d+bi=gi⁢x¯+λ⁢d.

Dowodzi to (6.1).

Pozostaje już tylko skonstruować ciąg xk⊂W, xk→x¯ i λk⊂0,∞. Kładziemy

xk=x¯+λ*k⁢d,⁢λk=kλ*.

Wówczas xk∈W, xk→x oraz λk⁢xk-x=d, czyli trywialnie

limk→∞⁡λk⁢xk-x¯=d,

a zatem d∈T⁢x¯.

∎

Przed przystąpieniem do dowodu analogicznych twierdzeń dla pozostałych warunków regularności sformułujemy pomocniczy lemat. Wprowadźmy zbiór

Ti⁢n⁢t⁢x¯=d∈Rn:⁢∀⁢i∈I⁢x¯⁢⁢D⁢gi⁢x¯⁢d<0.
Uwaga 6.1

Zauważmy, że jeśli w punkcie x¯∈W funkcje gi, i∈I⁢x¯, są różniczkowalne w x¯, zaś funkcje gi, i∉I⁢x¯ są ciągłe w x¯, to d∈Ti⁢n⁢t⁢x¯ oznacza, że x¯+λ⁢d∈intW dla dostatecznie małych λ>0.

Lemat 6.1

Niech x¯∈W oraz funkcje gi, i∈I⁢x¯, są różniczkowalne w x¯, zaś funkcje gi, i∉I⁢x¯ są ciągłe w x¯. Wówczas

  • I) Ti⁢n⁢t⁢x¯⊂T⁢x¯,

  • II) Jeśli Ti⁢n⁢t⁢x¯≠∅, to clTi⁢n⁢t⁢x¯=Tl⁢i⁢n⁢x¯.

Dowód

Dowód (I) zostawiamy jako ćwiczenie. Do dowodu (II) zauważmy, że Ti⁢n⁢t⁢x¯ jest wnętrzem zbioru Tl⁢i⁢n⁢x¯. Ponadto Tl⁢i⁢n⁢x¯ 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 T⁢x¯=Tl⁢i⁢n⁢x¯.

Dowód

Pokażemy najpierw, że Ti⁢n⁢t⁢x¯≠∅. Niech x∈X taki że gi⁢x<0 dla i∈I⁢x¯. Z pseudowypukłości gi w punkcie x¯ dostajemy D⁢gi⁢x¯⁢x-x¯<0 dla i∈I⁢x¯, czyli x-x¯∈Ti⁢n⁢t⁢x¯.

Na mocy lematu 6.1 mamy Tl⁢i⁢n⁢x¯=clTi⁢n⁢t⁢x¯. Udowodniliśmy także, że Ti⁢n⁢t⁢x¯⊂T⁢x¯⊂Tl⁢i⁢n⁢x¯ oraz, że T⁢x¯ jest domknięty. A zatem Tl⁢i⁢n⁢x¯=T⁢x¯.

∎

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)⁢⁢A⁢x<0,x∈Rn,⁢⁢(2)⁢⁢AT⁢y=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 yT⁢A⁢x=0. Z drugiej strony x rozwiązuje (1), czyli A⁢xi<0 dla każdego i=1,…,n. Pamiętając, że yj≥0, j=1,…,m, i y≠0 mamy yT⁢A⁢x<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=A⁢x⁢ 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

supz∈U⁡aT⁢z≤infz∈V⁡aT⁢z.

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→∞⁡aT⁢zn=∞, a zatem dostaliśmy sprzeczność, gdyż supz∈U⁡aT⁢z jest skończone.

Wiemy zatem, że wektor a ma wszystkie współrzędne nieujemne. Pociąga to supz∈U⁡aT⁢z=0. Weźmy z=A⁢-AT⁢a. Wówczas z∈V, czyli aT⁢z≥0. A zatem

0≤aT⁢z=aT⁢A⁢-AT⁢a=-AT⁢a2,

co implikuje, że AT⁢a=0, czyli AT⁢a=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 T⁢x¯=Tl⁢i⁢n⁢x¯.

Dowód

Identycznie jak w dowodzie tw. 6.2 wystarczy pokazać, że Ti⁢n⁢t⁢x¯≠∅. Niech A będzie macierzą składającą się z gradientów D⁢gi⁢x¯ ograniczeń aktywnych (jako rzędów). Na mocy liniowej niezależności nie istnieje wektor μ∈RI⁢x¯, μ≠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 A⁢d<0:

D⁢gi⁢x¯⁢d<0,⁢∀⁢i∈I⁢x¯.

Stąd d∈Ti⁢n⁢t⁢x¯.

∎

6.2. Przykłady

Przykład 6.1

Rozważmy problem optymalizacji na zbiorze:

W=x∈R2:⁢x12+x22≤1,⁢x1+2⁢x2≤1,⁢x1-3⁢x2≤1.

Zbiór X=R2. Ograniczenia są opisane przez trójkę funkcji

g1⁢x1,x2=x12+x22-1,⁢g2⁢x1,x2=x1+2⁢x2-1,⁢g3⁢x1,x2=x1-3⁢x2-1.

W punkcie x¯=1,0T wszystkie ograniczenia są aktywne i mamy

D⁢g1⁢x¯=2,0,⁢D⁢g2⁢x¯=1,2,⁢D⁢g3⁢x¯=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 gi⁢x=-1<0 dla i=1,2,3. Zachodzi więc warunek Slatera.

Przykład 6.2 (Kuhn, Tucker (1951))

Rozważmy zadanie optymalizacyjne:

x1→min,x2≤x13,x2≥0,
Rys. 6.1. Zbiór punktów dopuszczalnych dla przykładu Kuhna-Tuckera.

Zbiór punktów dopuszczalnych W naszkicowany jest na rysunku 6.1. Zapiszmy funkcje opisujące ograniczenia:

g1⁢x1,x2=-x13+x2,⁢g2⁢x1,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 T⁢x¯≠Tl⁢i⁢n⁢x¯:

T⁢x¯=d∈R2:⁢d1≥0,⁢d2=0,⁢Tl⁢i⁢n⁢x¯=d∈R2:⁢d2=0.
Przykład 6.3

Niech A będzie macierzą symetryczną n×n. Rozważmy zadanie optymalizacyjne:

xT⁢A⁢x→max,x≤1,x∈Rn.

Zapiszmy najpierw problem optymalizacyjny w kanonicznej formie. Zauważmy przy tym, że warunek x≤1 jest równoważny x2=xT⁢x≤1.

-xT⁢A⁢x→min,xT⁢x-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ć:

-2⁢xT⁢A+2⁢μ⁢xT=0T,μ⁢xT⁢x-1=0,μ≥0,⁢x∈Rn.

Przypadek xT⁢x-1<0. Wówczas μ=0 (z powodu drugiego równania) i pierwsze równanie przyjmuje postać xT⁢A=0T, którą poprzez transponowanie obu stron sprowadzamy do

A⁢x=0.

Równanie to spełnione jest przez wszystkie x∈ker⁡A, x<1. W szczególności ma ono co najmniej jedno rozwiązanie (x=0).

Przypadek xT⁢x-1=0. Teraz nic nie możemy powiedzieć o μ. Może być zerowe lub dodatnie. Pierwsze równanie przyjmuje jednak postać μ⁢xT=xT⁢A, które po stransponowaniu wygląda następująco:

μ⁢x=A⁢x.

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∈ker⁡A:⁢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∈ker⁡A, to wartość funkcji celu xT⁢A⁢x 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 Ti⁢n⁢t⁢x¯⊂T⁢x¯, gdzie Ti⁢n⁢t⁢x¯ 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-6⁢x+y2+2⁢y→min,x+2⁢y-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=1nci⁢xi2→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+3⁢x22-x1→min,x12-x2≤1,x1+x2≥1.
Ćwiczenie 6.5

Znajdź minima i maksima globalne funkcji

f⁢x1,x2=4⁢x12+2⁢x22-6⁢x1⁢x2+x1

na zbiorze

W=x1,x2∈R2:-2⁢x1+2⁢x2≥1, 2⁢x1-x2≤0,⁢x1≤0,⁢x2≥0.

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.