Benutzer:Stepri2005/Kurs:Optimierung II/Das lokale SQP-Verfahren

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.

10.1 Das Lagrange-Newton-Verfahren

Wir gehen im Folgenden von Funktionen $f,h_{j}\in C^{2}(\mathbb {R} ^{n})$ und von dem allgemeinen gleichungsrestringierten Optimierungsproblem

${\begin{array}{lll}({\mathcal {P}}_{GN}):&{\text{Minimiere}}&f(x)\\&{\text{u. d. N.}}&h_{j}(x)=0\quad (j=1,\ldots ,m)\end{array}}$

aus. Wie zuvor sei

$L(x,y):=f(x)+\sum _{j=1}^{m}y^{j}h_{j}(x)$

die zu $({\mathcal {P}}_{GN})$ gehörende Lagrange-Funktion und seien

(10.1) $A(x):=\left[\nabla h_{j}(x)^{T}\right]_{j=1,\ldots ,m}$

die $(m\times n)$-Jacobi-Matrix zu den $h_{j}$ sowie

$h(x):=(h_{j}(x))_{j=1,\ldots ,m}.$

Schließlich sei der Nullraum einer Matrix $B\in \mathbb {R} ^{p\times n}$ gegeben durch

${\mathcal {N}}(B):=\{x\in \mathbb {R} ^{n}{\big |}Bx=0\}.$

Nach Korollar 9.9 gilt nun: ist $x^{*}$ ein lokaler Minimalpunkt von $({\mathcal {P}}_{GN})$, in dem die LICQ, d. h. die Rangbedingung

$\operatorname {Rang} (A(x^{*}))=m$

erfüllt ist, so gibt es Multiplikatoren $y^{*}$, so dass $(x^{*},y^{*})$ die KKT-Bedingungen für $({\mathcal {P}}_{GN})$ erfüllt. Diese lauten

(10.2) $F(x,y):={\begin{pmatrix}\nabla _{x}L(x,y)\\h(x)\end{pmatrix}}={\begin{pmatrix}\nabla f(x)+A(x)^{T}y\\h(x)\end{pmatrix}}=0.$

Sie stellen ein System aus $n+m$ Gleichungen in den $n+m$ Unbekannten $(x,y)$ dar. Zu diesem System gehört die in diesem Fall symmetrische Jacobi-Matrix

(10.3) ${\mathcal {J}}_{F}(x,y):={\begin{pmatrix}\nabla _{xx}^{2}L(x,y)&A(x)^{T}\\A(x)&0\end{pmatrix}}.$

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)

(0) Wähle $(x^{0},y^{0})\in \mathbb {R} ^{n+m}$ und setze $k:=0$.

(1) Falls $F(x^{k},y^{k})=0$ für $F(x,y)$ aus (10.2) ist, stop! (Dann ist $x^{k}$ ein KKT-Punkt für $({\mathcal {P}}_{GN})$.)

(2) Bestimme eine Lösung $(p_{x}^{k},p_{y}^{k})$ des linearen Gleichungssystems

(10.4) ${\begin{pmatrix}\nabla _{xx}^{2}L(x^{k},y^{k})&A(x^{k})^{T}\\A(x^{k})&0\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{y}\end{pmatrix}}=-{\begin{pmatrix}\nabla f(x^{k})+A(x^{k})^{T}y^{k}\\h(x^{k})\end{pmatrix}}$

und setze

$(x^{k+1},y^{k+1}):=(x^{k},yk)+(p_{x}^{k},p_{y}^{k}).$

(3) Setze $k:=k+1$ 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 ${\mathcal {J}}_{F}(x,y)$ in $(x^{*},y^{*})$ sichergestellt werden. Das folgende Lemma gibt Bedingungen an, unter denen diese Nichtsingularität gewährleistet ist.

Lemma 10.2

Es seien $f,h_{j}\in C^{2}(\mathbb {R} ^{n})$ und es sei $x^{*}$ ein strikt lokaler Minimalpunkt von $({\mathcal {P}}_{GN})$, für den $\operatorname {Rang} (A(x^{*}))=m$ gilt und für den mit Multiplikatoren $y^{*}$ die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 9.12

(10.5) $\nabla _{x}L(x^{*},y^{*})=0,\quad s^{T}\nabla _{xx}^{2}L(x^{*},y^{*})s>0,\quad s\in {\mathcal {N}}(A(x^{*}))\setminus \{0\}$

erfüllt sind. Dann ist ${\mathcal {J}}_{F}(x^{*},y^{*})$ nichtsingulär.

Beweis.

Es gelte ${\mathcal {J}}_{F}(x^{*},y^{*})(p_{x},p_{y})^{T}=0$, d. h.

(10.6) $\nabla _{xx}^{2}L(x^{*},y^{*})p_{x}+A(x^{*})^{T}p_{y}=0,$

(10.7) $A(x^{*})p_{x}=0.$

Die zweite Gleichung besagt, dass $p_{x}\in {\mathcal {N}}(A(x^{*}))$ ist und somit gilt:

$0=p_{y}^{T}A(x^{*})p_{x}=[A(x^{*})p_{x}]^{T}p_{y}=p_{x}^{T}A(x^{*})^{T}p_{y}.$

Multiplikation der Gleichung (10.6) von links mit $p_{x}^{T}$ ergibt daher

$p_{x}^{T}\nabla _{xx}^{2}L(x^{*},y^{*})p_{x}=0,$

so dass mit (10.5) $p_{x}=0$ folgt. Wegen (10.6) ist folglich $A(x^{*})^{T}p_{y}=0$, was mit der vorausgesetzten Rangbedingung für $A(x^{*})$ auch $p_{y}=0$ impliziert.

q.e.d.

Man beachte, dass die erste Bedingung in (10.5) zusammen mit der für einen lokalen Minimierer $x^{*}$ von $({\mathcal {P}}_{GN})$ implizit geltenden Bedingung $h(x^{*})=0$ mit der Bedingung $F(x^{*},y^{*})=0$ ä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 ${\mathcal {J}}_{F}$ in $(x^{*},y^{*})$.

Definition 10.3

Eine Abbildung $H:\mathbb {R} ^{p}\to \mathbb {R} ^{p\times p}$ heißt lokal Lipschitz-stetig in

$z^{*}\in \mathbb {R} ^{p}$, wenn mit einem $\varepsilon >0$ und einem $L>0$

(10.8) $\left\|H(z^{*})-H(z)\right\|\leq L\left\|z^{*}-z\right\|,\quad z\in B_{\varepsilon }(z^{*})$

gilt, wobei $B_{\varepsilon }(z^{*}):=\{z{\big |}\left\|z^{*}-z\right\|<\varepsilon \}$ eine $\varepsilon$-Umgebung und $\|\cdot \|$ eine Vektornorm auf $\mathbb {R} ^{p}$ bzw. die dadurch induzierte Matrixnorm auf $\mathbb {R} ^{p\times p}$ ist.

Eine mit ${\mathcal {U}}_{\varepsilon }(z^{*})$ bezeichnete $\varepsilon$-Umgebung von $z^{*}$ 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 $H:\mathbb {R} ^{p}\to \mathbb {R} ^{p\times p}$, die in $z^{*}$ 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.

Lemma 10.4

Seien $f,h_{j}\in C^{2}(\mathbb {R} ^{n})$. Sind die Abbildungen $\nabla ^{2}f$ und $\nabla ^{2}h_{j}$ in $x^{*}$ lokal Lipschitz-stetig, so ist die durch (10.3) definierte Abbildung ${\mathcal {J}}_{F}$ in $(x^{*},y^{*})$ lokal Lipschitz-stetig.

Beweis.

Für $\varepsilon >0$ und $z^{*}\in \mathbb {R} ^{p}$ sei

$B_{\varepsilon }(z^{*}):=\{z\in \mathbb {R} ^{p}{\big |}\left\|z^{*}-z\right\|_{\infty }\leq \varepsilon \},$

wobei sich die Dimension $p$ des zugrunde gelegten Raums aus dem Zusammenhang ergebe. Offenbar gilt für alle $x\in \mathbb {R} ^{n}$ und $y\in \mathbb {R} ^{m}$

$\max\{\|x^{*}-x\|_{\infty },\|y^{*}-y\|_{\infty }\}=\|(x^{*},y^{*})-(x,y)\|_{\infty }.$

Laut Voraussetzung existieren Konstanten $\eta >0$ und $L_{1}>0$, so dass für alle $x\in B_{\eta }(x^{*})$ gilt:

$\max \left\{\left\|\nabla ^{2}f(x^{*})-\nabla ^{2}f(x)\right\|_{\infty },\max _{j=1,\ldots ,m}\left\|\nabla ^{2}h_{j}(x^{*})-\nabla ^{2}h_{j}(x)\right\|_{\infty }\right\}\leq L_{1}\left\|x^{*}-x\right\|_{\infty }.$

Weiter gibt es Konstanten $L_{2}>0$ und $L>0$, so dass für alle $(x,y)\in B_{\eta }(x^{*},y^{*})$ folgt

$\left\|\nabla _{xx}^{2}L(x^{*},y^{*})-\nabla _{xx}^{2}L(x,y)\right\|_{\infty }=\left\|\nabla ^{2}f(x^{*})+\sum _{j=1}^{m}y_{j}^{*}\nabla ^{2}h_{j}(x^{*})-\nabla ^{2}f(x)-\sum _{j=1}^{m}y_{j}\nabla ^{2}h_{j}(x)\right\|_{\infty }$

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

$\leq L_{1}\|x^{*}-x\|_{\infty }+\|y^{*}-y\|_{\infty }\sum _{j=1}^{m}\left\|\nabla ^{2}h_{j}(x^{*})\right\|_{\infty }+mL_{1}\|y\|_{\infty }\|x^{*}-x\|_{\infty }$

$\leq L_{1}\|x^{*}-x\|_{\infty }+L_{2}\|y^{*}-y\|_{\infty }+L_{1}(\|y^{*}\|_{\infty }+\eta )\|x^{*}-x\|_{\infty }\leq L\max\{\|x^{*}-x\|_{\infty },\|y^{*}-y\|_{\infty }\}$

$=L\|(x^{*},y^{*})-(x,y)\|_{\infty }.$

Ferner gibt es wegen $h_{j}\in C^{2}(\mathbb {R} ^{n})$ ein $M>0$, so dass für alle $x\in B_{\eta }(x^{*})$ gilt:

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

$\leq n\max _{1\leq j\leq m}\left\|\nabla h_{j}(x^{*})-\nabla h_{j}(x)\right\|_{\infty }\leq nM\|x^{*}-x\|_{\infty }.$

Da man überdies wegen der Äquivalenz von Normen auf endlich-dimensionalen Räumen für ein $C\geq 1$ die folgenden Beziehungen hat

$\left\|[A(x^{*})-A(x)]^{T}\right\|_{\infty }=\left\|A(x^{*})-A(x)\right\|_{1}\leq C\left\|A(x^{*})-A(x)\right\|_{\infty },$

erschließt man zusammen für alle $(x,y)\in B_{\eta }(x^{*},y^{*})$

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

$\leq \max \left\{\left\|\nabla _{xx}^{2}L(x^{*},y^{*})-\nabla _{xx}^{2}L(x,y)\right\|_{\infty }+C\left\|A(x^{*})-A(x)\right\|_{\infty },\left\|A(x^{*})-A(x)\right\|_{\infty }\right\}$

$\leq (L+nCM)\left\|(x^{*},y^{*})-(x,y)\right\|_{\infty }.$

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 ${\mathcal {U}}_{\delta }(x^{*},y^{*})$ statt ${\mathcal {U}}_{\delta }((x^{*},y^{*}))$ schreiben.

Satz 10.5

Es seien $f,h_{j}\in C^{2}(\mathbb {R} ^{n})$ und es sei $x^{*}$ ein strikt lokaler Minimalpunkt von $({\mathcal {P}}_{GN})$ mit zugehörigen Multiplikatoren $y^{*}$, für den $\operatorname {Rang} (A(x^{*}))=m$ gilt und die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus (10.5) erfüllt sind. Dann gibt es eine Umgebung ${\mathcal {U}}_{\delta }(x^{*},y^{*})$ von $(x^{*},y^{*})$ für ein $\delta >0$, so dass Algorithmus 10.1 für jeden Startpunkt $(x^{0},y^{0})\in {\mathcal {U}}_{\delta }(x^{*},y^{*})$ durchführbar ist und er, sofern er nicht nach endlich vielen Schritten mit $(x^{*},y^{*})$ abbricht, eine Folge $\left\{(x^{k},y^{k})\right\}$ erzeugt, für welche gilt:

(i) $\left\{(x^{k},y^{k})\right\}$ konvergiert superlinear gegen $(x^{*},y^{*})$.

(ii) Sind $\nabla ^{2}f$ und $\nabla ^{2}h_{j}$ $(j=1,\ldots ,m)$ in $x^{*}$ lokal Lipschitz-stetig, so konvergiert $\left\{(x^{k},y^{k})\right\}$ quadratisch gegen $(x^{*},y^{*})$.

10.2 Das Lagrange-Newton-Verfahren als SQP-Verfahren

Wendet man das lokale oder globalisierte Newton-Verfahren zur unrestringierten Minimierung einer Funktion $f\in C^{2}(\mathbb {R} ^{n})$ an (Algorithmen 6.5 und 6.7), so hat man in der $k$-ten Iteration das lineare Gleichungssystem

(10.9) $\nabla ^{2}f(x^{k})p=-\nabla f(x^{k})$

zu lösen. Ist dann die Matrix $\nabla ^{2}f(x^{k})$ positiv definit, was für jedes $x^{k}$ in der Umgebung eines lokalen Minimierers $x^{*}$ von $f$, für den $\nabla ^{2}f(x^{*})$ 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) $\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]$

aufgefasst werden (vgl. Abschnitt 6.1.2). Unter den genannten Voraussetzungen existiert also eine Umgebung von $x^{*}$, 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 $k$-ten Iteration des Newton-Verfahrens eine quadratische Näherung der Zielfunktion $f$ des Problems bei $x^{k}$. (Man addiere die Konstante $f(x^{k})$ zu der Funktion in (10.10) hinzu.)

Ähnlich kann man nun das lineare Gleichungssystem (10.4) im $k$-ten Schritt des Lagrange-Newton-Verfahrens, welches sich auf das gleichungsrestringierte Optimierungsproblem $({\mathcal {P}}_{GN})$ bezieht, als KKT-Bedingungen zu folgendem in $(x^{k},y^{k})$ definierten quadratischen Optimierungsproblem interpretieren:

(10.11) ${\begin{array}{ll}{\text{Minimiere}}&{\frac {1}{2}}p^{T}\nabla _{xx}^{2}L(x^{k},y^{k})p+\nabla f(x^{k})^{T}p\\{\text{u. d. N.}}&h_{j}(x^{k})+\nabla h_{j}(x^{k})^{T}p=0\quad (j=1,\ldots ,m).\end{array}}$

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

$\nabla _{xx}^{2}L(x^{k},y^{k})p+\nabla f(x^{k})+A(x^{k})^{T}y=0,$

$h(x^{k})+A(x^{k})p=0$

gegeben bzw. in Matrix-Vektor-Schreibweise durch

(10.12) ${\begin{pmatrix}\nabla _{xx}^{2}L(x^{k},y^{k})&A(x^{k})^{T}\\A(x^{k})&0\end{pmatrix}}{\begin{pmatrix}p\\y\end{pmatrix}}=-{\begin{pmatrix}\nabla f(x^{k})\\h(x^{k})\end{pmatrix}}.$

Das lineare Gleichungssystem in (10.12) ist zu dem in (10.4) äquivalent, was man erkennt, wenn man in (10.12) $p:=p_{x}$ sowie $y:=y^{k}+p_{y}$ setzt. Besitzt also das KKT-System (10.12) eine eindeutige Lösung $(p^{k},y^{k+1})$, so löst

(10.13) $p_{x}^{k}:=p^{k},\quad p_{y}^{k}:=y^{k+1}-y^{k}$

das System (10.4). Umgekehrt gewinnt man aus einer Lösung $(p_{x}^{k},p_{y}^{k})$ von (10.4) mittels

(10.14) $p^{k}:=p_{x}^{k},\quad y^{k+1}:=y^{k}+p_{y}^{k}$

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 $({\mathcal {P}}_{GN})$ 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 $(y^{k})^{T}$, so erhält man

$(y^{k})^{T}h(x^{k})=(y^{k})^{T}A(x^{k})p=\left[A(x^{k})^{T}y^{k}\right]^{T}p.$

Der Ausdruck $(y^{k})^{T}A(x^{k})p$ ist also für alle für (10.11) zulässigen Punkte $p$ konstant. Folglich könnten wir diesen Ausdruck sowie die Konstante $L(x^{k},y^{k})$ zur Zielfunktion von Problem (10.11) hinzu addieren und könnten wir diese in der Form

${\frac {1}{2}}p^{T}\nabla _{xx}^{2}L(x^{k},y^{k})p+\nabla _{x}L(x^{k},y^{k})^{T}p+L(x^{k},y^{k})$

darstellen. Die Aufgabe (10.11) können wir demnach so interpretieren, dass eine quadratische Näherung der Lagrange-Funktion von $({\mathcal {P}}_{GN})$ bezüglich $x$ in $(x^{k},y^{k})$ unter linearen Näherungen der Gleichungsnebenbedingungen von $({\mathcal {P}}_{GN})$ in $x^{k}$ 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)

(0) Wähle $(x^{0},y^{0})\in \mathbb {R} ^{n+m}$ und setze $k:=0$.

(1) Falls $F(x^{k},y^{k})=0$ für $F(x,y)$ aus (10.2) ist, stop! (Dann ist $x^{k}$ ein KKT-Punkt für $({\mathcal {P}}_{GN})$.)

(2) Berechne eine lokale Lösung $p^{k}$ des quadratischen Optimierungsproblems

${\begin{array}{lll}(QP_{GN})_{k}:&{\text{Minimiere}}&{\frac {1}{2}}p^{T}\nabla _{xx}^{2}L(x^{k},y^{k})p+\nabla f(x^{k})^{T}p\\&{\text{u. d. N.}}&h_{j}(x^{k})+\nabla h_{j}(x^{k})^{T}p=0\quad (j=1,\ldots ,m)\end{array}}$

und berechne zugehörige Multiplikatoren $y^{k+1}$. Setze

$x^{k+1}:=x^{k}+p^{k}.$

(3) Setze $k:=k+1$ und gehe nach (1).

Das Problem $(QP_{GN})_{k}$ 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 $(QP_{GN})_{k}$, welches hier durch (10.12) gegeben ist und dessen Lösung $(p_{x}^{k},p_{y}^{k})$ gemäß (10.14) die Lösung $(p^{k},y^{k+1})$ von $(QP_{GN})_{k}$ liefert.

Für den Nachweis der Durchführbarkeit und Konvergenz dieses Verfahrens benötigen wir nun zwei Resultate.

Lemma 10.7

Es seien $Q\in \mathbb {R} ^{n\times n},A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}$ und $c\in \mathbb {R} ^{n}$ gegeben, wobei $Q$ symmetrisch und $\operatorname {Rang} (A)=m$ seien. Gilt

(10.15) $s^{T}Qs>0,\quad s\in {\mathcal {N}}(A)\setminus \{0\},$

so besitzt das Problem

(10.16) ${\begin{array}{ll}Minimiere&{\frac {1}{2}}x^{T}Qx+c^{T}x\\u.\ d.\ N.&Ax=b\end{array}}$

eine eindeutige (lokale und gleichzeitig globale) Lösung mit eindeutigen Multiplikatoren.

Beweis.

Ist $Z\in \mathbb {R} ^{n\times (n-m)}$ eine Matrix, deren Spalten eine Basis von ${\mathcal {N}}(A)$ bilden, so ist jedes $s\in {\mathcal {N}}(A)$ in der Form $s=Zv$ mit einem $v\in \mathbb {R} ^{n-m}$ darstellbar. Gemäß der Voraussetzung in (10.15) gilt somit

$v^{T}Z^{T}QZv>0,\quad v\in \mathbb {R} ^{n-m}\setminus \{0\}.$

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 $(n\times n)$-Matrizen auf $(m\times n)$-Matrizen ausgedehnt werden können. Wie man durch eine direkte Abschätzung sofort erkennt, hat man auch in diesem Fall für alle $x\in \mathbb {R} ^{n}$ die Abschätzungen

$\|Ax\|_{\infty }\leq \|A\|_{\infty }\|x\|_{\infty },\quad \|Ax\|_{1}\leq \|A\|_{1}\|x\|_{1}.$

Lemma 10.8

Es sei $Q^{*}\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix und $A^{*}\in \mathbb {R} ^{m\times n}$ eine Matrix mit $\operatorname {Rang} (A)=m$ und es gelte

(10.17) $s^{T}Q^{*}s>0,\quad s\in {\mathcal {N}}(A)\setminus \{0\}.$

Dann existiert ein $\sigma >0$, so dass für alle $A\in \mathbb {R} ^{m\times n}$ und für alle symmetrischen Matrizen $Q\in \mathbb {R} ^{n\times n}$ mit

$\max \left\{\left\|A^{*}-A\right\|_{\infty },\left\|Q^{*}-Q\right\|\right\}\leq \sigma$

folgt:

(10.18) $\operatorname {Rang} (A)=m;\qquad s^{T}Qs>0,\quad s\in {\mathcal {N}}(A)\setminus \{0\}.$

Beweis.

Wäre die Definitheitsbedingung in (10.18) nicht richtig, dann gäbe es Folgen $\{A_{k}\},\{Q_{k}\}$ und $\left\{s^{k}\right\}$ mit

$\lim _{k\to \infty }\left\|A^{*}-A_{k}\right\|_{\infty }=0,\quad \lim _{k\to \infty }\left\|A^{*}-A_{k}\right\|=0$

und

$s^{k}\neq 0,\quad A_{k}s^{k}=0,\quad (s^{k})^{T}Q_{k}s^{k}\leq 0,$

wobei ohne Beschränkung der Allgemeinheit $\left\|s^{k}\right\|=1$ und $\lim _{k\to \infty }s^{k}=s$ für ein $s$ mit $\|s\|=1$ angenommen werden könnte. Damit erhielte man

$\left|s^{T}Q^{*}s-(s^{k})^{T}Q_{k}s^{k}\right|\leq \left|s^{T}Q^{*}(s-s^{k})+s^{T}(Q^{*}-Q_{k})s^{k}+(s-s^{k})^{T}Q_{k}s^{k}\right|$

$\leq \left\|Q^{*}\right\|\|s\|\left\|s-s^{k}\right\|+\left\|Q^{*}-Q_{k}\right\|\|s\|\left\|s^{k}\right\|+\|Q_{k}\|\left\|s-s^{k}\right\|\left\|s^{k}\right\|\to 0\quad (k\to \infty )$

und

(10.19) $\left\|A^{*}s\right\|_{\infty }=\left\|A^{*}s-A_{k}s^{k}\right\|_{\infty }\leq \left\|A^{*}\right\|_{\infty }\left\|s-s^{k}\right\|_{\infty }+\left\|A^{*}-A_{k}\right\|_{\infty }\left\|s^{k}\right\|_{\infty }\to 0\quad (k\to \infty ).$

Im Widerspruch zu (10.17) folgte daraus aber $s^{T}Q^{*}s\leq 0$ und $A^{*}s=0$.

Ähnlich könnte man schließen: gäbe es Folgen $\{A_{k}\}$ und $\left\{u^{k}\right\}$ mit

$\lim _{k\to \infty }\left\|A^{*}-A_{k}\right\|_{\infty }=0,\quad \left\|u^{k}\right\|_{\infty }=1,\quad A_{k}^{T}u^{k}=0,\quad \lim _{k\to \infty }u^{k}=u,$

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

$\left\|A^{*T}u-A_{k}^{T}u^{k}\right\|_{1}\leq \left\|A^{*T}\right\|_{1}\left\|u-u^{k}\right\|_{1}+\left\|A^{*T}-A_{k}^{T}\right\|_{1}\left\|u^{k}\right\|_{1}$

$=\left\|A^{*}\right\|_{\infty }\left\|u-u^{k}\right\|_{1}+\left\|A^{*}-A_{k}\right\|_{\infty }\left\|u^{k}\right\|_{1}\to 0\quad (k\to \infty ).$

Damit wäre $A^{*T}u=0$, was jedoch wegen $\|u\|=1$ im Widerspruch zur Voraussetzung $\operatorname {Rang} (A^{*})=m$ steht.

q.e.d.

Mit dem Vorangehenden lässt sich nun der folgende Satz beweisen.

Satz 10.9

Es seien $f,h_{j}\in C^{2}(\mathbb {R} ^{n})$ und es sei $x^{*}$ ein strikt lokaler Minimalpunkt von $({\mathcal {P}}_{GN})$, in dem $\operatorname {Rang} (A(x^{*}))=m$ gilt und mit Multiplikatoren $y^{*}$ die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 9.12

(10.20) $\nabla _{x}L(x^{*},y^{*})=0,\quad s^{T}\nabla _{xx}^{2}L(x^{*},y^{*})s>0,\quad s\in {\mathcal {N}}(A(x^{*}))\setminus \{0\}$

erfüllt sind. Dann gibt es eine Umgebung ${\mathcal {U}}_{\eta }(x^{*},y^{*})$ von $(x^{*},y^{*})$ für ein $\eta >0$, so dass für Algorithmus 10.6 mit $(x^{0},y^{0})\in {\mathcal {U}}_{\eta }(x^{*},y^{*})$ gilt:

(i) Für jedes $k$ hat das Problem $(QP_{GN})_{k}$ eine eindeutige (lokale und gleichzeitig globale) Lösung $p^{k}$ mit eindeutigen zugehörigen Multiplikatoren $y^{k+1}$.

(ii) Bricht Algorithmus 10.6 nicht nach endlich vielen Iterationen ab, so konvergiert die durch ihn erzeugte Folge $\left\{(x^{k},y^{k})\right\}$ superlinear und, falls $\nabla ^{2}f$ und $\nabla ^{2}h_{j}$ $(j=1,\ldots ,m)$ in $x^{*}$ lokal Lipschitz-stetig sind, sogar quadratisch gegen $(x^{*},y^{*})$.

Beweis.

Es sei $\delta >0$ das $\delta$ aus Satz 10.5, welches dem $\delta$ aus Satz 6.3 und dessen Beweis entspreche.

Aufgrund der Stetigkeit von $\nabla _{xx}^{2}L(\cdot ,\cdot )$ und $A(\cdot )$ in $(x^{*},y^{*})$ bzw. $x^{*}$ folgt wegen (10.20) mit Lemma 10.8, dass ein $\eta \in (0,\delta ]$ existiert, so dass für alle $(x,y)\in {\mathcal {U}}_{\eta }(x^{*},y^{*})$ gilt:

$\operatorname {Rang} (A(x))=m,\quad s^{T}\nabla _{xx}^{2}L(x,y)s>0,\quad s\in {\mathcal {N}}(A(x))\setminus \{0\}.$

Für $(x^{k},y^{k})\in {\mathcal {U}}_{\eta }(x^{*},y^{*})$ besitzt somit Problem $(QP_{GN})_{k}$ nach Lemma 10.7 eine eindeutige Lösung $p^{k}$ mit eindeutigen Multiplikatoren $y^{k+1}$ (s. Lemma 9.8). Demnach löst $(p^{k},y^{k+1})$ die KKT-Bedingungen in (10.12) und ist $(p_{x}^{k},p_{y}^{k})$ die Lösung des Systems (10.4) für $(x^{k},y^{k})$ im Lagrange-Newton-Verfahren (vgl. (10.13)). Der Beweis von Satz 6.3 zeigt, dass dann auch $(x^{k+1},y^{k+1})\in {\mathcal {U}}_{\eta }(x^{*},y^{*})$ 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 $(x^{k},y^{k})$, wenn man in beiden Fällen denselben Startpunkt $(x^{0},y^{0})$ wählt und dieser nahe genug bei $(x^{*},y^{*})$ liegt.

10.3 Das SQP-Verfahren für allgemeine Probleme

Es liegt nun nahe, den Algorithmus 10.6 auf allgemeine nichtlineare Optimierungsprobleme der Gestalt

${\begin{array}{lll}({\mathcal {P}}):&{\text{Minimiere}}&f(x)\\&{\text{u. d. N.}}&h_{j}(x)=0\quad (j=1,\ldots ,m),\\&&g_{i}(x)\leq 0\quad (i=1,\ldots ,l)\end{array}}$

zu erweitern, indem man die Ungleichungsbedingungen aus Problem $({\mathcal {P}})$ in linearisierter Form mit in das Unterproblem aufnimmt. Setzen wir $f,g_{i},h_{j}\in C^{2}(\mathbb {R} ^{n})$ voraus und definieren wir die zu $({\mathcal {P}})$ gehörende Lagrange-Funktion durch

${\mathcal {L}}(x,y,z):=f(x)+\sum _{j=1}^{m}y_{j}h_{j}(x)+\sum _{i=1}^{l}z_{i}g_{i}(x),$

so gelangen wir auf diese Weise zu dem nachstehenden Algorithmus.

Algorithmus 10.10 (Lokales SQP-Verfahren für allgemeine Probleme)

(0) Wähle $(x^{0},y^{0},z^{0})\in \mathbb {R} ^{n+m+l}$ mit $z^{0}\geq 0$ und $z_{i}^{0}:=0$ $(i\notin I(x^{0}))$. Setze $k:=0$.

(1) Falls $(x^{k},y^{k},z^{k})$ die KKT-Bedingungen von $({\mathcal {P}})$ erfüllt, stop!

(2) Berechne eine lokale Lösung $p^{k}$ des quadratischen Optimierungsproblems

${\begin{array}{lll}(QP)_{k}:&{\text{Minimiere}}&{\frac {1}{2}}p^{T}\nabla _{xx}^{2}{\mathcal {L}}(x^{k},y^{k},z^{k})p+\nabla f(x^{k})^{T}p\\&{\text{u. d. N.}}&h_{j}(x^{k})+\nabla h_{j}(x^{k})^{T}p=0\quad (j=1,\ldots ,m),\\&&g_{i}(x^{k})+\nabla g_{i}(x^{k})^{T}p\leq 0\quad (i=1,\ldots ,l)\end{array}}$

und zugehörige Multiplikatoren $(y^{k+1},z^{k+1})$ (mit $z^{k+1}\geq 0$). Setze

$x^{k+1}:=x^{k}+p^{k}.$

(3) Setze $k:=k+1$ und gehe nach (1).

Im Folgenden sei $Z$ wieder der zulässige Bereich von $({\mathcal {P}})$ und

$I(x):=\{i\in \{1,\ldots ,l\}{\big |}g_{i}(x)=0\}$

die Menge der in $x\in Z$ aktiven Indizes. Weiter sei $B(x)$ die Matrix mit Zeilen

$\nabla h_{j}(x)^{T}\ (j=1,\ldots ,m),\quad \nabla g_{i}(x)^{T}\ (i\in I(x)).$

Der Beweis der lokalen Konvergenz von Algorithmus 10.10 beruht darauf, dass die Menge der aktiven Indizes des Problems $(QP)_{k}$ für alle $x^{k}$ aus einer Umgebung eines lokalen Minimalpunktes $x^{*}$ von $({\mathcal {P}})$ unter geeigneten Voraussetzungen an $x^{*}$ konstant bleibt und gleich der (im Allgemeinen a priori unbekannten) Menge $I(x^{*})$ ist. Damit lässt sich zeigen, dass eine Folge $\left\{p^{k}\right\}$ von lokalen Lösungen der Teilprobleme $(QP)_{k}$ mit zugehörigen Multiplikatoren $\left\{(y^{k+1},z^{k+1})\right\}$ existiert, so dass Algorithmus 10.10 lokal dieselben Iterierten erzeugt wie das Lagrange-Newton-Verfahren für das gleichungsrestringierte Optimierungsproblem

(10.21) ${\begin{array}{ll}{\text{Minimiere}}&f(x)\\{\text{u. d. N.}}&h_{j}(x)=0\quad (j=1,\ldots ,m),\\&g_{i}(x)=0\quad (i\in I(x^{*})).\end{array}}$

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.

Satz 10.11

Es seien $f,g_{i},h_{j}\in C^{2}(\mathbb {R} ^{n})$ und es sei $x^{*}$ ein strikt lokaler Minimalpunkt von $({\mathcal {P}})$ mit Multiplikatoren $(y^{*},z^{*})$, in dem die LICQ, d. h.

(10.22) $\operatorname {Rang} (B(x^{*}))=m+|I(x^{*})|,$

gilt und für den die strikte Komplementaritätsbedingung, d. h.

(10.23) $z_{i}^{*}=0,\ g_{i}(x^{*})<0\quad oder\quad z_{i}^{*}>0,\ g_{i}(x^{*})=0,$

für alle $i\in \{1,\ldots ,l\}$ erfüllt ist. Ferner genüge $(x^{*},y^{*},z^{*})$ den hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 9.12:

(10.24) $\nabla _{x}L(x^{*},y^{*},z^{*})=0,\quad s^{T}\nabla _{xx}^{2}L(x^{*},y^{*},z^{*})s>0,\quad s\in {\mathcal {N}}(B(x^{*}))\setminus \{0\}.$

Dann gibt es ein $\delta >0$, so dass bei Wahl $(x^{0},y^{0},z^{0})\in {\mathcal {U}}_{\delta }(x^{*},y^{*},z^{*})$ für Algorithmus 10.10 gilt:

Bricht der Algorithmus nicht nach endlich vielen Iterationen ab, so existiert eine Folge $\left\{p^{k}\right\}$ lokaler Lösungen der Probleme $(QP)_{k}$ und eine Folge zugehöriger Multiplikatoren $\left\{(y^{k+1},z^{k+1})\right\}$, so dass die durch den Algorithmus erzeugte Folge $\left\{(x^{k},y^{k},z^{k})\right\}$ superlinear und, falls $\nabla ^{2}f,\nabla ^{2}h_{j}$ $(j=1,\ldots ,m)$ und $\nabla ^{2}g_{i}$ $(i=1,\ldots ,l)$ in $x^{*}$ lokal Lipschitz-stetig sind, sogar quadratisch gegen $(x^{*},y^{*},z^{*})$ konvergiert.

Beweis.

Siehe Geiger/Kanzow.

10.4 Hinweise

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 $(QP)_{k}$ gewonnene Richtung $p^{k}$ unter gewissen Voraussetzungen eine Abstiegsrichtung für die exakte $l_{1}$-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.