Nonlinear Opt.: Lagrangian condition 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Theory) |
(→Detailed Solution process with explanation) |
||
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 83: | Zeile 83: | ||
== ''Example'' == | == ''Example'' == | ||
− | Tom Müller | + | Tom Müller has to plan the transportation of a product wich might be transported in three different ways to three different stations. The cost for transportation with possibility A to Station A is equal to 2x², for transportation with possibility B to Station B is equal to 4x² and for transportation with possibility C to Station C is equal to 6x² , where x denotes the quantity of the product. The only things he knows: The sum of Station A and station B is A 30 units and the sum of Station B and Station C is 10. How can the total costs be minimized? |
== ''Presentation of the problem'' == | == ''Presentation of the problem'' == | ||
− | We decided the following variables: | + | ''We decided the following variables'': |
transportation to Station A= <math>x_1</math> | transportation to Station A= <math>x_1</math> | ||
Zeile 102: | Zeile 102: | ||
− | ''' | + | '''Constraints:''' |
Zeile 111: | Zeile 111: | ||
<math>x_1,x_2,x_3 \geq0 </math> | <math>x_1,x_2,x_3 \geq0 </math> | ||
− | <math>f(x_1,x_2,x_3)</math>, <math>g_1(x_1,x_2,x_3)</math> and <math>g_2(x_1,x_2,x_3)</math>are continuously differentiable. | + | <math>f(x_1,x_2,x_3)</math>, <math>g_1(x_1,x_2,x_3)</math> and <math>g_2(x_1,x_2,x_3)</math> are continuously differentiable. |
== ''Detailed Solution process with explanation'' == | == ''Detailed Solution process with explanation'' == | ||
− | '''Step 1:''' Transform all | + | |
+ | '''Step 1:''' Transform all constraints to the following form: <math>g_i(x_1,...,x_n)-b=0</math> | ||
Zeile 209: | Zeile 210: | ||
\end{pmatrix} = 0 \Leftrightarrow (2-\lambda)(4-\lambda)(6-\lambda)=0 \Rightarrow \lambda_1=2,\lambda_2=4,\lambda_3=6</math> | \end{pmatrix} = 0 \Leftrightarrow (2-\lambda)(4-\lambda)(6-\lambda)=0 \Rightarrow \lambda_1=2,\lambda_2=4,\lambda_3=6</math> | ||
− | All eigenvalues are > 0 that means the function is convex | + | All eigenvalues are > 0 that means the function is convex and the solution we found is a Minimum |
== ''Sources'' == | == ''Sources'' == |
Aktuelle Version vom 28. Juni 2013, 12:50 Uhr
Inhaltsverzeichnis
Theory
The Lagrangian condition is an method to solve nonlinear Optimizaion Problems that has only equations as constraints.
Such an problem is corresponding to en extremevalue problem with several variables and several constraints. From the analysis we know that it is possible to include the constraints in the objective function.
When we use the Lagrangian method we create new scalar variables (Lagrange-multiplies) for each constraint (),what reduces our Problem with constraints to a problem without constraints.
Supose we want to maximize a funktion with a constant c for which a constraint exists. A point (x,y) can only be a solution for our optimization problem, if the movement on the contour line g=c is tangential to .
The constant lagrangian multipliers are neccesary because the gradients should be parallel but can have a different length.
If you want to use the Lagrangian method your problem should be in the following form:
Objective funktion: or Constraits: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_j \geq0
Where and are continuously differentiable.
Now you can use the following Algorithm to solve your Problem:
Step 1:
Transform all constraints to the following form:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_i(x_1,...,x_n)-b=0
Step 2: Build the Lagrangian function
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x_1,...x_n,\lambda _1,...\lambda _m)=f(x_1,...X_n)-\sum_{i=1}^{m}{\lambda _i*g_i(x_1,...x_n)}
Step 3: Build all partial derivatives
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{dx_j}L(x_1,...x_n,\lambda _1,...\lambda _m)\forall j=1,...,n
and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{d\lambda _i}L(x_1,...x_n,\lambda _1,...\lambda _m)\forall i=1,...,m
Step 4: Set all partial derivatives=0 and find a solution for system of equations
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{dx_i}L(x_1,...x_n,\lambda _1,...\lambda _m)=0\forall i=1,...,n
and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{d\lambda _j}L(x_1,...x_n,\lambda _1,...\lambda _m)=0 \forall j=1,...,m and solve it
Step 5:
Build the Hessian Matrix
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x_1,...,x_n=)\begin{pmatrix} \frac{d}{dx_1,dx_1}L^2(x_1,..x_n,\lambda _1,...,\lambda _m) & \cdots & \frac{d}{dx_1,dx_n}L^2(x_1,..x_n,\lambda _1,...,\lambda _m)\\ \vdots & \ddots & \vdots\\ \frac{d}{dx_n,dx_1}L^2(x_1,..x_n,\lambda _1,...,\lambda _m) & \cdots & \frac{d}{dx_n,dx_n}L^2(x_1,..x_n,\lambda _1,...,\lambda _m) \end{pmatrix}
Step 6: Check if the function is convex for a minimum function or if the function is concave for a maximum funktion. Therefor you have to calculate the eigenvalues of the Hessian-matrix, espacially that means you have to find all solutions for:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \det (H(x_1,...x_n)-\lambda *I)=0
If all eigenvalues are >0, then the funktion is convex, and if all eigenvalues are <0, then the funktion is concave.
Example
Tom Müller has to plan the transportation of a product wich might be transported in three different ways to three different stations. The cost for transportation with possibility A to Station A is equal to 2x², for transportation with possibility B to Station B is equal to 4x² and for transportation with possibility C to Station C is equal to 6x² , where x denotes the quantity of the product. The only things he knows: The sum of Station A and station B is A 30 units and the sum of Station B and Station C is 10. How can the total costs be minimized?
Presentation of the problem
We decided the following variables:
transportation to Station A=
transportation to Station B=
transportation to Station C=
Objective funktion:
Constraints:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2,x_3 \geq0
, and are continuously differentiable.
Detailed Solution process with explanation
Step 1: Transform all constraints to the following form: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_i(x_1,...,x_n)-b=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_1(x_1,x_2,x_3)=x_1+x_2-30=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_2(x_1,x_2,x_3)=x_2+x_3-10=0
Step 2: Build the Lagrangian function
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x_1,x_2,x_3,\lambda _1,\lambda _2)=f(x_1,x_2,x_3)-\sum_{i=1}^{2}{\lambda _i*g_i(x_1,x_2,x_3)}2x_1^{2}+4x_2^{2}+6x_3^{2}-\lambda _1*(x_1+x_2-30)-\lambda _2*(x_2+x_3-10)
Step 3: Build all partial derivatives
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{dx_1}L(x_1,x_2,x_3,\lambda _1,\lambda _2)=\frac{d}{dx_1}2x_1^{2}+4x_2^{2}+6x_3^{2}-\lambda _1*(x_1+x_2-30)-\lambda _2*(x_2+x_3-10)=2x_1-\lambda _1
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{dx_2}L(x_1,x_2,x_3,\lambda _1,\lambda _2)=\frac{d}{dx_2}2x_1^{2}+4x_2^{2}+6x_3^{2}-\lambda _1*(x_1+x_2-30)-\lambda _2*(x_2+x_3-10)=4x_2-\lambda _1-\lambda _2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{dx_3}L(x_1,x_2,x_3,\lambda _1,\lambda _2)=\frac{d}{dx_3}2x_1^{2}+4x_2^{2}+6x_3^{2}-\lambda _1*(x_1+x_2-30)-\lambda _2*(x_2+x_3-10)=6x_3-\lambda _2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{d\lambda _1}L(x_1,x_2,x_3,\lambda _1,\lambda _2)=\frac{d}{d\lambda _1}2x_1^{2}+4x_2^{2}+6x_3^{2}-\lambda _1*(x_1+x_2-30)-\lambda _2*(x_2+x_3-10)=x_1+x_2-30
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{d}{d\lambda _2}L(x_1,x_2,x_3,\lambda _1,\lambda _2)=\frac{d}{d\lambda _2}2x_1^{2}+4x_2^{2}+6x_3^{2}-\lambda _1*(x_1+x_2-30)-\lambda _2*(x_2+x_3-10)=x_2+x_3-10
Step 4: Set all partial derivatives=0 and find a solution for system of equations
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): I:2x_1-\lambda _1=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): II:4x_2-\lambda _1-\lambda _2=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): III:6x_3-\lambda _2=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): IV: x_1+x_2-30=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): V: x_2+x_3-10=0
Solve
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): IV: x_1=30-x_2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): V: x_3=10-x_2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): IV,V in VI: 4x_2=2(30-x_2)+6(10-x_2)\Leftrightarrow 4x_2=60-2x_2+60-6x_2\Leftrightarrow 12x_2=120\Leftrightarrow x_2=10
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): IV: x_1=30-x_2\Leftrightarrow x_1=30-10 =20
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): V: x_3=10-x_2 \Leftrightarrow x_3=10-10=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): I: 2x_1=\lambda _1 \Leftrightarrow 2*20= \lambda _1=40
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): III: 6x_3=\lambda _2 \Leftrightarrow 6*0=\lambda _2=0
solution:
Step 5: Build the Hessian Matrix
Step 6: Check if the function is convex for a minimum function or if the function is concave for a maximum funktion.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \det (H(x_1,...x_n)-\lambda *I)\Leftrightarrow \begin{pmatrix} 2-\lambda & 0 & 0\\ 0 & 4-\lambda & 0\\ 0 & 0 & 6-\lambda \end{pmatrix} = 0 \Leftrightarrow (2-\lambda)(4-\lambda)(6-\lambda)=0 \Rightarrow \lambda_1=2,\lambda_2=4,\lambda_3=6
All eigenvalues are > 0 that means the function is convex and the solution we found is a Minimum
Sources
Script of Operations Research 2013 , Part 3
Repertitorium of Operations Research WS 2012
Mathematik für Ingenieure: Eine anschauliche Einführung für das praxisorientierte Studium (Springer-Lehrbuch)
Operations Research, Neumann,Morlock
http://massmatics.de/de/files/2012/09/Lagrangeoptimierung-v1.0.pdf
http://www.mathe-online.at/materialien/klaus.berger/files/Matrizen/eigenwerte.pdf