Algorytm BFGS

W trakcie studiów miałem bardzo ciekawy przedmiot nazwany metody optymalizacji. Wymogiem zaliczenia przedmiotu, było napisanie aplikacji służącego do porównania dwóch metod optymalizacyjnych. Tak właśnie powstała analiza porównawcza metody Newtona i metody Broydena-Fletchera-Goldfarba-Shanno.  Analiza miała polegać na porównaniu wydajności obu metod, przy poszukiwaniu minimum tej samej funkcji. Prowadząca przedmiot dała nam wolną rękę, w wyborze technologii wykorzystanej do stworzenia aplikacji. Ze względu na fakt, że powyższe metody optymalizacyjne skupiają się na rozwiązywaniu pochodnych, postanowiłem wykorzystać w tym celu bardzo zaawansowane narzędzie jakim jest Matlab.

Metoda Newtona i Broydena-Fletchera-Goldfarba-Shanno są metodami gradientowymi, tak więc wszystkie działania odbywają się przy wykorzystaniu gradientu, który oznaczany jest jako symbol nabla  \nabla.

Pierwszą jest metoda Newtona, która poszukuje minimum funkcji przy pomocy gradientu oraz hesjanu funkcji czyli macierzy Hessego. Druga z metoda również wykorzystuje gradient funkcji i wzorów obliczających minimum funkcji. Metoda ta jednak nie używa skomplikowanego hesjanu funkcji, a tylko i wyłącznie prostszej w konstrukcji macierzy V.

Obie metody posiadają również warunki stopu, przy spełnieniu których zostaje zakończony proces rozwiązywania zadania – wynik. Metoda Newtona jest dobrze opisana w Internecie, natomiast opisy metody BFGS, głównie znajdują się na strona w języku angielskim. Osobiście korzystałem z stron w języku angielskim i książki w języku polski – „Optymalizacja – Wybrane metody z przykładami zastosowań”, Jana Kusiaka. W powyższej książce zdarzają się małe błędy, które są poprawiany z wydania na wydanie.

Dlaczego porównywać obie metody? Jedna i druga metoda dąży do poszukania minimum funkcji, jednak robi to w inny sposób. Metoda Newtona używa hesjanu funkcji, co wiąże się z rozbudowaną macierzą, ponieważ hesjan rośnie wraz z wzrostem potęgi funkcji. Oznacza to, że w przypadku funkcji wejściowej x^2, rozmiar hesjanu wyniesie 2×2, a w przypadku funkcji x^6, hesjan urośnie do wymiarów 6×6. Dodatkowo w przypadku hesjanu funkcji należy obliczać pochodne cząstkowe drugiego rzędu, co skutkuje wydłużeniem obliczeń. W przypadku drugiej metody, wykorzystywana jest prosta macierz V, która początkowo jest macierzą jednostkową, a w kolejnych krokach obliczana jest przy użyciu wzorów. Obliczenie takiej macierzy jest prostsze, niż obliczanie hesjanu.

Analiza została przeprowadzona na kilku różnych funkcjach, o różnym stopniu skomplikowania i różnej wysokości potęg. Metoda Newtona bardzo dobrze sprawdza się do funkcji o potęgach niskich tzn. x^2 lub x^3. Metoda Broydena-Fletchera-Goldfarba-Shanno jest mniej efektywna w porównaniu do metody Newtona dla funkcji o niskich potęgach. Natomiast wykorzystanie metody BFGS jest bardziej uzasadnione dla funkcji x^3 i wyżej.

Różnice w przypadku potęg niskich wynosi około 2 kroki na korzyść metody Newtona, natomiast dla potęg wyższych jest to uzależnione od skomplikowania funkcji wejściowej.

Cały projekt wraz z dokumentacją znajduje się poniżej. Aplikacja została napisana w Matlabie R2011a.

Pobierz projekt