A Karush-Kuhn-Tucker (KKT) feltételek nemlineáris optimalizálási feladatok megoldását biztosító feltételek. A problémakör a Lagrange multiplikátoros módszer általánosításának tekinthető. Míg a Lagrange multiplikátoros módszer olyan feltételes szélsőérték-keresési feladatok megfoldásánál alkalmazható, ahol a feltételek egyenlőség formájában vannak megfogalmazva, a KKT optimalizálásnál az egyenlőség típusú feltételek helyett vagy azok mellett egyenlőtlenség típusú feltételek (is) szerepelnek.

Tekintsük a következő nemlineáris optimalizálási feladatot egy $X\subseteq {ℝ}^N$ konvex tartománnyal. Legyen $f\left(x\right)$ $x\in X$ egy konvex^[10] folytonosan differenciálható függvény és legyenek a $g_i\left(x\right)$ i=1, …, M és a $h_j\left(x\right)=0$ j=1, …, L függvények affin^[11] függvények.

Keressük

$\begin{array}{l}\underset{x\in R^N}{\text{min}}f\left(x\right)\text{-et}\text{, }x\in \text{X úgy}\text{, hogy közben a}\\ g_i\left(x\right)\ge 0\text{ és a}\\ h_j\left(x\right)=0\text{ feltételek is teljesüljenek}\text{.}\end{array}$ (F.45)

Definiáljunk egy általánosított Lagrange függvényt a következő formában:

$L\left(x,\alpha ,\beta \right)=f\left(x\right)-{\displaystyle \sum _{i=1}^M{\alpha }_i}{g}_i\left(x\right)-{\displaystyle \sum _{j=1}^L{\beta }_j}{h}_j\left(x\right)$ (F. 46)

ahol ${\alpha }_i\ge 0$ és ${\beta }_j\in R$ Lagrange multiplikátorok.

Annak szükséges és elégséges feltétele, hogy egy $x^{\ast }\in \text{X}$ a fenti feladat optimuma legyen az, hogy létezzenek olyan $\left({\alpha }^{\ast },{\beta }^{\ast }\right)$ , ${\alpha }^{\ast }\in {\left[\mathrm{0,}\infty \right)}^M$ , ${\beta }^{\ast }\in R^L$ változók, hogy

$\begin{array}{l}{\nabla }_{x}L\left(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)=\frac{\partial L\left(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)}{\partial x}=0\\ {\nabla }_{\beta }L\left(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)=\frac{\partial L\left(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)}{\partial \beta }=0\\ {\alpha }_{{}_i}^{\ast }{g}_i\left(x^{\ast }\right)=\mathrm{0,}i=\text{1}\text{,}\dots \text{,}M\\ g_i\left(x^{\ast }\right)\ge \mathrm{0,}i=\text{1}\text{,}\dots \text{,}M\\ {\alpha }_{{}_i}^{\ast }\ge \mathrm{0,}i=\text{1}\text{,}\dots \text{,}M\end{array}$ , (F.47)

$\left(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)$ -ra igaz, hogy bármely $x\in R^N$ és $\alpha \in {\left[\mathrm{0,}\infty \right)}^M$ és $\beta \in R^L$ mellett

$L\left(x^{\ast },\alpha ,\beta \right)\le L\left(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)\le L\left(x,{\alpha }^{\ast },{\beta }^{\ast }\right)$ (F.48)

vagyis $x^{\ast }$ egy nyeregpont (saddle point).

Elsődleges és másodlagos feladat

Az SVM-nél felmerülő elsődleges (primal) optimalizálási feladat minimumkeresési feladat egyenlőtlenség típusú mellékfeltételekkel.

Keressük

$\begin{array}{l}\underset{x\in R^N}{\text{min}}f\left(x\right)\text{-et}\text{, }x\in \text{X úgy}\text{, hogy közben a}\\ g_i\left(x\right)\ge 0\text{ feltételek is teljesüljenek}\text{.}\end{array}$ (F.49)

A megfelelő általánosított Lagrange függvény

$L\left(x,\alpha \right)=f\left(x\right)-{\displaystyle \sum _{i=1}^M{\alpha }_i}{g}_i\left(x\right)$ (F.50)

Feltételezve, hogy $\left(x^{\ast },{\alpha }^{\ast }\right)$ egyértelmű minimum, minden rögzített $\alpha \ge 0$ mellett definiálható egy Lagrange függvény,

$Q\left(\alpha \right)\underset{x}{\text{:}=\text{min}}L\left(x,\alpha \right)$ (F.51)

mely egyedül $\alpha$ függvénye.

Ennek megfelelően megfogalmazható a duális (dual) optimalizálási feladat:

$\begin{array}{l}\text{maximalizáljuk }Q\left(\alpha \right)\text{-t}\\ \text{úgy hogy }{\alpha }_i\ge 0i=\text{1}\text{,2}\text{,}\dots \text{,}M,\end{array}$ (F.52)

ahol $Q\left(\alpha \right)\text{-t}$ duális kritériumfüggvénynek nevezzük. A duális feladat megoldása nem feltétlenül egyszerűbb, mint az eredeti feladat megoldása. A duális feladat előnye, hogy a duális kritériumfüggvény csak $\alpha$ függvénye.

Az SVM esetén a duális feladat az ${\alpha }_i$ Lagrange multiplikátorok kvadratikus függvénye.

$Q\left(\alpha \right)={\alpha }^{T}1-\frac{1}{2}{\alpha }^{T}K\alpha$ (F.53)

az ${\alpha }_i$ Lagrange multiplikátorokra vonatkozó feltételekkel: ${\alpha }_i\ge 0$ és ${\displaystyle {\sum }_{i=1}^P{\alpha }_i{d}_i}=0$ , ahol d_i i=1,2,…,P az SVM feladatnál megfogalmazott kívánt válaszokat jelöli. Az SVM duális feladatát kvadratikus programozással oldhatjuk meg.