Nonlinear Opt.: Wolfe algorithm 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Ble (Diskussion | Beiträge) |
Ble (Diskussion | Beiträge) |
||
(2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
== '''1. Introduction''' == | == '''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 | + | 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 <math>c_{i}x_{j}</math>, also quadratic experessions of <math>c_{jj}x{_{j}}^{2}</math> and/or <math>c_{jj}x_{i}x_{j}</math> 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''' == | ||
+ | [2] | ||
+ | |||
'''''0. Formulate the corresponding Lagrangian function''''' | '''''0. Formulate the corresponding Lagrangian function''''' | ||
Zeile 28: | Zeile 30: | ||
'''''2. Transformation''''' | '''''2. Transformation''''' | ||
− | Transform inequation 2.1.1 and 2.1.3 into equation by introducing the slack variables | + | Transform inequation 2.1.1 and 2.1.3 into equation by introducing the slack variables <math>u_{i}</math> into 2.1.1 and <math>v_{j}</math> into 2.1.3. A feasible solution is on hand if the slack variables <math>u_{i}</math> and <math>v_{j}</math> are positive. Otherwise introduce auxiliary variables <math>h_{k}\geq 0</math> in order to atain a basic feasible solution. |
'''''3. Formulate the Simplex Tableau''''' | '''''3. Formulate the Simplex Tableau''''' | ||
− | Weight auxiliary variables | + | Weight auxiliary variables <math>h_{k}</math> with a big M in case of a minimization problem (-M in case of a maximization problem) |
<math>\min \sum _{k}M\cdot h_{k}</math> | <math>\min \sum _{k}M\cdot h_{k}</math> | ||
Zeile 44: | Zeile 46: | ||
'''''4. Iteration of the Simplex Tableau''''' | '''''4. Iteration of the Simplex Tableau''''' | ||
− | Iterate the Simplex-tableau by using the M-method until a feasible solution is gained. Be careful: | + | Iterate the Simplex-tableau by using the M-method until a feasible solution is gained. Be careful: <math>x_{i}</math> and the related <math>u_{i}</math> for the same i={1,...., n} or <math>\lambda _{j}</math> and the related <math>v_{j}</math> for the same j={1,...., m} may never be together in the basis. |
== '''3. Example''' == | == '''3. Example''' == | ||
+ | [3] | ||
'''objective function:''' | '''objective function:''' | ||
<math>\min f\left ( x_{1},x_{2} \right )=-30x_{1}+20x{_{1}}^{2}-50x_{2}+10x{_{2}}^{2}</math> | <math>\min f\left ( x_{1},x_{2} \right )=-30x_{1}+20x{_{1}}^{2}-50x_{2}+10x{_{2}}^{2}</math> | ||
Zeile 127: | Zeile 130: | ||
− | Take inequation 3.1.1 ⩾0 and transform it first into an inequation (⩽0). In order to transform inequation ⩽0 into an equation (=), you have to introduce the slack variable | + | Take inequation 3.1.1 ⩾0 and transform it first into an inequation (⩽0). In order to transform inequation ⩽0 into an equation (=), you have to introduce the slack variable <math>u_{1}</math>. Since the result of the equation is negative (-30), you have to multiply the term by (-1). After that step, your slack variable <math>u_{1}</math> becomes negative. Therefore you have to introduce the auxiliary variable <math>h_{1}</math>. |
Zeile 143: | Zeile 146: | ||
− | See explanation above. (3.2.1). Introduce auxiliary variable | + | See explanation above. (3.2.1). Introduce auxiliary variable <math>h_{2}</math>. |
Zeile 155: | Zeile 158: | ||
− | Use the slack variable | + | Use the slack variable <math>v_{1}</math> instead of <math>u_{1}</math>. Here, the slack variable <math>v_{1}</math> is positive. Therefore the auxiliary variable <math>h_{k}</math> is not needed. |
Zeile 169: | Zeile 172: | ||
− | See explanation above. (3.2.1). Use the slack variable | + | See explanation above. (3.2.1). Use the slack variable <math>v_{2}</math>. Introduce auxiliary variable <math>h_{3}</math>. |
Zeile 183: | Zeile 186: | ||
− | See explanation above. (3.2.1). Use the slack variable | + | See explanation above. (3.2.1). Use the slack variable <math>v_{3}</math>. Introduce auxiliary variable <math>h_{4}</math>. |
Zeile 203: | Zeile 206: | ||
'''Starting Tableau''' | '''Starting Tableau''' | ||
− | [[Datei: | + | [[Datei:Wolfe_Tabelle_Start.jpg]] |
''Here:'' Transfer all equations from 3.2 into the starting tableau. Solve all Ms, e.g. for x1: (-M) ∙ 40 + (-M) ∙ 0+ 0 ∙ 1 + (-M) ∙ 0 + (-M) ∙ 1 = - 41M | ''Here:'' Transfer all equations from 3.2 into the starting tableau. Solve all Ms, e.g. for x1: (-M) ∙ 40 + (-M) ∙ 0+ 0 ∙ 1 + (-M) ∙ 0 + (-M) ∙ 1 = - 41M | ||
Zeile 213: | Zeile 216: | ||
Iterate the Simplex-tableau by using the M-method until a feasible solution is gained. | Iterate the Simplex-tableau by using the M-method until a feasible solution is gained. | ||
− | Be careful: | + | Be careful: <math>x_{i}</math> and the related <math>u_{i}</math> for the same i={1,...., n} or λj and the related <math>v_{j}</math> for the same j={1,...., m} may never be together in the basis. |
− | [[Datei: | + | [[Datei:Wolfe_Tabelle_2.jpg]] |
− | ''Here:'' Take x1 as pivot column since | + | ''Here:'' Take x1 as pivot column since <math>x_{1}</math> has the smallest sum of M (=-41M). <math>x_{1}</math> can go into the basis since <math>u_{1}</math> is not in the basis. The pivot row is <math>h_{1}</math> because ϴ is also the smallest (30/40=3/4). The pivot element is 40. Iterate the simplex Tableau for the next step. |
− | [In case of a non feasible solution, e.g. Starting tableau: if | + | [In case of a non feasible solution, e.g. Starting tableau: if <math>u_{1}</math> is in the basis and <math>x_{1}</math> therefore may not enter the basis, take the next smallest sum of M as pivot column (<math>x_{2}</math>) and so on.] |
− | [[Datei: | + | [[Datei:Wolfe_Tabelle_3.jpg]] |
Iterate like described above. | Iterate like described above. | ||
− | ''Here:'' | + | ''Here:'' <math>h_{4}</math> leaves the basis and <math>x_{2}</math> enters the basis. You get a feasible solution since <math>u_{2}</math> is not in the basis. |
− | [[Datei: | + | [[Datei:Wolfe_Tabelle_4.jpg]] |
Iterate like decribed above. | Iterate like decribed above. | ||
− | ''Here:'' | + | ''Here:'' <math>h_{3}</math> leaves the basis and <math>h_{3}</math> enters the basis. You get a feasible solution since <math>\lambda _{3}</math> is not the basis. |
− | [[Datei: | + | [[Datei:Wolfe_Tabelle_5.jpg]] |
Iterate like described above. | Iterate like described above. | ||
− | ''Here:'' | + | ''Here:'' <math>\h_{2}</math> leaves the basis and <math>\v_{2}</math> enters the basis. You get a feasible solution since <math>\lambda _{2}</math> is not the basis. |
'''Final Tableau''' | '''Final Tableau''' | ||
− | [[Datei: | + | [[Datei:Wolfe_Tabelle_Final.jpg]] |
Tableau is the final tableau and also the optimal solution because there are no more h’s in the basis. | Tableau is the final tableau and also the optimal solution because there are no more h’s in the basis. | ||
Zeile 265: | Zeile 268: | ||
− | for F( | + | for objective function: \min F(0,75;2,5)=-73,75 |
+ | |||
+ | |||
+ | |||
+ | == '''Sources''' == | ||
+ | <math>\left [ 1 \right ]:</math> Domschke, Drexel; ''Einführung in Operations Research''; 5. Auflage; S.178 | ||
+ | |||
+ | <math>\left [ 2 \right ]:</math> O. Wendt; Skript SS 2012; ''Non linear Optimization''; F.121ff. | ||
+ | |||
+ | <math>\left [ 3 \right ]:</math> selfcreated Problem with selfcreated restrictions due Excel Solver; by Le Bao Thien Huong, Mehtap Sevinc, Thomas Hempler; 2013 | ||
+ | |||
+ | |||
+ | == '''Autors of the article''' == | ||
+ | Le Bao Thien Huong | ||
+ | --[[Benutzer:Ble|ble]] ([[Benutzer Diskussion:Ble|Diskussion]]) 23:59, 1. Jul. 2013 (CEST) | ||
+ | Mehtap Sevinc | ||
+ | --[[Benutzer:Ble|ble]] ([[Benutzer Diskussion:Ble|Diskussion]]) 23:59, 1. Jul. 2013 (CEST) | ||
+ | Thomas Hempler | ||
+ | --[[Benutzer:Ble|ble]] ([[Benutzer Diskussion:Ble|Diskussion]]) 23:59, 1. Jul. 2013 (CEST) |
Aktuelle Version vom 1. Juli 2013, 23:59 Uhr
Inhaltsverzeichnis
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 , also quadratic experessions of and/or 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
[2]
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 into 2.1.1 and into 2.1.3. A feasible solution is on hand if the slack variables and are positive. Otherwise introduce auxiliary variables Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): h_{k}\geq 0
in order to atain a basic feasible solution.
3. Formulate the Simplex Tableau
Weight auxiliary variables 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: and the related for the same i={1,...., n} or and the related for the same j={1,...., m} may never be together in the basis.
3. Example
[3] 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 )
All restrictions have to be transformed from ⩾ c into inequetions ⩽ c in order to formulate the Lagrangian function.
1. Formulate the KKT conditions
1.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_{1}}=-30+40x_{1}+\lambda _{1}-\lambda _{3}\geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial x_{2}}=-50+20x_{2}+\lambda _{2}-\lambda _{3}\geq 0
2.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\cdot \frac{\partial L}{\partial x_{1}}=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}\cdot \frac{\partial L}{\partial x_{2}}=0
3.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda _{1}}=x_{1}-3\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda _{2}}=-x_{2}+2\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial L}{\partial \lambda _{3}}=-x_{1}-x_{2}+2\leq 0
4.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda _{1}\cdot \frac{\partial L}{\partial \lambda _{1}}=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda _{2}\cdot \frac{\partial L}{\partial \lambda _{2}}=0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda _{3}\cdot \frac{\partial L}{\partial \lambda _{3}}=0
5.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x\geq 0
6.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda \geq 0
2. Transformation by introducing slack variables
1.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -30+40x_{1}+\lambda _{1}-\lambda _{3}\geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 30-40x_{1}-\lambda _{1}+\lambda _{3}\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -40x_{1}-\lambda _{1}+\lambda _{3}\leq -30
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -40x_{1}-\lambda _{1}+\lambda _{3}{\color{Red} + u_{1}}= -30
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 40x_{1}+\lambda _{1}-\lambda _{3}{\color{Red} -u_{1}}{\color{Blue} +h_{1}}=30
Take inequation 3.1.1 ⩾0 and transform it first into an inequation (⩽0). In order to transform inequation ⩽0 into an equation (=), you have to introduce the slack variable . Since the result of the equation is negative (-30), you have to multiply the term by (-1). After that step, your slack variable becomes negative. Therefore you have to introduce the auxiliary variable .
2.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -50+20x_{2-\lambda _{2}}-\lambda _{3}\geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 50-20x_{2+\lambda _{2}}+\lambda _{3}\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -20x_{2}+\lambda _{2}+\lambda _{3}\leq -50
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -20x_{2}+\lambda _{2}+\lambda _{3}{\color{Red} +u_{2}}= -50
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 20x_{2}-\lambda _{2}-\lambda _{3}{\color{Red} -u_{2}}{\color{Blue} +h_{2}}= 50
See explanation above. (3.2.1). Introduce auxiliary variable .
3.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}-3\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\leq 3
Use the slack variable instead of . Here, the slack variable is positive. Therefore the auxiliary variable is not needed.
4.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{2}+2\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{2}\leq -2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{2}{\color{Green} +v_{2}}= -2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}{\color{Green} -v_{2}}{\color{Blue} +h_{3}}= 2
See explanation above. (3.2.1). Use the slack variable . Introduce auxiliary variable .
5.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}-x_{2}+2\leq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}-x_{2}\leq -2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}-x_{2}{\color{Green} +v_{3}}=-2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}+x_{2}{\color{Green} -v_{3}}{\color{Blue} +h_{4}}=2
See explanation above. (3.2.1). Use the slack variable . Introduce auxiliary variable .
6.)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x\geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda \geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u\geq 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v\geq 0
3. Formulate the Simplex tableau
Starting Tableau
Here: Transfer all equations from 3.2 into the starting tableau. Solve all Ms, e.g. for x1: (-M) ∙ 40 + (-M) ∙ 0+ 0 ∙ 1 + (-M) ∙ 0 + (-M) ∙ 1 = - 41M
4. Iteration of the Simplex Tableau
Iterate the Simplex-tableau by using the M-method until a feasible solution is gained.
Be careful: and the related for the same i={1,...., n} or λj and the related for the same j={1,...., m} may never be together in the basis.
Here: Take x1 as pivot column since has the smallest sum of M (=-41M). can go into the basis since is not in the basis. The pivot row is because ϴ is also the smallest (30/40=3/4). The pivot element is 40. Iterate the simplex Tableau for the next step.
[In case of a non feasible solution, e.g. Starting tableau: if is in the basis and therefore may not enter the basis, take the next smallest sum of M as pivot column () and so on.]
Iterate like described above.
Here: leaves the basis and enters the basis. You get a feasible solution since is not in the basis.
Iterate like decribed above.
Here: leaves the basis and enters the basis. You get a feasible solution since is not the basis.
Iterate like described above.
Here: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \h_{2}
leaves the basis and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \v_{2}
enters the basis. You get a feasible solution since is not the basis.
Final Tableau
Tableau is the final tableau and also the optimal solution because there are no more h’s in the basis.
Results:
for objective function: \min F(0,75;2,5)=-73,75
Sources
Domschke, Drexel; Einführung in Operations Research; 5. Auflage; S.178
O. Wendt; Skript SS 2012; Non linear Optimization; F.121ff.
selfcreated Problem with selfcreated restrictions due Excel Solver; by Le Bao Thien Huong, Mehtap Sevinc, Thomas Hempler; 2013
Autors of the article
Le Bao Thien Huong --ble (Diskussion) 23:59, 1. Jul. 2013 (CEST) Mehtap Sevinc --ble (Diskussion) 23:59, 1. Jul. 2013 (CEST) Thomas Hempler --ble (Diskussion) 23:59, 1. Jul. 2013 (CEST)