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

Version vom 30. Juni 2013, 14:36 Uhr

1. Introduction

In 1956 Frank and Wolfe developed an algorithm to solve nonlinear quadratic optimization problems under certain restrictions. The difference between nonlinear and linear optimization problems only lays in the objective function F(x). Nonlinear functions include beside linear terms of cixj, also quadratic experessions of cjjxj2 and/or cjjxij for some or all i≠j. The quadratic minimization problem which is a convex objectiv function (and the quadratic maximization problem which is a concave objective function) will be solved with the Wolfe algorithm in the next step. Problems with quadratic objective functions which are not convex (not concave) can not be solved with the Wolfe algorithm.[1]

2. Theory

0. Formulate the corresponding Lagrangian function

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L\left ( x,\lambda_{j} \right )=F\left ( x \right )+\sum_{j=1}^{n}\lambda_{j}\cdot g_{j}(x)

1. Formulate KKT conditions

1. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L_{x_{i}}=\frac{\partial L}{\partial x_{i}}\geq 0

2. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{i}\cdot L_{x_{i}}=0

3. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L_{\lambda _{j}}=\frac{\partial L}{\partial \lambda _{_{j}}}\leq 0

4. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda _{j}\cdot L_{\lambda _{j}}=0

5. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{i}\geq 0

6. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda _{j}\geq 0

2. Transformation

Transform inequation 2.1.1 and 2.1.3 into equation by introducing the slack variables ui into 2.1.1 and vj into 2.1.3. A feasible solution is on hand if the slack variables ui and vj are positive. Otherwise introduce auxiliary variables h_k≥0 in order to atain a basic feasible solution.

3.Formulate the Simplex Tableau

Weight auxiliary variables hk with a big M in case of a minimization problem (-M in case of a maximization problem)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \min \sum _{k}M\cdot h_{k}

and

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \max \sum _{k}-M\cdot h_{k}