Optymalizacja - matematyka - Polski Serwis Naukowy

Optymalizacja (matematyka), w matematyce termin optymalizacja odnosi się do problemu znalezienia ekstremum (minimum lub maksimum) zadanej funkcji celu.

Definicja

Niech dana będzie funkcja $f$ : $f \colon A \mapsto \R$

gdzie $A \subset \R^n$ . Zadanie optymalizacji polega na znalezieniu takiej wartości $x^{\ast} \in A$ , że dla każdego $x \in A \backslash \{x^{\ast}\}$ zachodzi: $f(x) > f(x^{\ast})$

Problemem równoważnym jest znalezienie maksimum funkcji - problem zdefiniowany jest tak samo jak powyżej z wyjątkiem zmiany znaku funkcji $f$ .

Funkcjonał – odwzorowanie określone na pewnej przestrzeni (przestrzeni funkcji, przestrzeni liniowej, σ-ciele) o wartościach w ciele liczbowym. Pojęcie funkcjonału pierwotnie pojawiło się w rachunku wariacyjnym. W kontekście przestrzeni liniowych i modułów używa się także określenia forma.

Procedura (algorytm) (Tabu search - TS) stosowana do rozwiązywania problemów optymalizacyjnych. Wykorzystywana do otrzymywania rozwiązań optymalnych lub niewiele różniących się od niego dla problemów z różnych dziedzin (np. planowanie, planowanie zadań). Podstawową ideą algorytmu jest przeszukiwanie przestrzeni, stworzonej ze wszystkich możliwych rozwiązań, za pomocą sekwencji ruchów. W sekwencji ruchów istnieją ruchy niedozwolone, ruchy tabu. Algorytm unika oscylacji wokół optimum lokalnego dzięki przechowywaniu informacji o sprawdzonych już rozwiązaniach w postaci listy tabu (TL). Twórcą algorytmu jest Fred Glover.

O ile definicja matematyczna optymalizacji jest prosta, tak praktyczne wyznaczanie optimum już nie jest. W wielu problemach rzeczywistych mamy do czynienia z bardzo skomplikowaną daną funkcją, dla której wyszukanie optimum globalnego lub w zadanym zakresie nie jest łatwe. Na przestrzeni lat stworzono wiele algorytmów wyszukiwania optimum (algorytmy optymalizacji) oraz rozwinął się nowy dział badań naukowych, nazywany badaniami operacyjnymi.

Matematyka (. Ponieważ ścisłe założenia mogą dotyczyć najróżniejszych dziedzin myśli ludzkiej, a muszą być czynione w naukach ścisłych, technice a nawet w naukach humanistycznych, zakres matematyki jest szeroki i stale się powiększa.

Kryterium sterowania - to kryteria określające dodatkowy warunek nałożony na ruch robota. Najczęściej dotyczą czasu, energii lub błędu sterowania i mają postać całki (sumy) po podanym przedziale czasu.

Optymalizacja statyczna i dynamiczna

Zadania optymalizacji dzielimy na dwie podstawowe klasy:

optymalizację statyczną (sprowadzającą się do poszukiwania ekstremum funkcji) oraz

optymalizację dynamiczną, sprowadzającą się do poszukiwania ekstremum funkcjonału.

Optymalizacja statyczna zajmuje się poszukiwaniem optymalnego punktu pracy, czyli takiego, w którym wartość funkcji celu jest najlepsza. Zależnie od sformułowania zadania będzie to wartość największa i najmniejsza, ale zawsze ekstremalna. Poszukiwanie ekstremum moze się odbywać w pewnym ograniczonym obszarze zawierającym tylko jedno ekstremum - mówimy wówczas o poszukiwaniu ekstremum lokalnego. Może też odbywać się w całej przestrzeni argumentów i wówczas mówimy o poszukiwaniu ekstremum globalnego. Zadanie nie zawsze udaje się rozwiązać poprawnie. Mimo bowiem istnienia ekstremum globalnego procedura poszukiwania może się zakończyć w punkcie będącym ekstremum lokalnym. 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.

Optymalizacja - metoda wyznaczania najlepszego (optymalnego) rozwiązania (poszukiwanie ekstremum funkcji) z punktu widzenia określonego kryterium (wskaźnika) jakości (np. kosztu, drogi, wydajności).

Wśród metod optymalizacji statycznej wyróżnia się dwie zasadnicze grupy: programowanie liniowe i programowanie nieliniowe. Programowanie liniowe polega na poszukiwaniu ekstremum liniowej funkcji celu przy ograniczeniach będących również funkcjami liniowymi. W zagadnieniach programowania liniowego ekstremum jest zawsze globalne w danym obszarze poszukiwań. Programowanie nieliniowe polega na poszukiwaniu ekstremum funkcji celu dowolnej postaci, przy ograniczeniach będących również wyrażonymi przez dowolne funkcje.

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.

Metody optymalizacji

metoda Newtona (optymalizacja)

przeszukiwanie tabu

wyszukiwanie binarne

programowanie liniowe

programowanie kwadratowe

algorytm punktu wewnętrznego

Zobacz też

optymalizacja

Zasada Maksimum Pontriagina

kryterium sterowania

sterowanie minimalno-kwadratowe