Nonlinear Opt.: Wolfe algorithm 2

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

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

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

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

$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