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

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

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

Literatura

  • „Podstawy optymalizacji” - Wierzbicki, Stachurski
  • Findeisen
przedmioty/metody_obliczeniowe_optymalizacji.txt · ostatnio zmienione: 2007/01/08 18:13 (edycja zewnętrzna)
Recent changes RSS feed Creative Commons License Donate Minima Template by Wikidesign Driven by DokuWiki