Die KKT-Bedingungen stellen für ein gleichungsrestringiertes Optimierungsproblem ein nichtlineares Gleichungssystem dar. Dieses Gleichungssystem kann unter geeigneten Voraussetzungen mit dem lokalen Newton-Verfahren gelöst werden. Die resultierende Spezialisierung des Newton-Verfahrens, die wir in Abschnitt 10.1 ausformulieren werden, bezeichnet man als Lagrange-Newton-Verfahren.
Die linearen Gleichungen, die in jeder Iteration dieses Lagrange-Newton-Verfahrens zu lösen sind, lassen sich als KKT-Bedingungen für ein gewisses gleichungsrestringiertes quadratisches Minimierungsproblem interpretieren. Ersetzt man nun die linearen Gleichungen durch dieses quadratische Minimierungsproblem, so erhält man ein lokales Sequential Quadratic Programming (SQP-)Verfahren. In Abschnitt 10.2 werden wir Konvergenzaussagen für dieses Verfahren herleiten.
Die Gleichungsnebenbedingungen in dem quadratischen Optimierungsproblem, welches in dem SQP-Verfahren zu lösen ist, kann man dadurch erzeugen, dass man die in den Gleichungsnebenbedingungen des Ausgangsproblems auftretenden Funktionen durch lineare Taylor-Approximationen in der aktuellen Iterierten ersetzt. Es liegt dann nahe, Ungleichungsnebenbedingungen in einem SQP-Verfahren so zu behandeln, dass man sie wie die Gleichungsrestriktionen linearisiert. Das auf diese Weise entstehende lokale SQP-Verfahren für allgemeine nichtlineare Optimierungsprobleme werden wir abschließend in Abschnitt 10.3 auf seine Konvergenzeigenschaften hin untersuchen.
Wir gehen im Folgenden von Funktionen
und von dem allgemeinen gleichungsrestringierten Optimierungsproblem

aus. Wie zuvor sei

die zu
gehörende Lagrange-Funktion und seien
- (10.1)
![{\displaystyle A(x):=\left[\nabla h_{j}(x)^{T}\right]_{j=1,\ldots ,m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b81e55f28d5cb0b8de6113a3a8fd50835b6dc645)
die
-Jacobi-Matrix zu den
sowie

Schließlich sei der Nullraum einer Matrix
gegeben durch

Nach Korollar 9.9 gilt nun: ist
ein lokaler Minimalpunkt von
, in dem die LICQ, d. h. die Rangbedingung

erfüllt ist, so gibt es Multiplikatoren
, so dass
die KKT-Bedingungen für
erfüllt. Diese lauten
- (10.2)

Sie stellen ein System aus
Gleichungen in den
Unbekannten
dar. Zu diesem System gehört die in diesem Fall symmetrische Jacobi-Matrix
- (10.3)

Zur Lösung des Gleichungssystems in (10.2) kann man das in Abschnitt 6.1.1 beschriebene lokale Newton-Verfahren verwenden. Das für (10.2) ausformulierte Verfahren bezeichnet man als Lagrange-Newton-Verfahren:
Algorithmus 10.1 (Lagrange-Newton-Verfahren)
[Bearbeiten]
- (0) Wähle
und setze
.
- (1) Falls
für
aus (10.2) ist, stop! (Dann ist
ein KKT-Punkt für
.)
- (2) Bestimme eine Lösung
des linearen Gleichungssystems
- (10.4)

- und setze

- (3) Setze
und gehe nach (1).
Damit der Konvergenzsatz 6.3 für das Newton-Verfahren auf Algorithmus 10.1 angewendet werden kann, muss die Nichtsingularität der Jacobi-Matrix
in
sichergestellt werden. Das folgende Lemma gibt Bedingungen an, unter denen diese Nichtsingularität gewährleistet ist.
- Es seien
und es sei
ein strikt lokaler Minimalpunkt von
, für den
gilt und für den mit Multiplikatoren
die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 9.12
- (10.5)

- erfüllt sind. Dann ist
nichtsingulär.
Es gelte
, d. h.
- (10.6)

- (10.7)

Die zweite Gleichung besagt, dass
ist und somit gilt:
![{\displaystyle 0=p_{y}^{T}A(x^{*})p_{x}=[A(x^{*})p_{x}]^{T}p_{y}=p_{x}^{T}A(x^{*})^{T}p_{y}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8c059f1771c3628879fb3577ecb408d8608e505)
Multiplikation der Gleichung (10.6) von links mit
ergibt daher

so dass mit (10.5)
folgt. Wegen (10.6) ist folglich
, was mit der vorausgesetzten Rangbedingung für
auch
impliziert.
q.e.d.
Man beachte, dass die erste Bedingung in (10.5) zusammen mit der für einen lokalen Minimierer
von
implizit geltenden Bedingung
mit der Bedingung
äquivalent ist.
Für die quadratische Konvergenz von Algorithmus 10.1 benötigt man gemäß Satz 6.3 die lokale Lipschitz-Stetigkeit der durch (10.3) definierten Abbildung
in
.
- Eine Abbildung
heißt lokal Lipschitz-stetig in
, wenn mit einem
und einem
- (10.8)

- gilt, wobei
eine
-Umgebung und
eine Vektornorm auf
bzw. die dadurch induzierte Matrixnorm auf
ist.
Eine mit
bezeichnete
-Umgebung von
wird in diesem Manuskript ausschließlich mittels der Euklidischen Norm definiert und wird daher in dieser Definition nicht verwendet.
Unter Verwendung der Tatsache, dass Normen auf einem endlich-dimensionalen Vektorraum äquivalent sind (s. Satz 2.4, Optimierung I), sieht man leicht ein, dass eine Abbildung
, die in
bezüglich einer gegebenen Vektornorm und der durch sie induzierten Matrixnorm lokal Lipschitz-stetig ist, diese Eigenschaft auch bezüglich jeder anderen Vektornorm und induzierten Matrixnorm besitzt.
- Seien
. Sind die Abbildungen
und
in
lokal Lipschitz-stetig, so ist die durch (10.3) definierte Abbildung
in
lokal Lipschitz-stetig.
Für
und
sei

wobei sich die Dimension
des zugrunde gelegten Raums aus dem Zusammenhang ergebe. Offenbar gilt für alle
und

Laut Voraussetzung existieren Konstanten
und
, so dass für alle
gilt:

Weiter gibt es Konstanten
und
, so dass für alle
folgt

![{\displaystyle \leq \left\|\nabla ^{2}f(x^{*})-\nabla ^{2}f(x)\right\|_{\infty }+\left\|\sum _{j=1}^{m}\left[y_{j}^{*}-y_{j}\right]\nabla ^{2}h_{j}(x^{*})\right\|_{\infty }+\left\|\sum _{j=1}^{m}y_{j}\left[\nabla ^{2}h_{j}(x^{*})-\nabla ^{2}h_{j}(x)\right]\right\|_{\infty }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/175025e2483dc3cee20e0f26d99ca3f4302e3398)



Ferner gibt es wegen
ein
, so dass für alle
gilt:
![{\displaystyle \left\|A(x^{*})-A(x)\right\|_{\infty }=\left\|\left[\nabla h_{j}(x^{*})^{T}-\nabla h_{j}(x)^{T}\right]_{j=1,\ldots ,m}\right\|_{\infty }=\max _{1\leq j\leq m}\left\|\nabla h_{j}(x^{*})-\nabla h_{j}(x)\right\|_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87e6e4e04a5d9a9e4cdd073f5492c237d85cb1b1)

Da man überdies wegen der Äquivalenz von Normen auf endlich-dimensionalen Räumen für ein
die folgenden Beziehungen hat
![{\displaystyle \left\|[A(x^{*})-A(x)]^{T}\right\|_{\infty }=\left\|A(x^{*})-A(x)\right\|_{1}\leq C\left\|A(x^{*})-A(x)\right\|_{\infty },}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb254299eed2f93f509443094dfc03a68341c78f)
erschließt man zusammen für alle
![{\displaystyle \left\|{\mathcal {J}}_{F}(x^{*},y^{*})-{\mathcal {J}}_{F}(x,y)\right\|_{\infty }=\left\|{\begin{pmatrix}\nabla _{xx}^{2}L(x^{*},y^{*})-\nabla _{xx}^{2}L(x,y)&[A(x^{*})-A(x)]^{T}\\A(x^{*})-A(x)&0\end{pmatrix}}\right\|_{\infty }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ea16c3382961d65c954764463f64195f9dcb718)


q.e.d.
Aus dem Konvergenzsatz 6.3 für das Newton-Verfahren können wir nun unter Anwendung von Lemma 10.2 und Aufgabe 10.4 die folgende Aussage für Algorithmus 10.1 ableiten, wobei wir
statt
schreiben.
- Es seien
und es sei
ein strikt lokaler Minimalpunkt von
mit zugehörigen Multiplikatoren
, für den
gilt und die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus (10.5) erfüllt sind. Dann gibt es eine Umgebung
von
für ein
, so dass Algorithmus 10.1 für jeden Startpunkt
durchführbar ist und er, sofern er nicht nach endlich vielen Schritten mit
abbricht, eine Folge
erzeugt, für welche gilt:
- (i)
konvergiert superlinear gegen
.
- (ii) Sind
und
in
lokal Lipschitz-stetig, so konvergiert
quadratisch gegen
.
10.2 Das Lagrange-Newton-Verfahren als SQP-Verfahren
[Bearbeiten]
Wendet man das lokale oder globalisierte Newton-Verfahren zur unrestringierten Minimierung einer Funktion
an (Algorithmen 6.5 und 6.7), so hat man in der
-ten Iteration das lineare Gleichungssystem
- (10.9)

zu lösen. Ist dann die Matrix
positiv definit, was für jedes
in der Umgebung eines lokalen Minimierers
von
, für den
positiv definit ist, garantiert werden kann, so ist das System in (10.9) eindeutig lösbar und kann dieses System auch als Optimalitätsbedingung erster Ordnung für den eindeutigen Minimalpunkt des quadratischen Optimierungsproblems
- (10.10)
![{\displaystyle \min _{x\in \mathbb {R} ^{n}}\left[{\frac {1}{2}}p^{T}\nabla ^{2}f(x^{k})p+\nabla f(x^{k})^{T}p\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b35332e14fc3925641476c20cb8c913f785a17b4)
aufgefasst werden (vgl. Abschnitt 6.1.2). Unter den genannten Voraussetzungen existiert also eine Umgebung von
, für die im Newton-Verfahren die Aufgabe, das System in (10.9) zu lösen, äquivalent gegen die Minimierungsaufgabe (10.10) ausgetauscht werden kann. Gemäß dieser Interpretation minimiert man in der
-ten Iteration des Newton-Verfahrens eine quadratische Näherung der Zielfunktion
des Problems bei
. (Man addiere die Konstante
zu der Funktion in (10.10) hinzu.)
Ähnlich kann man nun das lineare Gleichungssystem (10.4) im
-ten Schritt des Lagrange-Newton-Verfahrens, welches sich auf das gleichungsrestringierte Optimierungsproblem
bezieht, als KKT-Bedingungen zu folgendem in
definierten quadratischen Optimierungsproblem interpretieren:
- (10.11)

Denn ist
wieder wie in (10.1) definiert, so sind die KKT-Bedingungen zu diesem Problem durch die Gleichungen


gegeben bzw. in Matrix-Vektor-Schreibweise durch
- (10.12)

Das lineare Gleichungssystem in (10.12) ist zu dem in (10.4) äquivalent, was man erkennt, wenn man in (10.12)
sowie
setzt. Besitzt also das KKT-System (10.12) eine eindeutige Lösung
, so löst
- (10.13)

das System (10.4). Umgekehrt gewinnt man aus einer Lösung
von (10.4) mittels
- (10.14)

eine Lösung von (10.12).
Wenn wir das lineare Gleichungssystem (10.4) im Lagrange-Newton-Verfahren durch die Minimierungsaufgabe (10.11) ersetzen wollen, haben wir allerdings noch zu garantieren, dass diese überhaupt eine lokale Lösung besitzt. Wie wir unten zeigen werden, ist Letzteres aber unter den Voraussetzungen des Konvergenzsatzes für das Lagrange-Newton-Verfahren (Satz 10.5) in einer geeigneten gewählten Umgebung des lokalen Minimierers von
gesichert.
Wir wollen noch eine Interpretation für das quadratische Optimierungsproblem in (10.11) geben. Multipliziert man die Gleichungsnebenbedingungen in diesem Problem von links mit
, so erhält man
![{\displaystyle (y^{k})^{T}h(x^{k})=(y^{k})^{T}A(x^{k})p=\left[A(x^{k})^{T}y^{k}\right]^{T}p.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c47a5bce42e0d7525e13f78adb999f1a06c0bc1)
Der Ausdruck
ist also für alle für (10.11) zulässigen Punkte
konstant. Folglich könnten wir diesen Ausdruck sowie die Konstante
zur Zielfunktion von Problem (10.11) hinzu addieren und könnten wir diese in der Form

darstellen. Die Aufgabe (10.11) können wir demnach so interpretieren, dass eine quadratische Näherung der Lagrange-Funktion von
bezüglich
in
unter linearen Näherungen der Gleichungsnebenbedingungen von
in
zu minimieren ist.
Algorithmus 10.1 lässt sich also auch äquivalent als SQP-Verfahren formulieren, wobei SQP für Sequential Quadratic Programming steht und sich auf die Tatsache bezieht, dass in jeder Iteration des Verfahrens ein quadratisches Optimierungsproblem zu lösen ist.
Algorithmus 10.6 (Lokales SQP-Verfahren für Gleichungsnebenbedingungen)
[Bearbeiten]
- (0) Wähle
und setze
.
- (1) Falls
für
aus (10.2) ist, stop! (Dann ist
ein KKT-Punkt für
.)
- (2) Berechne eine lokale Lösung
des quadratischen Optimierungsproblems

- und berechne zugehörige Multiplikatoren
. Setze

- (3) Setze
und gehe nach (1).
Das Problem
kann mittels irgendeiner Methode zur Lösung gleichungsrestringierter quadratischer Optimierungsprobleme gelöst werden, welche gleichzeitig auch Multiplikatoren zu einer Lösung mitliefert. Siehe z. B. die in Abschnitt 7.4, Optimierung I, beschriebene Nullraum-Methode oder die Methode der direkten Lösung des KKT-Systems zu
, welches hier durch (10.12) gegeben ist und dessen Lösung
gemäß (10.14) die Lösung
von
liefert.
Für den Nachweis der Durchführbarkeit und Konvergenz dieses Verfahrens benötigen wir nun zwei Resultate.
- Es seien
und
gegeben, wobei
symmetrisch und
seien. Gilt
- (10.15)

- so besitzt das Problem
- (10.16)

- eine eindeutige (lokale und gleichzeitig globale) Lösung mit eindeutigen Multiplikatoren.
Ist
eine Matrix, deren Spalten eine Basis von
bilden, so ist jedes
in der Form
mit einem
darstellbar. Gemäß der Voraussetzung in (10.15) gilt somit

Nach Satz 7.13, Optimierung I, sind daher das Problem (10.16) und das zugehörige KKT-System eindeutig lösbar.
q.e.d.
Im nächsten Lemma wird verwendet, dass die Definitionen der Zeilensummen- und Spaltensummennorm für
-Matrizen auf
-Matrizen ausgedehnt werden können. Wie man durch eine direkte Abschätzung sofort erkennt, hat man auch in diesem Fall für alle
die Abschätzungen

- Es sei
eine symmetrische Matrix und
eine Matrix mit
und es gelte
- (10.17)

- Dann existiert ein
, so dass für alle
und für alle symmetrischen Matrizen
mit

folgt:
- (10.18)

Wäre die Definitheitsbedingung in (10.18) nicht richtig, dann gäbe es Folgen
und
mit

und

wobei ohne Beschränkung der Allgemeinheit
und
für ein
mit
angenommen werden könnte. Damit erhielte man


und
- (10.19)

Im Widerspruch zu (10.17) folgte daraus aber
und
.
Ähnlich könnte man schließen: gäbe es Folgen
und
mit

so könnte man analog zu (10.19) schließen:


Damit wäre
, was jedoch wegen
im Widerspruch zur Voraussetzung
steht.
q.e.d.
Mit dem Vorangehenden lässt sich nun der folgende Satz beweisen.
- Es seien
und es sei
ein strikt lokaler Minimalpunkt von
, in dem
gilt und mit Multiplikatoren
die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 9.12
- (10.20)

- erfüllt sind. Dann gibt es eine Umgebung
von
für ein
, so dass für Algorithmus 10.6 mit
gilt:
- (i) Für jedes
hat das Problem
eine eindeutige (lokale und gleichzeitig globale) Lösung
mit eindeutigen zugehörigen Multiplikatoren
.
- (ii) Bricht Algorithmus 10.6 nicht nach endlich vielen Iterationen ab, so konvergiert die durch ihn erzeugte Folge
superlinear und, falls
und
in
lokal Lipschitz-stetig sind, sogar quadratisch gegen
.
Es sei
das
aus Satz 10.5, welches dem
aus Satz 6.3 und dessen Beweis entspreche.
Aufgrund der Stetigkeit von
und
in
bzw.
folgt wegen (10.20) mit Lemma 10.8, dass ein
existiert, so dass für alle
gilt:

Für
besitzt somit Problem
nach Lemma 10.7 eine eindeutige Lösung
mit eindeutigen Multiplikatoren
(s. Lemma 9.8). Demnach löst
die KKT-Bedingungen in (10.12) und ist
die Lösung des Systems (10.4) für
im Lagrange-Newton-Verfahren (vgl. (10.13)). Der Beweis von Satz 6.3 zeigt, dass dann auch
für das Lagrange-Newton-Verfahren und, wie (10.14) zeigt, auch für Algorithmus (10.6) gegeben ist. Die Aussagen des Satzes folgen damit induktiv, wobei sich Aussage (ii) aus Satz 10.5 ergibt.
q.e.d.
Unter den Voraussetzungen von Satz 10.9 bzw. von Satz 10.5 erzeugen also die Algorithmen 10.6 und 10.1 dieselben Iterierten
, wenn man in beiden Fällen denselben Startpunkt
wählt und dieser nahe genug bei
liegt.
10.3 Das SQP-Verfahren für allgemeine Probleme
[Bearbeiten]
Es liegt nun nahe, den Algorithmus 10.6 auf allgemeine nichtlineare Optimierungsprobleme der Gestalt

zu erweitern, indem man die Ungleichungsbedingungen aus Problem
in linearisierter Form mit in das Unterproblem aufnimmt. Setzen wir
voraus und definieren wir die zu
gehörende Lagrange-Funktion durch

so gelangen wir auf diese Weise zu dem nachstehenden Algorithmus.
Algorithmus 10.10 (Lokales SQP-Verfahren für allgemeine Probleme)
[Bearbeiten]
- (0) Wähle
mit
und
. Setze
.
- (1) Falls
die KKT-Bedingungen von
erfüllt, stop!
- (2) Berechne eine lokale Lösung
des quadratischen Optimierungsproblems

- und zugehörige Multiplikatoren
(mit
). Setze

- (3) Setze
und gehe nach (1).
Im Folgenden sei
wieder der zulässige Bereich von
und

die Menge der in
aktiven Indizes. Weiter sei
die Matrix mit Zeilen

Der Beweis der lokalen Konvergenz von Algorithmus 10.10 beruht darauf, dass die Menge der aktiven Indizes des Problems
für alle
aus einer Umgebung eines lokalen Minimalpunktes
von
unter geeigneten Voraussetzungen an
konstant bleibt und gleich der (im Allgemeinen a priori unbekannten) Menge
ist. Damit lässt sich zeigen, dass eine Folge
von lokalen Lösungen der Teilprobleme
mit zugehörigen Multiplikatoren
existiert, so dass Algorithmus 10.10 lokal dieselben Iterierten erzeugt wie das Lagrange-Newton-Verfahren für das gleichungsrestringierte Optimierungsproblem
- (10.21)

Demzufolge kann der Konvergenzsatz für den gleichungsrestringierten Fall lokal auf den allgemeinen Fall angewandt werden.
Der etwas knifflige Beweis des folgenden Konvergenzsatzes mag übergangen werden. Wir geben ihn der Vollständigkeit halber für den interessierten Leser an, weil der Satz nicht in genau der Form, wie er hier formuliert ist, in der Standardliteratur zu finden ist und weil der Beweis auch nur auf Ergebnisse zurückgreift, die an dieser Stelle zur Verfügung stehen.
- Es seien
und es sei
ein strikt lokaler Minimalpunkt von
mit Multiplikatoren
, in dem die LICQ, d. h.
- (10.22)

- gilt und für den die strikte Komplementaritätsbedingung, d. h.
- (10.23)

- für alle
erfüllt ist. Ferner genüge
den hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 9.12:
- (10.24)

- Dann gibt es ein
, so dass bei Wahl
für Algorithmus 10.10 gilt:
- Bricht der Algorithmus nicht nach endlich vielen Iterationen ab, so existiert eine Folge
lokaler Lösungen der Probleme
und eine Folge zugehöriger Multiplikatoren
, so dass die durch den Algorithmus erzeugte Folge
superlinear und, falls
und
in
lokal Lipschitz-stetig sind, sogar quadratisch gegen
konvergiert.
Siehe Geiger/Kanzow.
Die Hesse-Matrix der Lagrange-Funktion in Algorithmus 10.10 kann durch eine geeignete Quasi-Newton-Approximation ersetzt werden. Allerdings muss dann sichergestellt werden, dass die im Verfahren erzeugten Matrizen positiv definit bleiben. Letzteres ist insbesondere für eine bestimmte Modifikation der BFGS-Update-Formel der Fall (s. [GeiKa02]).
Ferner verwendet man SQP-Verfahren im Allgemeinen in globalisierter Form, d. h. in Verbindung mit einer Schrittweitenregel. In diesem Zusammenhang kann man zeigen, dass die durch Lösung des quadratischen Unterproblems
gewonnene Richtung
unter gewissen Voraussetzungen eine Abstiegsrichtung für die exakte
-Penalty-Funktion ist. Die Schrittweite in einem globalisierten SQP-Verfahren wird deshalb häufig mittels dieser Funktion und einer Armijo-artigen Regel bestimmt.
Im Hinblick auf die Globalisierung und praktische Effizienz von SQP-Verfahren sind aber noch weitere Schwierigkeiten zu bewältigen. So kann der zulässige Bereich des quadratischen Unterproblems leer sein, so dass dieses Problem modifiziert werden muss. Darüber hinaus ist es möglich, dass die gewünschte superlineare Konvergenz nicht eintritt, so dass man geeignete Gegenmaßnahmen zu treffen hat. Letzteres Phänomen wird als Maratos-Effekt bezeichnet. Für die Details verweisen wir wieder auf [GeiKa02] und [NoWri06].
Die so modifizierten SQP-Verfahren gehören zu den besten Methoden zur Lösung nichtlinearer Optimierungsprobleme, zumindest für Probleme, die nicht mehr als einige Hundert Variable haben. Es sei aber darauf hingewiesen, dass die hier diskutierten Lagrange-Multiplier- und SQP-Verfahren typischerweise keine Iterierten erzeugen, die zulässige Punkte für das Ausgangsproblem sind. Ein spezielles SQP-Verfahren, welches zulässige Iterierte liefert, ist in [LawTi01] vorgeschlagen worden. Die Zulässigkeit der Iterierten ist in einem solchen Verfahren zumeist aber nur für den Preis eines erhöhten Rechenaufwands zu erreichen.