Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

przedmioty:metody_obliczeniowe_optymalizacji [2007/01/08 18:13] (aktualna)
Linia 1: Linia 1:
 +====== 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
  
Recent changes RSS feed Creative Commons License Donate Minima Template by Wikidesign Driven by DokuWiki