Nonlinear Opt.: Wolfe algorithm 2
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.
Choose the most negative value in the last row to find your pivot column. Afterward the right site 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 have 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
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