Theorie: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 1: | Zeile 1: | ||
| + | '''Karush-Kuhn-Tucker Theorem''' | ||
== Introduction == | == Introduction == | ||
| Zeile 8: | Zeile 9: | ||
<math>L(x,\lambda) = f(x_1 , ... , x_n ) - \sum_{i=0} ^k \lambda_i * g_i (x_1,...,x_n) </math>, where <math> f(x_1,...,x_n) </math> is the objective function and <math>g_i (x_1,...,x_n) = 0</math> are the constraints. | <math>L(x,\lambda) = f(x_1 , ... , x_n ) - \sum_{i=0} ^k \lambda_i * g_i (x_1,...,x_n) </math>, where <math> f(x_1,...,x_n) </math> is the objective function and <math>g_i (x_1,...,x_n) = 0</math> are the constraints. | ||
| − | The algebraic sign of <math> | + | |
| + | The algebraic sign of <math> \sum_{i=0} ^k \lambda_i * g_i (x_1,...,x_n)</math> depends on the state of the problem, for a maximization problem it is “-” for minimization “+“. | ||
| + | |||
| + | |||
| + | The first KKT Condition is the derivative of <math>L (x,\lambda)</math> after all <math>x_i</math>, which is equal to the gradient of <math>L (x,\lambda)</math>, <math>\nabla L (x,\lambda)</math> and it includes the inequality: | ||
| + | |||
| + | <math>1) \frac {\partial L}{\partial x_i} x_i - \sum_{i=0} ^j * \frac {\partial g_i}{\partial x_i} \leq 0 </math> | ||
| + | |||
| + | If the objective function has to be minimized instead, only the sign of <math>\frac {\partial L}{\partial x_i} x_i</math> changes. The reason therefore is easy to see,when reflecting the objective function on the abcissa.The graphic below clarifies this coherence. It is visible, that only the algebraic sign of <math> \frac {\partial f} {\partial x} </math> changes, because <math>\max f(x) </math> = <math> \min</math><math> -(f(x)) </math>. The restrictions (in this case <math>x \le 1</math> ) don’t change. | ||
| + | |||
| + | |||
| + | |||
| + | The second KKT constraint ensures, any x can not be less than 0, which is basically the non-negativity constraint. | ||
| + | |||
| + | <math>2) x_i * \frac {\partial L}{\partial x_i} = 0</math> | ||
| + | |||
| + | The third and fourth constraints are analog to the first and the second one, but this time for <math>\lambda </math>. | ||
| + | |||
| + | <math>3) \frac {\partial L} {\partial \lambda_j} \leq 0</math> | ||
| + | |||
| + | Analogue to the previous changes, when one face a minimization problem, the sign of <math>g_i</math> changes. | ||
| + | |||
| + | |||
| + | <math>4) \lambda_j * \frac {\partial L}{\partial \lambda_j} = 0</math> | ||
| + | And finally the non-negativity constraints: | ||
| + | |||
| + | <math> 5) x_i \geq 0 , i=1,...,n </math> | ||
| + | |||
| + | <math>6) \lambda_j \geq 0 , j = 1,...,k </math> | ||
| + | |||
| + | == Examples == | ||
| + | |||
| + | |||
| + | == Further Information == | ||
| + | If <math>f(x_1,...,x_n)</math> is concave and all <math>h_i(x_1,...,x_n)</math> are convex, the satisfaction of all KKT conditions is necessary and sufficient for a global optimum, if the Slater condition is satisfied to. This means, there exist an <math>x \in \R_{+}^n</math>, so that <math>g(x)<o</math> which means there is a point inside the solution space. | ||
Version vom 30. Juni 2013, 23:20 Uhr
Karush-Kuhn-Tucker Theorem
Inhaltsverzeichnis
Introduction
The Karush-Kuhn-Tucker (KKT) Theorem is a model of nonlinear optimization (NLP). The model is based on the Langrangian optimization, but considers inequality as part of the KKT constraints. The approach proofs the optimality of a (given) point concerning a nonlinear objective function. The satisfaction of KKT constraint is a necessary condition for a solution being optimal in NLP.
KKT Conditions
The six KKT condition are based on the Langrangian function of a random maximization (or minimization) problem.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x,\lambda) = f(x_1 , ... , x_n ) - \sum_{i=0} ^k \lambda_i * g_i (x_1,...,x_n) , where is the objective function and are the constraints.
The algebraic sign of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0} ^k \lambda_i * g_i (x_1,...,x_n)
depends on the state of the problem, for a maximization problem it is “-” for minimization “+“.
The first KKT Condition is the derivative of after all , which is equal to the gradient of , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \nabla L (x,\lambda)
and it includes the inequality:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1) \frac {\partial L}{\partial x_i} x_i - \sum_{i=0} ^j * \frac {\partial g_i}{\partial x_i} \leq 0
If the objective function has to be minimized instead, only the sign of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac {\partial L}{\partial x_i} x_i
changes. The reason therefore is easy to see,when reflecting the objective function on the abcissa.The graphic below clarifies this coherence. It is visible, that only the algebraic sign of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac {\partial f} {\partial x}
changes, because = Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -(f(x))
. The restrictions (in this case Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \le 1
) don’t change.
The second KKT constraint ensures, any x can not be less than 0, which is basically the non-negativity constraint.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2) x_i * \frac {\partial L}{\partial x_i} = 0
The third and fourth constraints are analog to the first and the second one, but this time for .
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3) \frac {\partial L} {\partial \lambda_j} \leq 0
Analogue to the previous changes, when one face a minimization problem, the sign of changes.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4) \lambda_j * \frac {\partial L}{\partial \lambda_j} = 0
And finally the non-negativity constraints:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 5) x_i \geq 0 , i=1,...,n
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 6) \lambda_j \geq 0 , j = 1,...,k
Examples
Further Information
If is concave and all are convex, the satisfaction of all KKT conditions is necessary and sufficient for a global optimum, if the Slater condition is satisfied to. This means, there exist an Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \in \R_{+}^n , so that which means there is a point inside the solution space.
