Nonlinear Opt.: KKT- theorem 5

Karush-Kuhn Tucker Theory (KKT-Theory)

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

 Generalization of the Lagrangian condition

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

Take the inequality Constraints in consideration

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

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 $z$ $=$ $f$($x_{1}$, …., $x_{n}$)

s.t. $h_{i}$ ($x_{1}$, ...,$x_{n}$ ) – $b$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le

$0$ or  $g_{i}$($x_{1}$,. ..,$x_{n}$) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$    ,   $x_{j}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
$0$

$i=1,...,m$  ; $j=1,...,n$.

f and g are continuously differentiable

Lagrangian Function for a minimization Problem

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

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

Or

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

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

$L({\hat {x}},\lambda )$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le

$L({\hat {x}},{\hat {\lambda }})$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$L(x,{\hat {\lambda }})$

Saddle Point Condition :

The slater condition is satisfied if there exists a $x$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$0$ such that $g(x)$ $<$ 0

Minimizer :

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

Suppose that there exist a $x$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$0$ s.t. $g(x)$ $<$ $0$, so the following KKT conditions are necessary for $({\hat {x}},{\hat {\lambda }})$ being a saddle point of $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)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
$0$          ;       $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) 
$=$ $0$          ;       $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)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$      ;    $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)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$      ;    $i=1,...,m$

${\hat {x}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$0$

${\hat {\lambda }}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$0$

Nonlinear maximization problem

Given a nonlinear maximization problem:

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

s.t. $h_{i}$ ($x_{1}$, ...,$x_{n}$ ) – $b$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le

$0$ or  $g_{i}$($x_{1}$,. ..,$x_{n}$) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$    ,   $x_{j}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
$0$

$i=1,...,m$  ; $j=1,...,n$.

f and g are continuously differentiable

Lagrangian Function for a maximization Problem

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{k=1}^m\lambda_i
 $g_{i}$ ($x_{1}$,…,$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)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$          ;       $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) 
$=$ $0$          ;       $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)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$      ;    $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)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$      ;    $i=1,...,m$ 

${\hat {x}}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$0$

${\hat {\lambda }}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$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 $x_{1},x_{2}$  ∈ $R_{+}^{2}$ ,

under the following constraints :

$4x_{1}+2x_{2}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le

$10$  :  $g_{1}(x_{1},x_{2})$

$x_{2}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le

$15$         :   $g_{2}(x_{1},x_{2})$

$x_{1}+x_{2}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$3$     :   $g_{3}(x_{1},x_{2})$

$x_{1},x_{2}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$0$

$g_{2}(x_{1},x_{2})$ can be ignored because of $g_{1}(x_{1},x_{2})$

$g_{3}(x_{1},x_{2})$ : $x_{1}+x_{2}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$3$  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow
 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1+ x_2-3
≥ $0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -(x_1+ x_2)+3
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x_1,x_2,\lambda_1,\lambda_2) = x_1^2 + x_2^2 + (1-x_1-x_2)^2+\lambda_1(4x_1 +2x_2-10)+\lambda_2(-x_1 - x_2+3)

Formulate KKT-condition :

(1) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_1} = 2x_1+(-2)(1-x_1-x_2)+4\lambda_1-\lambda_2 = 4x_1+2x_2+4\lambda_1-\lambda_2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
$0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_2} = 2x_1+4x_2-2+2\lambda_1-\lambda_2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
$0$

(2) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1\cdot\frac{\partial L}{\partial x_1} = x_1\cdot(2x_1+(-2)(1-x_1-x_2)+4\lambda_1-\lambda_2) = x_1\cdot(4x_1+2x_2+4\lambda_1-\lambda_2)

$=$ $0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2\cdot\frac{\partial L}{\partial x_2} = x_2\cdot(2x_1+4x_2-2+2\lambda_1-\lambda_2)

$=$ $0$

(3) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda_1} = 4x_1+2x_2-10

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda_2} = -x_1-x_2+3

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$

(4) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_1\cdot\frac{\partial L}{\partial \lambda_1} = \lambda_1\cdot(4x_1+2x_2-10)

$=$ $0$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_2\cdot\frac{\partial L}{\partial \lambda_2} = \lambda_2\cdot(-x_1-x_2+3)

$=$ $0$

(5) $x_{1},x_{2}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge

$0$

We suspect that both constraints are active . Therefore Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda_1}

 , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda_2}
# $0$ and the constraints $g_{1},g_{3}$ are $0$.

$\lambda _{1},\lambda _{2}$ # $0$ , (4) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow x_1 = \frac{5-x_2}{2}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow -(\frac{5-x_2}{2})-x_2+3

  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):    \Rightarrow  x_2 = 1
 and $x_{1}=2$

$x_{1}$ and $x_{2}$ insert in (2) :

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2(4\cdot 2+2\cdot 1+4\lambda_1-\lambda_2) = 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1(2\cdot 2+4\cdot 1+2\lambda_1-\lambda_2-2) = 0

Solve the system of equations, get

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_1 = -1

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$0$;       $\lambda _{2}=4$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
$0$

We suspect that the lower constraint is active and the upper is not ( Minimization Problem )and that $x_{1},x_{2}$ $>$ $0$. Therefore $\lambda _{1}=0$

(4) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow -x_1-x_2+3 = 0

 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):   \Rightarrow x_1 = 3-x_2

$x_{1}$, $\lambda _{1}$ insert in (4)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow x_2 = \frac{3}{2}

; $x_{1}={\frac {3}{2}}$  ;  $\lambda _{1}=7$ $>$ $0$

Check Primal Constraints Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4\cdot \frac{3}{2}+2\cdot \frac{3}{2} = 9

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
$10$ . the other is obviously fulfilled

Therefore ${\bigg (}{\frac {3}{2}};{\frac {3}{2}}{\bigg )}$ is KKT Point.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \blacktriangleright

 A Local optimum Point hast to be KKT-Point ( necessary )

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \blacktriangleright

 But which one ?

The function 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

is convex. We can check it with the Hessian matrix. 

$H(x_{1};x_{2})=$ ${\begin{bmatrix}4&2\\2&2\end{bmatrix}}$

Therefore being KKT-Point is sufficient for being globally optimal (minimal ).

Sources

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

Repitutorium 2012/2013

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

Skript Operations research

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

www.wm.uni-bayreuth.de//MGW_Buch/lLeseprobe_6_5hp.pdf