Nonlinear Opt.: Lagrangian condition 1: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Detailed Solution process with explanation)
(→‎Detailed Solution process with explanation)
 
(6 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 2: Zeile 2:
  
 
[[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  
 
[[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 constraits.
+
maximization of f(x,y)]] 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 constraits. From the analysis we know that it is possible to include the constraits in the objective function.
+
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 constrait (<math>\lambda _1...\lambda _n</math>),what reduces our Problem with constraits to an Problem without constraits.
+
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 an constant c for which a constrait<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>.
+
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.
 
The constant lagrangian multipliers are neccesary because the gradients should be parallel but can have a different length.
  
Zeile 18: Zeile 18:
  
  
−
If you want to use the Lagrangian method your Problem should be in the following form:
+
If you want to use the Lagrangian method your problem should be in the following form:
 +
 
 
  '''Objective funktion''':
 
  '''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>
Zeile 30: 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.
  
−
If your Problem is in the upper form you can use the following Algorithm to solve your Problem:
+
Now you can use the following Algorithm to solve your Problem:
  
  
 
'''Step 1''':
 
'''Step 1''':
−
Transform all constraights to the following form: <math>g_i(x_1,...,x_n)-b=0</math>     
+
Transform all constraints to the following form:  
 +
 
 +
 
 +
<math>g_i(x_1,...,x_n)-b=0</math>     
 +
 
  
 
'''Step 2:'''
 
'''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>
+
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:'''
 
'''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 60: Zeile 74:
  
 
'''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 should plan the transportation of an 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 know, are that the sum of Station A and station B is A 30 units and that the sum of Station B and Station C is 10. How can the total cost be minimized?
+
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 84: Zeile 102:
 
   
 
   
  
−
'''Constraits:'''
+
'''Constraints:'''
  
  
Zeile 93: 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 constraights to the following form: <math>g_i(x_1,...,x_n)-b=0</math>   
+
 
 +
'''Step 1:''' Transform all constraints to the following form: <math>g_i(x_1,...,x_n)-b=0</math>   
 
    
 
    
  
Zeile 191: 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 an our found solution is a Minimum
+
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

Theory

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.


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

http://en.wikipedia.org/wiki/Lagrange_multiplier

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Nonlinear_Opt.:_Lagrangian_condition_1&oldid=5201“