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:
  1. bezgradientowe (bez znajomości pochodnych)
  2. gradientowe 1-go rzędu (mamy gradient)
  3. 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:
  1. <m>delim{|}{f(vec{x_{i+1}})-f(vec{x_i})}{|} ⇐ epsilon_1</m>
  2. <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
    1. dychotomia
       dwa eksperymenty blisko środka (środek +/- delta/2)
    2. bisekcja [mniej więcej skuteczna tak jak dychotomia]
       • 3 eksperymenty w 1 kroku
       • 2 każdym kolejnym
    3. złoty podział
       tau = 1,618…
       • nie wymaga podania liczby iteracji
    4. Fibonacci [najdokładniejszy spośród eliminacji]
  • interpolacyjne:
    1. kwadratowa (paraboliczna), kubiczna, splajnowa
    2. Newtona
    3. quasi-Newtona [gradientowa]
       • DFP
       • BFGS
    4. 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
    1. Hook-Jeeves
    2. Powell
    3. Rosenbrock
    4. 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
    1. odbicie
    2. ekspansja
    3. kontrakcja
    4. 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

• 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

1. Optymalizacja graficzna
2. Optymalizacja jednowymiarowa
3. Optymalizacja wielowymiarowa bez ograniczeń
4. Programowanie liniowe
5. Optymalizacja z ograniczeniami

• „Podstawy optymalizacji” - Wierzbicki, Stachurski
• Findeisen