Nonlinear Opt.: KKT- theorem 1
Introduction
The Karush-Kuhn-Tucker theorem (short: KKT-Theorem) is a way of nonlinear optimization. It is based on Lagrangian optimization. Beside the additional conditions of the Lagrangian attempt there are some other extra conditions which are called KKT-conditions. The aim of this theory is to solve a problem with additional conditions in form of inequaliities.
The first mention of the KKT-conditions was in the master thesis of William Karush in 1939. But it became more famous in 1951 where Harold W. Kuhn and Albert W. Tucker presented it in a conference paper.
KKT-Conditions
In the following chapter the conditions will be demonstrated in a mathematical form:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \frac{\delta L}{\delta x_{j}}= \frac{\delta f}{\delta x_{j}}\left ( \widehat{x} \right )+ \sum_{i=1}^{m} \widehat{\lambda_{i}}\cdot \frac{\delta g_{i}}{\delta x_{j}}\left ( \widehat{x} \right )\geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \widehat{x}\cdot \frac{\delta L}{\delta x_{j}}= \widehat{x}\cdot \left ( \frac{\delta f\left ( x \right )}{\delta x_{j}}+ \sum_{i=1}^{m}\widehat{\lambda _{i}}\cdot \frac{\delta g_{i}}{\delta x_{j}}\cdot \left ( \widehat{x} \right ) \right )=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \frac{\delta L}{\delta \lambda _{i}}=g_{i}\left ( \widehat{x} \right )\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (4)\widehat{\lambda _{i} }\cdot\frac{\delta L }{\delta \lambda _{i}}=\widehat{\lambda _{i}}\cdot g_{i}\left ( \widehat{x} \right )=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (5)\widehat{x}\geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (6)\widehat{\lambda }\geq 0
Langrangian function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\delta L}{\delta x_{j}}= \frac{\delta f}{\delta x_{j}}\left ( x \right )-\sum_{i=1}^{m}\lambda _{i}\frac{\delta g_{i}}{\delta x_{j}}\left ( x \right )
It exist a saddle point in if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L\left ( \widehat{x},\lambda \right )\leq L\left ( \widehat{x},\widehat{\lambda } \right )\leq L\left ( x,\widehat{\lambda } \right )
.
In general it holds that minimizes and maximizes
If the known Langrangian function is convex in x and concave in , so the KKT conditions are necessary and sufficient conditions for a seaddle point of
It doesn´t mean that every possible calculated candidate is an optimal solution for this problem.