Nelineární optimalizace

V optimalizaci , která je považována za obor matematiky , se nelineární optimalizace (anglicky: nelineární programování - NLP) zabývá hlavně optimalizačními problémy, jejichž data, tj. Funkce a množiny definující tyto problémy, jsou nelineární, ale jsou také tolikrát diferencovatelné nezbytné pro vytvoření teoretických nástrojů, jako jsou podmínky optimality , nebo pro řádné fungování rozlišovacích algoritmů, které jsou v nich zavedeny a analyzovány. Tato subdisciplína optimalizace s nedefinovanou hranicí a poněkud umělým úvodem má také svou existenci spojenou s komunitou vědců, kteří se specializují na tyto předměty, a s typem dosažených výsledků.

Doplňuje nehladkou (nebo nediferencovatelnou) optimalizaci , která je také spojena s komunitou specializovaných výzkumných pracovníků. Tyto dvě disciplíny, tvoří to, co se nazývá kontinuální optimalizaci , která sousedí další dílčí disciplíny jako kombinatorické (nebo diskrétní) optimalizace, stochastické optimalizace , atd .

Matematická formulace

Máme funkci s . Cílem je určit vektor x definovaný:

.

Ekvivalentně můžeme najít hodnotu, pro kterou je f maximální:

.

Metody řešení

Pokud je funkce konvexní nebo konkávní a sada omezení je konvexní, pak existují specializované metody, které se nazývají metody konvexní optimalizace .

Jinak existuje několik řešení. Například pomocí principu separace a vyhodnocení rozdělit a zpracovat několik parametrů samostatně.

Algoritmus lze také zastavit před dosažením úspěchu, pokud lze prokázat, že žádné následné řešení nebude lepší v rámci určité prahové hodnoty tolerance. Podmínky Karush-Kuhn-Tucker (KKT) zajišťují, že takto získané řešení je optimální.

Používáme algoritmy rozlišení, jako například:

Omezení

Pokud jsou omezení vyjádřena ve formě nerovností

lze použít metodu „logaritmické bariéry“. Pokud je ƒ funkce, kterou je třeba minimalizovat, definujeme funkci

když se tedy x přiblíží k hranici, hodnota ln ( h ) má sklon k –∞ , což penalizuje oblast. Provádíme několik vyhledávání tak, že μ směřujeme k 0.

Příklady

V dimenzi 2

Jednoduchý problém lze položit následovně:

x 1 ≥ 0 x 2 ≥ 0 x 1 2 + x 2 2 ≥ 1 x 1 2 + x 2 2 ≤ 2

kde se snažíme maximalizovat funkci

f ( x 1 , x 2 ) = x 1 + x 2

V dimenzi 3

Můžeme formulovat problém následovně:

x 1 2 - x 2 2 + x 3 2 ≤ 2 x 1 2 + x 2 2 + x 3 2 ≤ 10

kde se snažíme maximalizovat funkci:

f ( x 1 , x 2 , x 3 ) = x 1 x 2 + x 2 x 3

Poznámky a odkazy

  1. Numerická optimalizace , Mark S. Gockenbach, Michigan Tech

Podívejte se také

Související články

Bibliografie

externí odkazy

Dokumentace Implementace