Nonlinear Opt.: Wolfe algorithm 1

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 $c_{i}x_{j}$, also quadratic experessions of $c_{jj}x{_{j}}^{2}$ and/or $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 $u_{i}$ into 2.1.1 and $v_{j}$ into 2.1.3. A feasible solution is on hand if the slack variables $u_{i}$ and $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 $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: $x_{i}$ and the related $u_{i}$ for the same i={1,...., n} or $\lambda _{j}$ and the related $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 $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 $u_{1}$ becomes negative. Therefore you have to introduce the auxiliary variable $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 $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

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

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

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

Datei:Wolfe Tabelle 3.jpg

Iterate like described above.

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

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Iterate like decribed above.

Here: $h_{3}$ leaves the basis and $h_{3}$ enters the basis. You get a feasible solution since $\lambda _{3}$ is not the basis.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

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 $\lambda _{2}$ is not the basis.

Final Tableau

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tableau is the final tableau and also the optimal solution because there are no more h’s in the basis.

Results:

$x_{1}=0,75$

$x_{2}=2,5$

$v_{1}=2,25$

$v_{2}=0,5$

$v_{3}=1,25$

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

Sources

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

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

$\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)