#include <Newton.h>
Diagram dziedziczenia dla Newton
Podstawą metody Newtona jest aproksymacja funkcji celu funkcją kwadratową. Algorytm wyznacza każdy następny punkt w taki sposób by gradient kwadratowej funkcji aproksymującej wynosił w nim 0.
Przy zastosowaniu metody Newtona i przy niewystępowaniu niedokładności numerycznych, funkcje kwadratowe minimalizowane są w jednej iteracji. W przypadku gdy funkcja celu nie jest kwadratowa i gdy punkt startowy znajduje się w znacznej odległości od minimum, metoda Newtona charakteryzuje się wolną zbieżnością, lub nawet jej brakiem.
Algorytm metody:
Oznaczenia:
- numer aktualnej iteracji
- gradient w punkcie
- macierz hesjanu w punkcie
Dane potrzebne do obliczeń:
- minimalizowana funkcja celu
- punkt startowy
- wymagana dokładność,
warunek stopu - do wyboru:
Jeśli tak to STOP: Hejsan jest macierzą osobliwą.
W przeciwnym wypadku przejdź do kroku 3.
Krok 3:
Oblicz:
Podstaw i przejdź do kroku 1.
Uwagi:
W stosunku do wersji algorytmu zamieszczonej w [1] zmieniono kolejność wykonywania kroków. W zaimplementowanej wersji sprawdzanie warunku stopu dokonuje się na początku każdej iteracji. Dzięki temu algorytm może zatrzymać się nie wykonując żadnej iteracji w przypadku gdy punkt startowy znajduje sie w minimum i wykorzystywany jest "gradientowy" warunek stopu. Początkowe wartości zmiennych oznaczających rożnice położenia dwóch ostatnich punktów oraz różnice wartości funkcji w tych dwóch punktach są równe DBL_MAX, więc w przypadku wykorzystaniu innego warunku stopu niż "gradientowy" modyfikacja nie będzie miała żadnego wpływu na działanie algorytmu.
[1] Aleksander Ostanin - Metody i algorytmy optymalizacji, Wydawnictwo Politechniki Białostockiej, Białystok 2003
Metody publiczne | |
~Newton (void) | |
Destruktor. | |
virtual std::auto_ptr< Method > | Clone () const |
Tworzy kopię metody. | |
virtual void | UpdateStartingConditions (const Result *result) const |
virtual void | ResetStartingConditions () const |
virtual const wxString & | Name () const |
Zwraca nazwę metody. | |
virtual MethodIdType | Id () const |
Zwraca ID metody. | |
virtual wxString | ToString (bool standalone=true) const |
Zwraca opis tekstowy metody (nazwa + parametry). | |
virtual bool | CanHandle (const ProblemBase *pProblem) const |
Czy metoda nadaje się do rozwiązania zadanego problemu. | |
virtual StopConditions | AllowedStopConditions () const |
Zwraca listę warunków stopu odpowiednich dla danej metody. | |
Statyczne metody publiczne | |
static MethodIdType | ClassId () |
Zwraca ID metody. | |
Metody chronione | |
Newton (void) | |
Konstruktor domyślny. | |
Newton (const Newton &from) | |
Konstruktor kopiujący. | |
virtual wxString & | rName () |
Atrybuty chronione | |
ColumnVector | mStartingPoint |
Punkt startowy. | |
ColumnVector | mInitialStartingPoint |
CountedPtr< const StandardStopCondition > | mcpStopCondition |
Warunek stopu. | |
Przyjaciele | |
class | BasicMethodPanel< Newton > |
|
Konstruktor kopiujący.
|