Nonlinear Opt.: Wolfe algorithm 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Rapo (Diskussion | Beiträge) (→Example) |
Rapo (Diskussion | Beiträge) (→Example) |
||
Zeile 102: | Zeile 102: | ||
+ | In each row with a negative "right site", 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]] | ||
+ | |||
+ | First pivot element: -10 | ||
[[Datei:Wolfe2.jpeg]] | [[Datei:Wolfe2.jpeg]] | ||
+ | second pivot element: 10 | ||
[[Datei:Wolfe3.jpeg]] | [[Datei:Wolfe3.jpeg]] | ||
+ | third pivot element: | ||
[[Datei:Wolfe4.jpeg]] | [[Datei:Wolfe4.jpeg]] | ||
Zeile 125: | Zeile 130: | ||
<math>x_{2} , u_{2} , v_{1} , v_{2} , y_{1} = 0</math> | <math>x_{2} , u_{2} , v_{1} , v_{2} , y_{1} = 0</math> | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | == Sources == | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | == Authors == |
Version vom 30. Juni 2013, 23:45 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.): \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= \frac{1}{2}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.): x_{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}*(x_{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} \geq 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.): x_{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 site", we have to introduce a new variable "W". It has a negative value. Finally we have the linear starting tableau.
First pivot element: -10
second pivot element: 10
third pivot element:
Result