Nelineární programování - Nonlinear programming

v matematika, nelineární programování (NLP) je proces řešení optimalizační problém kde jsou některá omezení nebo objektivní funkce nelineární. An optimalizační problém je jedním z výpočtů extrémů (maxim, minim nebo stacionárních bodů) an Objektivní funkce přes sadu neznámých reálné proměnné a podmíněné uspokojením a Systém z rovnosti a nerovnosti, souhrnně nazývané omezení. Je to dílčí pole matematická optimalizace která se zabývá problémy, které nejsou lineární.

Použitelnost

Typický ne-konvexní problém spočívá v optimalizaci přepravních nákladů výběrem ze souboru přepravních metod, z nichž jeden nebo více vykazuje úspory z rozsahu s různými propojitelnostmi a kapacitními omezeními. Příkladem může být přeprava ropných produktů na základě výběru nebo kombinace potrubí, železničních cisteren, silničních cisteren, říčních člunů nebo pobřežních tanků. Vzhledem k velikosti ekonomické dávky mohou mít nákladové funkce kromě plynulých změn i diskontinuity.

V experimentální vědě lze některé jednoduché analýzy dat (například přizpůsobení spektra součtu vrcholů známého umístění a tvaru, ale neznámé velikosti) provést lineárními metodami, ale obecně jsou tyto problémy také nelineární. Typicky má člověk teoretický model studovaného systému s proměnnými parametry a model experimentu nebo experimentů, které mohou mít také neznámé parametry. Jeden se snaží najít nejvhodnější numericky. V tomto případě často potřebujete míru přesnosti výsledku a také nejlepší přizpůsobení.

Definice

Nechat n, m, a p být kladná celá čísla. Nechat X být podmnožinou Rⁿ, nechť F, G_i, a h_j být funkce se skutečnou hodnotou na X pro každého i v {1, …, m} a každý j v {1, …, p}, s alespoň jedním z F, G_i, a h_j být nelineární.

Nelineární problém s minimalizací je optimalizační problém formuláře

${ displaystyle { begin {zarovnáno} { text {minimalizovat}} & f (x) { text {předmět}} & g_ {i} (x) leq 0 { text {pro každý}} i in {1, dotsc, m } & h_ {j} (x) = 0 { text {for each}} j in {1, dotsc, p } & x in X. end {zarovnáno}}}$

Nelineární problém maximalizace je definován podobným způsobem.

Možné typy sady omezení

Existuje několik možností pro povahu sady omezení, známé také jako proveditelná sada nebo proveditelný region.

An nemožné problém je ten, u kterého žádná sada hodnot pro výběr proměnných nesplňuje všechna omezení. To znamená, že omezení jsou vzájemně protichůdná a neexistuje žádné řešení; proveditelná sada je prázdná sada.

A proveditelný problém je ten, pro který existuje alespoň jedna sada hodnot pro vybrané proměnné splňující všechna omezení.

An neomezený problém je proveditelný problém, pro který lze objektivní funkci udělat lepší než jakákoli daná konečná hodnota. Neexistuje tedy žádné optimální řešení, protože vždy existuje proveditelné řešení, které poskytuje lepší objektivní hodnotu funkce než jakékoli dané navrhované řešení.

Metody řešení problému

Pokud je objektivní funkce konkávní (problém s maximalizací), nebo konvexní (problém s minimalizací) a sada omezení je konvexní, pak se program nazývá konvexní a obecné metody z konvexní optimalizace lze použít ve většině případů.

Pokud je objektivní funkce kvadratický a omezení jsou lineární, kvadratické programování jsou používány techniky.

Pokud je objektivní funkce poměr konkávní a konvexní funkce (v případě maximalizace) a omezení jsou konvexní, pak lze problém transformovat na konvexní optimalizační problém pomocí částečné programování techniky.

Pro řešení nekonvexních problémů je k dispozici několik metod. Jedním z přístupů je použití speciálních formulací problémů lineárního programování. Další metoda zahrnuje použití větev a svázaný techniky, kdy je program rozdělen do podtříd, které mají být řešeny konvexní (problém s minimalizací) nebo lineárními aproximacemi, které tvoří spodní hranici celkových nákladů v rámci dalšího členění. S následnými děleními se v určitém okamžiku získá skutečné řešení, jehož cena se rovná nejlepší dolní meze získané pro kterékoli z přibližných řešení. Toto řešení je optimální, i když možná není jedinečné. Algoritmus lze také zastavit dříve, s jistotou, že nejlepší možné řešení je v toleranci od nalezeného nejlepšího bodu; takové body se nazývají ε-optimální. Ukončení do ε-optimálních bodů je obvykle nutné k zajištění konečného ukončení. To je užitečné zejména u velkých, obtížných problémů a problémů s nejistými náklady nebo hodnotami, kde lze nejistotu odhadnout pomocí vhodného odhadu spolehlivosti.

Pod rozlišitelnost a omezení kvalifikace, Karush – Kuhn – Tucker (KKT) poskytnout nezbytné podmínky pro optimální řešení. Za konvexnosti jsou tyto podmínky také dostatečné. Pokud jsou některé funkce nediferencovatelné, subdiferenciální verzePodmínky Karush – Kuhn – Tucker (KKT) jsou dostupné.^[1]

Příklady

2-rozměrný příklad

Modrá oblast je proveditelný region. The tečnost vedení s proveditelnou oblastí představuje řešení. Linka je nejlépe dosažitelná vrstevnice (lokus s danou hodnotou objektivní funkce).

Jednoduchý problém (zobrazený na obrázku) lze definovat omezeními

X₁ ≥ 0

X₂ ≥ 0

X₁² + X₂² ≥ 1

X₁² + X₂² ≤ 2

s objektivní funkcí, která má být maximalizována

F(X) = X₁ + X₂

kde X = (X₁, X₂).

Trojrozměrný příklad

Tečnost horního povrchu s omezeným prostorem ve středu představuje řešení.

Další jednoduchý problém (viz diagram) lze definovat omezeními

X₁² − X₂² + X₃² ≤ 2

X₁² + X₂² + X₃² ≤ 10

s objektivní funkcí, která má být maximalizována

F(X) = X₁X₂ + X₂X₃

kde X = (X₁, X₂, X₃).

Viz také

• Křivka
• Minimalizace nejmenších čtverců
• Lineární programování
• nl (formát)
• Nelineární nejmenší čtverce
• Seznam optimalizačního softwaru
• Kvadraticky omezené kvadratické programování
• Werner Fenchel, který vytvořil základ pro nelineární programování

Reference

Další čtení

• Avriel, Mordechaj (2003). Nelineární programování: Analýza a metody. Dover Publishing. ISBN  0-486-43227-0.
• Bazaraa, Mokhtar S. a Shetty, C. M. (1979). Nelineární programování. Teorie a algoritmy. John Wiley & Sons. ISBN  0-471-78610-1.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerická optimalizace: Teoretické a praktické aspekty. Universitext (druhé přepracované vydání překladu z roku 1997, francouzské vydání). Berlín: Springer-Verlag. str. xiv + 490. doi:10.1007/978-3-540-35447-5. ISBN  3-540-35445-X. PAN  2265882.
• Luenberger, David G.; Ye, Yinyu (2008). Lineární a nelineární programování. International Series in Operations Research & Management Science. 116 (Třetí vydání.). New York: Springer. str. xiv + 546. ISBN  978-0-387-74502-2. PAN  2423726.
• Nocedal, Jorge a Wright, Stephen J. (1999). Numerická optimalizace. Springer. ISBN  0-387-98793-2.
• Jan Brinkhuis a Vladimir Tikhomirov, Optimalizace: Statistiky a aplikace2005, Princeton University Press

externí odkazy

• Glosář matematického programování