Dokumentacja klasy QuadraticApproximation

#include <QuadraticApproximation.h>

Diagram dziedziczenia dla QuadraticApproximation

SectionLineSearch LineSearch Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda aproksymacji kwadratowej.

Metoda optymalizacji w kierunku polegająca na stopniowym skracaniu zadanego odcinka (patrz SectionLineSearch).

Opiera się na założeniu, że w otoczeniu minimum funkcja celu może być aproksymowana funkcją kwadratową.
W każdej iteracji dokonywana jest minimalizacja funkcji kwadratowej zbudowanej na podstawie wartości funkcji celu w trzech punktach próbnych: $a$, $m$ i $b$. Do skonstruowania takiej funkcji aproksymującej wykorzystywana jest interpolacja Lagrange'a:

\[ f(x) = F_a \frac{(x - a)(x - b)}{(a - m)(a - b)} + F_m \frac{(x - a)(x - b)}{(m - a)(m - b)} + F_b \frac{(x - a)(x - m)}{(b - a)(b - m)} . \]

Pierwsza pochodna tej funkcji zeruje się w punkcie:

\[ x = \frac{1}{2} \frac{(m^2 - b^2)F_a + (b^2 - a^2)F_m + (a^2 - m^2)F_b} {(m - b)F_a + (b - a)F_m + (a - m)F_b}.\]

Algorytm polega na zastępowaniu jednego z punktów próbnych $a$, $m$, $b$ punktem $x$ i skracaniu odcinka w taki sposób, aby obejmował on estymowane minimum.


Informacje wejściowe:
$f(x)$ - minimalizowana funkcja jednej zmiennej,
$a^0$ - lewy kraniec początkowego przedziału poszukiwań,
$b^0$ - prawy kraniec początkowego przedziału poszukiwań,
$\varepsilon$ - wymagana dokładność (graniczna długość odcinka, minimalna odległość $x$ od punktów próbnych).


Oznaczenia:
$k$ - numer aktualnej iteracji,
$a^k$ - lewy kraniec aktualnego przedziału poszukiwań - pierwszy punkt próbny,
$m^k$ - drugi punkt próbny,
$b^k$ - prawy kraniec aktualnego przedziału poszukiwań - trzeci punkt próbny,
$F_a$ - wartość funkcji celu w punkcie $a^k$,
$F_m$ - wartość funkcji celu w punkcie $m^k$,
$F_b$ - wartość funkcji celu w punkcie $b^k$,
$x^k$ - punkt zerowania się pierwszej pochodnej funkcji aproksymującej,
$F_x$ - wartość funkcji celu w punkcie $x^k$.


Procedura.


Krok wstępny:
Podstawiamy:

\[ a^1 = a^0, \]

\[ m^1 = \frac{a^0 + b^0}{2}, \]

\[ b^1 = b^0, \]

\[ F_a = f(a^1), \]

\[ F_m = f(m^1), \]

\[ F_b = f(b^1). \]


Krok 1:
Znajdujemy potencjalne minimum funkcji aproksymującej:

\[ x^k = \frac{1}{2} \frac{((m^k)^2 - (b^k)^2)F_a + ((b^k)^2 - (a^k)^2)F_m + ((a^k)^2 - (m^k)^2)F_b} {(m^k - b^k)F_a + (b^k - a^k)F_m + (a^k - m^k)F_b}.\]

Jeśli mianownik tego wyrażenia jest liczbą nieujemną, przechodzimy do kroku 8.
Podstawiamy $F_x = f(x^k)$ i przechodzimy do kroku 2.


Krok 2:
Sprawdzamy, czy $x^k$ znajduje się wystarczająco blisko jednego z punktów próbnych:
Jeśli $|x^k - a^k| < \varepsilon$ lub $|x^k - m^k| < \varepsilon$ lub $|x^k - b^k| < \varepsilon$, to przechodzimy do kroku 7.
Sprawdzamy, czy $x^k$ leży wewnątrz badanego odcinka:
Jeśli $a^k < x^k < b^k$, to przechodzimy do kroku 3. W przeciwnym wypadku przechodzimy do kroku 9.


Krok 3:
Jeśli $x^k < m^k$, przechodzimy do kroku 4. W przeciwnym wypadku przechodzimy do kroku 5.


Krok 4:
Jeśli $F_x < F_m$, redukujemy odcinek do $[a; \: m]$:

\[ a^{k+1} = a^k, \]

\[ m^{k+1} = x^k, \]

\[ b^{k+1} = m^k, \]

\[ F_b = F_m, \]

\[ F_m = F_x. \]

Przechodzimy do kroku 6.
Jeśli $F_x \ge F_m$, redukujemy odcinek do $[x; \: b]$:

\[ a^{k+1} = x^k, \]

\[ m^{k+1} = m^k, \]

\[ b^{k+1} = b^k, \]

\[ F_a = F_x, \]

Przechodzimy do kroku 6.


Krok 5:
Jeśli $F_x < F_m$, redukujemy odcinek do $[m; \: b]$:

\[ a^{k+1} = m^k, \]

\[ m^{k+1} = x^k, \]

\[ b^{k+1} = b^k, \]

\[ F_a = F_m, \]

\[ F_m = F_x. \]

Przechodzimy do kroku 6.
Jeśli $F_x \ge F_m$, redukujemy odcinek do $[a; \: x]$:

\[ a^{k+1} = a^k, \]

\[ m^{k+1} = m^k, \]

\[ b^{k+1} = x^k, \]

\[ F_b = F_x, \]

Przechodzimy do kroku 6.


Krok 6:
Sprawdzamy długość odcinka po redukcji:
Jeśli $b^{k+1} - a^{k+1} \ge \varepsilon $, przechodzimy do kroku 1. W przeciwnym wypadku przechodzimy do kroku 7.


Krok 7:
Kończymy procedurę. Jeśli $F_x < F_m$, wynikiem jest $x^k$. W przeciwnym wypadku wynikiem jest $m^k$.


Krok 8:
Kończymy procedurę z komunikatem błędu: "Optymalizacja nie powiodła się - znaleziono maksimum lub punkt siodłowy funkcji aproksymującej."


Krok 9:
Kończymy procedurę z komunikatem błędu: "Optymalizacja nie powiodła się - znalezione minimum funkcji aproksymującej znajduje się poza badanym odcinkiem."

Metoda zaimplementowana na podstawie opisu zamieszczonego w:
Schwefel H.-P.: Evolution and Optimum Seeking. Nowy Jork, Wiley-Interscience 1995.

Zobacz również:
SectionLineSearch

Niniejszy dokument został półautomatycznie wycięty z dokumentacji kodu źródłowego programu Eduoptim 2. Pełna dokumentacja dostępna jest wraz ze źródłami bądź osobno w dziale pliki.
Hierarchia klas w programie nie odpowiada klasyfikacji metod optymalizacji.