Karush-Kuhn-Takker feltételek

Az optimalizálás elméletében a Karush-Kuhn-Tucker feltételek ( Karush-Kuhn-Tucker feltételek , KKT) szükséges feltételek egy nemlineáris programozási probléma megoldásához . Ahhoz, hogy a megoldás optimális legyen, bizonyos szabályossági feltételeknek teljesülniük kell. A módszer a Lagrange-szorzó módszer általánosítása . Ezzel szemben a változókra vonatkozó megszorítások nem egyenletek , hanem egyenlőtlenségek .

Történelem

Kuhn és Tucker általánosította a Lagrange-szorzó módszert (az egyenlőségi megszorításokkal kapcsolatos problémák optimalitási kritériumainak megalkotására) egy általános nemlineáris programozási probléma esetére, amely egyenlőségi és egyenlőtlenségi megszorításokat is tartalmaz [1] .

A korlátokkal kapcsolatos problémák helyi minimumának szükséges feltételeit már régóta tanulmányozták. Az egyik fő a megszorítások átvitele a Lagrange által javasolt célfüggvényre. A Kuhn-Tucker feltételek is ebből az elvből származnak [2] .

A probléma leírása

A nemlineáris optimalizálás problémájában meg kell találni a többdimenziós változó értékét , minimalizálva a célfüggvényt: $x=(x^{{(1)}},...,x^{{(n)}})$

\min \limits _{{x\in X}}f(x)

olyan feltételek mellett, amikor a változóra egyenlőtlenség típusú megszorítások vonatkoznak: $x$

g_{i}(x)\leqslant 0,\;i=1\ldots m

és a vektorkomponensek nem negatívak [3] . $x$

William Karush dolgozatában megtalálta a szükséges feltételeket általános esetben, amikor a felállított feltételek tartalmazhatnak egyenleteket és egyenlőtlenségeket is. Tőle függetlenül Harold Kuhn és Albert Tucker ugyanerre a következtetésre jutott .

Szükséges feltételek egy függvény minimumához

Ha az előírt korlátozások mellett a probléma megoldása, akkor van olyan Lagrange-szorzóvektor , amely a következő feltételeket teljesíti a Lagrange-függvényre : ${\hat {x}}\in \arg \min f$ $\lambda \in \mathbb{R} ^{m}$ $L(x)=f(x)+\összeg _{{i=1}}^{m}\lambda _{i}g_{i}(x)$

állóképesség : ; $\min _{x}L(x)=L({\hat {x)))$
kiegészítő nem-merevség : ; $\lambda _{i}g_{i}({\hat {x)))=0,\;i=1\ldots m$
nonnegativitás : . $\lambda _{i}\geqslant 0,\;i=1\ldots m$

Elegendő feltételek egy függvény minimumához

A felsorolt szükséges feltételek a minimális funkcióhoz általános esetben nem elegendőek. Feltéve, hogy a és függvények konvexek, több lehetőség is van a további feltételekhez, amelyek elegendőek a Karush-Kuhn-Tucker tételből származó feltételekhez: $f$ ${\displaystyle g_{1},\dots ,g_{m))$

Egyszerű megfogalmazás

Ha egy megengedhető pont kielégíti a stacionaritás, a komplementer nem-merevség és a nem-negativitás feltételeit, valamint , akkor . ${\kalap {x}}$ $\lambda _{1}>0$ ${\hat {x}}\in \arg \min f$

Gyengébb feltételek

Ha egy megengedhető pontra teljesül a stacionaritás, a komplementer nem-merevség és a nem-negativitás, valamint ( Slater feltétel ) feltételei, akkor . ${\kalap {x}}$ $\exists {\tilde {x}}:g_{i}({\tilde {x}})<0,\;i=1\ldots m$ ${\hat {x}}\in \arg \min f$

Jegyzetek

↑ Kuhn-Tucker feltételek . Letöltve: 2011. február 7. Az eredetiből archiválva : 2011. január 24.. (határozatlan)
↑ Zhiliniskas A., Shaltyanis V. Keresd az optimumot: a számítógép kiterjeszti a lehetőségeket. — M.: Nauka, 1989, p. 76, ISBN 5-02-006737-7
↑ A kibernetika matematikai alapjai, 1980 , p. 253.

Lásd még

Operációkutatás

Irodalom

J. Hadley. Nemlineáris és dinamikus programozás. - M . : Mir, 1967. - 506 p.
Korshunov Yu. M. A kibernetika matematikai alapjai. - M . : Energia, 1980. - 424 p.