Rozważmy bardzo prostą modyfikację algorytmu największego spadku. Otóż jeśli punkt znajduje się wewnątrz zbioru W, to istnieje możliwość poruszania się wzdłuż kierunku największego spadku aż do uderzenia w brzeg. Jeśli punkt już jest na brzegu, to naturalne jest wybrać taki kierunek ruchu, by pozwalał on na jak największy spadek wartości funkcji celu a jednocześnie na ruch w jego kierunku. Kierunek taki nazywamy dopuszczalnym kierunkiem spadku w punkcie x i definiujemy jako kierunek dopuszczalny d, taki że D⁢f⁢x⁢d<0.

Okazuje się, że pomysł ten działa całkiem dobrze, jeśli ograniczenia są liniowe i nosi nazwę algorytm Zoutendijk'a. Przypomnijmy, że liniowość ograniczeń znacznie upraszcza problem, co pozwoli nam na rozszerzenie analizy w tym podrozdziale do zagadnień z ograniczeniami nierównościowymi i równościowymi, tzn.

Tutaj A jest macierzą m×n, Q jest macierzą l×n, zaś b∈Rm i a∈Rl. Poniższy lemat charakteryzuje zbiór dopuszczalnych kierunków spadku. Jego dowód pozostawiamy jako ćwiczenie.

Jak wybrać najlepszy dopuszczalny kierunek spadku w punkcie x? Najprościej byłoby rozwiązać zagadnienie

Ograniczenie na normę wektora d jest konieczne. Jeśli byśmy je opuścili, to dla dowolnego dopuszczalnego kierunku spadku d jego wielokrotność λ⁢d, λ>0, jest również kierunkiem spadku. Co więcej, D⁢f⁢x⁢d<0, czyli limλ→∞⁡D⁢f⁢x⁢λ⁢d=-∞ i problem powyższy nie ma jednoznacznego rozwiązania.

Korzystając z lematu 14.1 powyższe zagadnienie (14.4) można wyrazić jako

Zauważmy, że jedyna nieliniowość związana jest z ograniczeniem na normę wektora d. W praktyce, bez większych strat dla jakości algorytmu, zamienia się ją na ograniczenia liniowe, które pozwalają skorzystać z szybkich metod optymalizacji liniowej (np. algorytmu sympleks – patrz monografie Bazaraa, Jarvis'a, Shetty [2], Gass'a [8] lub Luenberger'a [9]). Najpopularniejsze są następujące dwa zamienniki normy euklidesowej d:

• norma l∞, tzn. supi⁡di≤1, co zapisuje się jako

  -1≤di≤1,⁢i=1,…,n.

• norma l1, tzn. ∑idi≤1, co zapisuje się jako

  ∑i=1nηi≤1,-ηi≤di≤ηi,⁢i=1,…,n,

  gdzie η1,…,ηn są nowymi zmiennymi (pomocniczymi).

Oto pełny algorytm:

• Inicjalizacja: Wybierz punkt początkowy x0.

• Krok k-ty:

  1. Wybierz kierunek ruchu dk jako rozwiązanie problemu optymalizacyjnego:

     D⁢f⁢x⁢d→min,A1⁢d≤0,Q⁢d=0,-1≤di≤1,⁢i=1,…,n.

     (14.5)

  2. Jeśli dk=0, to zakończ działanie algorytmu. Punkt xk spełnia warunek konieczny pierwszego rzędu. W przeciwnym przypadku kontynuuj.

  3. Połóż αk=argminα∈0,Ak⁢f⁢xk+α⁢dk, gdzie Ak jest największą liczbą o tej własności, że odcinek łączący xk i xk+Ak⁢dk zawarty jest w W.

  4. Połóż xk+1=xk+αk⁢dk.

Przyjrzyjmy się jeszcze raz wyborowi kierunku dk. Wektor d=0 spełnia wszystkie ograniczenia, a zatem optymalna wartość funkcji celu D⁢f⁢x⁢dk jest co najwyżej równa zeru. Wówczas punkt xk spełnia warunek konieczny pierwszego rzędu, czego dowodzimy w poniższym lemacie.

Zastanówmy się, czy algorytm Zoutendijk'a działa równie dobrze dla ograniczeń nieliniowych:

• Inicjalizacja: Wybierz punkt początkowy x0.

• Krok k-ty:

  1. Wybierz kierunek ruchu dk jako rozwiązanie problemu optymalizacyjnego:

     D⁢f⁢x⁢d→min,⁢d∈A⁢x,⁢d≤1.

  2. Jeśli dk=0, to zakończ działanie algorytmu. Punkt xk spełnia warunek konieczny pierwszego rzędu. W przeciwnym przypadku kontynuuj.

  3. Połóż αk=argminα∈0,Ak⁢f⁢xk+α⁢dk, gdzie Ak jest największą liczbą o tej własności, że odcinek łączący xk i xk+Ak⁢dk zawarty jest w W.

  4. Połóż xk+1=xk+αk⁢dk.

W poniższych przykładach rozważamy minimalizowanie funkcji f⁢x1,x2=-2⁢x1-x2 na różnych zbiorach. Punkt minimum oznaczamy zawsze przez x¯. Na rysunku 14.1 widać, że już w kroku drugim osiągamy minimum. Jeśli zbiór W nie jest wypukły algorytm prowadzi nas w kozi róg, z którego już nie możemy się uwolnić, patrz 14.2. Jest to niestety cecha wszystkich algorytmów tego typu, więc musimy zawsze wymagać, by zbiór punktów dopuszczalnych był wypukły. Czy to już wystarczy? Niestety nie. Na rysunku 14.3 możemy zobaczyć, że nawet w przypadku zbioru wypukłego algorytm nie działa. Problem wyboru kierunku d1 nie ma rozwiązania, gdyż zbiór D⁢x1 nie jest domknięty. Intuicyjnie łatwo jest podać rozwiązanie tego problemu. Należy wybrać taki kierunek dk, aby nie tylko spadek był jak największy, ale również, żeby dość duży fragment półprostej poprowadzonej w tym kierunku zawierał się w zbiorze W. Co więcej, zależy nam na prostocie, czytaj liniowości, zagadnienia optymalizacyjnego wyznaczającego kierunek dk. Rozwiązanie podpowiada następujący lemat, którego dowód pozostawiamy jako ćwiczenie.

Lemat powyższy podaje tylko warunek dostateczny. Łatwo znaleźć przykład zagadnienia optymalizacyjnego z ograniczeniami nierównościowymi, dla którego jeden z dopuszczalnym kierunków spadku nie spełnia założeń lematu (ćwiczenie 14.5).

Znalezienie wektora d∈Rn spełniającego D⁢f⁢x⁢d<0 i D⁢gi⁢x⁢d<0, i∈I⁢x sprowadza się do rozwiązania zagadnienia

Trudną w implementacji funkcję celu można sprowadzić do znacznie prostszej formy problemu optymalizacji liniowej:

Optymalizacji dokonuje się tutaj względem dwóch zmiennych: d∈Rn oraz η∈R. Zauważmy, że η≤0, gdyż para d=0, η=0 rozwiązuje powyższy układ. Jeśli wartość funkcji celu jest mniejsza od zera, to, na mocy lematu 14.1, rozwiązanie jest dopuszczalnym kierunkiem spadku. Jeśli η=0 jest rozwiązaniem i w punkcie x spełniony jest warunek liniowej niezależności ograniczeń, to wówczas w x zachodzi warunek konieczny pierwszego rzędu. Prawdziwa jest również odwrotna implikacja.

Zapiszmy w pełni algorytm zaproponowany przez Zoutendijka dla problemów z nieliniowymi ograniczeniami nierównościowymi:

• Inicjalizacja: Wybierz punkt początkowy x0.

• Krok k-ty:

  1. Wybierz kierunek ruchu dk jako rozwiązanie problemu optymalizacyjnego (14.6)

  2. Jeśli η=0, to zakończ działanie algorytmu. Punkt xk spełnia warunek konieczny pierwszego rzędu. W przeciwnym przypadku kontynuuj.

  3. Połóż αk=argminα∈0,Ak⁢f⁢xk+α⁢dk, gdzie Ak jest największą liczbą o tej własności, że odcinek łączący xk i xk+Ak⁢dk zawarty jest w W.

  4. Połóż xk+1=xk+αk⁢dk.

Algorytm Zoutendijka może polec nawet na dość prostych prostych problemach optymalizacyjnych. Rozważmy minimalizowanie funkcji liniowej f⁢x=-2⁢x1-x2 na zbiorze zaznaczonym na rysunku 14.5. Minimum znajduje się w punkcie x¯=1,1T. Rozpoczynając od punktu x0=-1,0T, kolejne iteracje algorytmu Zoutendijka wygenerują ciąg punktów zbiegający do 1,0T. Algorytm ten nie pozwoli nam na przybliżenie właściwego rozwiązania x¯. Co więcej, wartość funkcji celu w punkcie 1,0T wynosi -2, w porównaniu do f⁢x¯=-3. W następnym podrozdziale pokażemy jak mała modyfikacja pozwoli naprawić algorytm Zoutendijka.

Topkis i Veinott zaproponowali w roku 1967 niewielką modyfikację wyznaczania kierunku dk w algorytmie Zoutendijka:

Linia dotycząca warunku na gradienty ograniczeń obejmuje teraz wszystkie ograniczenia. Dla ograniczeń aktywnych, i∈I⁢x, mamy gi⁢x=0, a więc warunki te są identyczne jak w (14.6). W przypadku ograniczeń nieaktywnych gi⁢x<0, czyli prawa strona jest większa niż η. O ile dla dużych wartości gi⁢x ograniczenie takie jest prawie niezauważalne, to dla ograniczeń, które są ”prawie aktywne”, odgrywa znaczną rolę. Poza tym, z punktu widzenia implementacji, rozwiązuje to kwestię znajdowania zbioru ograniczeń aktywnych (ze względu na niedokładności zapisu liczb, prawie nigdy nie będzie spełniony warunek gi⁢x=0).

O skuteczności modyfikacji (14.7) świadczy następujące twierdzenie, które podamy bez dowodu:

Metody numeryczne opisane w tym rozdziale pozwalają na znalezienie aproksymacji punktów, w których spełniony jest warunek konieczny pierwszego rzędu. Twierdzenie 7.6 zagwarantuje dopiero optymalność tych punktów. W szczególności, jeśli ograniczenia są liniowe, to wystarczy założyć pseudowypukłość funkcji f. Zwróćmy uwagę, że wymagaliśmy podobnych założeń w poprzednim rozdziale, dla optymalizacji bez ograniczeń. Wymóg wypukłości okazuje się bardzo naturalnym i, co więcej, koniecznym dla sprawnego działania tych metod.