Spis treści
Metody Obliczeniowe Optymalizacji
- optymalizacja
- parametry (zmienne projektowe/decyzyjne)
- funkcja celu/koszt/kryterium jakości
<m>f(x_1, …, x_n):bbR^n right bbR</m>
- polioptymalizacja (optym. wielokryterialna)
<m>vec{F}=(f_1, …, f_m)</m>
rozwiazanie kompromisowe (front Pareto, rozwiązanie niezdominowane) - gradient
- <m>nabla(f(x_1, …, x_n)) = delim{[}{matrix{3}{1}{{delta f}/{delta x_1} vdots {delta f}/{delta x_n}}}{]}</m>
- <m>vec{nabla} = delim{[}{matrix{3}{1}{{delta}/{delta x_1} vdots {delta}/{delta x_n}}}{]}</m>
- <m>f prime(x)=0</m> - punkt stacjonarny (przegięcia - punkt siodłowy)
- laplacjan
- <m>Delta={delta^2}/{delta {x_{1}}^2} + cdots + {delta^2}/{delta {x_{n}}^2}</m>
- Macierz Hessego [dla funkcja klasy <m>C^2</m>]
- <m>H := delim{[}{matrix{2}{2}{{delta^2 f}/{delta {x_1}^2} {delta^2 f}/{delta x_1 delta x_2} {delta^2 f}/{delta x_2 delta x_1} {delta^2 f}/{delta {x_2}^2}}}{]}</m>
- <m>H = H^T</m> - dla pewnych funkcji (zgodnie z tw. Schwartza
- hesian określa czy f. jest wypukła
- Hesian to wyznacznik macierzy Hessego
- Gradient określa nachylenie w punkcie. Hesjan - krzywiznę
- Gradient określa lokalny kierunek najszybszego wzrostu.
Ujemny gradient - spadku. - Metody optymalizacji:
- bezgradientowe (bez znajomości pochodnych)
- gradientowe 1-go rzędu (mamy gradient)
- ze znajomością Hessiana (poch. 2-go rzędu)
- będziemy uwzględniać tylko met. deterministyczne (nie stochastyczne - losowe)
- <m>vec{x_{i+1}} = vec{x_i} + Delta vec{x_i}</m>
- <m>vec{x_1}} = vec{x_0} + Delta vec{x_0}</m>
- obliczanie poprawki zależy od wybranego algorytmu optymalizacji
- <m>Delta x_i := - alpha nabla f(x_i)</m> - met. gradientowa 1-go rzędu
- warunki stopu:
- <m>delim{|}{f(vec{x_{i+1}})-f(vec{x_i})}{|} ⇐ epsilon_1</m>
- <m>delim{|}{vec{x_{i+1}} - vec{x_i}}{|} ⇐ epsilon_2</m>
- metoda najszybszego spadku - Cauchy
- jeśli metoda jest gradientowa, to można liczyć pochodne numerycznie:
- metoda różnnic skończonych: wstecznych, przednich, środkowych
- problemy:
- zygzakowanie
- funkcja unimodalna:
- w danych przedziale ma dokladnie jedno minimum.
- znajdowanie przedziałów unimodalności może być przez siatkowanie
- f. unimodalna może być nieciągła, nieróżniczkowalna
- dla funkcji unimodalnych możemy ograniczyć przedział poszukiwań przez eliminację
- przy szukaniu ekstremów globalnych używa się met. stochastycznych (metaheurystyki - wychładzanie):
- alg. ewolucyjne
- alg. mrówkowe
- met. hybrydowe
- <m>{min}under{vec{x} in Omega} f(vec{x}) = delim{lbrace}{matrix{3}{1}{ {min f(vec{x})} {g_j(vec{x})⇐0} {h_k(vec{x})=0} }}{rbrace}</m>
- Ograniczanie nazywamy _aktywnym_ w rozwiązaniu, jeśli jest spełnione jako różność
- dla f-cji liniowych:
<m>f={vec{c^T}} vec{x} = c_1 x_1 + cdots + c_n x_n</m> - Funkcja liniowa jest wypukła
- Ekstremum f-cji wypukłej jest globalne (o ile jest)
- W dostatecznie małym otoczeniu punktu <m>p in D</m> funkcji nieliniowej można ją dowolnie przybliżyć za pomocą funkcji kwadratowej
- Dla bardzo dużych n stosuje się 2-fazową met. sympleksu
- Dla f-cji liniowej optimum znajduje się w wierzchołku obszaru dopuszczalnego
- Optymalizacja jednowymiarowa (met oparte na eliminacji) (met numeryczne):
- eliminacja
- dychotomia
dwa eksperymenty blisko środka (środek +/- delta/2) - bisekcja [mniej więcej skuteczna tak jak dychotomia]
- 3 eksperymenty w 1 kroku
- 2 każdym kolejnym
- złoty podział
tau = 1,618…- nie wymaga podania liczby iteracji
- Fibonacci [najdokładniejszy spośród eliminacji]
- interpolacyjne:
- kwadratowa (paraboliczna), kubiczna, splajnowa
- Newtona
- quasi-Newtona [gradientowa]
- DFP
- BFGS
- siecznych
- Programowanie liniowe - funkcja celu i ograniczenia są liniowe
zwane też minimalizacją wypukłą - Programowanie całkowitoliczbowe - zmienne decyzyjne naturalne (opt. kombinatoryczna)
- Programowanie nieliniowe (NLP):
- ograniczenia nie muszą być wielościanem
- optimum nie musi być punktem brzegowym
- SUMT - sekwencyjna minimalizacja bez ograniczeń
- nie można zagwarantować znalezienia globalnego ekstremum
- ale możliwe są heurystyki (różne punktu początkowe, zaburzenia ekstremów)
- przeszukiwanie tabu (jest lista tabu [heurystyka]). jest to bezgradientowe
- Stabilność optymalizacji
- warunki stabilnośći
- automatyczne różniczkowanie programów komputerowych
(za pomocą przeciążania operatorów) - optymalizacja wielowymiarowa bez ograniczeń
- tylko wartość f. celu - pełzający symplex
- Hook-Jeeves
- Powell
- Rosenbrock
- Nelder-Mead
- f. celu oraz I pochodna - najszybszy spadek
- f. celu oraz I i II pochodna - met. Newtona
- f. celu oraz I i przybliżenie II poch.
- Pełzający symplex
W n wymiarach: figura o n+1 wierzchołkach.
Trójkąt w 2D. Tetrahedron w 3D.- centroid
- operacje
- odbicie
- ekspansja
- kontrakcja
- redukcja
TODO:
- wartości własne (eigen values)
- określają stabilność optymalizacji
- wartości szczególne (singular values)
- równanie sekularne
Algorytm optymalizacji jest stabilny, jeżeli małe zaburznia danych wejściowych mało zaburzają wyjście
Druga połowa semsetru - na drugie kolokwium
- Metoda Newtona
- Metoda Quasi-Newtona (zmiennej metryki)
- wektory sprzężone
- algorytm gradientów sprzężonych
- Optymalizacja wielowymiarowa bez ograniczeń
- metody drugiego rzędu
- metoda Newtona
- metoda Levenberg'a-Marquardt'a
- formuła DFP
- formuła BFGS
- Rodzina Huang'a
- Metoda sympleks
- Tablica sympleksowa
- Kryterium wyjścia z bazy
- Zadanie dualne i zadanie prymalne optymalizacji
- Twierdzenie o dualności
- Twierdzenie o równowadze
Laboratorium
- Optymalizacja graficzna
- Optymalizacja jednowymiarowa
- Optymalizacja wielowymiarowa bez ograniczeń
- Programowanie liniowe
- Optymalizacja z ograniczeniami
Literatura
- „Podstawy optymalizacji” - Wierzbicki, Stachurski
- Findeisen