Nonlinear Opt.: Wolfe algorithm 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
Ble (Diskussion | Beiträge) |
Ble (Diskussion | Beiträge) |
||
| Zeile 3: | Zeile 3: | ||
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. | 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] | Problems with quadratic objective functions which are not convex (not concave) can not be solved with the Wolfe algorithm.[1] | ||
| + | |||
== '''2. Theory''' == | == '''2. Theory''' == | ||
| Zeile 39: | Zeile 40: | ||
<math>\max \sum _{k}-M\cdot h_{k}</math> | <math>\max \sum _{k}-M\cdot h_{k}</math> | ||
| + | |||
| + | |||
| + | ''4. Iteration of the Simplex Tableau'' | ||
| + | |||
| + | Iterate the Simplex-tableau by using the M-method until a feasible solution is gained. Be careful: xi and the related ui for the same i={1,...., n} or λj and the related vj for the same j={1,...., m} may never be together in the basis. | ||
| + | |||
| + | |||
| + | == '''3.Example''' == | ||
| + | objective function: | ||
| + | <math>\min f\left ( x_{1},x_{2} \right )=-30x_{1}+20x{_{1}}^{2}-50x_{2}+10x{_{2}}^{2}</math> | ||
| + | |||
| + | s.t. | ||
| + | <math>x_{1}\leq 3</math> | ||
| + | <math>x_{2}\geq 2</math> --> <math>-x_{1}\leq -2</math> | ||
| + | <math>x_{1}+x_{2}\geq 2</math> --> <math>-x_{1}-x_{2}\leq -2</math> | ||
| + | |||
| + | ''0. Formulate the Lagrangian function'' | ||
| + | |||
| + | <math>L\left ( x,\lambda \right )=-30x_{1}+20{_{1}}^{2}-50x_{2}+10x{_{2}}^{2}+\lambda _{1}\cdot \left ( x_{1}-3 \right )+\lambda _{2}\cdot \left ( -x_{2}+2 \right )+\lambda _{3}\cdot \left ( -x_{1} -x_{2}+2\right )</math> | ||
Version vom 30. Juni 2013, 15:21 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}
4. Iteration of the Simplex Tableau
Iterate the Simplex-tableau by using the M-method until a feasible solution is gained. Be careful: xi and the related ui for the same i={1,...., n} or λj and the related vj for the same j={1,...., m} may never be together in the basis.
3.Example
objective function:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \min f\left ( x_{1},x_{2} \right )=-30x_{1}+20x{_{1}}^{2}-50x_{2}+10x{_{2}}^{2}
s.t.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\leq 3
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}\geq 2
--> Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}\leq -2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}+x_{2}\geq 2
--> Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}-x_{2}\leq -2
0. Formulate the Lagrangian function
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): L\left ( x,\lambda \right )=-30x_{1}+20{_{1}}^{2}-50x_{2}+10x{_{2}}^{2}+\lambda _{1}\cdot \left ( x_{1}-3 \right )+\lambda _{2}\cdot \left ( -x_{2}+2 \right )+\lambda _{3}\cdot \left ( -x_{1} -x_{2}+2\right )
