Please enable JavaScript.
Coggle requires JavaScript to display documents.
Optymalizacja Matematyczna (Matematyczne podstawy (Gradient) (Uogólnieniem…
Optymalizacja Matematyczna
Zmienne dyskretne (nieciągłe)
optymalizacja kombinatoryczna
Zmienne ciągłe
Constrained Problems
Multimodal Problems
MO
NMO
CO TO
problem polegający na znalezieniu ekstremum (optimum) zadanej funkcji celu.
Definicja matematyczna prosta, wyznaczanie w praktyce juz nie.
W realu mamy bardzo skomplikowane funkcje z bardzo wieloma zmiennymi
Opracowywano różne algorytmy operacyjne, aż powstał nowy dział nauki = BADANIA OPERACYJNE.
KLASY
Opt. STATYCZNA
poszukujemy ekstremum FUNKCJI
PROGRAMOWANIE LINIOWE
poszukiwanie ekstremum liniowej funkcji celu przy ograniczeniach będących również funkcjami liniowymi.
ekstremum jest zawsze globalne w danym obszarze poszukiwań
Programowanie liniowe znalazło szerokie zastosowanie w teorii decyzji, np. do optymalizacji planu produkcyjnego. Wiele problemów optymalizacyjnych znajduje rozwiązanie poprzez sprowadzenie ich do postaci problemu programowania liniowego
PROGRAMOWANIE NIELINIOWE (PNL)
polega na poszukiwaniu ekstremum
funkcji celu dowolnej postaci,
przy ograniczeniach będących również wyrażonymi przez
dowolne funkcje.
Większość algorytmów numerycznych to algorytmy poszukiwania ekstremum lokalnego. Skuteczność działania takich procedur jest więc w dużym stopniu uwarunkowana wyborem odpowiedniego punktu startowego.
EKSTREMUM LOKALNE
Poszukiwanie ekstremum może się odbywać w pewnym ograniczonym obszarze zawierającym tylko jedno ekstremum
EKSTREMUM GLOBALNE
w całej przestrzeni argumentów. Skuteczność zależy mocno od ustalonego punktu startowego
Opt. DYNAMICZNA
poszukujemy ekstremum FUNKCJONAŁU
Typowe zagadnienie optymalizacji dynamicznej polega na poszukiwaniu takiego ciągu decyzji w danym przedziale czasu, który zapewni ekstremum pewnego wskaźnika jakości zależącego od przebiegu zmian tej decyzji, określanym na całym przedziale czasu. Wskaźnik jakości jest więc funkcjonałem tej decyzji, określanym na danym przedziale czasu.
Matematyczne podstawy
Funkcje wypukłe
mają fajne właściwości. Dlatego bada się czy są wypukłe.
Gradient
)
Gradientem nazywa się również pojedynczy wektor wskazujący kierunek i szybkość wzrostu wspomnianego pola skalarnego w danym punkcie;
„zgodnie z gradientem” należy rozumieć jako „zgodnie z kierunkiem najszybszego wzrostu”.
Uogólnieniem gradientu na funkcje przestrzeni euklidesowej w inną jest macierz Jacobiego.
Jest ona macierzą przekształcenia liniowego znanego jako pochodna zupełna, dlatego za dalej idące uogólnienia (na funkcje między przestrzeniami Banacha) można uważać pochodną Gâteaux, a przy dodatkowych założeniach: pochodną Frécheta.
LUB
wektorowy operator różniczkowy nazywany nabla
Jak liczyć? Zależy od przestrzeni.
W układzie współrzędnych kartezjańskich składowe gradientu funkcji f są pochodnymi cząstkowymi tej funkcji
Antygradient
wektor przeciwny do gradientu (oraz odpowiadające mu przeciwne do gradientowego pole wektorowe) nazywa się często antygradientem
Hesjan
FUNKCJA CELU
OGRANICZENIA
Funkcja
unimodalna
Funkcja unimodalna – funkcja ciągła, dla której w zadanym przedziale istnieje maksymalnie jedno ekstremum lokalne.
Unimodalność jest wymagana do poprawnego działania wielu metod optymalizacyjnych (np. metody złotego podziału), służących do wyszukiwania lokalnych minimów funkcji.
ZMIENNE DECYZYJNE
Metody Numeryczna
metoda rozwiązywania problemów matematycznych za pomocą
operacji na liczbach.
Otrzymywane tą drogą wyniki są na ogół przybliżone, jednak dokładność obliczeń może być z góry określona i dobiera się ją zależnie od potrzeb. Obecnie ta dziedzina matematyki rozwija się bardzo szybko ze względu na liczne zastosowania w informatyce i algorytmice.
wykorzystywane są wówczas, gdy badany problem
nie ma w ogóle rozwiązania analitycznego
(danego wzorami) lub
korzystanie z takich rozwiązań jest uciążliwe
ze względu na ich złożoność.
Przykłady
całkowania
znajdowania miejsc zerowych wielomianów stopnia większego niż 2 (korzystanie ze wzorów na dokładne wartości pierwiastków równań stopnia 3 i stopnia 4 jest niepraktyczne, dla równań stopnia wyższego niż 4 wzorów już nie ma)
rozwiązywania układów równań liniowych w przypadku większej liczby równań i niewiadomych
rozwiązywania równań różniczkowych i układów takich równań
znajdowania wartości i wektorów własnych (zob. równanie własne)
aproksymacji, czyli przybliżaniu nieznanych funkcji (np. pomiarów zjawisk fizycznych)
vs METODY ANALITYCZNE
Algorytmy
Numeryczne
bez ograniczeń
Metody gradientowe I rzędu
Metoda Gradientu Prostego
Metody te wymagają znajomości pierwszych pochodnych funkcji celu.
Pierwsze pochodne możemy policzyć analitycznie (i następnie zaimplementować w programie odpowiednią procedurę) lub przybliżyć ich wartość w sposób numeryczny (np. metodą różnic skończonych). Istnieją też dokładne, automatyczne metody policzenia pochodnych, np. z wykorzystaniem obliczeń symbolicznych lub metoda automatycznego różniczkowania programów komputerowych (AD).
popularne metody
najszybszego spadku
gradientów sprzężonych
Quasi-Newtona (zmiennej metryki)
Metoda Najszybszego Spadku
Metody gradientowe II rzędu
Metoda Newtona
#
Jednowymiarowej funkcji celu
Metoda Złotego Podziału
M. Dychotomii
M. Podziału Środkowego
Metody bezgradientowe
Metoda Gaussa
Metoda Powella
zazwyczaj traktują funkcje celu jak „czarną skrzynkę”, tzn. zakładają że można odczytać wartość funkcji celu w dowolnym punkcie jej dziedziny, ale nie wymagają żadnych informacji na temat jej krzywizny (tzn. znajomości jej pochodnych)
z ograniczeniami
Wiele metod bez ograniczeń można przystosować do optymalizacji z ograniczeniami (np. dodając do funkcji celu składnik kary za naruszenie ograniczeń). Typowymi metodami optymalizacji z ograniczeniami są:
dwufazowa metoda sympleksu
SLP
na NMO
Metoda Kar
metoda grg
nieliniowa
uogólniony, zredukowany gradient
metoda uogolnionego lagrangea
Sieci Neuronowe
