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

Aktuelle Version vom 1. Juli 2013, 00:05 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

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
${\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= -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.): -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

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

${\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} \leq 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.): -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}

${\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

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

${\displaystyle x_{1}=0,1}$

${\displaystyle u_{2}=50}$

${\displaystyle y_{2}=4}$

${\displaystyle x_{2},u_{2},v_{1},v_{2},y_{1}=0}$

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