nonlinear programming

nonlinear programming (tsz. nonlinear programmings)

1. (informatika) nemlineáris programozás

A nonlinear programming (rövidítve: NLP) olyan optimalizálási probléma, ahol a célfüggvény és/vagy a korlátok legalább egyike nem lineáris. Ez a programozási forma rendkívül fontos a való életbeli problémák többségénél, mert a legtöbb rendszer nem lineárisan viselkedik.

Egy általános nemlineáris programozási probléma alakja:

$${\displaystyle {\begin{aligned}{\text{Minimize / Maximize:}}\quad &f(x)\\{\text{subject to:}}\quad &g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&h_{j}(x)=0,\quad j=1,\dots ,p\\&x\in \mathbb {R} ^{n}\end{aligned}}}$$

• ${\textstyle f(x)}$: nemlineáris célfüggvény
• ${\textstyle g_{i}(x)}$: egyenlőtlenségi korlátok
• ${\textstyle h_{j}(x)}$: egyenlőségi korlátok
• ${\textstyle x}$: döntési változók vektora

A legtöbb reális döntési helyzet nem írható le lineárisan. Például:

• Gazdaság: csökkenő hozadék, nemlineáris költségek
• Mérnöki tudomány: energiafogyasztás, terhelés
• AI, gépi tanulás: veszteségfüggvények
• Logisztika, hálózatok: nemlineáris sebesség, késleltetés

Feladat:

Minimalizáld:

$${\displaystyle f(x,y)=x^{2}+y^{2}}$$

Korlát:

$${\displaystyle x+y\geq 1}$$

Ez egy konvex NLP – mert ${\textstyle f(x,y)}$ konvex, és a megengedett tartomány is az.

• Célfüggvény konvex, tartomány konvex → garantált globális minimum
• Jó algoritmusok léteznek rá (pl. belsőpontos módszerek)

• Több lokális minimum is lehet
• Nehéz megtalálni a globális optimumot

• Használható, ha a célfüggvény differenciálható
• Iteratív lépések a gradiens irányába

• Másodrendű derivált (Hesse-mátrix) használata
• Gyorsabb, de számításigényes

(Karush-Kuhn-Tucker conditions)

• Nemlineáris korlátokkal rendelkező problémák szükséges optimalitási feltételei
• Általánosítják a Lagrange-multiplikátorokat

• Szükséges nem konvex függvényekhez
• Példák: genetikus algoritmusok, szimulált hűtés, méhkolónia-optimalizálás

Tegyük fel, hogy minimalizálunk ${\textstyle f(x)}$-et, ahol:

• ${\textstyle g_{i}(x)\leq 0}$
• ${\textstyle h_{j}(x)=0}$

A KKT-feltételek:

1. Állandóság: ${\textstyle \nabla f+\sum \lambda _{i}\nabla g_{i}+\sum \mu _{j}\nabla h_{j}=0}$
2. Korlátok teljesülése: ${\textstyle g_{i}(x)\leq 0,h_{j}(x)=0}$
3. Komplementaritás: ${\textstyle \lambda _{i}g_{i}(x)=0}$
4. ${\textstyle \lambda _{i}\geq 0}$

#include <iostream>
#include <cmath>

double f(double x) {
    return x * x + 2 * x + 1;  // (x+1)^2 minimum x = -1
}

double df(double x) {
    return 2 * x + 2;
}

int main() {
    double x = 0; // kezdőpont
    double alpha = 0.1; // lépésköz
    int iter = 100;

    for (int i = 0; i < iter; ++i) {
        x = x - alpha * df(x);
    }

    std::cout << "Optimális x: " << x << ", f(x): " << f(x) << "\n";
    return 0;
}

• nonlinear programming - Szótár.net (en-hu)
• nonlinear programming - Sztaki (en-hu)
• nonlinear programming - Merriam–Webster
• nonlinear programming - Cambridge
• nonlinear programming - WordNet
• nonlinear programming - Яндекс (en-ru)
• nonlinear programming - Google (en-hu)
• nonlinear programming - Wikidata
• nonlinear programming - Wikipédia (angol)