Nelineární programování

Nelineární programování (NLP) — je odvětví matematického programování a operačního výzkumu, které se zabývá úlohami optimalizace, kde účelová funkce a/nebo alespoň jedno z omezení jsou nelineárními funkcemi rozhodovacích proměnných.

NLP je zobecněním lineárního programování a umožňuje modelovat širší třídu reálných systémů a procesů, kde závislosti mezi proměnnými nejsou striktně proporcionální (tj. jsou popsány křivkami, nikoli přímkami).

Předmět a účel

Nelineární programování se používá k nalezení optimálních řešení v situacích, kdy:

• Závislost cílového ukazatele (zisku, nákladů, efektivity atd.) na řízených parametrech je nelineární (například klesající výnosy z rozsahu, kvadratické náklady).
• Omezení zdrojů nebo technologických procesů jsou popsána nelineárními vztahy (například chemické reakce, fyzikální zákony, ekonomické závislosti).

Úlohy NLP se vyskytují v mnoha oblastech:

• Inženýrský návrh (optimalizace konstrukcí, procesů).
• Ekonomika a finance (optimalizace portfolia s ohledem na riziko, modelování trhu).
• Chemická technologie (optimalizace režimů reaktorů).
• Machine Learning (trénování neuronových sítí, metoda podpůrných vektorů).
• Řízení výrobních procesů. Logistika (s ohledem na nelineární náklady).

Matematická formulace úlohy NLP

Obecná úloha nelineárního programování je formulována takto:

Je třeba nalézt sadu hodnot rozhodovacích proměnných, která maximalizuje nebo minimalizuje nelineární účelovou funkci. Přitom hodnoty proměnných musí splňovat soustavu omezení, která mohou být vyjádřena jak ve formě nerovností (například „hodnota A musí být menší nebo rovna B"), tak ve formě rovností (například „hodnota C se musí přesně rovnat D"). Důležité je, že alespoň jedna z funkcí popisujících cíl nebo omezení je nelineární. Často se přidávají podmínky nezápornosti proměnných, tedy požadavek, aby jejich hodnoty byly větší nebo rovny nule.

Množina všech sad hodnot proměnných splňujících omezení tvoří oblast přípustných řešení (OPŘ).

Rozdíly oproti lineárnímu programování

Nelineární programování se podstatně liší od lineárního programování (LP):

• Nelinearita: Účelová funkce nebo omezení (nebo obojí) obsahují nelineární závislosti.
• Vlastnosti OPŘ: Oblast přípustných řešení v NLP může být nevypuklá (na rozdíl od LP, kde OPŘ je vždy vypuklý mnohostěn).
• Vlastnosti optima: Optimální řešení v NLP nemusí ležet ve vrcholu OPŘ, může ležet na hranici nebo uvnitř oblasti. V NLP mohou existovat lokální optima, která nejsou globálními optimy.
• Složitost řešení: Úlohy NLP jsou zpravidla výrazně obtížnější k řešení než úlohy LP. Neexistuje žádný jednotný univerzální algoritmus analogický simplexové metodě pro všechny úlohy NLP.

Hlavní obtíže a výzvy NLP

Řešení úloh nelineárního programování je spojeno s řadou obtíží:

• Existence lokálních extrémů: Většina metod NLP zaručuje nalezení pouze lokálního optima (řešení, které je nejlepší v určitém okolí). Hledání globálního optima (nejlepšího řešení v celé OPŘ) je složitá úloha, zejména pro nevypuklé problémy.
• Nevypuklost: Pokud úloha není vypuklá (účelová funkce nebo OPŘ jsou nevypuklé), může existovat mnoho lokálních optim a standardní gradientní metody se mohou „uvíznout" v jednom z nich.
• Výpočetní složitost: Algoritmy pro řešení NLP často vyžadují výrazně větší výpočetní zdroje ve srovnání s LP.

Důležité třídy úloh NLP

Navzdory obecné složitosti existují důležité podtřídy úloh NLP, pro které byly vyvinuty účinné metody řešení:

• Vypuklé programování: Úloha minimalizace vypuklé funkce na vypuklé množině přípustných řešení (nebo maximalizace konkávní funkce). Klíčová vlastnost: každé lokální minimum je zároveň globálním minimem. To výrazně zjednodušuje hledání optimálního řešení.
• Kvadratické programování: Účelová funkce je kvadratická a všechna omezení jsou lineární.
• Separabilní programování: Účelová funkce a omezení mohou být vyjádřeny jako součty funkcí, z nichž každá závisí pouze na jedné proměnné.

Metody řešení úloh NLP

Metody řešení úloh nelineárního programování (NLP)

I. Metody bezpodmínkové optimalizace (optimalizace bez omezení):

• Gradientní metody (metoda nejstrmějšího sestupu, metoda sdružených gradientů);
• Newtonova metoda a kvazi-newtonovské metody (například BFGS);
• Metody využívající aproximaci Hessiánu.

II. Metody podmíněné optimalizace (optimalizace s omezeními):

• Transformační metody:
  • Metoda penalizačních funkcí (penalty methods);
  • Metoda bariérových funkcí (barrier methods).
• Metody přímého hledání směrů:
  • Metoda přípustných směrů.
• Metody založené na podmínkách optimality:
  • Metody Karuše-Kuhna-Tuckera (KKT-podmínky);
  • Metoda Lagrangeových multiplikátorů.
• Iterační metody:
  • Sekvenční kvadratické programování (SQP);
  • Metody vnitřních bodů.

III. Metody globální optimalizace:

• Heuristické a metaheuristické metody:
  • Genetické algoritmy;
  • Simulované žíhání;
  • Prohledávání se zákazem (tabu search).
• Deterministické metody:
  • Větvení a ohraničení (branch and bound);
  • Algoritmy globální optimalizace pro úlohy se speciální strukturou.

Literatura

• Bazara M., Šetty K. Nelineární programování. Teorie a algoritmy. — M.: Mir, 1982.
• Fiakko A., Mak-Kormik G. Nelineární programování. Metody sekvenční bezpodmínkové minimalizace. — M.: Mir, 1972.
• Chimmelblau D. Aplikované nelineární programování. — M.: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Viz také

• Operační výzkum
• Optimalizace
• Lineární programování
• Vypuklé programování
• Účelová funkce
• Omezení
• Oblast přípustných řešení