Nonlinear Opt.: Wolfe algorithm 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Rapo (Diskussion | Beiträge) (→Example) |
Rapo (Diskussion | Beiträge) (→Example) |
||
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 102: | Zeile 102: | ||
− | In each row with a negative "right | + | In each row with a negative "right side", we have to introduce a new variable "W". It has a negative value. Finally we have the linear starting tableau. |
[[Datei:Wolfe1.jpeg]] | [[Datei:Wolfe1.jpeg]] | ||
− | Choose the most negative value in the last row to find your pivot column. Afterward the right | + | Choose the most negative value in the last row to find your pivot column. Afterward the right side has to be divided by each positive value in the same row of the pivot column. The lowest result gives you the pivot row, so you get the pivot element. If the last row only has positive values you have your optimal solution. Otherwise you have to repeat the simplex-iteration. |
First pivot element: -10 | First pivot element: -10 | ||
Zeile 120: | Zeile 120: | ||
[[Datei:Wolfe4.jpeg]] | [[Datei:Wolfe4.jpeg]] | ||
+ | Optimal solution | ||
Aktuelle Version vom 1. Juli 2013, 00:05 Uhr
Inhaltsverzeichnis
Introduction
The wolf algorithm is based on the consideration, that the Karush-Kuhn-Tucker-conditions are necessary for solving convex optimization problems. The necessary and effectual condition of the KKT-conditions make sure that an optimal solution can be found. The wolf algorithm can be seen as a systematical method to solve these KKT-conditions. Therefore you have to add artificial variables in the constructed conditions to transform the non-linear problem into a linear system of equations. This has to be done so the simplex-method can be used to solve the problem in consideration of an additional method.
Theory
The wolf algorithm can be separated in four steps:
1. Formulation of the Lagrange-function
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L(x_{1},...,x_{n} ; u_{1},...u_{m}) = f(x_{1},...,x_{n})-\sum_{i=1}^{m}u_{i}g_{i}(x_{1},...x_{n})
2. Formulation of the KKT-conditions
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1) L_{x} = \frac{\partial L}{\partial x} = c+Cx+A^{T}u \geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2) x^{T}*L_{x} = x^{t}(c+Cx+A^{T}u) = 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3) L_{u} = \frac{\partial L}{\partial u} = A^{T}x-b \leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4) u^{T}*L_{u} = u^{T}(A^{T}x-b) = 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 5) x \geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 6) u \leq 0
3. Transforming the KKT-conditions into a linear-optimization-model by introducing slack variables (v, y)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 1') Cx+A^{T}u-v = -c
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y = b-A^{T}u
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \geq 0, u \geq o, v \geq 0, y \geq o.
4. Solving the LO-model in consideration of the non-linear restrictions
Formulate the simplex tableau
Example
Objective function
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}^{2}+\frac{1}{4}x_{2}^{2}+10x_{1}+5x_{2}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rightarrow
Restrictions
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}-5 \leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}-4 \leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} \geq 0
, Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2} \geq 0
1. Formulation of the Lagrange-function
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L= -x_{1}^{2}+\frac{1}{4}x_{2}^{2}+10x_{1}+5x_{2}-u_{1}*(x_{1}-5)-u_{2}*(x_{2}-4)
2. Formulation of the KKT-conditions
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -2x_{1}+10-u_{1} \leq 0
; Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{1}{2}x_{2}+5-u_{2} \leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}*(-2x_{1}+10-u_{1}) = 0
; Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}*(\frac{1}{2}x_{2}+5-u_{2}) = 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} , x_{2} \geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}-5 \leq 0
; Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}-4 \leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u_{1}*(x_{1}-5) \leq 0
; Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u_{2}*(x_{2}-4) \leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u_{1} , u_{2} \leq 0
3. Transforming the KKT-conditions into a linear-optimization-model by introducing slack variables (v, y)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -2x_{1}-u_{1}+v_{1}=-10
; Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{1}{2}x_{2}-u_{2}+v_{2}
;
, , ,
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} , x_{2} , u_{1} , u_{2} , y_{1} , y_{2} , v_{1} , v_{2} \geq 0
4. Solving the LO-model in consideration of the non-linear restrictions
In each row with a negative "right side", we have to introduce a new variable "W". It has a negative value. Finally we have the linear starting tableau.
Choose the most negative value in the last row to find your pivot column. Afterward the right side has to be divided by each positive value in the same row of the pivot column. The lowest result gives you the pivot row, so you get the pivot element. If the last row only has positive values you have your optimal solution. Otherwise you have to repeat the simplex-iteration.
First pivot element: -10
second pivot element: 10
third pivot element: 1/50
Optimal solution
Result
Sources
Ellinger, Beuermann, Leisten, "Operations Research - Eine Einführung" 4.Auflage
Corsten, Sartor, "Operations Research - WISO Kurzlehrbücher"
Skript Operations Research SS2013
Authors
Alen Rapo
Florian Schütz