Benutzer:Alva2004/nlp

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Alva2004 auf.

In der Mathematik ist ein nicht lineares Programm der Prozess eine skalare Zielfunktion einer oder mehrerer reeller Variablen in einem eingeschränkten Bereich zu optimieren, wobei die Zielfunktion oder die Bereichsgrenzen nicht linear (nicht affin) sind. Es ist ein Teilgebiet der mathematischen Optimierung und ein Obergebiet der konvexen Optimierung. In Abgrenzung von den genannten Artikeln wird hier die Anwendung auf differenzierbare nichtlineare Zielfunktionen ohne Beschränkung auf Konvexität der Zielfunktion oder des Suchbereiches beschrieben. Für Begriffsklärung empfiehlt sich die Lektüre von Begriffe: Zielfunktion, Nebenbedingungen, zulässige Menge, lokale und globale Optimierung.

Anwendungsfelder

Nicht lineare Programme finden sich in vielfältiger Weise in der Wissenschaft und im Ingenieurswesen.

In der Wirtschaftswissenschaft kann es darum gehen die Kosten eines Prozesses zu minimieren, der Einschränkungen in der Verfügbarkeit der Mittel und Kapazitäten unterliegt. Die Kostenfunktion kann darin nicht linear sein. In der theoretischen Mechanik findet sich im Hamiltonschen Prinzip ein Extremalprinzip, dessen Lösung bei nichtlinearen Randbedingungen ein nichtlineares Programm darstellt.

Moderne Ingenieursanwendungen beinhalten oft und in komplizierter Weise Optimierungsaufgaben. So kann es darum gehen, das Gewicht eines Bauteils zu minimieren, das gleichzeitig bestimmten Anforderungen (z. B. Einschränkungen des Bauraumes, Obergrenzen für Verformungen bei gegebenen Lasten) genügen muss.

Bei der Anwendung eines mathematischen Modells kann es darum gehen die Parameter des Modells an gemessene Werte anzupassen. Nichtlineare Einflüsse der Parameter und Einschränkungen an die Parameter (z.B. dass nur positive Werte zugelassen sind) führen hier auf ein nichtlineares Programm.

In diesen Fragestellung ist oftmals nicht a priori bekannt, ob das gestellte Problem konvex ist oder nicht. Manchmal beobachtet man auch eine Abhängigkeit der gefundenen optimalen Lösung vom Startpunkt der Suche. Dann hat man lokale Optima gefunden und das Problem ist mit Sicherheit nicht konvex.

Problemdefinition

Es gibt viele mögliche Formulierungen eines nicht linearen Programms. An dieser Stelle soll eine möglichst allgemeine Form gewählt werden. Der Eingabeparameter ${\vec {x}}$ sei aus dem $\mathbb {R} ^{n}$, das heißt das Problem hängt von $n$ Einflussparametern ab, die im Vektor ${\vec {x}}$ eingelagert sind. Die Zielfunktion $f:D\rightarrow \mathbb {R}$ sei zwei mal stetig differenzierbar. Weiterhin seien die Nebenbedingungen (NB) $g_{i}:D\rightarrow \mathbb {R}$ mit $1\leq i\leq m$ und $h_{j}:D\rightarrow \mathbb {R}$ mit $1\leq j\leq l$ gegeben und einmal stetig differenzierbar.

Das Optimierungsproblem ist durch $P:f({\vec {x}})\rightarrow \mathrm {extremum}$ gegeben. Der zulässige Bereich $S\subset D$ wird von den Nebenbedingungen (NB) einschränkt: Für alle Werte der Parameter aus dem zulässigen Bereich (${\vec {x}}\in S$) sollen die NB erfüllt sein. Zulässig ist das Problem $P$, wenn der zulässige Bereich $S$ nicht leer ist.

Vorgehen

Das Problem wird mit unten beschriebenen Verfahren auf die Optimierung einer Hilfsfunktion ohne NB zurück geführt. Um sich die Gradienten basierten Methoden zu Nutze machen zu können, teilt man das abzusuchende Gebiet gegebenenfalls in solche auf, in denen die Zielfunktion differenzierbar ist. Wenn möglich sollten die Teilgebiete konvex sein und die Zielfunktion in ihnen auch. Dann kann man die globalen Extrema in den Teilgebieten mit den in Mathematische Optimierung und Konvexe Optimierung aufgeführten Verfahren berechnen und das optimale auswählen.

Die Konstruktion der Hilfsfunktion soll an Hand eines einfachen Beispiels erläutert werden: Zwei Kugeln in einer Mulde versuchen den tiefstmöglichen Punkt einzunehmen, dürfen sich dabei aber nicht durchdringen. Die Zielfunktion ist also die Lageenergie der Kugeln und nimmt im Gleichgewicht ein Minimum an. Die Nebenbedingung $g(x,y)\leq 0$ würde hier die Durchdringung der Kugeln $x$ und $y$ bezeichnen, wobei mit negativer Durchdringung ein positiver Abstand gemeint wird.

1. Lagrange-Multiplikatoren: Die NB werden mit reellen Faktoren, den Lagrange Multiplikatoren, multipliziert und zur Zielfunktion hinzu addiert. Die Faktoren werden als Unbekannte in das Problem eingeführt und müssen ebenfalls bestimmt werden. Bei den Kugeln sind die Lagrange Multiplikatoren gerade die Kontaktkräfte, die die Kugeln bei Berührung aufeinander ausüben, so dass sie sich nicht durchdringen.
2. Barrierefunktionen: Die NB werden mit Barrierefunktionen dargestellt, die bei Annäherung an die Grenze des Definitionsbereiches positive Werte und auf der Grenze ins Unendliche wachsen, so dass die Verletzung der NB verhindert wird. Im Kugelbild bekämen die Kugeln einen mehr oder weniger dicken Mantel, der immer steifer wird, je stärker er bei Berührung zusammen gedrückt wird. Eine Verletzung der NB wird so verhindert zu dem Preis, dass bereits die Annäherung an die Bereichsgrenze bestraft wird. Die Methode wird bei Innere-Punkte-Verfahren angewendet.
3. Straffunktionen: Die Straffunktionen werden wie die Barrierefunktionen eingesetzt. Die NB werden mit Straffunktionen dargestellt, die im Definitionsbereich verschwinden und bei Verletzung der NB ungleich null sind. Die Straffunktionen werden mit Strafparametern multipliziert und in die Zielfunktion eingebatu so dass die Verletzung der NB bestraft wird, daher der Name. Hier werden aktive NB evtl. verletzt und die Zulässigkeit der Lösung muss geprüft werden. Im Kugel-Bild entspricht die Straffunktion der „echten“Durchdringung (die bei positivem Abstand der Kugeln verschwindet) und der Strafparameter einer Federsteifigkeit. Die Feder versucht eindringende Punkte wieder an die Oberfläche zu ziehen. Je steifer die Feder ausfällt, desto geringer wird die Eindringung sein.
4. Erweiterte Lagrange Methode (engl. Augmented Lagrange method): Dies ist eine Kombination der vorhergehenden Methoden. Der Lagrange Multiplikator wird iterativ an Hand der Verletzung der NB bestimmt.
5. Trivial aber doch zu erwähnen ist, dass aktive NB dazu genutzt werden können, Variable zu eliminieren. Die Variablen werden auf Werte festgelegt, derart dass eine Verletzung der NB nunmehr unmöglich ist. Im Kugel-Bild würde man Berühungspunkte der Kugeln aneinanderkoppeln (ihre Koordinaten gleichsetzen), so dass eine Durchdringung (dort) nicht mehr stattfinden kann.

Theorie der Optimierung

Isolierte Punkte

In einem nicht linearen Programm können NB den zulässigen Bereich in einigen Punkten ${\vec {x}}$ derart einschränken, dass zwar ${\vec {x}}$ aber kein Punkt in seiner Umgebung $U_{\varepsilon }({\vec {x}})$ im zulässigen Bereich liegt. Mathematisch

$U_{\varepsilon }({\vec {x}})\cap S=\lbrace {\vec {x}}\rbrace$.

Isolierte Punkte müssen alle einzeln, jeder für sich, auf Optimalität geprüft werden.

Regularitäts-Bedingungen, Tangenten- und Linearisierender Kegel

Beispiel eines Nicht Linearen Programms

Für die Formulierung von Optimalitätsbedingungen müssen die NB gewisse Anforderungen (CQ) erfüllen, engl. constraint qualifications. Es existieren mehrere unterschiedlich scharfe Formulierungen, welche die Erfüllung dieser Anforderungen sicherstellen. Punkte, in denen die Anforderungen erfüllt sind, heißen regulär. Irreguläre Punkte, in denen keine dieser Anforderungen greift, müssen ausgeschlossen oder gesondert betrachtet werden.

Zentral für die Formulierung der Anforderungen an die NB und der Optimalitätsbedingungen ist der Begriff Tangentenkegel $T(S,{\vec {x}})$ und Linearisierender Kegel. Um sich diese anschaulich klar zu machen, stellt man sich an einen Punkt im zulässigen Gebiet und betrachtet alle am Standort aktiven NB als undurchsichtige Wände. Die Kegel sind dann das, was man vom zulässigen Bereich sieht wobei man sehr kurzsichtig ist. Alle NB die an Ort und Stelle nicht aktiv sind, verschwinden in der Ferne und werden übersehen. Steht man an einem Ort im zulässigen Bereich, an dem keine NB aktiv ist, hat man vollen Rundumblick. Der Tangentenkegel und linearisierende Kegel unterscheiden sich dort, wo zwei Wände am Standort parallel verlaufen und man dann sozusagen in einem Gang steht. Im linearisierenden Kegel kann man dann in beide Richtungen in den Gang sehen, er linearisiert die Wände. Wenn die zunächst parallelen Wände in einer Richtung unmittelbar ihre Parallelität verlieren und den Gang unmittelbar zumachen, kann man im Tangentenkegel nur in die offene Richtung sehen. Das ist der Unterschied. In der Grafik stimmen Tangentenkegel und Linearisierender Kegel im optimalen Punkt überein und sind rot angedeutet.

Die Anforderungen an die NB stellen sicher, dass im optimalen Punkt der Tangentenkegel und der linearisierende Kegel übereinstimmen. Beispiele für Formulierungen sind:

• Konvexität: Die Zielfunktion und die NB sind konvex. Das ist sehr restriktiv aber wahr.
• Slater: Es treten keine Gleichungsnebenbedingungen auf. Des Weiteren gibt es einen Punkt ${\tilde {x}}\in K$, so dass $g_{i}({\tilde {x}})<0$ für alle $1\leq i\leq m$.
• Lineare Unabhängigkeit – Linear independence constraint qualification (LICQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind linear unabhängig im Punkt ${\bar {x}}$.
• Mangasarian-Fromovitz – Mangasarian-Fromovitz constraint qualification (MFCQ): Die Gradienten der aktiven Ungleichungsbedingungen und die Gradienten der Gleichungsbedingungen sind positiv-linear unabhängig im Punkt ${\bar {x}}$.
• Konstanter Rang – Constant rank constraint qualification (CRCQ): Für jede Untermenge der Gradienten der Ungleichungsbedingungen, welche aktiv sind, und der Gradienten der Gleichungsbedingungen ist der Rang in der Nähe von ${\bar {x}}$ konstant.
• Konstante positive-lineare Abhängigkeit – Constant positive-linear dependence constraint qualification (CPLD): Für jede Untermenge der Gradienten, der Ungleichungsbedingungen, welche aktiv sind, und der Gradienten der Gleichungsbedingungen, und falls eine positive-lineare Abhängigkeit im Punkt ${\bar {x}}$ vorliegt, dann gibt es eine positiv-lineare Abhängigkeit in der Nähe von ${\bar {x}}$.

Man kann zeigen, dass die folgenden beiden Folgerungsstränge gelten

${\mbox{LICQ}}\Rightarrow {\mbox{MFCQ}}\Rightarrow {\mbox{CPLD}}$ und ${\mbox{LICQ}}\Rightarrow {\mbox{CRCQ}}\Rightarrow {\mbox{CPLD}}$,

obwohl MFCQ nicht äquivalent zu CRCQ ist. In der Praxis werden schwächere Constraint Qualifications bevorzugt, da diese stärkere Optimalitäts-Bedingungen liefern.

Optimalitätsbedingungen

Die Karush-Kuhn-Tucker-Bedingungen (auch bekannt als die KKT-Bedingungen) sind notwendig für die Optimalität einer Lösung in der nichtlinearen Optimierung. Sie wurden zum ersten Mal 1939 in der Master-Arbeit (unveröffentlicht) von William Karush aufgeführt. Bekannter wurden diese jedoch erst 1951 nach einem Konferenz-Paper von Harold W. Kuhn und Albert W. Tucker. Sie sind die Verallgemeinerung der notwendigen Bedingung $\nabla f(x)=0$ von Optimierungsproblemen ohne Nebenbedingungen.

Notwendige Bedingung und Satz von Karush-Kuhn-Tucker

In Worten bedeutet der Satz von Karush-Kuhn-Tucker ungefähr, dass wenn ${\bar {x}}$ ein zulässiger, regulärer und optimaler Punkt ist, sich der Gradient der Zielfunktion $-\nabla f({\bar {x}})$ als positive Linearkombination der Gradienten der aktiven NB darstellen läßt, siehe auch das Bild oben.

Sei $f:D\rightarrow \mathbb {R}$ die Zielfunktion und die Funktionen $g_{i}:D\rightarrow \mathbb {R}$ mit $1\leq i\leq m$ und die Funktionen $h_{j}:D\rightarrow \mathbb {R}$ mit $1\leq j\leq l$ sind Nebenbedingungs-Funktionen. Alle vorkommenden Funktionen $f,g_{i},h_{j}$ sollen einmal stetig differenzierbar. Es sei ${\bar {x}}\in S$ ein regulärer Punkt, das heißt die Regularitätsanforderung (CQ) oben ist erfüllt. Falls ${\bar {x}}$ ein lokales Optimum ist, dann existieren Konstanten $\mu _{i}$ und $\nu _{j}$ so dass

$\nabla f({\bar {x}})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}({\bar {x}})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}({\bar {x}})=0$,

$g_{i}({\bar {x}})\leq 0\,,\;\mu _{i}\geq 0\,,\;\mu _{i}g_{i}({\bar {x}})=0$ für alle $1\leq i\leq m$,

$h_{j}({\bar {x}})=0$ für alle $1\leq j\leq l$.

Jeder Punkt, in dem diese Bedingungen erfüllt sind, heißt Karush-Kuhn-Tucker-Punkt ( kurz: KKT-Punkt).

Ist ${\bar {x}}$ ein innerer Punkt des zulässigen Gebietes, in dem also keine NB aktiv sind, insbesondere keine Gleichheitsnebenbedingungen $h_{j}(x)=0$ vorliegen, dann sind wegen $g_{i}({\bar {x}})<0$ alle $\mu _{i}=0$ und die obigen Bedingungen reduzieren sich auf die bekannte notwendige Bedingung unrestringierter Probleme $\nabla f({\bar {x}})=0$.

Hinreichende Bedingungen

Ist ${\bar {x}}$ ein KKT-Punkt und es gilt

$\nabla f({\bar {x}})\cdot {\vec {d}}>0\;(\mathrm {oder} <0)$ für alle ${\vec {d}}\in T(S,{\bar {x}})\setminus \lbrace {\vec {0}}\rbrace$,

dann ist ${\bar {x}}$ ein lokales Minimum (bzw. Maximum). Dies ist ein hinreichendes Optimalitätskriterium erster Ordnung. Ein hinreichendes Optimalitätskriterium zweiter Ordnung für einen KKT-Punkt ${\bar {x}}$ ist:

$\nabla f({\bar {x}})={\vec {0}}$ und ${\vec {d}}\cdot \nabla ^{2}f({\bar {x}}){\vec {d}}>0\;(\mathrm {oder} <0)$ für alle ${\vec {d}}\in T(S,{\bar {x}})\setminus \lbrace {\vec {0}}\rbrace$.

Darin ist $T(S,{\vec {x}})$ der Tangentenkegel, siehe #Regularitäts-Bedingungen, Tangenten- und Linearisierender Kegel.

Sätze zu den Näherungsverfahren

1. Im Grenzwert der gegen null gehenden Barriereparameter geht die mit Barrierefunktionen gefundene Lösung in die mit den Lagrange Multiplikatoren gefundene Lösung über.
2. Im Grenzwert der gegen unendlich gehenden Strafparameter geht die mit Straffunktionen gefundene Lösung in die mit den Lagrange Multiplikatoren gefundene Lösung über.
3. Im Grenzwert unendlich vieler Iterationen strebt die mit der erweiterten Lagrange Methode gefundene Lösung auch gegen die mit den Lagrange Multiplikatoren gefundene Lösung.

Beispiel

Fläche f(a,b) = a b

An Hand eines einfachen Beispiels sollen die oben genannten fünf Methoden der Lösung eines Problems erläutert werden. In dem Problem soll das Produkt zweier positiver reeller Zahlen maximiert werden, deren Summe höchsten vierzehn beträgt. Mathematisch formuliert heißt das: Gesucht wird

$f\left(a,b\right)=a\cdot b\rightarrow \mathrm {max}$

mit der NB

$g\left(a,b\right)=a+b-14\leq 0$.

Es ist anschaulich klar, dass im Optimum die NB aktiv ist, sonst könnte leicht eine kleinere Lösung gefunden werden. Der einzige stationäre Punkt mit $\nabla f={\vec {0}}$ dieser in $a$ und $b$ linearen Funktion liegt in $(0,0)$ weswegen die Suche manchmal in diese Richtung geht. Dann muss man die NB gewissermaßen „in den Weg legen“, damit der Algorithmus sie „bemerkt“.

Eliminierung der Freiheitsgrade

Aus der als aktiv erkannten NB ermittelt man

$a+b-14=0\rightarrow b=14-a$

und die Hilfsfunktion hängt nur noch von $a$ ab, so dass die Lösung mittels Kurvendiskussion berechnet werden kann:

${\begin{array}{l}\Pi (a):=f(a,14-a)=a\cdot (14-a)=14a-a^{2}\rightarrow \mathrm {max} \\\rightarrow \Pi '(a)=14-2a=0\rightarrow a=7\rightarrow b=14-7=7\\\rightarrow \Pi ''(a=7)=-2<0\end{array}}$.

Man sieht:

1. Die Hilfsfunktion hat nur noch eine Variable.
2. Die Lösung ist korrekt, denn es handelt sich um ein Maximum.
3. Das Verfahren findet vor allem dann Anwendung, wenn bekannt ist, dass die NB aktiv ist, z.B. im Kontakt fest verklebter Bauteile.

Lagrange Multiplikator

Hier wird die $\lambda$ fache NB von der Zielfunktion subtrahiert, worin der Faktor $\lambda$ der Lagrange Multiplikator ist und wie eine zusätzliche Unbekannte behandelt wird. Die Subtraktion wird gewählt, damit die Gradienten der Zeilfunktion und der Nebenbedingung entgegengesetzt sind. Ansonsten würde sich ein negativer Lagrange Multiplikator ergeben. Die Hilfsfunktion lautet hier also:

$\Pi (a,b,\lambda )=a\cdot b-\lambda (a+b-14)\rightarrow \mathrm {max}$.

Im Minimum verschwinden alle Ableitung nach allen Variablen:

${\begin{array}{l}{\frac {\partial \Pi }{\partial a}}=b-\lambda =0\rightarrow \lambda =b\\{\frac {\partial \Pi }{\partial b}}=a-\lambda =0\rightarrow a=\lambda =b\\{\frac {\partial \Pi }{\partial \lambda }}=14-a-b=14-2a=0\rightarrow a=b=\lambda =7\end{array}}$.

und die Lösung $a=b=7$ ist gefunden. Wegen $g(a=7,b=7)=0$ und $\lambda =7\geq 0$ ist die Karush-Kuhn-Tucker-Bedingung erfüllt. Das obige Gleichungssystem kann als Matrizengleichung geschrieben werden:

$\left({\begin{array}{ccc}1&0&-1\\0&1&-1\\-1&-1&0\end{array}}\right)\left({\begin{array}{c}b\\a\\\lambda \end{array}}\right)=\left({\begin{array}{c}0\\0\\-14\end{array}}\right)$

Die Methode der Lagrangeschen Multiplikatoren:

• erfüllt die NB exakt,
• führt zusätzliche Unbekannte ($\lambda$) ein,
• schleust verschwindende Diagonalelemente in das Gleichungssystem ein,
• kann anhand des Vorzeichens von $\lambda$ beurteilen, ob die Nebenbedingung aktiv ist oder nicht (positiv bei Aktivität).

Barrierefunktion

Mit Barrierefunktionen können Neben-Bedingungen mit Sicherheit erfüllt werden zu dem Preis, dass im Optimum die NB nicht ausgereizt wird. Bei der Suche nach einer Lösung wird zur Ziel-Funktion $f$ das $r$-fache einer Barrierefunktion hinzu addiert, z. B.:

$\Pi \left(a,b\right)=a{\cdot }b+2r\ln(14-a-b)\rightarrow \mathrm {max}$.

Darin ist $\ln(14-a-b)$ die Barrierefunktion und $2r$ der Barriereparameter. Im Extremum verschwinden wieder alle Ableitungen:

${\begin{array}{c}{\frac {{\partial }\Pi }{\partial a}}=b-{\frac {2r}{14-a-b}}=0\\{\frac {{\partial }\Pi }{\partial b}}=a-{\frac {2r}{14-a-b}}=0\end{array}}$,

und daher $a=b$ sowie $a(14-2a)-2r=-2(a^{2}-7a+r)=0$ , was die Lösung

$a=b={\frac {7}{2}}{\pm }{\sqrt {{\frac {49}{4}}-r}}$

besitzt, die für $r\rightarrow 0$ die Lösungen $(a,b)\in \{(0,0),(7,7)\}$ besitzt. Bei der iterativen Suche mit dem Newton-Raphson Verfahren bekommt man die Vorschrift

${\nabla }\Pi +{\nabla }^{2}\Pi \Delta {\vec {x}}=\left({\begin{array}{c}b-{\frac {2r}{14-a-b}}\\a-{\frac {2r}{14-a-b}}\end{array}}\right)+\left({\begin{array}{cc}-{\frac {2r}{(14-a-b)^{2}}}&1-{\frac {2r}{{\left(14-a-b\right)}^{2}}}\\1-{\frac {2r}{(14-a-b)^{2}}}&-{\frac {2r}{{\left(14-a-b\right)}^{2}}}\end{array}}\right)\left({\begin{array}{c}\Delta a\\\Delta b\end{array}}\right)=\left({\begin{array}{c}0\\0\end{array}}\right)$

für die Berechnung des Inkrements $\Delta a$ und $\Delta b$. Die Determinante der Hesse-Matrix ${\nabla }^{2}\Pi$ lautet:

${\frac {4r^{2}}{(14-a-b)^{4}}}-\left(1-{\frac {2r}{(14-a-b)^{2}}}\right)^{2}={\frac {4r}{(14-a-b)^{2}}}-1$ .

Man sieht:

• Die Nebenbedingung wird erfüllt.
• Im Grenzwert $r\rightarrow 0$ erhält man die exakte Lösung.
• Nicht für alle Werte von $r$ existiert eine Lösung. Allgemein stimmen die Höhenlinien der Hilfsfunktion nicht mit denen der Zielfunktion überein.
• Bei Annäherung an die Lösung und mit $r\rightarrow 0$ ist die Hesse-Matrix schlecht konditioniert.
• Bei einer Gradienten basierten Suche muss sicher gestellt werden, dass das Inkrement in den Unbekannten nicht so groß ist, dass man aus Versehen auf der falschen Seite der Barriere landet, wo die Barrierefunktion in diesem Beispiel nicht definiert ist.

Strafverfahren

Mit Straf-Verfahren können Neben-Bedingungen näherungsweise erfüllt werden. Bei der Suche nach einer Lösung wird von der Ziel-Funktion $f$ das $r$-fache einer Straffunktion abgezogen (soll ja die Verletzung bestrafen):

$\Pi (a,b)=a\cdot b-{\frac {r}{n}}\cdot \mathrm {max} (0,a+b-14)^{n}\rightarrow \mathrm {max}$.

Darin ist $r$ der Straf-Parameter und $\mathrm {max} (0,a+b-14)^{n}$ die Straffunktion. Mit $n=1$ nennt man die Straffunktion exakt, sie ist aber nicht differenzierbar. Hier soll $n=2$ benutzt werden. Im Extremum verschwinden wieder alle Ableitungen:

${\begin{array}{l}{\frac {\partial \Pi }{\partial a}}=b-r\cdot \mathrm {max} (0,a+b-14)=b-r(a+b-14)=0\rightarrow a+(1-{\frac {1}{r}})b=14\\{\frac {\partial \Pi }{\partial b}}=a-r\cdot \mathrm {max} (0,a+b-14)=0\rightarrow (1-{\frac {1}{r}})a+b=14\end{array}}$.

Mit $a+b-14\leq 0$ bekommt man $a=b=0$ weswegen man hier im „verbotenen“ Gebiet $a+b-14>0$ starten muss. Dann hat man das Gleichungssystem

$\left({\begin{array}{cc}1-{\frac {1}{r}}&1\\1&1-{\frac {1}{r}}\end{array}}\right)\left({\begin{array}{c}a\\b\end{array}}\right)=\left({\begin{array}{c}14\\14\end{array}}\right)$,

mit der Lösung

$a=b={\frac {14r}{2r-1}}$,

die für $r\rightarrow \infty$ in die Lösung $a=b=7$ übergeht.

Man sieht:

• Die Nebenbedingung wird nur näherungsweise erfüllt aber mit wachsendem Strafparameter immer besser, allerdings nur weil hier exakt gerechnet werden kann. Bei numerischer Lösung des Gleichungssystems würden Rundungsfehler mit wachsendem Strafparameter zu Fehlern führen.
• Der Grund hierfür liegt darin, dass auch hier mit zunehmendem Strafparameter der Wert der Determinante des Gleichungssystems $\left(1-{\frac {1}{r}}\right)^{2}-1={\frac {1}{{r}^{2}}}-{\frac {2}{r}}$ gegen null geht. Das Problem ist zunehmend schlecht gestellt.
• Es muss ein Kompromiss hinsichtlich der Konditionierung des Gleichungssystems und der Genauigkeit der Erfüllung der NB gefunden werden.
• Durch Einsetzen von $a$ und $b$ in die NB kann geprüft werden, wie stark sie verletzt wird.
• Es werden keine verschwindenden Diagonalelemente eingeschläust und das Verfahren gilt als numerisch robust.

Erweiterte oder verallgemeinerte-Lagrange-Methode

Die erweiterte oder verallgemeinerte Lagrange-Methode (engl. augmented-Lagrange-Methode) benutzt die Strafparameter, um die Lagrangeschen Multiplikatoren näherungsweise zu berechnen. Bei der Suche nach einer Lösung wird nun von der Zielfunktion $f$ das ${\lambda }_{i}$-fache der NB und das $r$-fache einer Straffunktion abgezogen (Strafidee):

$\Pi (a,b)=a\cdot b-{\frac {1}{2r}}\left(\mathrm {max} (0,\lambda _{i}+r(a+b-14))^{2}-{\lambda }_{i}^{2}\right)\rightarrow \mathrm {max}$.

Im Extremum verschwinden alle Ableitungen:

${\begin{array}{l}{\frac {\partial \Pi (a,b)}{\partial a}}=b-\mathrm {max} (0,\lambda _{i}+r(a+b-14))=0\\{\frac {\partial \Pi (a,b)}{\partial b}}=a-\mathrm {max} (0,\lambda _{i}+r(a+b-14))=0\end{array}}$.

Mit $a+b-14\leq 0$ bekommt man $a=b=0$ weswegen man auch hier im „verbotenen“ Gebiet $a+b-14>0$ starten muss. Dann bekommt man aus

${\begin{array}{l}b-\lambda _{i}-r(a+b-14)=0\rightarrow a+\left(1-{\frac {1}{r}}\right)b=14-{\frac {\lambda _{i}}{r}}\\a-\lambda _{i}-r(a+b-14)=0\rightarrow \left(1-{\frac {1}{r}}\right)a+b=14-{\frac {\lambda _{i}}{r}}\end{array}}$

das Gleichungssystem

$\left({\begin{array}{cc}1-{\frac {1}{r}}&1\\1&1-{\frac {1}{r}}\end{array}}\right)\left({\begin{array}{c}a\\b\end{array}}\right)=\left({\begin{array}{c}14-{\frac {\lambda _{i}}{r}}\\14-{\frac {\lambda _{i}}{r}}\end{array}}\right)$,

das die Lösung

${a}_{i+1}={b}_{i+1}={\frac {14r-{\lambda }_{i}}{2r-1}}=7+{\frac {7-\lambda _{i}}{2r-1}}$

hat.

Die numerische Suche des Extremums mit der erweiterten Lagrange-Methode

1. startet normalerweise mit $i=0$ und den Anfangswerten ${a}_{0}={b}_{0}={\lambda }_{0}=0$,
2. berechnet $a_{i+1}$ und ${b}_{i+1}$ (im nicht-linearen Fall Iteration bis zur Konvergenz),
3. setzt ${\lambda }_{i+1}=\mathrm {max} (0,\lambda _{i}+r\cdot g(a_{i+1},b_{i+1}))=\mathrm {max} (0,\lambda _{i}+r\cdot (a_{i+1}+b_{i+1}-14))$ und
4. bricht ab, wenn ein geeignetes Konvergenzkriterium erfüllt ist oder inkrementiert $i$ und kehrt in Schritt 2 zurück.

Hier muss allerdings ein Startwert mit $a+b-14>0$ vorgegeben werden, damit der Punkt $(a,b)=(7,7)$ gefunden werden kann. Mit $r=100\,,\;a_{0}=100$ und $b_{0}=0$ ergibt sich bis zu einem Fehler $|a_{i+1}+b_{i+1}-14|<10^{-10}$ folgender Iterationsverlauf:

$i$	$a_{i}$	$\lambda _{i}$	$a_{i}b_{i}-a_{i-1}b_{i-1}$	$a_{i}+b_{i}-14$
1	7.03015075377	7.03015075377	49.4230196207	0.0603015075377
2	6.99984848867	6.99984848867	-0.425140756318	-0.000303022650945
3	7.00000076136	7.00000076136	0.00213179468975	1.52272689036e-06
4	6.99999999617	6.99999999617	-1.07126520774e-05	-7.65189511753e-09
5	7.00000000002	7.00000000002	5.38324300692e-08	3.84527965025e-11
6	7.0	7.0	-2.70524935786e-10	-1.93622895495e-13

Die erweiterte Lagrange-Methode

• erfüllt die Neben-Bedingung beliebig genau,
• führt weder neue Unbekannte noch große Terme in das Gleichungssystem ein,
• benötigt dazu mehrere konvergierte Lösungen des globalen Problems (im zweiten Schritt) und
• kann die Aktivität der Neben-Bedingung an ${\lambda }_{i}$ messen.

Literatur

• Avriel, Mordecai: Nonlinear Programming: Analysis and Methods. Dover Publishing, 2003, ISBN 0-486-43227-0.
• R. Andreani, J. M. Martínez, M. L. Schuverdt: On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, 2005, pp. 473–485.
• Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2003, ISBN 3-540-43575-1.
• R. Reinhardt, A. Hoffmann, T. Gerlach: Nichtlineare Optimierung. Springer 2013. ISBN 978-3-8274-2948-3.

Weblinks

• Buch Convex Optimization von Stephen Boyd und Lieven Vandenberghe im pdf-Format (engl.)

Kategorie:Optimierung