Reguła minimalizacji jest dobrze określona, jeśli minimum po prawej stronie istnieje. Do jej implementacji możemy zastosować wówczas metodę Newtona opisaną w poprzednim rozdziale. Ograniczenie przedziału poszukiwań kroku do ma dwie zalety. Po pierwsze zadanie to ma zawsze rozwiązanie, gdyż minimalizujemy funkcję ciągłą na zbiorze zwartym. Po drugie, możemy zastosować szybsze metody poszukiwania minimum podobne do optymalizacji bez użycia pochodnych opisanej w poprzednim rozdziale.

W zadaniu 13.1 dowodzimy, że obie reguły minimalizacyjne wyznaczają krok o tej własności, że Pozostają jednak dwa pytania: czy warunek końca jest poprawny i czy ciąg zbiega do minimum.

W poniższym twierdzeniu dowodzimy, że każdy punkt skupienia ciągu jest punktem krytycznym, tzn. zeruje się w nim pochodna. Nie jest jednak w ogólności prawdą, że musi w nim być minimum lokalne. Dopiero założenie, że funkcja jest pseudowypukła daje nam pewność, że w znalezionym punkcie jest minimum, które dodatkowo jest globalne.

Powyższe twierdzenie dowodzi poprawności metody największego spadku, lecz nie mówi nic o szybkości zbieżności i o warunku końca. Wzmacniając założenia będziemy mogli dowieść, że zbieżność jest wykładniczo szybka oraz, podobnie jak w lemacie 12.4, warunek końca jest poprawny. Zdefiniujmy zbiór , gdzie jest punktem początkowym. Oznaczmy przez najmniejszą wartość własną macierzy drugich pochodnych , zaś przez – jej największą wartość własną.

Dowód lematu 13.1 pozostawiamy jako ćwiczenie. Zauważmy, że założenie o wypukłości jest dość naturalne. Jeśli macierz jest dodatnio określona, to na pewnej kuli o środku w funkcja jest wypukła. Jeśli jest jedynym minimum globalnym, to biorąc dostatecznie bliskie dostajemy, że zbiór poziomicowy jest zawarty w kuli i wnioskujemy dalej, że jest on wypukły.

Podsumujmy. Na mocy lematu 13.1 wiemy, że warunek końca sformułowany jako ograniczenie na normę gradientu funkcji jest poprawny i daje ograniczenia zarówno na odległość przybliżenia od punktu minimum, jak i na dokładność wyznaczenia wartości minimalnej funkcji. Zwróćmy uwagę, że czym ”bardziej” ściśle wypukła jest funkcja na otoczeniu , tj. czym większe , tym ostrzejsza zależność między normą gradientu a odległością od punktu . Lemat 13.2 sugeruje, że zbieżność wartości funkcji jest najszybsza, jeśli funkcja podobnie zachowuje się we wszystkich kierunkach, czyli wartości własne macierzy drugich pochodnych leżą dość blisko siebie. Wówczas iloraz jest największy, co korzystnie wpływa na współczynnik kontrakcji . A zatem algorytm największego spadku, podobnie jak wszystkie inne metody spadkowe, będzie najlepiej pracował na takich funkcjach, które mają stosunkowo duży iloraz , lub inaczej, jest tego samego rzędu co .

Przypomnijmy regułę Armijo. Kładziemy , gdzie jest najmniejszą liczbą całkowitą nieujemną spełniającą nierówność

Stała nazywana jest krokiem, reguluje szybkość zmniejszania kroku (czym mniejsza wartość, tym szybciej krok się zmniejsza), zaś odpowiedzialna jest za ostrość warunku: mniejsza wartość osłabia warunek. Zauważmy, że w przypadku metody największego spadku warunek powyższy upraszcza się nieznacznie, ponieważ :

(13.3)

Implementacja metody Armijo jest bardzo łatwa. Startujemy z punktu i sprawdzamy, czy spełniony jest w nim warunek (13.3). Jeśli tak, to kończymy poszukiwanie. W przeciwnym przypadku, rozważamy punkty W zadaniu 13.3 pokażemy, że w skończonej liczbie kroków znajdziemy punkt spełniający warunek (13.3), jeśli . Z nierówności (13.3) wynika, że

Poprawność warunku stopu algorytmu pozostaje w mocy, gdyż Lemat 13.1 nie zależy od metody optymalizacyjnej. Teza lematu 13.2 wymaga pewnych zmian, pozostawiając jednak wykładniczą zbieżność (patrz zadanie 13.4).

Jakie zatem są zalety reguły Armijo? Otóż, jak wspomniane zostało wyżej, jest ona prosta w implementacji i nie wymaga stosowania metod optymalizacji funkcji jednej zmiennej. Koszt tego uproszczenia nie jest zwykle również duży, lecz zależy od parametrów Nie ma niestety reguł doboru tych parametrów – pozostawia się to doświadczeniu i intuicji użytkownika.