Nemlineáris programozás

A nemlineáris programozás (NLP) a matematikai programozás és az operációkutatás olyan ága, amely olyan optimalizálási feladatokkal foglalkozik, ahol a célfüggvény és/vagy legalább egy korlát a döntési változók nemlineáris függvénye.

Az NLP a lineáris programozás általánosítása, és lehetővé teszi a valós rendszerek és folyamatok szélesebb osztályának modellezését, ahol a változók közötti összefüggések nem szigorúan arányosak (azaz görbékkel, nem egyenes vonalakkal írhatók le).

Tárgy és rendeltetés

A nemlineáris programozást olyan helyzetekben alkalmazzák optimális megoldások keresésére, amikor:

• A célmutató (nyereség, költség, hatékonyság stb.) és a vezérelt paraméterek közötti összefüggés nemlineáris (például csökkenő léptékhozam, másodfokú költségek).
• Az erőforrásokra vagy technológiai folyamatokra vonatkozó korlátok nemlineáris összefüggésekkel írhatók le (például kémiai reakciók, fizikai törvények, gazdasági összefüggések).

NLP-feladatok számos területen merülnek fel:

• Mérnöki tervezés (szerkezetek és folyamatok optimalizálása).
• Közgazdaságtan és pénzügyek (portfólióoptimalizálás kockázattal, piaci modellezés).
• Vegyipari technológia (reaktorüzemmódok optimalizálása).
• Machine Learning (neurális hálózatok tanítása, support vector machine).
• Termelési folyamatok irányítása. Logisztika (nemlineáris költségek figyelembevételével).

Az NLP-feladat matematikai megfogalmazása

A nemlineáris programozás általános feladata a következőképpen fogalmazható meg:

Meg kell találni a döntési változók olyan értékkészletét, amely maximalizál vagy minimalizál egy nemlineáris célfüggvényt. A változók értékeinek eleget kell tenniük egy korlátrendszernek, amelyek kifejezhetők egyenlőtlenségek formájában (például „az A mennyiség kisebb vagy egyenlő B-vel"), valamint egyenlőségek formájában (például „a C mennyiség pontosan egyenlő D-vel"). Fontos, hogy a célt vagy a korlátokat leíró függvények közül legalább egy nemlineáris. Gyakran hozzáadják a változók nemnegatívitási feltételét is, azaz azt a követelményt, hogy értékeik nagyobbak vagy egyenlők legyenek nullával.

Az összes olyan változóértékkészlet, amely kielégíti a korlátokat, alkotja a megengedett megoldások tartományát (MMT).

Különbségek a lineáris programozástól

A nemlineáris programozás lényegesen különbözik a lineáris programozástól (LP):

• Nemlinearitás: A célfüggvény vagy a korlátok (vagy mindkettő) nemlineáris összefüggéseket tartalmaznak.
• Az MMT tulajdonságai: A megengedett megoldások tartománya NLP esetén nemkonvex lehet (szemben az LP-vel, ahol az MMT mindig konvex sokszög).
• Az optimum tulajdonságai: Az optimális megoldás NLP esetén nem feltétlenül az MMT csúcsában található, a tartomány határán vagy belsejében is elhelyezkedhet. NLP esetén létezhetnek lokális optimumok, amelyek nem globálisak.
• A megoldás összetettsége: Az NLP-feladatok általában lényegesen nehezebbek a megoldás szempontjából, mint az LP-feladatok. Nem létezik egyetlen univerzális algoritmus, amely az összes NLP-feladatra alkalmazható lenne, hasonlóan a szimplex-módszerhez.

Az NLP fő nehézségei és kihívásai

A nemlineáris programozási feladatok megoldása számos nehézséggel jár:

• Lokális szélsőértékek jelenléte: Az NLP-módszerek többsége csak lokális optimum (egy bizonyos környezetben legjobb megoldás) megtalálását garantálja. A globális optimum (az egész MMT-n legjobb megoldás) keresése összetett feladat, különösen nemkonvex problémák esetén.
• Nemkonvexitás: Ha a feladat nem konvex (a célfüggvény vagy az MMT nemkonvex), több lokális optimum is létezhet, és a szokásos gradiens módszerek ezek egyikébe „ragadhatnak".
• Számítási komplexitás: Az NLP megoldási algoritmusai gyakran lényegesen nagyobb számítási erőforrást igényelnek az LP-hez képest.

Az NLP feladatok fontos osztályai

Az általános összetettsége ellenére léteznek fontos NLP-feladatosztályok, amelyekre hatékony megoldási módszereket dolgoztak ki:

• Konvex programozás: Konvex függvény minimalizálása konvex megengedett megoldáshalmazon (vagy konkáv függvény maximalizálása). Kulcstulajdonság: bármely lokális minimum egyben globális minimum is. Ez jelentősen megkönnyíti az optimális megoldás keresését.
• Kvadratikus programozás: A célfüggvény másodfokú, és az összes korlát lineáris.
• Szeparábilis programozás: A célfüggvény és a korlátok olyan függvények összegeként ábrázolhatók, amelyek mindegyike csak egyetlen változótól függ.

Az NLP-feladatok megoldási módszerei

A nemlineáris programozási (NLP) feladatok megoldási módszerei

I. Feltétel nélküli optimalizálás módszerei (korlátozások nélküli optimalizálás):

• Gradiens módszerek (legmeredekebb ereszkedés módszere, konjugált gradiens módszer);
• Newton-módszer és kvázi-Newton módszerek (például BFGS);
• A Hesse-mátrix approximációját alkalmazó módszerek.

II. Feltételes optimalizálás módszerei (korlátozásokkal rendelkező optimalizálás):

• Transzformációs módszerek:
  • Büntetőfüggvény-módszer (penalty methods);
  • Barriersfüggvény-módszer (barrier methods).
• Közvetlen iránykeresési módszerek:
  • Lehetséges irányok módszere.
• Optimalitási feltételeken alapuló módszerek:
  • Karush–Kuhn–Tucker-módszerek (KKT-feltételek);
  • Lagrange-szorzók módszere.
• Iteratív módszerek:
  • Szekvenciális kvadratikus programozás (SQP);
  • Belső pont módszerek.

III. Globális optimalizálás módszerei:

• Heurisztikus és metaheurisztikus módszerek:
  • Genetikus algoritmusok;
  • Szimulált lehűtés (szimulált anneling);
  • Tabu search.
• Determinisztikus módszerek:
  • Elágazás és korlátok (branch and bound);
  • Speciális szerkezetű feladatok globális optimalizálási algoritmusai.

Irodalom

• Bazara, M.; Shetty, C. Nелинейное программирование. Теория и алгоритмы. — М.: Мир, 1982.
• Fiacco, A.; McCormick, G. Нелинейное программирование. Методы последовательной безусловной минимизации. — М.: Мир, 1972.
• Himmelblau, D. Прикладное нелинейное программирование. — М.: Мир, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Lásd még

• Operációkutatás
• Optimalizálás
• Lineáris programozás
• Konvex programozás
• Célfüggvény
• Korlátok
• Megengedett megoldások tartománya