Nonlinear Opt.: Lagrangian condition 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
(→Theory) |
(→Detailed Solution process with explanation) |
||
| (12 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
== ''Theory'' == | == ''Theory'' == | ||
| − | The Lagrangian condition is an method to solve | + | [[Datei:Lagrange-Wikipedia.png|280px|thumb|right|Contour map: The red line shows the constraint g(x,y)=c. The blue lines are contours of f(x,y). The point where the red line tangentially touches a blue contour is our solution.Since d_1>d_2, the solution is a |
| + | maximization of f(x,y)]] The Lagrangian condition is an method to solve nonlinear Optimizaion Problems that has only equations as constraints. | ||
| − | + | ||
| − | Objective funktion: | + | |
| + | 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 (<math>\lambda _1...\lambda _n</math>),what reduces our Problem with constraints to a problem without constraints. | ||
| + | |||
| + | |||
| + | Supose we want to maximize a funktion <math>f(x,y)</math> with a constant c for which a constraint<math>g(x,y)=c</math> 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 <math>f(x,y)=d</math>. | ||
| + | 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''': | ||
<math>\min z =f(x_1,...,x_n)</math> or <math>\max z =f(x_1,...,x_n)</math> | <math>\min z =f(x_1,...,x_n)</math> or <math>\max z =f(x_1,...,x_n)</math> | ||
| − | Constraits: | + | '''Constraits''': |
<math>g_i(x_1,...,x_n )=b</math> | <math>g_i(x_1,...,x_n )=b</math> | ||
<math>x_j \geq0 </math> | <math>x_j \geq0 </math> | ||
| Zeile 15: | Zeile 31: | ||
Where <math>f(x_1,...,x_n)</math> and <math>g_i(x_1,...,x_n )</math> are continuously differentiable. | Where <math>f(x_1,...,x_n)</math> and <math>g_i(x_1,...,x_n )</math> are continuously differentiable. | ||
| − | + | Now you can use the following Algorithm to solve your Problem: | |
| − | Step 1: | + | '''Step 1''': |
| − | Transform all | + | Transform all constraints to the following form: |
| − | |||
| − | |||
| − | Step 3: | + | <math>g_i(x_1,...,x_n)-b=0</math> |
| + | |||
| + | |||
| + | '''Step 2:''' | ||
| + | Build the Lagrangian function | ||
| + | |||
| + | |||
| + | <math>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)}</math> | ||
| + | |||
| + | |||
| + | '''Step 3:''' | ||
Build all partial derivatives | Build all partial derivatives | ||
| + | |||
<math>\frac{d}{dx_j}L(x_1,...x_n,\lambda _1,...\lambda _m)\forall j=1,...,n</math> and <math>\frac{d}{d\lambda _i}L(x_1,...x_n,\lambda _1,...\lambda _m)\forall i=1,...,m</math> | <math>\frac{d}{dx_j}L(x_1,...x_n,\lambda _1,...\lambda _m)\forall j=1,...,n</math> and <math>\frac{d}{d\lambda _i}L(x_1,...x_n,\lambda _1,...\lambda _m)\forall i=1,...,m</math> | ||
| − | Step 4: | + | |
| + | '''Step 4:''' | ||
Set all partial derivatives=0 and find a solution for system of equations | Set all partial derivatives=0 and find a solution for system of equations | ||
| + | |||
<math>\frac{d}{dx_i}L(x_1,...x_n,\lambda _1,...\lambda _m)=0\forall i=1,...,n</math> and <math>\frac{d}{d\lambda _j}L(x_1,...x_n,\lambda _1,...\lambda _m)=0 \forall j=1,...,m</math> and solve it | <math>\frac{d}{dx_i}L(x_1,...x_n,\lambda _1,...\lambda _m)=0\forall i=1,...,n</math> and <math>\frac{d}{d\lambda _j}L(x_1,...x_n,\lambda _1,...\lambda _m)=0 \forall j=1,...,m</math> and solve it | ||
| − | Step 5: | + | |
| + | '''Step 5''': | ||
Build the Hessian Matrix | Build the Hessian Matrix | ||
| + | |||
<math>H(x_1,...,x_n=)\begin{pmatrix} | <math>H(x_1,...,x_n=)\begin{pmatrix} | ||
| Zeile 44: | Zeile 73: | ||
| − | Step 6: | + | '''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: <math>\det (H(x_1,...x_n)-\lambda *I)=0</math> | + | 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: |
| + | |||
| + | |||
| + | <math>\det (H(x_1,...x_n)-\lambda *I)=0</math> | ||
| + | |||
If all eigenvalues are >0, then the funktion is convex, and if all eigenvalues are <0, then the funktion is concave. | If all eigenvalues are >0, then the funktion is convex, and if all eigenvalues are <0, then the funktion is concave. | ||
== ''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 63: | Zeile 96: | ||
| − | Objective funktion: | + | '''Objective funktion:''' |
| Zeile 69: | Zeile 102: | ||
| − | + | '''Constraints:''' | |
| Zeile 78: | 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 92: | Zeile 125: | ||
| − | Step 2: Build the Lagrangian function <math></math> | + | '''Step 2:''' Build the Lagrangian function <math></math> |
| Zeile 98: | Zeile 131: | ||
| − | Step 3: Build all partial derivatives | + | '''Step 3:''' Build all partial derivatives |
| Zeile 112: | Zeile 145: | ||
| − | Step 4: Set all partial derivatives=0 and find a solution for system of equations | + | '''Step 4:''' Set all partial derivatives=0 and find a solution for system of equations |
| Zeile 126: | Zeile 159: | ||
| − | Solve | + | ''Solve'' |
| Zeile 155: | Zeile 188: | ||
| − | solution: <math>x_1=20, x_2=10, x_3=0,\lambda _1=40, \lambda _2=0 </math> | + | ''solution'': <math>x_1=20, x_2=10, x_3=0,\lambda _1=40, \lambda _2=0 </math> |
| − | + | ||
| − | Step 5: Build the Hessian Matrix | + | '''Step 5''': Build the Hessian Matrix |
| Zeile 168: | Zeile 201: | ||
| − | Step 6: Check if the function is convex for a minimum function or if the function is concave for a maximum funktion. | + | '''Step 6''': Check if the function is convex for a minimum function or if the function is concave for a maximum funktion. |
| Zeile 177: | 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'' == | ||
| Zeile 185: | Zeile 218: | ||
Mathematik für Ingenieure: Eine anschauliche Einführung für das praxisorientierte Studium (Springer-Lehrbuch) | 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://massmatics.de/de/files/2012/09/Lagrangeoptimierung-v1.0.pdf | ||
http://www.mathe-online.at/materialien/klaus.berger/files/Matrizen/eigenwerte.pdf | http://www.mathe-online.at/materialien/klaus.berger/files/Matrizen/eigenwerte.pdf | ||
| + | |||
| + | http://en.wikipedia.org/wiki/Lagrange_multiplier | ||
Aktuelle Version vom 28. Juni 2013, 12:50 Uhr
Inhaltsverzeichnis
Theory
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
