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 .
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 , rozmiar hesjanu wyniesie 2×2, a w przypadku funkcji , 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. lub . 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 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.