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

Aktuelle Version vom 1. Juli 2013, 23:59 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 ${\displaystyle c_{i}x_{j}}$, also quadratic experessions of ${\displaystyle c_{jj}x{_{j}}^{2}}$ and/or ${\displaystyle c_{jj}x_{i}x_{j}}$ 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 ${\displaystyle u_{i}}$ into 2.1.1 and ${\displaystyle v_{j}}$ into 2.1.3. A feasible solution is on hand if the slack variables ${\displaystyle u_{i}}$ and ${\displaystyle v_{j}}$ 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 ${\displaystyle h_{k}}$ 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: ${\displaystyle x_{i}}$ and the related ${\displaystyle u_{i}}$ for the same i={1,...., n} or ${\displaystyle \lambda _{j}}$ and the related ${\displaystyle v_{j}}$ 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 ${\displaystyle u_{1}}$. Since the result of the equation is negative (-30), you have to multiply the term by (-1). After that step, your slack variable ${\displaystyle u_{1}}$ becomes negative. Therefore you have to introduce the auxiliary variable ${\displaystyle h_{1}}$.

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 ${\displaystyle h_{2}}$.

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

${\displaystyle x_{1}{\color {Green}+v_{1}}=3}$

Use the slack variable ${\displaystyle v_{1}}$ instead of ${\displaystyle u_{1}}$. Here, the slack variable ${\displaystyle v_{1}}$ is positive. Therefore the auxiliary variable ${\displaystyle h_{k}}$ 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 ${\displaystyle v_{2}}$. Introduce auxiliary variable ${\displaystyle h_{3}}$.

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 ${\displaystyle v_{3}}$. Introduce auxiliary variable ${\displaystyle h_{4}}$.

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: ${\displaystyle x_{i}}$ and the related ${\displaystyle u_{i}}$ for the same i={1,...., n} or λj and the related ${\displaystyle v_{j}}$ for the same j={1,...., m} may never be together in the basis.

Here: Take x1 as pivot column since ${\displaystyle x_{1}}$ has the smallest sum of M (=-41M). ${\displaystyle x_{1}}$ can go into the basis since ${\displaystyle u_{1}}$ is not in the basis. The pivot row is ${\displaystyle h_{1}}$ 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 ${\displaystyle u_{1}}$ is in the basis and ${\displaystyle x_{1}}$ therefore may not enter the basis, take the next smallest sum of M as pivot column (${\displaystyle x_{2}}$) and so on.]

Datei:Wolfe Tabelle 3.jpg

Iterate like described above.

Here: ${\displaystyle h_{4}}$ leaves the basis and ${\displaystyle x_{2}}$ enters the basis. You get a feasible solution since ${\displaystyle u_{2}}$ is not in the basis.

Iterate like decribed above.

Here: ${\displaystyle h_{3}}$ leaves the basis and ${\displaystyle h_{3}}$ enters the basis. You get a feasible solution since ${\displaystyle \lambda _{3}}$ 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 ${\displaystyle \lambda _{2}}$ 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:

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

${\displaystyle x_{2}=2,5}$

${\displaystyle v_{1}=2,25}$

${\displaystyle v_{2}=0,5}$

${\displaystyle v_{3}=1,25}$

for objective function: \min F(0,75;2,5)=-73,75

Sources

${\displaystyle \left[1\right]:}$ Domschke, Drexel; Einführung in Operations Research; 5. Auflage; S.178

${\displaystyle \left[2\right]:}$ O. Wendt; Skript SS 2012; Non linear Optimization; F.121ff.

${\displaystyle \left[3\right]:}$ 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)