Nonlinear Opt.: Wolfe algorithm 2: Unterschied zwischen den Versionen

Version vom 30. Juni 2013, 22:20 Uhr

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

${\displaystyle 2')x^{T}v=0}$ ${\displaystyle due}$ ${\displaystyle to}$ ${\displaystyle v=Cx+A^{T}u+c}$

${\displaystyle 3')A^{T}x+y=b}$

${\displaystyle 4')u^{T}y=0}$ ${\displaystyle due}$ ${\displaystyle to}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y = b-A^{T}u

${\displaystyle where}$ 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

${\displaystyle {\frac {1}{2}}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

${\displaystyle max!}$

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

${\displaystyle (1)}$ 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

${\displaystyle (2)}$ 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

${\displaystyle (3)}$ Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} , x_{2} \geq 0

${\displaystyle (4)}$ 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

${\displaystyle (5)}$ 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

${\displaystyle (6)}$ 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)

${\displaystyle (1')}$ 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}

${\displaystyle (4')}$ ${\displaystyle x_{1}+y_{1}=5}$ ; ${\displaystyle x_{2}+y_{2}=4}$

${\displaystyle (2')(5')}$ ${\displaystyle x_{1}v_{1}=0}$ , ${\displaystyle x_{2}v_{2}=0}$ , ${\displaystyle u_{1}y_{1}=0}$ , ${\displaystyle u_{2}y_{2}=0}$

${\displaystyle (3')('6)}$ 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