Nonlinear Opt.: KKT- theorem 5: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| (4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | + | '''Karush-Kuhn Tucker Theory (KKT-Theory) ''' | |
| + | |||
<nowiki>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.</nowiki> | <nowiki>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.</nowiki> | ||
| − | = | + | = Optimality conditions according to KKT-Theorem = |
| − | <nowiki> | + | <math>\bullet</math> <nowiki>Generalization of the Lagrangian condition</nowiki> |
| − | + | <math>\bullet</math> <nowiki>Take the inequality Constraints in consideration</nowiki> | |
| − | + | <math>\bullet</math> <nowiki>Necessary (even sufficient under certain preconditions) conditions which shall be satisfied by an extremizer of the Lagrangian function.</nowiki> | |
| − | = | + | = Nonlinear minimization problem = |
'''Consider the nonlinear optimization Problem :''' | '''Consider the nonlinear optimization Problem :''' | ||
| − | <nowiki>Min</nowiki> <math>z</math> = <math>f</math>(<math>x_1</math>, …., <math>x_n</math>) | + | <nowiki>Min</nowiki> <math>z</math> <math>=</math> <math>f</math>(<math>x_1</math>, …., <math>x_n</math>) |
| − | s.t. <math>h_i</math> (<math>x_1</math>, ...,<math>x_n</math> ) – b | + | s.t. <math>h_i</math> (<math>x_1</math>, ...,<math>x_n</math> ) – <math>b</math> <math>\le</math> <math>0</math> or <math>g_i</math>(<math>x_1</math>,. ..,<math>x_n</math>) <math>\le</math> <math>0</math> , <math>x_j</math> <math>\ge</math> <math>0</math> |
<math>i=1,...,m</math> ; <math>j=1,...,n</math>. | <math>i=1,...,m</math> ; <math>j=1,...,n</math>. | ||
| Zeile 21: | Zeile 22: | ||
<nowiki>f and g are continuously differentiable</nowiki> | <nowiki>f and g are continuously differentiable</nowiki> | ||
| − | + | == Lagrangian Function for a minimization Problem == | |
| − | <math>L(x;\lambda)</math> = <math>f</math>(<math>x_1</math>,…,<math>x_n</math>)+ <math>\sum_{k=1}^m\lambda_i</math> <math>g_i</math> (<math>x_1</math>,…,<math>x_n</math>) | + | <math>L(x;\lambda)</math> <math>=</math> <math>f</math>(<math>x_1</math>,…,<math>x_n</math>) <math>+</math> <math>\sum_{k=1}^m\lambda_i</math> <math>g_i</math> (<math>x_1</math>,…,<math>x_n</math>) |
<nowiki>Or</nowiki> | <nowiki>Or</nowiki> | ||
| Zeile 32: | Zeile 33: | ||
And <math>\lambda</math> ∈<math>R_+^m</math> : | And <math>\lambda</math> ∈<math>R_+^m</math> : | ||
| − | <math>L(\hat x,\lambda)</math> | + | <math>L(\hat x,\lambda)</math> <math>\le</math> <math>L(\hat x,\hat \lambda)</math> <math>\le</math> <math>L(x,\hat \lambda)</math> |
| − | == | + | == Saddle Point Condition : == |
| − | <nowiki>The slater condition is satisfied if there exists a</nowiki> <math>x</math> | + | <nowiki>The slater condition is satisfied if there exists a</nowiki> <math>x</math> <math>\ge</math> <math>0</math> <nowiki>such that</nowiki> <math>g(x)</math> <math><</math> 0 |
'''Minimizer :''' | '''Minimizer :''' | ||
| Zeile 42: | Zeile 43: | ||
<nowiki>If the vector</nowiki> <math>(\hat x;\hat \lambda)</math> is saddle point of <math>L(x,\lambda)</math>, <nowiki>then</nowiki> <math>\hat x</math> <nowiki>is a minimizer of NLP.</nowiki> | <nowiki>If the vector</nowiki> <math>(\hat x;\hat \lambda)</math> is saddle point of <math>L(x,\lambda)</math>, <nowiki>then</nowiki> <math>\hat x</math> <nowiki>is a minimizer of NLP.</nowiki> | ||
| − | <nowiki>Suppose that there exist a</nowiki> <math>x</math> | + | <nowiki>Suppose that there exist a</nowiki> <math>x</math> <math>\ge</math> <math>0</math> <nowiki>s.t.</nowiki> <math>g(x)</math> <math><</math> <math>0</math>, <nowiki>so the following KKT conditions are necessary for</nowiki> <math>(\hat x,\hat \lambda)</math> <nowiki>being a saddle point of</nowiki> <math>L(x;\lambda)</math> : |
| − | <math>\frac{\partial L}{\partial x_j}</math> = <math>\frac{\partial f}{\partial x_j}</math> <math>(\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x)</math> | + | <math>\frac{\partial L}{\partial x_j}</math> <math>=</math> <math>\frac{\partial f}{\partial x_j}</math> <math>(\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x)</math> <math>\ge</math> <math>0</math> ; <math>j=1,...,n</math>. |
| − | <math>\hat x \cdot \frac{\partial L}{\partial x_j}</math> = <math>\hat x \cdot \bigg( \frac{\partial f}{\partial x_j}</math> <math>(\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x) \bigg) </math> = <math>0</math> ; <math>j=1,...,n</math>. | + | <math>\hat x \cdot \frac{\partial L}{\partial x_j}</math> <math>=</math> <math>\hat x \cdot \bigg( \frac{\partial f}{\partial x_j}</math> <math>(\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x) \bigg) </math> <math>=</math> <math>0</math> ; <math>j=1,...,n</math>. |
| − | <math>\frac{\partial L}{\partial \lambda_i} = g(\hat x)</math> | + | <math>\frac{\partial L}{\partial \lambda_i} = g(\hat x)</math> <math>\le</math> <math>0</math> ; <math>i=1,...,m</math> |
| − | <math>\hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)</math> | + | <math>\hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)</math> <math>\le</math> <math>0</math> ; <math>i=1,...,m</math> |
| − | <math>\hat x</math> | + | <math>\hat x</math> <math>\ge</math> <math>0</math> |
| − | <math>\hat \lambda</math> | + | <math>\hat \lambda</math> <math>\ge</math> <math>0</math> |
| − | = | + | = Nonlinear maximization problem = |
'''Given a nonlinear maximization problem:''' | '''Given a nonlinear maximization problem:''' | ||
| − | <nowiki>Max</nowiki> <math>z</math> = <math>f</math>(<math>x_1</math>, …., <math>x_n</math>) | + | <nowiki>Max</nowiki> <math>z</math> <math>=</math> <math>f</math>(<math>x_1</math>, …., <math>x_n</math>) |
| − | s.t. <math>h_i</math> (<math>x_1</math>, ...,<math>x_n</math> ) – b | + | s.t. <math>h_i</math> (<math>x_1</math>, ...,<math>x_n</math> ) – <math>b</math> <math>\le</math> <math>0</math> or <math>g_i</math>(<math>x_1</math>,. ..,<math>x_n</math>) <math>\le</math> <math>0</math> , <math>x_j</math> <math>\ge</math> <math>0</math> |
<math>i=1,...,m</math> ; <math>j=1,...,n</math>. | <math>i=1,...,m</math> ; <math>j=1,...,n</math>. | ||
| Zeile 69: | Zeile 70: | ||
<nowiki>f and g are continuously differentiable</nowiki> | <nowiki>f and g are continuously differentiable</nowiki> | ||
| − | + | == Lagrangian Function for a maximization Problem == | |
| − | <math>L(x;\lambda)</math> = <math>f</math>(<math>x_1</math>,…,<math>x_n</math>) - <math>\sum_{k=1}^m\lambda_i</math> <math>g_i</math> (<math>x_1</math>,…,<math>x_n</math>) | + | <math>L(x;\lambda)</math> <math>=</math> <math>f</math>(<math>x_1</math>,…,<math>x_n</math>) <math>-</math> <math>\sum_{k=1}^m\lambda_i</math> <math>g_i</math> (<math>x_1</math>,…,<math>x_n</math>) |
<nowiki>Or</nowiki> | <nowiki>Or</nowiki> | ||
| Zeile 79: | Zeile 80: | ||
'''KKT-condition for a maximization problem.''' | '''KKT-condition for a maximization problem.''' | ||
| − | <math>\frac{\partial L}{\partial x_j}</math> = <math>\frac{\partial f}{\partial x_j}</math> <math>(\hat x)-\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x)</math> | + | <math>\frac{\partial L}{\partial x_j}</math> <math>=</math> <math>\frac{\partial f}{\partial x_j}</math> <math>(\hat x)-\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x)</math> <math>\le</math> <math>0</math> ; <math>j=1,...,n</math>. |
| − | <math>\hat x \cdot \frac{\partial L}{\partial x_j}</math> = <math>\hat x \cdot \bigg( \frac{\partial f}{\partial x_j}</math> <math>(\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x) \bigg) </math> = <math>0</math> ; <math>j=1,...,n</math>. | + | <math>\hat x \cdot \frac{\partial L}{\partial x_j}</math> <math>=</math> <math>\hat x \cdot \bigg( \frac{\partial f}{\partial x_j}</math> <math>(\hat x)+\sum_{j=1}^m \hat \lambda_i \cdot \frac{\partial g_i}{\partial x_j}(\hat x) \bigg) </math> <math>=</math> <math>0</math> ; <math>j=1,...,n</math>. |
| − | <math>\frac{\partial L}{\partial \lambda_i} = g(\hat x)</math> | + | <math>\frac{\partial L}{\partial \lambda_i} = g(\hat x)</math> <math>\le</math> <math>0</math> ; <math>i=1,...,m</math> |
| − | <math>\hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)</math> | + | <math>\hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)</math> <math>\le</math> <math>0</math> ; <math>i=1,...,m</math> |
| − | <math>\hat x</math> | + | <math>\hat x</math> <math>\ge</math> <math>0</math> |
| − | <math>\hat \lambda</math> | + | <math>\hat \lambda</math> <math>\ge</math> <math>0</math> |
| − | + | = Example = | |
Given the following optimization problem: | Given the following optimization problem: | ||
| Zeile 99: | Zeile 100: | ||
under the following constraints : | under the following constraints : | ||
| − | <math>4x_1 +2x_2</math> | + | <math>4x_1 +2x_2</math> <math>\le</math> <math>10</math> : <math>g_1(x_1,x_2)</math> |
| − | <math>x_2</math> | + | <math>x_2</math> <math>\le</math> <math>15</math> : <math>g_2(x_1,x_2)</math> |
| − | <math>x_1+ x_2</math> | + | <math>x_1+ x_2</math> <math>\ge</math> <math>3</math> : <math>g_3(x_1,x_2)</math> |
| − | <math>x_1, x_2</math> | + | <math>x_1, x_2</math> <math>\ge</math> <math>0</math> |
<math>g_2(x_1,x_2)</math> <nowiki>can be ignored because of</nowiki> <math>g_1(x_1,x_2)</math> | <math>g_2(x_1,x_2)</math> <nowiki>can be ignored because of</nowiki> <math>g_1(x_1,x_2)</math> | ||
| − | <math>g_3(x_1,x_2)</math> : <math>x_1+ x_2</math> | + | <math>g_3(x_1,x_2)</math> : <math>x_1+ x_2</math> <math>\ge</math> <math>3</math> <math>\Rightarrow</math> <math>x_1+ x_2-3</math> ≥ <math>0</math> |
| − | <math>\Rightarrow</math> <math>-(x_1+ x_2)+3</math> | + | <math>\Rightarrow</math> <math>-(x_1+ x_2)+3</math> <math>\le</math> <math>0</math> |
<math>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)</math> | <math>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)</math> | ||
| − | ''' | + | '''Formulate KKT-condition :''' |
| + | |||
| + | <nowiki>(1)</nowiki> <math>\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</math> <math>\ge</math> <math>0</math> | ||
| + | |||
| + | <math>\frac{\partial L}{\partial x_2} = 2x_1+4x_2-2+2\lambda_1-\lambda_2</math> <math>\ge</math> <math>0</math> | ||
| + | |||
| + | |||
| + | <nowiki>(2)</nowiki> <math>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)</math> <math>=</math> <math>0</math> | ||
| + | |||
| + | <math>x_2\cdot\frac{\partial L}{\partial x_2} = x_2\cdot(2x_1+4x_2-2+2\lambda_1-\lambda_2)</math> <math>=</math> <math>0</math> | ||
| + | |||
| + | |||
| + | <nowiki>(3)</nowiki> <math>\frac{\partial L}{\partial \lambda_1} = 4x_1+2x_2-10</math> <math>\le</math> <math>0</math> | ||
| + | |||
| + | <math>\frac{\partial L}{\partial \lambda_2} = -x_1-x_2+3</math> <math>\le</math> <math>0</math> | ||
| + | |||
| + | |||
| + | <nowiki>(4)</nowiki> <math>\lambda_1\cdot\frac{\partial L}{\partial \lambda_1} = \lambda_1\cdot(4x_1+2x_2-10)</math> <math>=</math> <math>0</math> | ||
| + | |||
| + | <math>\lambda_2\cdot\frac{\partial L}{\partial \lambda_2} = \lambda_2\cdot(-x_1-x_2+3)</math> <math>=</math> <math>0</math> | ||
| + | |||
| + | |||
| + | <nowiki>(5)</nowiki> <math>x_1,x_2</math> <math>\ge</math> <math>0</math> | ||
| + | |||
| + | |||
| + | We suspect that both constraints are active . Therefore <math>\frac{\partial L}{\partial \lambda_1}</math> , <math>\frac{\partial L}{\partial \lambda_2}</math> # <math>0</math> and the constraints <math>g_1 , g_3</math> are <math>0</math>. | ||
| + | |||
| + | <math>\lambda_1,\lambda_2</math> # <math>0</math> , <nowiki>(4)</nowiki> <math>\Rightarrow x_1 = \frac{5-x_2}{2}</math> | ||
| + | <math> \Rightarrow -(\frac{5-x_2}{2})-x_2+3</math> <math> \Rightarrow x_2 = 1</math> <nowiki>and</nowiki> <math>x_1 = 2</math> | ||
| + | |||
| + | <math>x_1</math> <nowiki>and</nowiki> <math>x_2</math> <nowiki>insert in</nowiki> <nowiki>(2)</nowiki> : | ||
| + | |||
| + | <math>2(4\cdot 2+2\cdot 1+4\lambda_1-\lambda_2) = 0</math> | ||
| + | |||
| + | <math>1(2\cdot 2+4\cdot 1+2\lambda_1-\lambda_2-2) = 0</math> | ||
| + | |||
| + | <nowiki>Solve the system of equations, get</nowiki> | ||
| + | |||
| + | <math>\lambda_1 = -1</math> <math>\le</math> <math>0</math>; <math>\lambda_2 = 4</math> <math>\ge</math> <math>0</math> | ||
| + | |||
| + | |||
| + | <nowiki>We suspect that the lower constraint is active and the upper is not ( Minimization Problem )and that</nowiki> <math>x_1,x_2</math> <math>></math> <math>0</math>. <nowiki>Therefore</nowiki> <math>\lambda_1 = 0</math> | ||
| + | |||
| + | <nowiki>(4)</nowiki> <math> \Rightarrow -x_1-x_2+3 = 0</math> <math> \Rightarrow x_1 = 3-x_2</math> | ||
| + | |||
| + | <math>x_1</math>, <math>\lambda_1</math> <nowiki>insert in (4)</nowiki> | ||
| + | |||
| + | <math> \Rightarrow x_2 = \frac{3}{2}</math> ''';''' <math>x_1 = \frac{3}{2}</math> ''';''' <math>\lambda_1 = 7</math> <math>></math> <math>0</math> | ||
| + | |||
| + | Check Primal Constraints <math>4\cdot \frac{3}{2}+2\cdot \frac{3}{2} = 9</math> <math>\le</math> <math>10</math> '''.''' the other is obviously fulfilled | ||
| + | |||
| + | <nowiki>Therefore</nowiki> <math>\bigg(\frac 32 ; \frac 32\bigg)</math> <nowiki>is KKT Point.</nowiki> | ||
| + | |||
| + | |||
| + | <math>\blacktriangleright</math> <nowiki>A Local optimum Point hast to be KKT-Point ( necessary )</nowiki> | ||
| + | |||
| + | <math>\blacktriangleright</math> <nowiki>But which one ?</nowiki> | ||
| + | |||
| + | <nowiki>The function</nowiki> <math>f(x_1,x_2)= x_1^2 + x_2^2 + (1-x_1-x_2)^2</math> <nowiki>is convex. We can check it with the Hessian matrix.</nowiki> | ||
| + | |||
| + | <math>H(x_1;x_2) = </math> <math>\begin{bmatrix} | ||
| + | 4 & 2\\ | ||
| + | 2 & 2 | ||
| + | \end{bmatrix}</math> | ||
| + | |||
| + | <nowiki>Therefore being KKT-Point is sufficient for being globally optimal (minimal ).</nowiki> | ||
| + | |||
| − | + | = Sources = | |
<math>\bullet</math> Repitutorium 2012/2013 | <math>\bullet</math> Repitutorium 2012/2013 | ||
Aktuelle Version vom 1. Juli 2013, 18:03 Uhr
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.
Inhaltsverzeichnis
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 (, …., )
s.t. (, ..., ) – Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
or (,. ..,) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
; .
f and g are continuously differentiable
Lagrangian Function for a minimization Problem
(,…,) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{k=1}^m\lambda_i
(,…,)
Or
A vector in is called saddle point of Lagrangian function , if it holds for all x ∈ And ∈ :
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
Saddle Point Condition :
The slater condition is satisfied if there exists a Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
such that 0
Minimizer :
If the vector is saddle point of , then is a minimizer of NLP.
Suppose that there exist a Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
s.t. , so the following KKT conditions are necessary for being a saddle point of :
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 ; .
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) ; .
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 ;
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 ;
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
Nonlinear maximization problem
Given a nonlinear maximization problem:
Max (, …., )
s.t. (, ..., ) – Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
or (,. ..,) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
; .
f and g are continuously differentiable
Lagrangian Function for a maximization Problem
(,…,) 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
(,…,)
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 ; .
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) ; .
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 ;
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 ;
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
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 ∈ ,
under the following constraints :
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \le
:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
can be ignored because of
: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
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.): \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
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
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
(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)
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)
(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
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
(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)
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)
(5) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
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}
# and the constraints are .
# , (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
and 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 ; Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \ge
We suspect that the lower constraint is active and the upper is not ( Minimization Problem )and that . Therefore
(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
, insert in (4)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow x_2 = \frac{3}{2}
; ;
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
. the other is obviously fulfilled
Therefore 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.
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
