Version vom 30. Juni 2013, 03:34 Uhr

Karush-Kuhn Tucker Theorie (KKT-Theorie) :

Karush-Kuhn Tucker Theorem (KKT-Theorem) is a mathematical Method to solve Nonlinear optimization problems with help of Lagrangian Function. It requires inequality constraints. The system of equations corresponding to the KKT conditions is usually not solved directly, except in the few special cases where a closed-form solution can be derived analytically.

Optimality conditions according to KKT-Theorem:

#Generalization of the Lagrangian condition #Take the inequality Constraints in consideration #Necessary (even sufficient under certain preconditions) conditions which shall be satisfied by an extremizer of the Lagrangian function.

Nonlinear minimization problem

Consider the nonlinear optimization Problem :

Min ${\displaystyle z}$ = ${\displaystyle f}$(${\displaystyle x_{1}}$, …., ${\displaystyle x_{n}}$)

s.t. ${\displaystyle h_{i}}$ (${\displaystyle x_{1}}$, ...,${\displaystyle x_{n}}$ ) – b ≤0 bzw. ${\displaystyle g_{i}}$(${\displaystyle x_{1}}$,. ..,${\displaystyle x_{n}}$) ≤ ${\displaystyle 0}$ , ${\displaystyle x_{j}}$ ≥ ${\displaystyle 0}$

${\displaystyle i=1,...,m}$  ; ${\displaystyle j=1,...,n}$.

f and g are continuously differentiable

Lagrangian Function for a minimization Problem :

${\displaystyle L(x;\lambda )}$ = ${\displaystyle f}$(${\displaystyle x_{1}}$,…,${\displaystyle x_{n}}$)+ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{k=1}^m\lambda_i

 ${\displaystyle g_{i}}$ (${\displaystyle x_{1}}$,…,${\displaystyle x_{n}}$)

Or

${\displaystyle L(x;\lambda )=f(x)+\lambda ^{T}g(x)}$

A vector ${\displaystyle ({\hat {x}},{\hat {\lambda }})}$ in ${\displaystyle R_{+}^{n+m}}$ is called saddle point of Lagrangian function ${\displaystyle L(x,\lambda )}$, if it holds for all x ∈${\displaystyle R_{+}^{n}}$ And ${\displaystyle \lambda }$ ∈${\displaystyle R_{+}^{m}}$ :

${\displaystyle L({\hat {x}},\lambda )}$ ≤ ${\displaystyle L({\hat {x}},{\hat {\lambda }})}$ ≤ ${\displaystyle L(x,{\hat {\lambda }})}$

Saddle Point Condition :

The slater condition is satisfied if there exists a ${\displaystyle x}$ ≥ 0 such that ${\displaystyle g(x)}$ < 0

Minimizer :

If the vector ${\displaystyle ({\hat {x}};{\hat {\lambda }})}$ is saddle point of ${\displaystyle L(x,\lambda )}$, then ${\displaystyle {\hat {x}}}$ is a minimizer of NLP.

Suppose that there exist a ${\displaystyle x}$ ≥0 s.t. ${\displaystyle g(x)}$ < 0, so the following KKT conditions are necessary for ${\displaystyle ({\hat {x}},{\hat {\lambda }})}$ being a saddle point of ${\displaystyle L(x;\lambda )}$ :

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_j}

= Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial f}{\partial x_j}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x)
≥ ${\displaystyle 0}$          ;       ${\displaystyle j=1,...,n}$.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat x \cdot \frac{\partial L}{\partial x_j}

= Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat x \cdot \bigg( \frac{\partial f}{\partial x_j}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x) \bigg) 
= ${\displaystyle 0}$          ;       ${\displaystyle j=1,...,n}$.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda_i} = g(\hat x)

≤ ${\displaystyle 0}$      ;    ${\displaystyle i=1,...,m}$                                                                  

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)

≤ ${\displaystyle 0}$      ;    ${\displaystyle i=1,...,m}$

${\displaystyle {\hat {x}}}$ ≥ ${\displaystyle 0}$

${\displaystyle {\hat {\lambda }}}$ ≥ ${\displaystyle 0}$

Nonlinear maximization problem

Given a nonlinear maximization problem:

Max ${\displaystyle z}$ = ${\displaystyle f}$(${\displaystyle x_{1}}$, …., ${\displaystyle x_{n}}$)

s.t. ${\displaystyle h_{i}}$ (${\displaystyle x_{1}}$, ...,${\displaystyle x_{n}}$ ) – b ≤0 bzw. ${\displaystyle g_{i}}$(${\displaystyle x_{1}}$,. ..,${\displaystyle x_{n}}$) ≤ ${\displaystyle 0}$ , ${\displaystyle x_{j}}$ ≥ ${\displaystyle 0}$

${\displaystyle i=1,...,m}$  ; ${\displaystyle j=1,...,n}$.

f and g are continuously differentiable

Lagrangian Function for a maximization Problem :

${\displaystyle L(x;\lambda )}$ = ${\displaystyle f}$(${\displaystyle x_{1}}$,…,${\displaystyle x_{n}}$)- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{k=1}^m\lambda_i

 ${\displaystyle g_{i}}$ (${\displaystyle x_{1}}$,…,${\displaystyle x_{n}}$)

Or

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x;\lambda)=f(x)-\lambda^T g(x)

KKT-condition for a maximization problem.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_j}

= Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial f}{\partial x_j}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (\hat x)-\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x)
≤ ${\displaystyle 0}$          ;       ${\displaystyle j=1,...,n}$.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat x \cdot \frac{\partial L}{\partial x_j}

= Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat x \cdot \bigg( \frac{\partial f}{\partial x_j}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x) \bigg) 
= ${\displaystyle 0}$          ;       ${\displaystyle j=1,...,n}$.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda_i} = g(\hat x)

≤ ${\displaystyle 0}$      ;    ${\displaystyle i=1,...,m}$                                                                  

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)

≤ ${\displaystyle 0}$      ;    ${\displaystyle i=1,...,m}$ 

${\displaystyle {\hat {x}}}$ ≥ ${\displaystyle 0}$

${\displaystyle {\hat {\lambda }}}$ ≥ ${\displaystyle 0}$

Example:

Given the following optimization problem:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): minf(x_1,x_2)= x_1^2 + x_2^2 + (1-x_1-x_2)^2

  with ${\displaystyle x_{1},x_{2}}$  ∈ ${\displaystyle R_{+}^{2}}$ ,

under the following constraints :

${\displaystyle 4x_{1}+2x_{2}}$ ≤ ${\displaystyle 10}$

${\displaystyle x_{2}}$ ≤ ${\displaystyle 15}$

${\displaystyle x_{1}+x_{2}}$ ≥ ${\displaystyle 3}$

${\displaystyle x_{1},x_{2}}$ ≥ ${\displaystyle 0}$

KKT-Conditions :

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_1,x_2)= x_1^2 + x_2^2 + (1-x_1-x_2)^2