Methode der zulässigen Richtung

In diesem Abschnitt wird die Methode der zulässigen Richtungen für nichtlineare Minimierungsprobleme unter Ungleichungsrestriktionen aufgezeigt.

Es werden nun im Folgenden die notwendigen Definitionen für die Anwendung des Verfahrens aufgeführt und erläuertet.

Definitionen

Zulässiger Bereich:

$K = \{x | Ax \le b \}$

Menge aktiver Indizes:

$I(x) = \{i | a_ix = b_i \}$

Menge zulässiger Richtungen:

$S(x) = \{s | a_i s \le 0 \} \forall \; i \in I(x)$

Lokal beste Richtung:

$s \in S(x)$ (in Richtung des Gradienten)

Vorgehensweise

Die obigen Definitionen sind aufgeführt worden, um das im folgenden beschriebene Vorgehen zu verstehen. Es muss zu Beginn das nichtlineare Optimierungsproblem in der obigen Form vorliegen. Liegt es nicht in dieser Form vor, so muss es in die Form überführt werden. Dabei kann man sich dem Abschnitt Umformung in die Standardform bedienen. Ist eine Nichtnegativitätsbedingung im Ausgangsproblem gegeben, so wird auch diese in der Form $-x_j \le 0$ geschrieben. Nachdem das nichtlineare Optimierungsproblem in der obigen Form (Maximierungsproblem, $\le$-Nebenbedingungen) vorliegt, werden die folgenden Schritte angewandt:

1. Schritt: Es wird zunächst eine Startlösung bestimmt. Diese muss innerhalb des zulässigen Bereichs $K$ liegen. Die Startlösung $x$ (zulässige Lösung) ist entweder vorgegeben oder wird beliebig bestimmt. Ob die gewählte Startlösung im zulässigen Bereich liegt, kann man überprüfen, indem diese in die Nebenbedingungen eingegeben wird. Werden diese nicht verletzt, so ist die Startlösung zulässig. 

2. Schritt: Es werden als nächstes die aktiven Indizes $I(x)$ bestimmt. Diese werden bestimmt, indem die zulässige Lösung $x$ in die Nebenbedingungen eingesetzt wird. Wird eine Nebenbedingung zur Gleichung, so ist diese Nebenbedingung ein aktives Indizee. Dieses Vorgehen wird für alle Nebenbedingungen durchgeführt.

3. Schritt: Es wird der Gradient der Zielfunktion $\frac{\partial f(x)}{\partial x}$ gebildet und die zulässige Lösung $x$ eingesetzt. Das Ergebnis stellt die zu maximierende Zielfunktion des Ersatzproblems dar, wobei $x_j := s_j$.

4. Schritt: Das Ersatzproblem wird aufgestellt und gelöst. Die Aufstellung wird wie folgt vorgenommen:

$\frac{\partial f(x)}{\partial x} \cdot s$   max!

u.d.N.

$a_i \cdot s \le 0$     $i \in I(x)$

$\frac{\partial f(x)}{\partial x} \cdot s \le 1$.

Das Ersatzproblem wird mittels Simplex-Verfahren gelöst. Hierbei muss aber die Standardform vorliegen (Maximierungsproblem, $\le$-Nebenbedingung, Nichtnegativitätsbedingung für alle Variablen). Liegt für eine Variable keine Nichtnegativitätsbedingung vor, so muss diese ersetzt werden durch (siehe: Umformung in die Standardform):

$s_j = s_j' - s_j''$  mit  $s_j', s_j'' \ge 0$

Nach Anwendung des Simplex-Verfahrens, wird dann wieder rücksubstituiert. 

Es ergibt sich dann die optimale Lösung des Ersatzproblems mit $s^*$.

5. Schritt: Es wird als nächstes bestimmt, wie weit man gehen kann ohne den zulässigen Bereich $K$ zu verlassen. Dies geschieht mit $\mu'$.

Hier werden nur diejenigen Nebenbedingungen betrachtet, die nicht aktive Indizes darstellen.

6.Schritt: Danach wird bestimmt, wie weit man gehen kann, ohne die Zielfunktion zu verschlechtern. Dies geschieht mit $\mu''$. Zunächst wird berechnet:

Einsetzen der Vektoren $x$ und $s$ und danach in die Zielfunktion $f(x) = f(x + \mu'' \cdot s)$. Danach wird diese abgleitet nach $\mu''$ und aufgelöst nach $\mu''$.

7. Schritt: Bestimmung des Minimums aus Schritt 4 und 5:

8. Schritt: Berechnung der neuen zulässigen Lösung durch:

Die Schritte 2-8 wird solange wiederholt bis bei Lösung des Ersatzproblems $s = (0,0)$ eintritt. 

Für das bessere Verständnis wird in den folgenden Abschnitten ein Bespiel aufgeführt, um die Anwendung des Verfahrens aufzuzeigen.