Nonlinear Opt.: KKT- theorem 5: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Zeile 71: | Zeile 71: | ||
=== Lagrangian Function for a maximization Problem : === | === 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>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>) |
<nowiki>Or</nowiki> | <nowiki>Or</nowiki> | ||
Zeile 99: | Zeile 99: | ||
under the following constraints : | under the following constraints : | ||
− | <math>4x_1 +2x_2</math> ≤ <math>10</math> | + | <math>4x_1 +2x_2</math> ≤ <math>10</math> : <math>g_1(x_1,x_2)</math> |
− | <math>x_2</math> ≤ <math>15</math> | + | <math>x_2</math> ≤ <math>15</math> : <math>g_2(x_1,x_2)</math> |
− | <math>x_1+ x_2</math> ≥ <math>3</math> | + | <math>x_1+ x_2</math> ≥ <math>3</math> : <math>g_3(x_1,x_2)</math> |
<math>x_1, x_2</math> ≥ <math>0</math> | <math>x_1, x_2</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> | + | <math>g_3(x_1,x_2)</math> : <math>x_1+ x_2</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>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> | ||
+ | |||
+ | '''Primal Constraints :''' | ||
+ | |||
+ | Source | ||
+ | |||
+ | <math>\bullet</math> Repitutorium 2012/2013 | ||
+ | |||
+ | <math>\bullet</math> Skript Operations research | ||
+ | |||
+ | <math>\bullet</math> https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions | ||
+ | |||
+ | <math>\bullet</math> www.wm.uni-bayreuth.de//MGW_Buch/lLeseprobe_6_5hp.pdf |
Version vom 30. Juni 2013, 04:19 Uhr
Inhaltsverzeichnis
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 = (, …., )
s.t. (, ..., ) – b ≤0 bzw. (,. ..,) ≤ , ≥
; .
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 ∈ :
≤ ≤
Saddle Point Condition :
The slater condition is satisfied if there exists a ≥ 0 such that < 0
Minimizer :
If the vector is saddle point of , then is a minimizer of NLP.
Suppose that there exist a ≥0 s.t. < 0, 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.): \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.): \hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)
≤ ;
≥
≥
Nonlinear maximization problem
Given a nonlinear maximization problem:
Max = (, …., )
s.t. (, ..., ) – b ≤0 bzw. (,. ..,) ≤ , ≥
; .
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.): \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.): \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.): \hat \lambda_i \cdot \frac{\partial L}{\partial \lambda_i} = \hat \lambda_i \cdot g(\hat x)
≤ ;
≥
≥
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 :
≤ :
≤ :
≥ :
≥
can be ignored because of
: ≥ 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.): 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)
Primal Constraints :
Source
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