Constraint Qualifications und Optimalitätsbedingungen für MPECs

Inhaltsverzeichnis

1 Einf uhrung 1

2 Tangentialkegel 4

2.1 Tangentialkegel f ur NLPs 4

2.2 Tangentialkegel des MPEC 7

2.3 Hilfsprobleme und deren Tangentialkegel 12

2.3.1 Deﬁnition der zum MPEC verwandten Hilfsprobleme 12

2.3.2 Die Tangentialkegel der Hilfsprobleme 16

2.4 Zusammenfassung Tangentialkegel 22

3 Constraint Qualiﬁcations 24

3.1 Standard CQs f ur NLPs 24

3.2 Geometrische CQs 30

3.3 MPEC-speziﬁsche CQs 33

3.3.1 MPEC-speziﬁsche Standard CQs 33

3.3.2 MPEC-speziﬁsche geometrische CQs 43

3.4 Zusammenfassung Constraint Qualiﬁcations 46

4 Optimalit atsbedingungen 47

4.1 B-Stationarit at 47

4.2 KKT-Punkte 50

4.2.1 KKT-Punkt f ur das NLP 50

4.2.2 KKT-Punkt f ur das MPEC 53

4.2.3 KKT-Punkte der Hilfsprobleme 55

4.2.4 Zusammenfassung KKT-Punkte 60

4.3 Starke Stationarit at 62

4.3.1 Starke Stationarit at unter der GCQ 64

4.3.2 Starke Stationarit at unter der MPEC-LICQ 66

4.3.3 Starke Stationarit at unter der MPEC-SMFCQ 67

4.4 Alternative Stationarit atskonzepte 69

4.4.1 Die MPEC-Buchstabensuppe 70

4.4.2 -MStationarit at unter der MPEC-GCQ 75

4.4.3 MPEC-linearisierte B-Stationarit at 79

4.5 Hinreichende Optimalit atsbedingungen 2. Ordnung 81

4.6 Zusammenfassung Optimalit atsbedingungen 89

5 Numerische L osungsans atze 92

5.1 Regularisierung und Penalisierung 93

5.2 Anwendung von Standard NLP-L osern 97

5.2.1 Innere Punkte Methoden f ur MPECs 98

5.2.2 SQP-Methoden f ur MPECs 102

5.3 Ein SLPEC-EQP Algorithmus 107

6 Schlusswort und Ausblick 111

Literatur 115

1 Einf¨ uhrung

Wir betrachten in dieser Arbeit ein sogenanntes mathematical program with equilibirium constraints [MPEC] in der Form eines mathematical program with complementarity constraints [MPCC]: 

  

MPEC als MPCC

  

wobei das Zielfunktional f : R n → R und die Nebenbedingungen (c E , c I ) : R n → R |E|+|I| , G : R n → R p , H : R n → R p zweimal stetig diﬀerenzierbar

sind. Hierbei bezeichnen wir die c i als Standardnebenbedingungen (standard equality constraints f¨ ur i ∈ E und standard inequality constraints f¨ ur i ∈ I), w¨ ahrend wir die Bedingungen G(z) ≥ 0, H(z) ≥ 0 und G(z) T H(z) = 0 als

Komplementarit¨ atsbedingung zusammenfassen.

MPECs sind von großem Interesse f¨ ur praktische Anwendungen in zahlreichen Bereichen. Dabei ergibt sich das MPEC oft aus einem bilevel optimization problem [BIOP] oder aus einem problem with variational inequality constraints [OPVIC]: 

BIOP

OPVIC

wobei C(x) der zul¨ assige Bereich und Θ(x, ·) das Zielfunktional eines inne-

ren Optimierungsproblems f¨ ur ein ﬁxiertes x ist. Es handelt sich hierbei um Optimierungsprobleme, deren zul¨ assige Punkte bereits L¨ osung eines, von der Variable x abh¨ angigen, inneren Optimierungsproblems sein m¨ ussen. Unsere Formulierung (1.1) des MPEC entsteht, indem wir die KKT-Bedingungen des inneren Optimierungsproblems von BIOP als Nebenbedingungen des ¨ außeren Problems formulieren. Damit sind die Formulierungen OPVIC, BIOP und (1.1) ¨ aquivalent und wir werden uns ab jetzt immer auf die Formulierung (1.1) beziehen, wenn wir von MPECs sprechen. Die Idee das MPEC wie in (1.1) als MPCC zu deﬁnieren, stammt dabei

1

urspr¨ unglich von Scheel und Scholtes in [16]. Damit wird das MPEC zu einem Spezialfall eines nicht linearen Problems [NLP], das sich von herk¨ ommlichen NLPs lediglich durch die Komplementarit¨ atsbedingung unterscheidet. Die Anwesenheit dieser Komplementarit¨ atsbedingung ist jedoch gerade der Ursprung der Kernproblematik von MPECs. Sie ist Ursache daf¨ ur, dass der zul¨ assige Bereich des MPEC nicht konvex ist. Des Weiteren ist die Komplementarit¨ atsbedingung daf¨ ur verantwortlich, dass herk¨ ommliche constraint qualiﬁcations [CQ], wie die linear independence constraint qualiﬁcation [LICQ] oder die Mangasarian Fromovitz constraint qualication [MFCQ] nicht erf¨ ullt sind (siehe Proposition 3.7). Dabei gibt es unterschiedliche Wege diese Komplementarit¨ atsbedingung zu deﬁnieren, welche jedoch in der Theorie alle zu unserer Formulierung in (1.1) ¨ aquivalent sind:

0 ≤ G(z ∗ ) ⊥ H(z ∗ ) ≥ 0

(1.2)

⇔ G(z ∗ ) ≥ 0, H(z ∗ ) ≥ 0, G(z ∗ ) T H(z ∗ ) ≤ 0

⇔ G i (z ∗ ) ≥ 0, H i (z ∗ ) ≥ 0, G i (z ∗ )H i (z ∗ ) ≤ 0, i ∈ {1, . . . , p}

W¨ ahrend (1.2) lediglich eine andere Notation unserer Formulierung der Komplementarit¨ at ist, bietet nach [8] die Formulierung (1.3) Vorteile bei der Anwendung von sequential quadratic programming [SQP] Methoden. Die komponentenweise Formulierung (1.4) bildet in [15] den Ausgangspunkt f¨ ur einen Regularisierungsansatz, welcher wiederum Grundlage f¨ ur die Anwendung einer Inneren Punkte Methode in [14] darstellt.

Diese Arbeit konzentriert sich auf die theoretische Analyse des MPEC (1.1). Insbesondere werden die Probleme bei der Entwicklung von Optimalit¨ atsbedingungen diskutiert. Im Gegensatz zu vielen anderen Ausf¨ uhrungen ¨ uber

MPECs ([1], [8], [11], [14], [15]) liegt unser Hauptaugenmerk also nicht bei Problempunkten in der Anwendung von verschiedenen L¨ osungsalgorithmen, sondern vielmehr in dem Ursprung jener Probleme. Inspiriert durch Arbeiten von Flegel und Kanzow ([2], [4], [5]) werden im zweiten Kapitel zun¨ achst verschiedene Tangentialkegel des MPEC (1.1) und seiner Hilfsprobleme betrachtet und deren Zusammenh¨ ange erarbeitet. Ausgehend von diesem geometrischen Standpunkt wird im dritten Kapitel eine Auswahl an CQs f¨ ur MPECs vorgestellt. Eine wichtige Rolle werden in diesem Zusammenhang vor allem geometrische CQs, wie die lange Zeit in Vergessenheit geratene Guignard constraint qualiﬁcation [GCQ], spielen. Im vierten Kapitel werden unter der Vorraussetzung verschiedener CQs Optimalit¨ atsbedingungen erster und zweiter Ordnung hergeleitet. Dabei wird sowohl auf die geometrische Boulingand Stationarit¨ at, als auch auf alle Stationarit¨ atsbegriﬀe der sogenannten MPEC-Buchstabensuppe eingegangen. Außerdem

2

werde ich mit der MPEC-WSOSC die erste hinreichende Optimalit¨ atsbedingung zweiter Ordnung f¨ ur MPECs deﬁnieren, welche keinen stark station¨ aren Punkt voraussetzt. Abschließend wird im f¨ unften Kapitel eine engere Auswahl an numerischen L¨ osungsans¨ atzen f¨ ur MPECs vorgestellt.

3

2 Tangentialkegel

Im Verlauf dieser Arbeit werden Tangentialkegel als Hilfsmittel zur lokalen Beschreibung von zul¨ assigen Bereichen eine zentrale Rolle spielen. Aus meiner Sicht bietet die Betrachtung der Tangentialkegel einen anschaulichen Zugang zu MPEC-speziﬁschen Problemen, weshalb ich den Tangentialkegeln ein eigenes Kapitel widme.

Nachdem wir Tangentialkegel f¨ ur Standard-NLPs deﬁniert haben und einige grundlegende Dinge besprochen haben, werden wir diese Ergebnisse auf den Fall des MPEC (1.1) anwenden und erweitern. Anschließend f¨ uhren wir zum MPEC (1.1) geh¨ orige Hilfsprobleme ein, betrachten deren Tangentialkegel und setzen diese mit den Tangentialkegeln des MPEC in Beziehung.

2.1 Tangentialkegel f¨ ur NLPs

Wir beginnen mit dem Fall eines allgemeinen, nicht linearen Problems der Form:

wobei f : R n → R, und (c E , c I ) : R n → R |E|+|I| , stetig diﬀerenzierbare

Funktionen sind. Bevor wir die Tangentialkegel einf¨ uhren, deﬁnieren wir uns folgende Indexmengen der aktiven Nebenbedingungen:

Deﬁnition 2.1 Sei Z der zul¨ assige Bereich des NLP (2.1), dann heißt ∀z ∗ ∈ Z { }

z k − z ∗

T (z ∗ ) :=

der Tangentialkegel von Z am Punkt z ∗ . Weiter sei ∀z ∗ ∈ Z { }

T lin (z ∗ ) :=

der linearisierte Tangentialkegel von Z am Punkt z ∗ .

4

Oﬀensichtlich beschreiben diese Kegel den zul¨ assigen Bereich Z lokal an einem zul¨ assigen Punkt z ∗ ∈ Z. Der Tangentialkegel T (z ∗ ), der auch unter

dem Namen Boulingand-Kegel bekannt ist, enth¨ alt alle tats¨ achlich zul¨ assi-

gen Richtungen d (vom Punkt z ∗ ausgehend). Der linearisierte Tangentialkegel T lin (z ∗ ) entspricht hingegen allen zul¨ assigen Richtungen d des an dem Punkt z ∗ linearisierten zul¨ assigen Bereichs, denn f¨ ur die am Punkt z ∗ aktiven

Nebenbedingungen gilt:

Betrachten wir kurz den Unterschied zwischen den beiden Kegeln anhand eines Beispiels.

Beispiel 2.2

Abb. 1: zul¨ assiger Bereich Z Abb. 3: lin. Tangentialkegel

Der zul¨ assige Bereich dieses Problems sei Z. Die L¨ osung des Problems ist z ∗ = (0, 0). Wenden wir obige Deﬁnitionen an, um den Tangentialkegel und

5

den linearisierten Tangentialkegel am Punkt z ∗ aufzustellen, so erhalten wir: { }

z k − z ∗ T (z ∗

) = T lin (z ∗ ) =

Die beiden Tangentialkegel am Punkt z ∗ sind in diesem Beispiel also nicht

identisch. Der linearisierte Tangentialkegel beschreibt hier den zul¨ assigen Be-reich des Problems am Punkt z ∗ nicht richtig. Wie man in Abbildung 3 sehen kann, ist die negative z 1 -Achse im linearisierten Tangentialkegel T lin (z ∗ ) enthalten, obwohl diese Richtungen bzgl. Z nicht zul¨ assig sind. Im Gegensatz dazu, beschreibt der Tangentialkegel T (z ∗ ) den zul¨ assigen Bereich Z korrekt.

Bevor wir die zwei unterschiedlichen Kegel in Beziehung zueinander setzen, greifen wir noch einige allgemein bekannte Aussagen ¨ uber Kegel auf:

Lemma 2.3 Sei z ∗ zul¨ assiger Punkt des NLP (2.1), dann gilt:

(i) T (z ∗ ) und T lin (z ∗ ) sind abgeschlossene Kegel,

(ii) T lin (z ∗ ) ist ein konvexer Kegel

Beweis: siehe [9].

Da wir nun wissen, dass T (z ∗ ) und T lin (z ∗ ) Kegel sind, pr¨ asentieren wir

kurz ein paar grundlegende Rechenregeln f¨ ur Kegel, die wir anschließend f¨ ur unsere Tangentialkegel verwenden k¨ onnen. Dazu deﬁnieren wir zun¨ achst den dualen Kegel.

Deﬁnition 2.4 Sei K ein beliebiger Kegel, dann ist der zu K duale Kegel

K ∗ deﬁniert durch:

K ∗ := {v ∈ R n | v T d ≥ 0 ∀d ∈ K}

(2.4)

Lemma 2.5 Seien K und L zwei beliebige nicht leere Kegel. Dann gilt:

(i) K ∗ ist ein abgeschlossener konvexer Kegel,

(ii) K ⊆ L ⇒ K ∗ ⊇ L ∗ ,

(iii) K ⊆ K ∗∗ ,

6

(iv) K konvex ⇒ K ∗∗ = cl(K),

(v) K ∗∗ = cl(conv(K)),

(vi) (K ∪ L) ∗ = K ∗ ∩ L ∗

Beweis: siehe [9].

Richten wir unsere Aufmerksamkeit wieder auf die Tangentialkegel, so k¨ onnen

wir zwischen dem Tangentialkegel T (z ∗ ) und dem linearisierten Tangentialkegel T (z ∗ ) lin folgenden Zusammenhang feststellen.

Lemma 2.6 Sei z ∗ zul¨ assiger Punkt des NLP (2.1), dann gilt:

T (z ∗ ) ⊆ T lin (z ∗ )

Beweis: siehe [9].

2.2 Tangentialkegel des MPEC

Bevor wir die Tangentialkegel des MPEC (1.1) deﬁnieren werden, unterteilen wir die Indexmenge {1 . . . p} (das sind jene Indizes, auf die die Komplementarit¨ at wirkt) an jedem zul¨ assigen Punkt z ∗ in drei Indexmengen. Dabei

verwende ich die am weitesten verbreitete Notation, wie sie beispielsweise auch in [5] und [17] zu ﬁnden ist:

Zur Vereinfachung der Notation werden wir im Folgenden stets lediglich α, β und γ schreiben, obwohl sich die Indexmengen immer auf einen festen

zul¨ assigen Punkt z ∗ beziehen. Außerdem werden wir die Elemente von β als

biaktiv bezeichnen, w¨ ahrend wir die Elemente von α und γ einseitig aktiv nennen. F¨ ur das MPEC (1.1) unterscheiden wir folgende drei Tangentialkegel:

Deﬁnition 2.7 Sei Z M P EC der zul¨ assige Bereich des MPEC(1.1). Dann heißt ∀z ∗ ∈ Z M P EC { }

z k − z ∗ T M P EC (z ∗ ) :=

der Tangentialkegel von Z M P EC am Punkt z ∗ . Weiter sei  

M P EC (z ∗ ) := T lin

der linearisierte Tangentialkegel von Z M P EC am Punkt z ∗ . Im Gegensatz

dazu heißt

 

        

M P EC (z ∗ ) := F lin

        

der MPEC-linearisierte Tangentialkegel von Z M P EC am Punkt z ∗ .

An dieser Stelle verweise ich darauf, dass ich hier von der Notation von Kanzow und Flegel in [5] abweiche, welche den MPEC-linearisierten Tan-

MP EC (z ∗ ) bezeichnen, was in meiner Arbeit dem normal gentialkegel als T lin

linearisierten Tangentialkegel des MPEC (1.1) entspricht.

Analog zu dem allgemeineren Fall des NLP (2.1) enth¨ alt T M P EC (z ∗ ) alle

tats¨ achlich zul¨ assigen Richtungen d des MPEC (1.1), w¨ ahrend der lineari-

MP EC (z ∗ ) alle zul¨ assigen Richtungen d des an dem sierte Tangentialkegel T lin

Punkt z ∗ linearisierten zul¨ assigen Bereichs enth¨ alt. Im Gegensatz zu dem

Fall des NLP (2.1) haben wir f¨ ur des MPEC noch den MPEC-linearisierten

M P EC (z ∗ ) deﬁniert. Um den Unterschied zwischen den Ke-Tangentialkegel F lin M P EC (z ∗ ) und F lin M P EC (z ∗ ) herauszuarbeiten, betrachten wir kurz die geln T lin

Linearisierung der Komplementarit¨ atsbedingung:

G(z ∗ + d) T H(z ∗ + d) ≈ G(z ∗ ) T H(z ∗ ) + ∇ z (G(z ∗ ) T H(z ∗ )) T d

∑ ( )

H i (z ∗ )∇ z G i (z ∗ ) T d + G i (z ∗ )∇ z H i (z ∗ )) T d

=

i∈{1,...,p}

Wegen ∇ z (G(z ∗ ) T H(z ∗ )) T d = 0 ergibt sich zusammen mit den Bedingungen ∇ z G i (z ∗ ) T d ≥ 0, ∀i ∈ α ∪ β und ∇ z H i (z ∗ ) T d ≥ 0, ∀i ∈ γ ∪ β f¨ ur die

8

M P EC (z ∗ ): zul¨ assigen Richtungen d ∈ T lin

D.h. die beiden Tangentialkegel unterscheiden sich lediglich in der zus¨ atz-lichen Forderung (∇ z G i (z ∗ ) T d)(∇ z H i (z ∗ ) T d) = 0 ∀i ∈ β des F lin M P EC (z ∗ ).

Aufgrund dieser zus¨ atzlichen Bedingung ist der MPEC-linearisierte Tangen-

MP EC (z ∗ ) nicht mehr konvex und beschreibt dadurch unter sehr tialkegel F lin

schwachen Constraint Qualiﬁcations das MPEC (1.1) besser als der normal

M P EC (z ∗ ). Zur Veranschaulichung betrachten linearisierte Tangentialkegel T lin

wir nun noch die Tangentialkegel eines sehr einfachen MPEC:

Beispiel 2.8 Standard-MPEC

min

z

s.t. G(z) := z 1 ≥ 0,

Betrachten wir die Tangentialkegel an dem Minimum z ∗ = (0, 0): { }

d ∈ R ² | ∃{z k } ⊂ Z, ∃t k ↘ 0 : z k → z ∗ , z k −z ∗ T M P EC (z ∗ ) := → d

t k { ( ) ( ) }

 

M P EC (z ∗ ) := T lin

 

M P EC (z ∗ ) := F lin

Abb. 5: Beispiel 2.8 Tangentialkegel

Oﬀensichtlich gilt hier also: T M P EC (z ∗ ) = F lin M P EC (z ∗ ) ̸ = T lin M P EC (z ∗ ). Das il-lustriert, dass schon bei einfachsten MPECs mit linearen Nebenbedingungen der Tangentialkegel des MPEC an biaktiven Punkten nicht mit dem linearisierten Tangentialkegel des MPEC ¨ ubereinstimmen. Alle Standard-CQs, wie

die LICQ oder die MFCQ, fordern aber implizit, dass T (z ∗ ) = T lin (z ∗ ) gilt.

Gehen wir wieder zur¨ uck zu dem allgemeinen Fall und vergleichen wir den Tangentialkegel des MPEC (1.1) mit dem MPEC-linearisierten Tangentialkegel und dem normal linearisierten Tangentialkegel, so k¨ onnen wir auch f¨ ur den Allgemeinfall folgenden Zusammenhang feststellen:

Lemma 2.9 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1), dann gilt:

T M P EC (z ∗ ) ⊆ F lin M P EC (z ∗ ) ⊆ T lin M P EC (z ∗ )

10

Um jedoch die erste Inklusion dieser Behauptung zu zeigen, ben¨ otigen wir

das sogenannte auf (β 1 , β 2 )-reduzierte N LP ^(β 1 ,β 2 ) (z ∗ ). Dieses werden wir zu-

sammen mit zwei weiteren zum MPEC (1.1) verwandten Hilfsproblemen im folgenden Abschnitt einf¨ uhren, in welchem wir dann auch obiges Lemma zeigen werden.

11

2.3 Hilfsprobleme und deren Tangentialkegel

Schon Scheel und Scholtes haben in [16] f¨ ur den etwas allgemeineren Fall des MPCC (mathematical program with complementarity constraints) nachfolgende drei Hilfsprobleme deﬁniert. Die Idee dabei ist, das MPEC (1.1) an

jedem zul¨ assigen Punkt z ∗ lokal mit Hilfe von Standard-NLPs ohne Komple-

mentarit¨ atsbedingung zu beschreiben. Diese Herangehensweise ist inzwischen in der MPEC-Gemeinde weit verbreitet und nicht mehr wegzudenken. So ist beispielsweise das sogenannte tightend NLP (TNLP (2.9)) Grundlage f¨ ur die Deﬁnition MPEC-speziﬁscher Standard-CQs, wie der MPEC-LICQ. Das relaxed NLP (RNLP (2.10)) spielt eine essenzielle Rolle bei Fletcher, Leyﬀer, Ralph und Scholtes, welche in [8] unter bestimmten Voraussetzungen die lokale Konvergenz von SQP-Methoden f¨ ur MPECs zeigen.

Im Gegensatz zu bisherigen Ausf¨ uhrungen, werden wir uns noch etwas ausf¨ uhrlicher mit den Hilfsproblemen besch¨ aftigen. So werden wir die Tangentialkegel aller drei Hilfsprobleme betrachten und diese, sowohl untereinander, als auch mit den Tangentialkegeln des MPEC (1.1) in Beziehung setzen. Dabei werden Resultate von Kanzow und Flegel in [4] und [5] eine wichtige Rolle spielen, wobei diese jedoch lediglich mit den Tangentialkegeln der auf

(β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ) (2.8) arbeiten. Insbesondere der Vergleich

des linearisierten Tangentialkegels des MPEC mit dem linearisierten Tangentialkegel des RNLP liefert ein sehr sch¨ ones Ergebnis, das zwar sehr einfach zu zeigen ist, aber in dieser Form meines Wissens noch nicht formuliert wurde.

2.3.1 Deﬁnition der zum MPEC verwandten Hilfsprobleme

Beginnen wir mit den Deﬁnitionen der zum MPEC verwandten Hilfsprobleme. Dazu erinnern wir uns zur¨ uck an die bereits vorgestellten Indexmengen

α, β und γ. Zudem deﬁnieren wir zu jedem zul¨ assigen Punkt z ∗ des MPEC

(1.1) mit zugeh¨ origer Indexmenge β die Menge aller Partitionen von β:

P(β(z ∗ )) := {(β 1 (z ∗ ), β 2 (z ∗ )) | β 1 (z ∗ ) ∪ β 2 (z ∗ ) = β(z ∗ ), β 1 (z ∗ ) ∩ β 2 (z ∗ ) = ∅}

Sei in folgenden Deﬁnitionen z ∗ ein zul¨ assiger Punkt des MPEC (1.1) mit

den zugeh¨ origen Indexmengen α, β und γ:

12

Deﬁnition 2.10 Zu jeder Partition (β 1 , β 2 ) ∈ P(β) deﬁnieren wir das auf (β 1 , β 2 )-reduzierte N LP ^(β 1 ,β 2 ) (z ∗ ) wie folgt:



Deﬁnition 2.11 Das tightened NLP (TNLP(z ∗ )) ist deﬁniert durch:



Deﬁnition 2.12 Das relaxed NLP (RNLP(z ∗ )) ist deﬁniert durch:



Hierbei sei noch einmal betont, dass diese Hilfsprobleme jeweils von dem ent-sprechenden zul¨ assigen Punkt z ∗ des MPEC (1.1) abh¨ angen, mit Hilfe dessen sie aufgestellt worden sind. Dabei erweitert das RNLP(z ∗ ) den zul¨ assigen Bereich des MPEC (1.1) lokal an dem Punkt z ∗ , indem es die biaktiven Neben-

bedingungen losl¨ asst und lediglich die einseitig aktiven Nebenbedingungen

von z ∗ bei Null festh¨ alt. Das TNLP(z ∗ ) hingegen h¨ alt sowohl die einseitig aktiven, als auch die biaktiven Nebenbedingungen von z ∗ bei Null fest und engt somit den zul¨ assigen Bereich des MPEC (1.1) an dem Punkt z ∗ ein. Im Gegensatz dazu h¨ alt das auf (β 1 , β 2 )-reduzierte N LP ^(β 1 ,β 2 ) (z ∗ ) neben den einseitig aktiven Nebenbedingungen alle G i , ∀i ∈ β 1 und alle H i , ∀i ∈ β 2 bei

Null fest.

Im Folgenden wird dieser Zusammenhang an einem Beispiel verdeutlicht, welches urspr¨ unglich in einem anderen Kontext bei Scheel und Scholtes in [16] aufgetaucht ist:

13

Beispiel 2.13

min

z s.t. c I (z) :=

Die L¨ osung dieses MPEC liegt im Ursprung. Sei z ∗ = (0, 0, 0). Um die zu diesem MPEC geh¨ orenden Hilfsprobleme am Punkt z ∗ aufzustellen, deﬁnieren

wir zun¨ achst die Indexmengen: (beachte n=3, p=1)

α(z ∗ ) = γ(z ∗ ) = ∅ und β(z ∗ ) = {1}

Nun sind wir in der Lage die Hilfsprobleme RN LP (z ∗ ), T N LP (z ∗ ) und das auf (β 1 , β 2 )-reduzierte N LP ^(β 1 ,β 2 ) (z ∗ ) aufzustellen. Wir beginnen mit dem T N LP (z ∗ ):



    

T N LP (z ∗ )

    

Das TNLP (z ∗ ) h¨ alt also den biaktiven Index bei Null fest (in diesem Bsp.

gilt p=1 und somit gibt es nur einen Index auf den die Komplementarit¨ at wirkt und dieser ist biaktiv) und engt somit den zul¨ assigen Bereich an dem

Punkt z ∗ ein. Im Gegensatz dazu l¨ asst das RNLP (z ∗ ) die biaktiven Indizes los und erweitert somit den zul¨ assigen Bereich am Punkt z ∗ :

14

RN LP (z ∗ )

Im Vergleich dazu stellen wir jetzt unsere auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ )

auf, welche die Indizes je nach gew¨ ahlter Partition von β festhalten. F¨ ur die beiden Partitionen von β gilt dabei:

N LP ({1},∅) (z ∗ )

N LP (∅,{1}) (z ∗ )

Im Allgemeinen gilt jedoch nicht α = γ = ∅ und daher gilt im Gegensatz zu obigem Beispiel 2.13 im Allgemeinen nicht Z M P EC ⊆ Z RN LP (z ∗ ) . Wenn

wir sp¨ ater zu der Betrachtung der jeweiligen Tangentialkegel ¨ ubergehen, so

werden wir in Korollar 2.14 sehen, dass der zul¨ assige Bereich des MPEC (1.1)

lokal an dem Punkt z ∗ in dem zul¨ assigen Bereich des RNLP(z ∗ ) enthalten

ist.

15

2.3.2 Die Tangentialkegel der Hilfsprobleme

Um die Tangentialkegel der Hilfsprobleme zueinander und mit dem Tangentialkegel des MPEC (1.1) in Beziehung setzen zu k¨ onnen, m¨ ussen wir zun¨ achst die Tangentialkegel der Hilfsprobleme deﬁnieren. Da die Hilfsprobleme insbesondere NLPs sind, funktioniert dies analog zu dem Fall der NLPs. Sei also

z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Z T N LP , Z RN LP und Z N LP ^(β 1 ,β 2 ⁾ bezeichnen die zul¨ assigen Bereiche der jeweiligen am Punkt z ∗ aufgestell-ten Hilfsprobleme. Dann sind die Tangentialkegel der Hilfsprobleme gegeben durch:

{ }

z k − z ∗ T T N LP (z ∗

) := T RN LP (z ∗ ) :=

T N LP ^(β 1 ,β 2 ) (z ∗ ) :=

Seien weiter α, γ und β die zu z ∗ geh¨ origen Indexmengen. Dann sind die

linearisierten Tangentialkegel der Hilfsprobleme gegeben durch:

 

  

T N LP (z ∗ ) (z ∗ ) := T lin

  

N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) := T lin



      

RN LP (z ∗ ) (z ∗ ) := T lin

      

16

Da diese Hilfsprobleme NLPs sind, k¨ onnen wir Lemma 2.6 anwenden und erhalten die Aussage, dass die Tangentialkegel dieser Probleme jeweils in den entsprechenden linearisierten Tangentialkegeln enthalten sind. Dar¨ uber hinaus k¨ onnen wir die Tangentialkegel der Hilfsprobleme miteinander und mit dem Tangentialkegel des MPEC in Beziehung setzen und erhalten folgenden Zusammenhang:

Korollar 2.14 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann gilt:

T T N LP (z ∗ ) (z ∗ ) ⊆ T N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) ⊆ T M P EC (z ∗ ) ⊆ T RN LP (z ∗ ) (z ∗ )

Beweis: Wegen Z T N LP ⊆ Z N LP (β 1 ,β 2 ) ⊆ Z M P EC (∀(β 1 , β 2 ) ∈ P(β)) folgen die

ersten zwei Inklusionen direkt aus der Deﬁnition der Tangentialkegel. Die zweite Inklusion ist hingegen etwas schwieriger zu zeigen, da im RNLP die Bedingungen G α (z) = 0, H γ (z) = 0 stehen und somit im Allgemeinen

nicht Z M P EC ⊆ Z RN LP gilt. Sei d ∈ T M P EC (z ∗ ), dann gilt nach (2.2):

Da {z k } ⊂ Z M P EC , gilt insbesondere G i (z k )H i (z k ) = 0 ∀i ∈ {1, . . . , p}. Weil G und H stetig sind und H α (z ∗ ) > 0 und G γ (z ∗ ) > 0 (nach Deﬁnition der Indexmengen), gibt es eine Umgebung U (z ∗ ) von z ∗ mit: H α (y) > 0 und G γ (y) > 0 ∀y ∈ U (z ∗ ).

Insgesamt gibt es deshalb eine Teilfolge {z l } ⊂ {z k } ⊂ Z M P EC in U(z ∗ ) derart, dass ∀l gilt: G α (z l ) = 0 und H γ (z l ) = 0 (sonst w¨ are z l nicht zul¨ assig bzgl. der Komplementarit¨ atsbedingung). Damit gilt aber schon {z l } ⊂ Z RN LP , denn alle anderen Nebenbedingungen von RN LP (z ∗ ) (2.10) sind bereits erf¨ ullt, weil {z l } ⊂ Z M P EC . Somit folgt:

Also gilt d ∈ T RN LP (z ∗ )

Eine direkte Folgerung dieses Korollars ist folgende Aussage:

Korollar 2.15 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann gilt:

17

Eine weitere sehr wichtige Beziehung besteht zwischen dem Tangentialkegel des MPEC (1.1) und den Tangentialkegeln der auf (β 1 , β 2 )-reduzierten

N LP ^(β 1 ,β 2 ) (z ∗ ). Vgl. dazu Kanzow und Flegel [4].

Lemma 2.16 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann gilt:

∪

Beweis: vgl. [2].

Die Inklusion ⊇ in (2.14) gilt oﬀensichtlich, da ∀(β 1 , β 2 ) ∈ P(β):

T M P EC (z ∗ ) ⊇ T N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ )

F¨ ur die andere Inklusion ⊆ sei nun Z M P EC der zul¨ assige Bereich des MPEC (1.1) und ∀(β 1 , β 2 ) ∈ P(β) sei Z ^(β 1 ,β 2 ) der zul¨ assige Bereich des Hilfsproblems N LP ^(β 1 ,β 2 ) (z ∗ ). Da G und H stetig sind, existiert eine Umgebung U (z ∗ ) von z ∗ derart, dass ∀y ∈ U (z ∗ ) gilt:

• G i (y) = 0 und H i (y) > 0 ∀i ∈ α

• G i (y) > 0 und H i (y) = 0 ∀i ∈ γ

Sei y ∈ Z M P EC ∩ U (z ∗ ) beliebig. Da y ein zul¨ assiger Punkt des MPEC

ist, gilt insbesondere die Komplementarit¨ at und somit gibt es eine Partition (β 1 , β 2 ) ∈ P(β) derart, dass f¨ ur y gilt:

D.h. aber gerade, dass y ∈ Z ^(β 1 ,β 2 ) ∩ U (z ∗ ) und da y beliebig gew¨ ahlt war,

haben wir folgende Inklusion gezeigt:

∪

Daraus folgt direkt die Behauptung.

Ein ¨ ahnlicher Zusammenhang besteht auch zwischen dem MPEC-linearisierten Tangentialkegel des MPEC (1.1) und den linearisierten Tangentialkegeln der

auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ).

18

Lemma 2.17 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1), dann gilt: ∪

Beweis: vgl. [2].

∪

N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) T lin

^(β 1 ,β 2 ^)∈P(β)  

=

^(β 1 ,β 2 )∈P(β)

 

        

(∗)

=

        

M P EC (z ∗ ) = F lin

(∗) gilt wegen β 1 ∪ β 2 = β ∀(β 1 , β 2 ) ∈ P(β).

Mit Hilfe dieser zwei Lemmata sind wir in der Lage, Lemma 2.9 aus dem vorangegangenen Abschnitt zu zeigen. Dazu m¨ ussen wir zeigen, dass f¨ ur alle

zul¨ assigen Punkte z ∗ des MPEC (1.1) gilt:

T M P EC (z ∗ ) ⊆ F lin M P EC (z ∗ ) ⊆ T lin M P EC (z ∗ )

Beweis zu Lemma 2.9: Sei z ∗ ∈ Z M P EC , dann gilt:

∪

M P EC (z ∗ ) Lemma ^2.17 F lin =

19

Damit ist die erste Inklusion gezeigt und die zweite Inklusion ist einfach einzusehen, wenn man die beiden Tangentialkegel vergleicht:  

M P EC (z ∗ ) = F lin

Damit ist Lemma 2.9 gezeigt.

Ein weiterer interessanter Zusammenhang besteht zwischen dem linearisierten Tangentialkegel des MPEC (1.1) und dem linearisierten Tangentialkegel des RNLP (2.10). Sie sind n¨ amlich identisch. Diese einfache Aussage scheint bisher in der MPEC-Gemeinde ¨ ubersehen worden zu sein.

Proposition 2.18 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann gilt:

M P EC (z ∗ ) = T lin RN LP (z ∗ ) (z ∗ ) T lin

Beweis: Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann ist der linearisierte

Tangentialkegel des MPEC gegeben durch:

 

M P EC (z ∗ ) := T lin

20

Formulieren wir die letzte Bedingung um, so erhalten wir:

Dies ist genau dann Null, wenn gilt:

∇ z G i (z ∗ ) T d = 0, ∀i ∈ α und ∇ z H i (z ∗ ) T d = 0, ∀i ∈ γ

M P EC (z ∗ ): Somit erhalten wir f¨ ur den T lin  

      

M P EC (z ∗ ) = T lin

      

RN LP (z ∗ ) (z ∗ ). Das ist aber gerade T lin

Diese Tatsache spielt implizit auch bei Fletcher, Leyﬀer, Ralph und Scholtes eine große Rolle, die in [8] unter bestimmten Voraussetzungen zeigen, dass

eine SQP-Methode, angewendet auf das RNLP(z ∗ ), ¨ aquivalent ist zu einer

SQP-Methode, angewendet auf das MPEC (1.1), auch wenn diese nicht mit Tangentialkegeln arbeiten. Im Rahmen dieser Arbeit wird obige Aussage zudem noch eine zentrale Rolle spielen, wenn wir in Kapitel 4 zeigen, dass die starke Stationarit¨ at unter der GCQ eine notwendige Optimalit¨ atsbedingung 1. Ordnung darstellt. Vergleicht man die restlichen linearisierten Tangentialkegel mit besonderem Augenmerk auf die Gleichheitsrestriktionen, so sieht man sofort ein, dass folgender Zusammenhang besteht:

T N LP (z ∗ ) (z ∗ ) ⊆ T lin N LP ^(β 1 ,β 2 )(z ∗ ) (z ∗ ) ⊆ T lin M P EC (z ∗ ) T lin

Nachdem wir die zum MPEC verwandten NLPs (2.8 - 2.10) und deren Tangentialkegel n¨ aher kennen gelernt haben, werden wir zum Abschluss dieses Kapitels noch einmal alle bisher erarbeiten Ergebnisse anschaulich zusammenfassen.

21

2.4 Zusammenfassung Tangentialkegel

Tragen wir alle Resultate dieses Kapitels zusammen, so ergibt sich folgende ¨ Ubersicht:

T T N LP (z ∗ ) ⊆ T N LP (β 1 ,β 2 ) (z ∗ ) ⊆ T M P EC (z ∗ ) ⊆ T RN LP (z ∗ )

⊆ ⊆ ⊆ ⊆

∪

T N LP (z ∗ ) ⊆ T lin (z ∗ ) ⊆ M P EC (z ∗ ) RN LP (z ∗ ) T lin T lin = T lin

N LP (β 1 ,β 2 )

Abb. 11: ¨ Ubersicht: Tangentialkegel

Beachte hierbei, dass die Hilfsprobleme in obiger ¨ Ubersicht wiederum am

Punkt z ∗ aufgestellt wurden. So bezeichnet beispielsweise T lin RN LP (z ∗ ) eigent- RNLP (z ∗ ) (z ∗ ) und die Information, dass das Hilfsproblem am Punkt z ∗ lich T lin

aufgestellt wurde, wurde in obiger ¨ Ubersicht lediglich aus Platzgr¨ unden weggelassen.

Betrachten wir die Tangentialkegel des MPEC (1.1) in obiger Abbildung, so sehen wir, dass diese durch die Tangentialkegel der Hilfsprobleme regelrecht eingesperrt werden. Dar¨ uber hinaus gilt sogar : ∪

Das heißt, dass wir den Tangentialkegel des MPEC (1.1) bzw. den MPEClinearisierten Tangentialkegel jeweils als endliche Vereinigung von Tangentialkegeln bzw. linearisierten Tangentialkegeln der auf (β 1 , β 2 )-reduzierten

N LP ^(β 1 ,β 2 ) (z ∗ ) darstellen k¨ onnen. Damit m¨ ussen wir die Kegel des MPEC

22

(1.1) gar nicht direkt anfassen, sondern k¨ onnen sie mit Hilfe von Standard-NLPs ohne Komplementarit¨ atsbedingungen exakt beschreiben. Beachte hier- NLP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β) konvex sind, F lin M P EC (z ∗ ) bei, dass zwar T lin

hingegen im Allgemeinen nicht, da die Vereinigung von konvexen Mengen

M P EC (z ∗ ) schon im Allgemeinen nicht konvex ist. Im Gegensatz dazu ist T lin konvex und identisch mit dem linearisierten Tangentialkegel des RNLP(z ∗ ) am Punkt z ∗ .

Wir haben also mit Hilfe der Tangentialkegel das MPEC (1.1) und seine Hilfsprobleme beschrieben, sowie deren Zusammenh¨ ange herausgearbeitet, wodurch wir einen guten Gesamteindruck erhalten haben. Erinnern wir uns zur¨ uck, an das globale Ziel dieser Arbeit, n¨ amlich die Herleitung von Optimalit¨ atsbedingungen vom KKT-Typ. Diese Bedingungen arbeiten ausschließlich mit dem linearisierten zul¨ assigen Bereich und somit m¨ ussen wir zuvor noch sicherstellen, dass der zul¨ assige Bereich des MPEC (1.1) durch die linearisierten Tangentialkegel auch richtig beschrieben wird. Das ist Aufgabe der Constraint Qualiﬁcations.

23

3 Constraint Qualiﬁcations

Um Optimalit¨ atsbedingungen in der Form von KKT-Bedingungen aufstellen zu k¨ onnen, muss unser Problem spezielle Anforderungen an die Nebenbedingungen erf¨ ullen. Diese Anforderungen werden Constraint Qualiﬁcations [CQs] genannt und sorgen daf¨ ur, dass die Linearisierung des zul¨ assigen Bereichs an einem zul¨ assigen Punkt die tats¨ achliche Beschaﬀenheit des zul¨ assigen Bereichs korrekt beschreibt. Wie wir jedoch in Beispiel 2.8 bereits gesehen haben, sind selbst f¨ ur einfachste MPECs der Tangentialkegel des MPEC und der linearisierte Tangentialkegel des MPEC verschieden, wodurch im Vergleich zu herk¨ ommlichen NLPs Probleme entstehen. Ziel dieses Kapitels ist es daher CQs zu ﬁnden, welche zum einen so schwach sind, dass MPECs eine Chance haben, diese zu erf¨ ullen, und zum anderen noch stark genug daf¨ ur sind, dass man unter diesen CQs auch Optimalit¨ atsbedingungen in der Form von KKT-Bedingungen herleiten kann. Dabei wird Flegels und Kanzows Wiederentdeckung, der lange in Vergessenheit geratenen Guignard CQ in [5] eine wichtige Rolle spielen.

Wir gehen im folgenden Abschnitt zun¨ achst auf die am weitesten verbreiteten Standard CQs (LICQ, MFCQ, SMFCQ) ein. Wie sich herausstellen wird, erf¨ ullen MPECs an keinem zul¨ assigen Punkt diese Standard CQs (Proposition 3.7). Deshalb werden wir anschließend geometrische CQs (Adabie CQ, Guignard CQ) einf¨ uhren mit deren Hilfe wir sp¨ ater in Kapitel 4 in der Lage sein werden, Optimalit¨ atsbedingungen 1. Ordnung f¨ ur eine spezielle Klasse von MPECs herzuleiten. Da geometrische CQs schwer zu ¨ uberpr¨ ufen sind,

gehen wir in einem weiteren Abschnitt auf MPEC-speziﬁsche Standard CQs, wie der MPEC-LICQ ein, die zum Teil hinreichend f¨ ur die geometrische Guignard CQ sind. Zudem werden wir MPEC-speziﬁsche geometrische CQs betrachten und mit der sogenannten MPEC-GCQ die bislang schw¨ achste CQ deﬁnieren, bevor wir am Ende dieses Kapitels alle CQs in einer ¨ Ubersicht zusammenfassen werden.

3.1 Standard CQs f¨ ur NLPs

Wie wir bereits erw¨ ahnt haben und am Ende dieses Abschnittes noch zeigen werden (Proposition 3.7), erf¨ ullt ein MPEC an keinem zul¨ assigen Punkt eine Standard CQ. Somit macht es keinen Sinn diese CQs anhand des MPECs zu deﬁnieren. Deshalb betrachten wir hier zun¨ achst die Standard CQs eines allgemeinen nichtlinearen Problems der Form (2.1). Die dabei wohl am weitesten verbreitete CQ ist die Linear Independence Constraint Qualiﬁcation [LICQ]:

24

Deﬁnition 3.1 Ein zul¨ assiger Punkt z ∗ des NLP (2.1) erf¨ ullt die LICQ,

falls die Gradienten der aktiven Nebenbedingungen

∇ z c i (z ∗ ) ∀i ∈ E ∪ A I (z ∗ )

(3.1)

linear unabh¨ angig sind.

Um zu illustrieren, dass die LICQ selbst f¨ ur einfachste MPECs zu strikt sind, betrachten wir erneut unser Beispiel 2.8:

Beispiel 3.2 Standard-MPEC

min

z

s.t. G(z) := z 1 ≥ 0,

Oﬀensichtlich liegt das Minimum dieses Problems im Ursprung z ∗ = (0, 0).

Ebenso leicht ist einzusehen, dass an diesem Punkt alle drei Nebenbedingungen aktiv sind, und somit k¨ onnen die Gradienten der drei Nebenbedingungen nicht linear unabh¨ angig sein. Mit anderen Worten ist die LICQs am Punkt

z ∗ nicht erf¨ ullt.

Sei ˆ z ein beliebiger zul¨ assiger Punkt unseres Beispiels. So muss entweder ˆ z ¹ oder ˆ z 2 gleich Null sein. Ohne Einschr¨ ankung sei ˆ z 1 = 0. Folglich ist die erste

und letzte Nebenbedingung aktiv. Betrachten wir die Gradienten der aktiven Nebenbedingungen am Punkt (0, ˆ z 2 ) so sieht man leicht, dass diese linear abh¨ angig sind:

( ) ( )

Somit erf¨ ullt dieses Beispiel an keinem zul¨ assigen Punkt die LICQ.

Eine etwas schw¨ achere Constraint Qualiﬁcation, welche jedoch im Allgemeinen keine Eindeutigkeit der Lagrangemultiplikatoren im KKT-System liefert, ist die sogenannte Mangasarian Fromovitz Constraint Qualiﬁcation [MFCQ]:

Deﬁnition 3.3 Ein zul¨ assiger Punkt z ∗ des NLP (2.1) erf¨ ullt die MFCQ,

falls die Gradienten der equality constraints

∇ z c i (z ∗ ) ∀i ∈ E

25

linear unabh¨ angig sind und ein Vektor d ∈ R n existiert, so dass gilt:

Wie sp¨ ater noch genauer erl¨ autert wird, ist die MFCQ an einem lokalen

Minimum z ∗ hinreichend um die Existenz von Lagrangemultiplikatoren zu

zeigen, welche die KKT-Bedingungen erf¨ ullen. Existieren bereits Lagrange-multiplikatoren λ i , so dass die KKT-Bedingungen an einem lokalen Minimum

z ∗ erf¨ ullt sind, so k¨ onnen wir eine st¨ arkere Variante der MFCQ deﬁnieren,

die sogenannte Strict Mangasarian Fromovitz Constraint Qualiﬁcation [SM- I (z ∗ ):= {i ∈ A I (z ∗ )|λ i > 0} die Menge der strikt aktiven FCQ]. Sei dazu A +

inequality constraints.

Deﬁnition 3.4 Eine lokale L¨ osung z ∗ des NLP (2.1), an welcher Lagran-

gemultiplikatoren λ i existieren, so dass die KKT-Bedingungen gelten, erf¨ ullt die SMFCQ, falls folgende Gradienten linear unabh¨ angig sind

∇ z c i (z ∗ ) ∀i ∈ E ∪ A ⁺ I (z ∗ )

und ein Vektor d ∈ R n existiert, so dass gilt:

Hierbei ist nochmals hervorzuheben, dass die SMFCQ bereits ein lokales Minimum sowie die Existenz der Lagrangemultiplikatoren im KKT-System

voraussetzt. Daf¨ ur kann man zeigen, dass f¨ ur einen Punkt z ∗ mit SMFCQ

bereits die Eindeutigkeit der Lagrangemultiplikatoren folgt. Es ist allgemein bekannt, dass zwischen den eben vorgestellten CQs folgender Zusammenhang besteht: (vgl. Flegel [2].)

Proposition 3.5 Sei z ∗ zul¨ assiger Punkt (bzw. lokale L¨ osung) des NLP

(2.1), dann gilt:

LICQ ⇒ ( SMFCQ ⇒ ) MFCQ

(Der eingeklammerte Teil gilt nur, falls z ∗ eine L¨ osung des MPEC (1.1) ist,

an der Lagrangemultiplikatoren existieren)

Um diese Proposition zu zeigen, ben¨ otigen wir folgendes Hilfslemma:

26

Lemma 3.6 Sei a i ∈ R n , ∀i ∈ {1, . . . , m} derart, dass f¨ ur ein s ≤ m alle a i f¨ ur i ∈ {1, . . . , s} linear unabh¨ angig sind. Zudem existiere ein d ∈ R n , so

dass gilt:

Dann ∃b ∈ R n derart, dass ∀r ≤ s gilt:

Beweis: vgl. Flegel [2].

Wegen der linearen Unabh¨ angigkeit aller a i ∀i ∈ {1, . . . , s} ∃ ˆ d ∈ R n , so dass

gilt:

Sei nun d ∈ R n beliebig gew¨ ahlt, derart, dass (3.2) gilt und setze b := d + δ ˆ d

f¨ ur ein beliebiges δ > 0. Nun gilt wegen (3.3):

Außerdem gilt f¨ ur ein hinreichend kleines δ:

Damit haben wir das Hilfslemma gezeigt und wir k¨ onnen Proposition 3.5 zeigen.

Beweis zu Proposition (3.5):

Sei z ∗ lokale L¨ osung des NLP (2.1), und sei die LICQ am Punkt z ∗ erf¨ ullt.

(Folglich existieren eindeutige Lagrangemultiplikatoren, so dass die KKT-

Bedingungen erf¨ ullt sind.) D.h. ∀i ∈ E ∪ A I (z ∗ ) sind die Gradienten ∇ z c i (z ∗ )

( E ∪ A I ) ⊆ (E ∪ A I (z ∗ )) folgt direkt die li- ⁺ (z ∗ ) linear unabh¨ angig. Wegen ( E ∪ A I )

neare Unabh¨ angigkeit aller ∇ z c i (z ∗ ) mit i ∈ ⁺ (z ∗ ) und somit die

erste Bedingung der SMFCQ. Die restlichen Bedingungen der SMFCQ folgen nach evtl. Umsortierung der Indizes, indem wir Lemma 3.6 mit s = m =

27

|E ∪ A I (z ∗ )| und r = |E ∪ A ⁺ I (z ∗ )| anwenden. D.h. es existiert ein Vektor d ∈ R n , so dass gilt:

Damit gilt die SMFCQ am Punkt z ∗ .

Sei z ∗ lokale L¨ osung des NLP (2.1), und sei die SMFCQ am Punkt z ∗ erf¨ ullt.

( E ∪ A + )

I (z ∗ ) Wegen E ⊆ sind wieder die entsprechenden Gradienten der

Nebenbedingungen linear unabh¨ angig und somit ist die erste Bedingung f¨ ur die MFCQ erf¨ ullt. Die verbleibenden Bedingungen f¨ ur die MFCQ folgen ana-log zu oben durch die Anwendung des Lemmas (3.6) mit m = |E ∪ A I (z ∗ )|, I (z ∗ )| und r = |E|. s = |E ∪ A +

Damit haben wir die Behauptung bewiesen f¨ ur den Fall, dass z ∗ eine lokale L¨ osung ist. Da wir jedoch die Voraussetzung, dass z ∗ eine lokale L¨ osung ist I (z ∗ ) ben¨ otigt haben, gilt LICQ lediglich f¨ ur die Deﬁnition der Indexmenge A +

⇒ MFCQ auch f¨ ur einen beliebigen zul¨ assigen Punkt des NLP (2.1) und der

Beweis ist komplett.

Richten wir unsere Aufmerksamkeit wieder auf den Fall des MPEC (1.1), so zeigt die nachfolgende Proposition, dass f¨ ur MPECs an keinem zul¨ assigen Punkt die MFCQ erf¨ ullt sein kann:

Proposition 3.7 Sei z ∗ ein beliebiger, zul¨ assiger Punkt des MPEC (1.1). Dann sind die MFCQ am Punkt z ∗ nicht erf¨ ullt.

Beweis: vgl. Flegel [2].

Annahme: Das MPEC (1.1) erf¨ ullt die MFCQ an einem beliebigen zul¨ assigen

Punkt z ∗ .

D.h. ∇ z c E (z ∗ ) und ∇ z (H(z ∗ ) T G(z ∗ )) sind linear unabh¨ angig und es existiert ein Vektor d ∈ R n , so dass gilt:

1.Fall: G i (z ∗ ) = H i (z ∗ ) = 0 ∀i ∈ {1, . . . , p} und somit folgt: ∑

∇ z (H(z ∗ ) T G(z ∗ )) = [G i (z ∗ )∇ z H i (z ∗ ) + H i (z ∗ )∇ z G i (z ∗ )] = 0

i∈{1,...,p}

28

Das widerspricht aber der linearen Unabh¨ angigkeit der Gleichheitsnebenbedingungen.

2.Fall: ∃ i ∈ {1, . . . , p} mit G i (z ∗ ) > 0 oder H i (z ∗ ) > 0.

Ohne Einschr¨ ankung existiere ein j ∈ {1, . . . , p} mit G j (z ∗ ) > 0. Also ist j ∈ γ nach der Deﬁnition der Indexmengen. Nun folgt: ∑

∇ z (H(z ∗ ) T G(z ∗ )) T d =

Das widerspricht jedoch der zweiten Zeile in (3.4). Insgesamt folgt, dass die

MFCQ am Punkt z ∗ nicht erf¨ ullt ist.

Zusammen mit der vorangegangenen Proposition 3.5 zeigt diese Proposition 3.7, dass sich die Standard CQs nicht f¨ ur MPECs eignen, da sie an keinem zul¨ assigen Punkt des MPEC (1.1) erf¨ ullt sein k¨ onnen. Diese Tatsache motiviert den n¨ achsten Abschnitt, der an einer elementareren geometrischen Betrachtung ansetzt, um eine CQ zu ﬁnden, welche von MPECs erf¨ ullt werden kann.

29

3.2 Geometrische CQs

Unser Ziel ist es nun, eine geeignete Anforderung an den zul¨ assigen Bereich (CQs) aufzustellen, welche von MPECs erf¨ ullt werden kann und unter welcher die KKT-Bedingungen eine notwendige Optimalit¨ atsbedingung erster Ordnung bilden. Da die KKT-Bedingungen lediglich Anforderungen an den linearisierten zul¨ assigen Bereich stellen, ist es an der Aufgabe einer CQ daf¨ ur zu sorgen, dass die Linearisierung des zul¨ assigen Bereichs nicht fehlschl¨ agt. Die wohl naheliegendste Art und Weise das zu garantieren ist die Adabie Constraint Qualiﬁcation [ACQ], welche fordert, dass f¨ ur alle zul¨ assigen Punkte der Tangentialkegel gleich dem linearisierten Tangentialkegel ist:

Deﬁnition 3.8 Ein zul¨ assiger Punkt z ∗ des NLP (2.1) erf¨ ullt die ACQ,

falls gilt:

T (z ∗ ) = T lin (z ∗ )

(3.5)

Diese geometrische CQ ist Grundlage aller im vorangegangenen Teilabschnitt vorgestellten Standard CQs. Wie wir jedoch schon anhand des Beispiels 2.8 gesehen haben, sind der Tangentialkegel und der linearisierte Tangentialkegel selbst f¨ ur sehr einfache MPECs unterschiedlich und erf¨ ullen die ACQ daher nicht. Somit suchen wir nach einer schw¨ acheren CQ. Dazu haben Flegel und Kanzow in [5] die lange Zeit in Vergessenheit geratene Guignard Constraint Qualiﬁcation [GCQ] wieder aufgegriﬀen:

Deﬁnition 3.9 Ein zul¨ assiger Punkt z ∗ des NLP (2.1) erf¨ ullt die GCQ,

falls gilt:

T (z ∗ ) ∗ = T lin (z ∗ ) ∗

(3.6)

Die GCQ fordert also im Gegensatz zur ACQ nur, dass die jeweils dualen Tangentialkegel ¨ ubereinstimmen. Man erkennt sofort, dass die ACQ hinreichend ist f¨ ur die GCQ. Inwiefern die GCQ wirklich schw¨ acher ist als die ACQ, sehen wir schnell ein, wenn wir uns die sogenannte primale Formulierung der GCQ ansehen, welche ¨ aquivalent ist zur obigen dualen Formulierung (3.6):

cl(conv(T (z ∗ ))) = T lin (z ∗ )

(3.7)

Im Hinblick auf Lemma 2.3 ist T lin (z ∗ ) ein abgeschlossener konvexer Kegel. T (z ∗ ) ist jedoch im Allgemeinen nicht konvex und f¨ ur den Fall des MPEC

(1.1) sogar an allen biaktiven Punkten sicher nicht konvex. Damit haben bei einem MPEC (1.1) nur die zul¨ assigen Punkte mit β = ∅ eine Chance die

ACQ zu erf¨ ullen. Um nun den Zusammenhang von den geometrischen CQs zu den herk¨ ommlichen Standard CQs herzustellen, sei hier folgende Proposition angebracht.

30

Proposition 3.10 Sei z ∗ zul¨ assiger Punkt des NLP (2.1), dann gilt:

M F CQ ⇒ ACQ ⇒ GCQ (3.8)

Beweis: ACQ ⇒ GCQ ist klar.

M F CQ ⇒ ACQ: siehe z.B. [9]

Da MPECs insbesondere NLPs sind, sind diese Deﬁnitionen und die Proposition 3.10 ohne weitere Anstrengungen auch auf MPECs ¨ ubertragbar. Damit

sind f¨ ur das MPEC (1.1) die ACQ bzw. die GCQ an einem zul¨ assigen Punkt

z ∗ erf¨ ullt, genau dann wenn T M P EC (z ∗ ) = T lin M P EC (z ∗ ) bzw. T M P EC (z ∗ ) ∗ =

M P EC (z ∗ ) ∗ gilt. Wie sich herausstellen wird, haben wir mit der GCQ eine T lin

CQ gefunden, welche durchaus von einer großen Gruppe von MPECs erf¨ ullt werden kann. Um das einzusehen, betrachten wir erneut unser Standardbeispiel 2.8, das zwar nicht die ACQ, sehr wohl aber die GCQ erf¨ ullt:

Beispiel 3.11 Standard-MPEC

min

z

s.t. G(z) := z 1 ≥ 0,

Betrachten wir erneut die Tangentialkegel an dem Minimum z ∗ = (0, 0): { ( ) ( ) }

T M P EC (z ∗ ) =

M P EC (z ∗ ) = R ² T lin

+

Oﬀensichtlich gilt: T M P EC (z ∗ ) ̸ = T lin M P EC (z ∗ ). Die ACQ ist also am Punkt z ∗

nicht erf¨ ullt. Im Gegensatz dazu gilt f¨ ur die jeweils dualen Tangentialkegel

am Punkt z ∗ :

{ }

T M P EC (z ∗ ) ∗ = v ∈ R ² | v T d ≥ 0 ∀d ∈ T M P EC (z ∗ )

{ ( ) ( ) }

{ }

M P EC (z ∗ ) ∗ = M P EC (z ∗ ) T lin v ∈ R ² | v T d ≥ 0 ∀d ∈ T lin = R 2

+

31

Somit gilt: T M P EC (z ∗ ) = T lin M P EC (z ∗ ) und die GCQ sind am Punkt z ∗ erf¨ ullt.

Abb. 14: Beispiel 3.11: Tangentialkegel und deren duale Tangentialkegel

Wir haben somit unser erstes Ziel erreicht und mit der GCQ eine CQ ge-funden, f¨ ur die MPECs eine echte Chance haben, sie zu erf¨ ullen. Wie wir in Kapitel 4 sehen werden ist es auch m¨ oglich unter der GCQ eine notwendige Optimalit¨ atsbedingung erster Ordnung in der Form von KKT-Bedingungen herzuleiten. Leider ist jedoch der (nicht linearisierte) Tangentialkegel f¨ ur komplexere Probleme sehr schwer zu bestimmen und somit sind die GCQ

im Allgemeinen sehr schwer zu ¨ uberpr¨ ufen. Daher werden wir im folgenden Teilabschnitt MPEC-speziﬁsche CQs einf¨ uhren, die leichter zu ¨ sind und teilweise f¨ ur die GCQ hinreichend sind.

32

3.3 MPEC-speziﬁsche CQs

Dieser Abschnitt besch¨ aftigt sich mit CQs, welche speziell f¨ ur MPECs entwickelt wurden. Dabei werden zun¨ achst zu einem vorliegendem MPEC die schon vorgestellten nichtlinearen Hilfsprobleme konstruiert, mit deren Hilfe dann MPEC-speziﬁsche Standard CQs deﬁniert werden k¨ onnen. Diese Idee stammt im Wesentlichen von Scheel und Scholtes, welche diese Strategie in [16] erstmals f¨ ur MPCCs entwickelten.

Nachdem wir mit Hilfe des TNLP (2.9) die MPEC-speziﬁschen Standard CQs deﬁniert haben, werden wir zeigen, dass die sogenannte MPEC-SMFCQ bereits hinreichend f¨ ur die im letzten Abschnitt vorgestellte GCQ ist. Jedoch werden wir sehen, dass die sogenannte MPEC-MFCQ nicht hinreichend f¨ ur die GCQ ist, was den letzten Teilabschnitt dieses Kapitels motiviert, in dem wir noch schw¨ achere MPEC-speziﬁsche geometrische CQs deﬁnieren werden.

3.3.1 MPEC-speziﬁsche Standard CQs

Wie bereits erw¨ ahnt, liegt der wesentliche Vorteil der MPEC-speziﬁschen Standard CQs darin, dass sie leichter zu ¨ uberpr¨ ufen sind als geometrische

CQs, wie die GCQ. Das ist in der Tatsache begr¨ undet, dass die MPECspeziﬁschen Standard CQs den normalen Standard CQs f¨ ur das Hilfsproblem

T N LP (z ∗ ) (2.9) entsprechen:

Deﬁnition 3.12 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Dann erf¨ ullt z ∗ die MPEC-LICQ (MPEC-MFCQ, MPEC-SMFCQ) genau dann, wenn z ∗ die LICQ (MFCQ, SMFCQ) f¨ ur das zum MPEC geh¨ orige TNLP(z ∗ )

(2.9) erf¨ ullt.

(Hierbei setzen die MPEC-SMFCQ bzw. die SMFCQ wieder voraus, dass z ∗

bereits eine L¨ osung ist, an der Lagrangemultiplikatoren existieren.)

Im Gegensatz zu den Ausf¨ uhrungen von Fletcher, Leyﬀer, Ralph und Schol-

tes in [8], welche die MPEC-LICQ anhand des RN LP (z ∗ ) deﬁnieren, haben wir hier die MPEC-speziﬁschen Standard CQs mit Hilfe des T N LP (z ∗ ) (2.9) deﬁniert. Vergleichen wir die LICQ am Punkt z ∗ f¨ ur das RNLP(z ∗ ) (2.10) mit den LICQ am Punkt z ∗ f¨ ur das TNLP(z ∗ ) (2.9), so sehen wir, dass diese identisch sind. Dies liegt daran, dass die Hilfsprobleme an dem gleichen Punkt z ∗

aufgestellt werden und die LICQ f¨ ur die Hilfsprobleme ebenfalls nur an die-

sem Punkt z ∗ ¨ uberpr¨ uft wird. Die LICQ, welche die lineare Unabh¨ angigkeit

der Gradienten der aktiven Nebenbedingungen am Punkt z ∗ fordert, h¨ angen nur von z ∗ ab, da f¨ ur alle Hilfsprobleme dieselben Bedingungen am Punkt z ∗

aktiv sind. Deshalb gilt:

33

Lemma 3.13 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann sind fol-gende Aussagen ¨ aquivalent:

i) z ∗ erf¨ ullt die LICQ f¨ ur T N LP (z ∗ )

ii) z ∗ erf¨ ullt die LICQ f¨ ur N LP ^(β 1 ,β 2 ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β)

iii) z ∗ erf¨ ullt die LICQ f¨ ur RN LP (z ∗ )

Beweis: Stellen wir die LICQ aller drei Hilfsprobleme auf, so sehen wir, dass f¨ ur alle drei Probleme die LICQ genau dann erf¨ ullt sind, wenn folgende Gradienten linear unabh¨ angig sind:

Damit ist die Behauptung bewiesen.

Vergleicht man die Nebenbedingungen der Hilfsprobleme (2.8 - 2.10), so er-

kennt man schnell, dass die equality constraints des T N LP (z ∗ ) (2.9) alle equality constraints des N LP ^(β 1 ,β 2 ) (z ∗ ) (2.8) beinhalten und dass die equality constraints des N LP ^(β 1 ,β 2 ) (z ∗ ) (2.8) wiederum alle equality constraints des RN LP (z ∗ ) (2.10) enthalten. Daher folgt f¨ ur die MFCQ, welche unter ande-

rem die lineare Unabh¨ angigkeit der Gradienten der equality constraints fordert, folgender Zusammenhang f¨ ur einen zul¨ assigen Punkt des MPEC (1.1):

Lemma 3.14 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann gilt:

z ∗ erf¨ ullt die MFCQ f¨ ur T N LP (z ∗ )

⇒ z ∗ erf¨ ullt die MFCQ f¨ ur N LP ^(β 1 ,β 2 ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β) ⇒ z ∗ erf¨ ullt die MFCQ f¨ ur RN LP (z ∗ )

Beweis: Der Beweis entspricht, wie in Proposition 3.5 einer direkten Anwendung des Hilfslemmas 3.6.

Im Gegensatz zu den MPEC-LICQ ist es also bei den MPEC-MFCQ nicht

egal, ob man die MFCQ f¨ ur das T N LP (z ∗ ) (2.9) oder f¨ ur das RN LP (z ∗ )

(2.10) fordert. Deﬁniert man n¨ amlich wie Ralph und Wright in [15] die

MPEC-MFCQ anhand des RN LP (z ∗ ), so fordern die MPEC-MFCQ kei-

ne lineare Unabh¨ angigkeit der Gradienten der biaktiven Nebenbedingungen. F¨ ur viele Schlussforderungen, welche wir im Verlauf dieser Arbeit noch verwenden werden, wird es notwendig sein, dass die MPEC-MFCQ hinreichend

34

sind f¨ ur die MFCQ f¨ ur N LP ^(β 1 ,β 2 ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β) (siehe z.B. Beweis zu

Theorem 3.17). Dies impliziert jedoch die lineare Unabh¨ angigkeit der Gradienten bestimmter biaktiver Nebenbedingungen. Deshalb ist es f¨ ur unsere

Ziele unabdingbar, die MPEC-MFCQ anhand des T N LP (z ∗ ) (2.9) zu deﬁ-

nieren.

F¨ ur die SMFCQ ist eine zu Lemma 3.14 analoge Aussage nicht m¨ oglich, weil

ein lokales Minimum z ∗ des MPEC (1.1) oder des T N LP (z ∗ ) im Allgemeinen nicht ein lokales Minimum des RNLP(z ∗ ) (2.10) ist (Korollar 2.15). Die

SMFCQ setzen jedoch jeweils immer eine lokale L¨ osung mit entsprechenden Lagrangemultiplikatoren voraus und somit k¨ onnen wir obige Aussage nicht auf die SMFCQ ¨ ubertragen.

Da die MPEC-speziﬁschen Standard CQs im Grunde nichts anderes sind

als Standard CQs f¨ ur das T N LP (z ∗ ) (2.9) und weil das T N LP (z ∗ ) (2.9)

insbesondere ein NLP ist, erhalten wir direkt aus Proposition 3.5 folgendes Korollar:

Korollar 3.15 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Dann gilt:

MPEC-LICQ ⇒ (MPEC-SMFCQ ⇒) MPEC-MFCQ

(Der eingeklammerte Teil gilt wiederum nur, falls z ∗ eine L¨ osung des MPEC

(1.1) ist, an der Lagrangemultiplikatoren existieren)

Beweis: Folgt direkt aus Proposition 3.5.

Nachdem wir mehrere Zusammenh¨ ange zwischen den MPEC-speziﬁschen Standard CQs untereinander erarbeitet haben, ist es nun an der Zeit sie mit den geometrischen CQs in Beziehung zu setzen. Eine der wichtigsten Aussagen stellt dabei Theorem 3.17 dar, das oﬀen legt, dass die MPEC-SMFCQ hinreichend f¨ ur die GCQ ist. Um das zu zeigen, verwende ich zum Großteil jene Schl¨ usse, welche bereits Flegel in [5] benutzt hat, um zu zeigen, dass die MPEC-LICQ hinreichend f¨ ur die GCQ ist. Flegel pr¨ asentiert in [5] zwar eine Heuristik f¨ ur einen indirekten Beweis, dass die MPEC-SMFCQ bereits hinreichend f¨ ur die GCQ ist, nach einer Anmerkung in [5] gelang es ihm jedoch nicht, diese Behauptung direkter zu beweisen. Im Gegensatz dazu werden wir diese Behauptung nun im Folgenden direkt zeigen. Dazu zun¨ achst folgendes Hilfslemma:

35

Lemma 3.16 Sei k, l ∈ N und α i , β j ∈ R und seien folgende Kegel gegeben: { }

K :=

{

L :=

Dann gilt: K = L ∗ und K ∗ = L.

Beweis: vgl. Flegel [5].

d ∈ R n { }

K =

{

⊆

{ =

noch zu zeigen: L ∗ ⊆ K

Sei dazu d ∈ L ∗ und w¨ ahle ein beliebiges i 0 ∈ {1, . . . , k}. Setze α i 0 = 1 und α i = 0, ∀i ∈ {1, . . . , k} \ {i 0 }. Setze außerdem b j = 0, ∀j ∈ {1, . . . , l}. Dann d ≥ 0. folgt: a T

i 0

i d ≥ 0, ∀i ∈ {1, . . . , k}. Analog dazu folgt: Da i 0 beliebig gew¨ ahlt war, folgt: a T

j d = 0, ∀j ∈ {1, . . . , l}. Also gilt d ∈ K und somit folgt insgesamt K = L ∗ b T und damit auch K ∗ = L.

Mit Hilfe dieses Lemmas k¨ onnen wir nun folgendes Theorem beweisen:

Theorem 3.17 Sei z ∗ ein lokales Minimum des MPEC (1.1), an welchem Lagrangemultiplikatoren existieren, und erf¨ ullt z ∗ die MPEC-SMFCQ, dann erf¨ ullt z ∗ die GCQ f¨ ur das MPEC (1.1).

Beweis: vgl. Flegel [5].

Wegen T M P EC (z ∗ ) ⊆ T lin M P EC (z ∗ ) folgt direkt: T M P EC (z ∗ ) ∗ ⊇ T lin

Es bleibt noch zu zeigen: T M P EC (z ∗ ) ∗ ⊆ T lin

Wegen Lemma (2.16) gilt:

∪

36

Mit Hilfe einiger vorangegangener Lemmata k¨ onnen wir nun die gleiche Aussage (3.11) erreichen, welche Flegel in [5] unter der MPEC-LICQ gezeigt hat:

Wegen der MPEC-SMFCQ gilt insbesondere die MFCQ f¨ ur das TNLP(z ∗ ) und mit Lemma 3.14 folgt die MFCQ f¨ ur N LP ^(β 1 ,β 2 ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β). Nach Proposition 3.5 ist somit auch die ACQ f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ) erf¨ ullt.

D.h. wir haben auch in dem Fall der MPEC-SMFCQ:

T N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) = T lin N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ), ∀(β 1 , β 2 ) ∈ P(β)

(3.11)

N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) ∗ und wenden darauf unser Hilfslemma 3.16 Betrachten wir T lin

an, so erhalten wir:

 

N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) ∗ = T lin



      

Lemma ^3.16 =

      

Bisher verlief dieser Beweis ¨ ahnlich zu dem Beweis von Flegel in [5]. Jetzt fehlt uns jedoch im Vergleich zu dem Fall der MPEC-LICQ die lineare Unabh¨ angigkeit der Gradienten aller aktiven Nebenbedingungen. Ziel ist es nun zun¨ achst zu zeigen, dass µ G und µ H in (3.12) eindeutig sind. Betrachten wir dazu die Bedingungen f¨ ur die MPEC-SMFCQ:



und es existiert ein d ∈ R n , so dass gilt :

37

Im Vergleich zu dem Fall mit der MPEC-LICQ fehlt uns hier also nur die li-neare Unabh¨ angigkeit der ∇ z c i (z ∗ ), ∀i ∈ A I \A I ⁺ . Wegen (3.14) liegen diese

Gradienten im echt positiven Halbraum eines Vektors d ∈ R n , der wiederum

im Nullraum aller anderen Gradienten liegt. Daher kann keiner der linear unabh¨ angigen Gradienten aus (3.13) als eine positive Linearkombination aus

den ∇ z c i (z ∗ ) mit i ∈ A I \ A I ⁺ dargestellt werden. D.h. ∀ µ c + > 0 gilt:

A I \A I ∑ ∑

Mit (3.13) folgt die Eindeutigkeit von µ c + , µ G und µ H in (3.12).

A I

Nun geht es wieder weiter wie bei Flegel in [5]: Sei v ∈ T M P EC (z ∗ ) ∗ beliebig gew¨ ahlt, dann gilt wegen (3.10) ∀(β 1 , β 2 ) ∈ P(β):

v ∈ T N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) ∗ und v ∈ T N LP (β 2 ,β 1 ) (z ∗ ) (z ∗ ) ∗

(3.16)

Wegen der Eindeutigkeit von µ G und µ H in (3.12) folgt mit β 1 ∪ β 2 = β und β ≥ 0 und µ H β ≥ 0. Damit gilt: (3.16): µ G   ∑

 

∗

       Lemma ^3.16 =

      

Prop. ^2.18 M P EC (z ∗ ) ∗ T lin =

Insgesamt gilt also: T M P EC (z ∗ ) ∗ = T lin M P EC (z ∗ ) ∗

38

An dieser Stelle m¨ ochte ich nochmals darauf aufmerksam machen, dass wir in dem obigen Beweis, sowohl f¨ ur (3.11), als auch f¨ ur die Eindeutigkeit der

µ G und µ H in (3.12), die MFCQ f¨ ur das T N LP (z ∗ ) verwendet haben. H¨ atten wir die MPEC-MFCQ wie Ralph und Wright in [15] anhand des RN LP (z ∗ )

deﬁniert, so h¨ atte dieser Beweis wegen der fehlenden linearen Unabh¨ angigkeit der Gradienten der biaktiven Nebenbedingungen nicht funktioniert. Eine direkte Folgerung von obigem Theorem ist folgende Aussage f¨ ur die MPEC-LICQ:

Korollar 3.18 Sei z ∗ ein zul¨ assiger Punkt des MPEC(1.1) und erf¨ ullt z ∗ die MPEC-LICQ, dann erf¨ ullt z ∗ die GCQ f¨ ur das MPEC (1.1).

Beweis: Da wir in dem Beweis zu Theorem 3.17 die Voraussetzung eines lokalen Minimums nicht ben¨ otigt haben, folgt die Behauptung direkt aus Theorem 3.17 und Korollar 3.15.

Im Gegensatz dazu sind die MPEC-MFCQ im Allgemeinen nicht hinreichend f¨ ur die GCQ, was folgendes Gegenbeispiel zeigt:

Beispiel 3.19

Die L¨ osung dieses MPEC (3.17) liegt im Ursprung. Sei z ∗ = (0, 0, 0), dann ist TNLP(z ∗ ) gegeben durch: (beachte n=3, p=1, α(z ∗ ) = γ(z ∗ ) = ∅ und β(z ∗ ) = {1}) 

Da am Punkt z ∗ alle vier Bedingungen aktiv sind, wir aber nur drei Dimensionen (n=3) haben, k¨ onnen die LICQ f¨ ur das TNLP(z ∗ ) nicht erf¨ ullt sein.

Somit gelten auch keine MPEC-LICQ f¨ ur das MPEC (3.17).

39

Pr¨ ufen wir nun, ob die MFCQ f¨ ur das TNLP(z ∗ ) erf¨ ullt ist:    

 • ∇ z G 1 (z ∗ ) =

⇒ die Gradienten der equality constraints sind lin. unabh.  

• Sei d ∈ R ³ mit d =

⇒ Es gilt die MPEC-MFCQ f¨ ur das MPEC (3.17) am Punkt z ∗

Testen wir, ob geometrische CQs am Punkt z ∗ f¨ ur das MPEC (3.17): { }

d ∈ R ³ | ∃{z k } ⊂ Z M P EC , ∃t k ↘ 0 : z k → z ∗ , z k −z ∗ T M P EC (z ∗ ) := → d

t k      

M P EC (z ∗ ) T lin

40

     

=

Es gilt: T M P EC (z ∗ ) ̸ = T lin M P EC (z ∗ ). Die ACQ ist also am Punkt z ∗ nicht erf¨ ullt. Betrachten wir die jeweils dualen Tangentialkegel am Punkt z ∗ : { }

T M P EC (z ∗ ) ∗ := v ∈ R ³ | v T d ≥ 0 ∀d ∈ T M P EC (z ∗ )

       

{ }

M P EC (z ∗ ) ∗ := M P EC (z ∗ ) T lin v ∈ R ³ | v T d ≥ 0 ∀d ∈ T lin

       

Abb. 15: Beispiel 3.19: Tangentialkegel und deren duale Tangentialkegel

⇒ T M P EC (z ∗ ) ∗ ̸ = T lin M P EC (z ∗ ) ∗ und somit ist die GCQ f¨ ur das MPEC (3.17) am Punkt z ∗ auch nicht erf¨ ullt!

41

Wie bereits mehrfach angesprochen, werden wir in Kapitel 4 eine notwendige Bedingung erster Ordnung unter der GCQ herleiten. Da wir aber im obigen Beispiel gesehen haben, dass die MPEC-MFCQ im Allgemeinen nicht f¨ ur die GCQ hinreichend ist, k¨ onnen wir dieses Ergebnis f¨ ur die MPEC-MFCQ nicht nutzen. Diese Tatsache motiviert den n¨ achsten Teilabschnitt dieses Kapitels, in welchem wir f¨ ur die MPEC-MFCQ hinreichende MPEC-speziﬁsche geometrische CQs deﬁnieren werden, mit Hilfe derer wir wiederum sp¨ ater in Kapitel 4 alternative Stationarit¨ atskonzepte entwickeln werden.

42

3.3.2 MPEC-speziﬁsche geometrische CQs

Um die Idee der MPEC-speziﬁschen geometrischen CQs zu erl¨ autern, erinnern wir uns an dieser Stelle an die Tatsache, dass aufgrund der Natur eines MPEC der zul¨ assige Bereich des MPEC unter Anwesenheit einer Komplementarit¨ atsbedingung nie konvex ist. Daher ist der Tangentialkegel

T M P EC (z ∗ ) an biaktiven Punkten (mit β ̸ = ∅) nicht konvex und hat somit M P EC (z ∗ ) zu entsprechen, keine Chance dem linearisierten Tangentialkegel T lin

da dieser ja immer konvex ist. Unsere erste Idee dieses Problem zu umgehen bzw. zu l¨ osen, war die Einf¨ uhrung der GCQ. Dabei haben wir beide

Kegel dualisiert, wodurch wir den Tangentialkegel T M P EC (z ∗ ) im Grunde

konvexiﬁziert haben. Indem wir in den GCQ also die jeweils dualen Kegel miteinander verglichen haben, gaben wir dem MPEC eine echte Chance diese CQ zu erf¨ ullen.

Die MPEC-ACQ verfolgt nun eine im Prinzip dazu gegens¨ atzliche Idee. Anstatt den Tangentialkegel des MPEC zu konvexiﬁzieren, kommen wir hier von der anderen Richtung und ¨ andern den linearisierten Tangentialkegel ab, indem wir ihn unkonvex machen. Dieser neue unkonvexiﬁzierte Kegel ist unser

M P EC (z ∗ ) (2.7). bereits vorgestellter MPEC-linearisierter Tangentialkegel F lin

Dieser Kegel wurde zum ersten mal bei Pang und Fukushima in [13] deﬁniert und dann von Kanzow und Flegel aufgegriﬀen, welche unter anderem in [2], [4] und [5] damit arbeiten. Mit Hilfe des MPEC-linearisierten Tangentialkegels sind wir in der Lage, die MPEC-speziﬁschen geometrischen CQs zu deﬁnieren:

Deﬁnition 3.20 Ein zul¨ assiger Punkt z ∗ des MPEC(1.1) erf¨ ullt die MPEC-

ACQ, falls gilt:

T M P EC (z ∗ ) = F lin M P EC (z ∗ )

(3.18)

Die MPEC-ACQ vergleicht also den Tangentialkegel T M P EC (z ∗ ) mit dem M P EC (z ∗ ), um dem MPEC (1.1) eine Chance zu genicht konvexen Kegel F lin

ben, diese CQ zu erf¨ ullen. Die MPEC-ACQ sind auch f¨ ur einige MPECs erf¨ ullt. So gilt z.B. f¨ ur alle MPAECs (mathematical programs with aﬃne complementarity constraints) die MPEC-ACQ, wobei jedoch bei MPA-ECs anders als der Name vermuten l¨ asst, alle Nebenbedingungen aﬃn sein m¨ ussen. Schw¨ acher als die MPEC-ACQ ist die MPEC-GCQ:

Deﬁnition 3.21 Ein zul¨ assiger Punkt z ∗ des MPEC(1.1) erf¨ ullt die MPEC-

GCQ, falls gilt:

T M P EC (z ∗ ) ∗ = F lin M P EC (z ∗ ) ∗

(3.19)

43

Diese Deﬁnitionen unterscheiden sich also von den Deﬁnitionen der herk¨ ommlichen geometrischen CQs nur darin, dass der linearisierte Tangentialkegel

M P EC (z ∗ ) durch MPEC-linearisierten Tangentialkegel F lin M P EC (z ∗ ) ersetzt T lin wurde. ¨ Ahnlich zu dem Fall der GCQ k¨ onnen wir auch hier f¨ ur die MPEC-GCQ die primale Formulierung von (3.19) angeben. Diese lautet:

cl(conv(T M P EC (z ∗ ))) = conv(F lin M P EC (z ∗ ))

(3.20)

Die MPEC-GCQ kombiniert damit unsere beiden Ideen. Auf der einen Seite ersetzt sie, wie die MPEC-ACQ auch, den linearisierten Tangentialkegel

M P EC (z ∗ ) durch den nicht konvexen Kegel F lin M P EC (z ∗ ), auf der anderen T lin

Seite werden anschließend beide Kegel konvexiﬁziert, bevor sie miteinander verglichen werden. Die MPEC-GCQ ist damit die schw¨ achste CQ, welche meines Wissens bisher f¨ ur MPECs existiert.

Oﬀensichtlich ist die MPEC-ACQ hinreichend f¨ ur die MPEC-GCQ. Wesentlich interessanter ist, dass die im vorherigen Abschnitt vorgestellten MPEC-MFCQ bereits hinreichend f¨ ur die MPEC-ACQ ist, was wir nun ¨ ahnlich zu Flegel in [2] im folgenden Theorem zeigen werden:

Theorem 3.22 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1), dann gilt:

MPEC-MFCQ ⇒ MPEC-ACQ ⇒ MPEC-GCQ

Beweis: vgl. Flegel [2].

MPEC-ACQ ⇒ MPEC-GCQ ist klar.

Sei z ∗ zul¨ assiger Punkt des MPEC (1.1), der die MPEC-MFCQ erf¨ ullt. D.h. das T N LP (z ∗ ) erf¨ ullt die MFCQ und nach Lemma 3.14 gilt somit auch die MFCQ am Punkt z ∗ f¨ ur N LP ^(β 1 ,β 2 ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β). Nach Proposition 3.10 gilt daher die ACQ am Punkt z ∗ f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ). Daraus folgt:

∪

M P EC (z ∗ ) ^Lemma2.17 F lin =

Außerdem gelten folgende Zusammenh¨ ange zwischen den geometrischen CQs und den MPEC-speziﬁschen geometrischen CQs:

44

Proposition 3.23 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1), dann gilt:

(i) ACQ ⇒ MPEC-ACQ

(ii) GCQ ⇒ MPEC-GCQ

Beweis: zu (i): Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), so dass die ACQ erf¨ ullt ist. D.h. es gilt: T M P EC (z ∗ ) = T lin M P EC (z ∗ )

Wegen Lemma 2.9 gilt:

T M P EC (z ∗ ) ⊆ F lin M P EC (z ∗ ) ⊆ T lin M P EC (z ∗ )

Insgesamt folgt also: T M P EC (z ∗ ) = F lin M P EC (z ∗ )

zu (ii): Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), so dass die GCQ erf¨ ullt ist. D.h. es gilt: T M P EC (z ∗ ) ∗ = T lin M P EC (z ∗ ) ∗

Wegen Lemma 2.9 und Lemma 2.5 (ii) gilt:

T M P EC (z ∗ ) ∗ ⊇ F lin M P EC (z ∗ ) ∗ ⊇ T lin M P EC (z ∗ ) ∗

Insgesamt folgt also: T M P EC (z ∗ ) ∗ = F lin M P EC (z ∗ ) ∗

Mit der MPEC-GCQ haben wir also die bisher schw¨ achste CQ gefunden und sp¨ ater in Kapitel 4 werden wir sehen, dass die sogenannte MPEC-linearisierte B-Stationarit¨ at unter den MPEC-GCQ eine notwendige Optimalit¨ atsbedingung erster Ordnung darstellt. Davor werden wir jedoch noch einmal alle Constraint Qualiﬁcations und deren Beziehungen untereinander zusammenfassen.

45

3.4 Zusammenfassung Constraint Qualiﬁcations

Tragen wir die wichtigsten Resultate dieses Kapitels zusammen, so ergibt sich folgende ¨ Ubersicht:



     

Standard

      CQs

geometrische

CQs

Eine wichtige Rolle im Hinblick auf die Optimalit¨ atsbedingungen im n¨ achsten Kapitel werden vor allem die GCQ und die MPEC-GCQ spielen, da diese einen sehr direkten ¨ Ubergang zur sogenannten Boulingand-Stationarit¨ at erm¨ oglichen. Wie wir sehen werden, sind diese CQs genau die Anforderungen, welche wir f¨ ur die jeweiligen Optimalit¨ atsbedingungen brauchen werden. Zudem sind die GCQ und die MPEC-GCQ, wie in obiger Abbildung zu sehen ist, auf ihrem jeweiligen Level die schw¨ achsten CQs. So sind insbesondere die MPEC-LICQ und die MPEC-SMFCQ hinreichend f¨ ur die GCQ. Ebenso ist die MPEC-MFCQ hinreichend f¨ ur die MPEC-GCQ. Demnach k¨ onnen wir alle Ergebnisse, welche wir unter der GCQ bzw. MPEC-GCQ erarbeitet haben, auf die jeweils st¨ arkeren CQs ¨ ubertragen.

46

4 Optimalit¨ atsbedingungen

Nachdem wir im letzten Kapitel mehrere CQs und ihre Zusammenh¨ ange kennengelernt haben, werden wir uns in diesem Kapitel mit Optimalit¨ atsbedingungen besch¨ aftigen. W¨ ahrend die CQs mit Ausnahme der SMFCQ und MPEC-SMFCQ lediglich Anforderungen an den zul¨ assigen Bereich darstellen, stellen die Optimalit¨ atsbedingungen Anforderungen an das gesamte Problem, d.h. an den zul¨ assigen Bereich und an das Zielfunktional. Jene Optimalit¨ atsbedingungen m¨ ussen, wie der Name schon sagt, an jedem Optimum des Problems auf jeden Fall erf¨ ullt sein.

In diesem Kapitel beginnen wir mit der Boulingand-Stationarit¨ at [B-Stationarit¨ at], welche in ihrer urspr¨ unglichen Form unabh¨ angig von jeglichen CQs ist. Anschließend werden wir zu Optimalit¨ atsbedingungen vom KKT-Typ ubergehen, welche Anforderungen an das Zielfunktional und an den lineari¨

sierten zul¨ assigen Bereich stellen und somit wesentlich von den CQs abh¨ angen. Dabei werden wir zun¨ achst die KKT-Punkte des MPEC und seiner Hilfsprobleme betrachten. Anschließend gehen wir ¨ uber zur sogenannten starken

Stationarit¨ at, welche unter der GCQ, MPEC-LICQ und der MPEC-SMFCQ eine wesentliche Rolle spielen werden. F¨ ur alle schw¨ acheren CQ ist die starke Stationarit¨ at im Allgemeinen jedoch zu stark, weshalb wir im Anschluss noch auf alternative Stationarit¨ atskonzepte eingehen werden, welche eigens f¨ ur MPECs entwickelt wurden. Abschließend werden wir hinreichende Optimalit¨ atsbedingungen zweiter Ordnung f¨ ur MPECs kennenlernen und mit der sogenannten MPEC-WSOSC die erste second order suﬃcient condition [SOSC] f¨ ur MPECs vorstellen, welche keinen stark station¨ aren Punkt voraussetzt.

4.1 B-Stationarit¨ at

Die B-Stationarit¨ at bedarf keiner Lagrangefunktion und entspricht im Grunde einer geometrischen Formulierung einer notwendigen Optimalit¨ atsbedingung erster Ordnung. Leider wird in der MPEC-Gemeinde der Begriﬀ Bstation¨ ar unterschiedlich deﬁniert und verwendet, wobei aber die gemeinten Begriﬀe nur miteinander ¨ ubereinstimmen, falls entsprechende CQs gelten. Deshalb werden wir hier dem Vorschlag von Kanzow und Flegel in [4] folgen, welche f¨ ur MPECs folgende drei unterschiedliche Begriﬀe f¨ ur B-station¨ ar einf¨ uhren:

Deﬁnition 4.1 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Dann heißt z ∗

B-station¨ ar genau dann, wenn gilt:

∇ z f (z ∗ ) ∈ T M P EC (z ∗ ) ∗

(4.1)

47

z ∗ heißt linearisiert B-station¨ ar, falls gilt:

∇ z f (z ∗ ) ∈ T lin M P EC (z ∗ ) ∗

(4.2)

und z ∗ heißt MPEC-linearisiert B-station¨ ar, falls gilt:

∇ z f (z ∗ ) ∈ F lin M P EC (z ∗ ) ∗

(4.3)

F¨ ur den allgemeineren Fall des NLP (2.1) k¨ onnen B-station¨ ar und linearisiert B-station¨ ar analog zu Deﬁnition 4.1 deﬁniert werden:

Deﬁnition 4.2 Sei z ∗ ein zul¨ assiger Punkt des NLP (2.1). Dann heißt z ∗

B-station¨ ar genau dann, wenn gilt:

∇ z f (z ∗ ) ∈ T (z ∗ ) ∗

(4.4)

z ∗ heißt linearisiert B-station¨ ar, falls gilt:

∇ z f (z ∗ ) ∈ T lin (z ∗ ) ∗

(4.5)

Da B-station¨ ar (4.1 bzw. 4.4) anhand des nicht linearisierten Tangentialkegels deﬁniert ist, ist dieser Begriﬀ unabh¨ angig von jeglichen CQs. Deﬁniert man den Begriﬀ B-station¨ ar f¨ ur das MPEC (1.1) mit Hilfe des MPEC-

MP EC (z ∗ ), wie es implizit z.B. in [8], [11], linearisierten Tangentialkegels F lin

[15] und [16] gemacht wird, so entspricht das nur unter der MPEC-GCQ

(T M P EC (z ∗ ) ∗ = F lin M P EC (z ∗ ) ∗ ) der eigentlichen Deﬁnition der B-Stationarit¨ at.

Außer Flegel und Kanzow in [5] und Ye in [17] setzt jedoch keiner die MPEC-GCQ voraus, was streng genommen falsch ist. Diese kleine Schlamperei kann zu fatalen Fehlschl¨ ussen f¨ uhren, denn wie wir gleich sehen werden, stellt die B-Stationarit¨ at unabh¨ angig von jeglichen CQs eine notwendige Optimalit¨ atsbedingung erster Ordnung dar, w¨ ahrend die MPEC-linearisierte B-Stationarit¨ at nur dann eine notwendige Optimalit¨ atsbedingung ist, wenn die MPEC-GCQ auch wirklich erf¨ ullt ist.

Proposition 4.3 Sei z ∗ eine L¨ osung des MPEC (1.1) bzw. des NLP (2.1), dann ist z ∗ B-station¨ ar.

Beweis: Sei z ∗ eine L¨ osung des NLP (2.1). D.h. es existiert keine zul¨ assige Richtung d vom Punkt z ∗ aus, welche bzgl. des Zielfunktionals f eine echte

Abstiegsrichtung w¨ are. Also gilt:

48

Da das MPEC (1.1) insbesondere ein Spezialfall eines NLP ist, gilt dies ebenso f¨ ur das MPEC und die Proposition ist bewiesen.

Betrachten wir die Deﬁnitionen der linearisierten B-Stationarit¨ at und der MPEC-linearisierten B-Stationarit¨ at, so erhalten wir mit Hilfe dieser Proposition 4.3 folgende zwei Korollare:

Korollar 4.4 Sei z ∗ eine L¨ osung des MPEC (1.1) bzw. des NLP (2.1) und gilt die GCQ am Punkt z ∗ , dann ist z ∗ linearisiert B-station¨ ar.

Beweis: folgt direkt aus den Deﬁnitionen 4.1 bzw. 4.2 und 3.9, sowie aus der vorangegangenen Proposition 4.3.

Korollar 4.5 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die MPEC-GCQ am Punkt z ∗ , dann ist z ∗ MPEC-linearisiert B-station¨ ar.

Beweis: folgt direkt aus den Deﬁnitionen 4.1 und 3.21, sowie aus der vorangegangenen Proposition 4.3.

An diesem Punkt wird deutlich, dass die GCQ bzw. MPEC-GCQ genau die CQs sind, welche wir ben¨ otigen, um von der B-Stationarit¨ at zur linearisierten B-Stationarit¨ at bzw. zur MPEC-linearisierten B-stationarit¨ at zu kommen. Was nun noch zu tun ist, ist im Grunde nichts anderes als die Umformulierung zu Optimalit¨ atsbedingungen vom KKT-Typ. F¨ ur den Fall der linearisierten B-Stationarit¨ at entspricht diese Umformulierung einer einfachen Anwendung des Farkas Lemmas 4.8. F¨ ur den Fall der MPEC-linearisierten B-Stationarit¨ at k¨ onnen wir Farkas Lemma jedoch leider nicht direkt anwenden,

M P EC (z ∗ ) nicht konvex ist. Unter anderem dadurch motiviert, werden da F lin

wir uns sp¨ ater auch den KKT-Punkten der Hilfsprobleme widmen.

49

4.2 KKT-Punkte

Ziel dieses Kapitels ist es zu zeigen, dass die KKT-Bedingungen unter der Voraussetzung der GCQ eine Optimalit¨ atsbedingung erster Ordnung darstellen. Dabei beginnen wir mit dem allgemeinen Fall des NLP (2.1), der dann ohne weiteres auf das MPEC (1.1) und seine Hilfsprobleme zu ¨ ubertragen ist.

4.2.1 KKT-Punkt f¨ ur das NLP

Wir deﬁnieren uns zun¨ achst die Lagrangefunktion des NLP (2.1) und mit Hilfe dieser dann den KKT-Punkt.

Deﬁnition 4.6 Sei z ∗ zul¨ assiger Punkt des NLP (2.1) und sei weiter λ ∈ R l (mit l = |E| + |I|). Dann deﬁnieren wir die Lagrangefunktion des NLP

(2.1) wie folgt:

∑

Hier m¨ ochte ich anmerken, dass die Vorzeichenwahl f¨ ur jene Summanden der Lagrangefunktion, welche sich auf Gleichheitsnebenbedingungen beziehen, frei ist. W¨ ahrend die Vorzeichen der Ungleichheitsnebenbedingungen davon abh¨ angen, ob man die inequality constraints im NLP (2.1) mit ≥ oder ≤ formuliert, ist das Vorzeichen der equality constraints egal, denn deren

Lagrangemultiplikatoren unterliegen im KKT-System keinerlei Vorzeichenrestriktionen. Ich habe mich entschieden den Gleichheitsnebenbedingungen das gleiche Vorzeichen zu geben, wie den Ungleichheitsnebenbedingungen, da sich dies vor allem f¨ ur die Lagrangefunktionen der Hilfsprobleme als vorteilhaft erwiesen hat.

Deﬁnition 4.7 Sei z ∗ zul¨ assiger Punkt des NLP (2.1). Dann heißt z ∗ KKT-Punkt des NLP (2.1) genau dann, wenn ein λ ∈ R l (mit l = |E| + |I|)

existiert, so dass gilt:

Man beachte hierbei, dass wir, im Gegensatz zu anderen Ausf¨ uhrungen, die

Bedingungen f¨ ur die Zul¨ assigkeit des Punktes z ∗ der ¨ Ubersichtlichkeit wegen

nicht in die KKT-Systeme packen, sondern sie wie in obiger Deﬁnition 4.7 im Vorfeld voraussetzen.

Um zu zeigen, dass eine L¨ osung des NLP (2.1) unter der GCQ immer ein

50

KKT-Punkt ist, also dass die KKT-Bedingungen (4.6) eine notwendige Optimalit¨ atsbedingung unter der GCQ darstellen, m¨ ussen wir zun¨ achst das folgende Lemma zeigen, das im Wesentlichen eine Version des bekannten Farkas Lemmas ist.

Lemma 4.8 (Farkas)

Sei A ∈ R m×n und b ∈ R n , dann sind folgende Aussagen ¨ aquivalent:

i) ∀d ∈ R n mit Ad ≥ 0 gilt: b T d ≥ 0

ii) ∃y ∈ R m d.d. gilt: A T y = b und y ≥ 0

Beweis: Dieser Beweis ist ¨ ahnlich zu den Ausf¨ uhrungen von Nocedal in [12]. ii) ⇒ i): Sei y ∈ R m d.d. gilt: A T y = b und y ≥ 0. Weiter sei d ∈ R n mit Ad ≥ 0 beliebig, dann gilt: ( ) T d = y T

i) ⇒ ii): Wir wollen nun folgende Aussage zeigen: (y ∈ R m mit A T y = b und y ≥ 0) ⇒ (∃d ∈ R n mit Ad ≥ 0 und b T d < 0) Sei y ∈ R m + beliebig. Nach Voraussetzung gilt nun A T y ̸ = b. Sei zudem B := {x ∈ R n |x = A T y, y ∈ R m

∈ B und somit hat folgendes Problem eine eindeutige konvexer Kegel mit b / L¨ osung:

}

Sei x ∗ ∈ B die eindeutige L¨ osung des Problems (∗). Da x ∗ ∈ B und wegen der Tatsache, dass B ein Kegel ist, folgt: δx ∗ ∈ B, ∀δ ≥ 0. Da x ∗ L¨ osung des Problems (∗) ist, hat ∥δx ∗ − b∥ 2 2 sein Minimum bei δ = 1

und wir erhalten:

Wiederum weil x ∗ L¨ osung des Problems (∗) ist und weil B konvex ist, gilt nun f¨ ur ein beliebig x ∈ B mit x ̸ = x ∗ :

∥x ∗ + θ(x − x ∗ ) − b∥ 2 2 ≥ ∥x ∗ − b∥ ² ∀θ ∈ [0, 1]; 2 ,

⇒ 2θ(x − x ∗ ) T (x ∗ − b) + θ ² ∥x − x ∗ ∥ 2 2 ≥ 0, ∀θ ∈ [0, 1].

51

F¨ ur θ ↘ 0 erhalten wir (x − x ∗ ) T (x ∗ − b) ≥ 0 und zusammen mit (4.7) folgt:

x T (x ∗ − b) ≥ 0, ∀x ∈ B.

(4.8)

Wir setzen d = x ∗ − b und zeigen, dass gilt: b T d < 0 und Ad ≥ 0. ∈ B gilt d ̸ = 0 und wir erhalten: Wegen b /

^(4.7) b T d = d T (x ∗ − d) = d T x ∗ − d T d = (x ∗ − b) T x ∗ − d T d = −∥d∥ 2 2 < 0.

Mit (4.8) gilt d T x ≥ 0 f¨ ur alle x ∈ B. D.h. :

Damit ist die Behauptung bewiesen.

Jetzt haben wir den Punkt erreicht, an dem wir mit Korollar 4.4 und dem Farkas Lemma 4.8 leicht zeigen k¨ onnen, dass die KKT-Bedingungen unter der GCQ eine notwendige Optimalit¨ atsbedingung darstellen.

Theorem 4.9 Sei z ∗ eine L¨ osung des NLP (2.1) und gilt die GCQ f¨ ur das NLP (2.1) am Punkt z ∗ . Dann ist z ∗ ein KKT-Punkt des NLP (2.1).

Beweis: vgl. Flegel [2].

Nach Korollar 4.4 folgt sofort, dass z ∗ linearisiert B-station¨ ar ist, d.h.:

∇ z f (z ∗ ) ∈ T lin (z ∗ ) ∗

Um nun die Voraussetzungen f¨ ur Farkas Lemma zu schaﬀen, setzen wir:  

Beachte, dass somit gilt: T lin (z ∗ ) = {d ∈ R n | Ad ≥ 0}.

Wegen b = ∇ z f (z ∗ ) ∈ T lin (z ∗ ) ∗ gilt: b T d ≥ 0, ∀d ∈ R n mit Ad ≥ 0.

Mit Farkas Lemma 4.8 folgt: ∃y ∈ R m d.d. gilt: A T y = b und y ≥ 0. Identiﬁziere nun die Komponenten von y mit: y T = (y T , y T E + , y T E − ). A I

Setze jetzt:

52

Damit haben wir aber schon die KKT-Bedingungen (4.6), denn es gilt:

∑

A T y = b ⇒

D.h. z ∗ ist ein KKT-Punkt.

Im Vergleich zu den meisten Ausf¨ uhrungen ¨ uber die KKT-Theorie, welche oft

die LICQ oder zumindest die ACQ voraussetzen, haben wir hier die KKT-Bedingungen unter der schw¨ acheren GCQ hergeleitet. Allerdings ist es mit dieser schw¨ acheren CQ nicht m¨ oglich die Eindeutigkeit der Lagrangemultipli-katoren zu zeigen, was unter der Voraussetzung der LICQ oder der SMFCQ m¨ oglich ist. F¨ ur den Fall des MPEC (1.1) werden wir nun sogar sehen, dass die Menge der Lagrangemultiplikatoren immer mindestens einen Freiheitsgrad hat.

4.2.2 KKT-Punkt f¨ ur das MPEC

Um die Ergebnisse des NLP (2.1) auf das MPEC (1.1) zu ¨ ubertragen, m¨ ussen

wir zun¨ achst die Lagrangefunktion und den KKT-Punkt f¨ ur das MPEC (1.1) deﬁnieren:

Deﬁnition 4.10 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Seien weiter ( ˆ ν 2 , ˆ ξ) ∈ R l × R p × R p × R (mit l = |E| + |I|), dann ist die Lagrange- λ, ˆ ν 1 , ˆ

funktion des MPEC(1.1) deﬁniert durch:

∑

L M P EC (z ∗ , λ, ν 1 , ν 2 , ξ) := f (z ∗ ) −

Wie bereits bei der Lagrangefunktion des NLP (2.1) erw¨ ahnt, ist die Vorzeichenwahl f¨ ur die Summanden der Gleichheitsbedingungen nicht von Bedeutung. F¨ ur mich hat es sich als vorteilhaft erwiesen, den Standard-equalities ein negatives Vorzeichen zu geben und dem Summanden der Komplementarit¨ atsbedingung ein positives Vorzeichen zu geben. Damit vertr¨ agt sich diese Notation auch mit der Notation in [8], wo die Komplementarit¨ atsbedingung des MPEC wie folgt formuliert wird:

G(z) ≥ 0, H(z) ≥ 0, G(z) T H(z) ≤ 0

53

F¨ ur diese Formulierung muss dem letzten Summanden der Lagrangefunktion ein positives Vorzeichen gegeben werden, wenn man die Vorzeichenrestriktionen im KKT-System beibehalten will.

Deﬁnition 4.11 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1). Dann heißt z ∗ KKT-Punkt des MPEC (1.1) genau dann, wenn ein ( ˆ ν 2 , ˆ ξ) ∈ R l × λ, ˆ ν 1 , ˆ

R p × R p × R existiert, so dass gilt:

Dabei ist anzumerken, dass an dem Punkt z ∗ wegen der Deﬁnition der Indexmengen α und γ gilt: G γ (z ∗ ) > 0 und H α (z ∗ ) > 0. Somit sind die Bedin-

gungen ˆ ν 1γ = 0 und ˆ ν 2α = 0 im KKT-System (4.10) gerade die Komplemen-

tarit¨ atsbedingungen f¨ ur G bzw. H und es gilt: G(z ∗ ) T ˆ

Nachdem wir die Lagrangefunktion und die KKT-Bedingungen deﬁniert haben, k¨ onnen wir Theorem 4.9 anwenden und erhalten unter der GCQ, dass die KKT-Bedingungen (4.10) eine notwendige Optimalit¨ atsbedingung f¨ ur unser MPEC (1.1) sind.

Korollar 4.12 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die GCQ f¨ ur das MPEC (1.1) am Punkt z ∗ . Dann ist z ∗ ein KKT-Punkt des MPEC (1.1).

Beweis: Folgt direkt aus Theorem 4.9, da ein MPEC insbesondere auch ein NLP ist.

Wie allgemein bekannt ist, f¨ uhrt die Verletzung der MFCQ dazu, dass die Menge der Lagrangemultiplikatoren im KKT-System unbeschr¨ ankt ist. Da jedoch in unserem Fall des MPEC (1.1) an keinem zul¨ assigen Punkt die MFCQ erf¨ ullt ist (Proposition 3.7), heißt das, dass die Menge der Lagrangemul-tiplikatoren im KKT-System (4.10) immer mindestens einen Freiheitsgrad besitzt. Aufgrund der speziellen Beschaﬀenheit des MPEC (1.1) ist es aber m¨ oglich diesen Freiheitsgrad zu eliminieren, was wir sp¨ ater im Abschnitt 4.3. durchf¨ uhren werden. Jetzt widmen wir uns aber zuerst den KKT-Punkten der Hilfsprobleme.

54

4.2.3 KKT-Punkte der Hilfsprobleme

Da die Hilfsprobleme (2.8-2.10) normale NLPs sind, k¨ onnen wir Theorem 4.9 ohne weiteres auf die Hilfsprobleme anwenden. Zun¨ achst m¨ ussen wir jedoch wieder die Lagrangefunktionen und die KKT-Bedingungen f¨ ur die Hilfsprobleme deﬁnieren:

Deﬁnition 4.13 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Seien weiter (λ, ν 1 , ν 2 ) ∈ R l × R p × R p (mit l = |E| + |I|).

(i) Sei (β 1 , β 2 ) ∈ P(β), dann ist die Lagrangefunktion des auf (β 1 , β 2 )- reduzierten NLP ^(β 1 ,β 2 ) (z ∗ ) deﬁniert durch:

∑

(ii) Die Lagrangefunktion des T N LP (z ∗ ) ist deﬁniert durch:

∑

(iii) Die Lagrangefunktion des RN LP (z ∗ ) ist deﬁniert durch:

∑

Da wir den Gleichheitsnebenbedingungen das gleiche Vorzeichen gegeben haben wie den Ungleichheitsbedingungen, sind die Lagrangefunktionen aller Hilfsprobleme identisch. Dies liegt daran, dass sich die verschiedenen Hilfsprobleme lediglich darin unterscheiden, f¨ ur welche G i bzw. H i sie gleich Null oder gr¨ oßer gleich Null fordern. Die KKT-Bedingungen der Hilfsprobleme sind hingegen im Allgemeinen nicht identisch, da sie Vorzeichenrestriktionen an die Lagrangemultiplikatoren der jeweiligen Ungleichheitsbedingungen fordern.

55

Deﬁnition 4.14 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1) und sei (β 1 , β 2 ) ∈ P(β). z ∗ heißt KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ) (2.8), genau dann wenn ∃(λ, ν 1 , ν 2 ) ∈ R l × R p × R p , so dass gilt: 

Deﬁnition 4.15 Ein zul¨ assiger Punkt z ∗ des MPEC (1.1) heißt KKT-Punkt des TNLP(z ∗ ) (2.9), genau dann wenn ∃(λ, ν 1 , ν 2 ) ∈ R l ×R p ×R p ,

so dass gilt:



Deﬁnition 4.16 Ein zul¨ assiger Punkt z ∗ des MPEC (1.1) heißt KKT-Punkt des RNLP(z ∗ ) (2.10), genau dann wenn ∃(λ, ν 1 , ν 2 ) ∈ R l × R p × R p , so dass gilt: 

Wie immer, wenn es um die Hilfsprobleme geht, verweise ich auch hier wieder

darauf, dass die Hilfsprobleme immer von dem Punkt z ∗ abh¨ angen, an wel-chem sie aufgestellt wurden. Betrachtet man obige Deﬁnitionen aufmerksam, so erkennt man, dass die KKT-Bedingungen hier stets nur an jenem Punkt gepr¨ uft werden, an welchem das jeweilige Hilfsproblem aufgestellt worden ist. Somit ist es kein Problem, dass wir in Deﬁnition 4.16 lediglich die Zul¨ assigkeit bzgl. des MPEC (1.1) voraussetzen, denn es gilt zwar im Allgemeinen

nicht, dass Z RN LP ⊆ Z M P EC , aber mit Sicherheit ist z ∗ in dem zul¨ assigen Bereich des am Punkt z ∗ aufgestellten RN LP (z ∗ ).

56

Da die Lagrangefunktionen identisch sind, unterscheiden sich die KKT- Bedingungen der Hilfsprobleme nur in ihren Anforderungen an die Lagrange-multiplikatoren der biaktiven Komponenten. D.h. unter anderem, dass die KKT-Bedingungen der Hilfsprobleme identisch sind, falls β = ∅. Dies ist auch naheliegend, denn f¨ ur β = ∅ sind schon die Hilfsprobleme (2.8) - (2.10)

identisch. Zudem sieht man leicht ein, dass folgender Zusammenhang zwischen den KKT-Punkten gilt:

Lemma 4.17 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1), dann gilt:

z ∗ ist KKT-Punkt des RN LP (z ∗ )

⇒ z ∗ ist KKT-Punkt des N LP ^(β 1 ,β 2 ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β) ⇒ z ∗ ist KKT-Punkt des T N LP (z ∗ )

Beweis: Vergleich der Anforderungen an ν 1 und ν 2 in den KKT-Systemen (4.11) - (4.13) liefert mit β 1 ⊆ β und β 2 ⊆ β sofort die Behauptung.

Wenden wir nun Theorem 4.9 direkt auf die Hilfsprobleme an, so bekommen wir folgendes Korollar.

Korollar 4.18 Sei z ∗ zul¨ assiger Punkt des MPEC (1.1), dann gilt:

(i) Ist z ∗ L¨ osung des T N LP (z ∗ ) und gilt die GCQ f¨ ur das T N LP (z ∗ ) am Punkt z ∗ , dann ist z ∗ ein KKT-Punkt des T N LP (z ∗ ).

(ii) Sei (β 1 , β 2 ) ∈ P(β) beliebig. Ist z ∗ L¨ osung des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ) und gilt die GCQ f¨ ur das N LP ^(β 1 ,β 2 ) (z ∗ ) am Punkt z ∗ , dann ist z ∗ ein KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ).

(iii) Ist z ∗ L¨ osung des RN LP (z ∗ ) und gilt die GCQ f¨ ur das RN LP (z ∗ ) am Punkt z ∗ , dann ist z ∗ ein KKT-Punkt des RN LP (z ∗ ).

Beweis: Folgt direkt aus Theorem 4.9

Wir haben hier die GCQ f¨ ur die jeweiligen Hilfsprobleme vorausgesetzt, um die jeweiligen KKT-Bedingungen als notwendige Optimalit¨ atsbedingungen zu bekommen. F¨ ur den Fall der MPEC-GCQ f¨ ur unser MPEC (1.1) haben wir aber im Allgemeinen keine GCQ f¨ ur die Hilfsprobleme. Interessanterweise ist es aber unter den MPEC-GCQ m¨ oglich, von einer L¨ osung

z ∗ des MPEC (1.1) ausgehend, die KKT-Bedingungen f¨ ur ein auf (β 1 , β 2 )reduziertes N LP ^(β 1 ,β 2 ) (z ∗ ) herzuleiten, ohne die GCQ f¨ ur jenes N LP ^(β 1 ,β 2 ) (z ∗ )

vorauszusetzen. Um dies zu beweisen, zeigen wir zun¨ achst folgendes sehr m¨ achtige Theorem 4.19, dessen Aussage bereits Kanzow und Flegel in [5] verwendet haben.

57

Theorem 4.19 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann ist z ∗ genau dann MPEC-linearisiert B-station¨ ar, wenn ∀(β 1 , β 2 ) ∈ P(β) z ∗ KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ) ist.

Beweis: ∇ z f (z ∗ ) ∈ F lin

M P EC (z ∗ ) ∗

∇ z f (z ∗ ) T d ≥ 0, ∀d ∈ F lin ⇔

⇔ ∀(β 1 , β 2 ) ∈ P gilt: ∇ z f (z ∗ ) T d ≥ 0, ∀d ∈ T lin N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ )

^Farkas ⇔ ∀(β 1 , β 2 ) ∈ P gilt:

Mit Hilfe dieses Theorems 4.19 k¨ onnen wir nun zeigen, dass f¨ ur eine L¨ osung z ∗

des MPEC (1.1) mit MPEC-GCQ die KKT-Bedingungen f¨ ur die auf (β 1 , β 2 )-

reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ) notwendige Optimalit¨ atsbedingungen darstellen, ohne dass wir die GCQ f¨ ur die jeweiligen N LP ^(β 1 ,β 2 ) (z ∗ ) voraussetzen m¨ ussen.

Korollar 4.20 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die MPEC-GCQ f¨ ur das MPEC (1.1) am Punkt z ∗ , dann ist ∀(β 1 , β 2 ) ∈ P(β) z ∗ KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ).

Beweis: Folgt direkt aus Korollar 4.5 und obigem Theorem 4.19.

Diese Aussage ist sehr stark. Mit der schw¨ achsten CQ, der MPEC-GCQ, haben wir in Korollar 4.5 gerade die Anforderungen erf¨ ullt, um die MPEClinearisierte B-Stationarit¨ at zu folgern. Die MPEC-linearisierte B-Stationarit¨ at ist nach Theorem 4.19 wiederum ¨ aquivalent zu der Bedingung, dass

∀(β 1 , β 2 ) ∈ P(β) z ∗ KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ )

ist. Damit haben wir also keinerlei Informationen verschenkt. Angesichts der

Tatsache, dass es 2 |β| Partitionen von β gibt, ist es jedoch sehr aufw¨ andig uberpr¨ ufen, da wir folglich 2 |β| KKT-Systeme diese Bedingung vollst¨ andig zu ¨

checken m¨ ussten. Nichts desto trotz wird Korollar 4.20 insbesondere bei den alternativen Stationarit¨ atskonzepten noch eine sehr wichtige Rolle spielen. Betrachten wir erneut das Lemma 4.17, so k¨ onnen wir mit Korollar 4.20

sofort eine analoge Aussage f¨ ur das T N LP (z ∗ ) folgern.

Korollar 4.21 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die MPEC-GCQ f¨ ur das MPEC (1.1) am Punkt z ∗ , dann ist z ∗ KKT-Punkt des T N LP (z ∗ ).

Beweis: Folgt direkt aus Lemma 4.17 und Korollar 4.20.

58

F¨ ur das RN LP (z ∗ ) k¨ onnen wir eine derartige Aussage unter der MPEC-GCQ RN LP (z ∗ ) (z ∗ ) ⊆ F lin M P EC (z ∗ ). nicht herleiten, denn im Allgemeinen gilt nicht: T lin

Wie wir jetzt sehen werden, lassen sich f¨ ur den Fall, dass die GCQ f¨ ur unser MPEC (1.1) erf¨ ullt ist, analoge und ebenso starke Aussagen f¨ ur das

RN LP (z ∗ ) herleiten, wie in Theorem 4.19 und Korollar 4.20.

Theorem 4.22 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann ist z ∗ genau dann linearisiert B-station¨ ar, wenn z ∗ KKT-Punkt des RN LP (z ∗ ).

Beweis:

⇔

^Farkas ⇔

Beachte hierbei die Rolle von Proposition 2.18, welche aussagt, dass gilt:

M P EC (z ∗ ) = T lin RN LP (z ∗ ) (z ∗ ). Wie bereits erw¨ ahnt, ﬁndet sich die Aussage die- T lin

ser Proposition in keinem mir bekannten Paper. Sie erleichtert uns aber den Weg erheblich, da wir unter der GCQ relativ fr¨ uh von dem MPEC (1.1) zum

RN LP (z ∗ ) ¨ ubergehen k¨ onnen und somit mit Hilfe des Farkas Lemmas sofort

die KKT-Bedingungen des RN LP (z ∗ ) (4.13) als notwendige Optimalit¨ ats-

bedingung f¨ ur unser MPEC (1.1) bekommen (siehe nachfolgendes Korollar

M P EC (z ∗ ) zu T lin RN LP (z ∗ ) (z ∗ ) impliziert dabei die Ubergang von T lin 4.23). Der ¨

Eliminierung eines Freiheitsgrades von dem KKT-System (4.10) des MPEC

(1.1) zu dem KKT-System (2.10) des RN LP (z ∗ ). In Theorem 4.26 des n¨ achsten Abschnittes werden wir zeigen, dass z ∗ genau dann ein KKT-Punkt des MPEC (1.1) ist, wenn er KKT-Punkt des RN LP (z ∗ ) ist.

Korollar 4.23 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die GCQ f¨ ur das MPEC (1.1) am Punkt z ∗ , dann ist z ∗ KKT-Punkt des RN LP (z ∗ ).

Beweis: Folgt direkt aus Korollar 4.4 und obigem Theorem 4.22.

Wir haben es also auch f¨ ur das RN LP (z ∗ ) geschaﬀt, von einer L¨ osung z ∗ des MPEC (1.1) ausgehend, die KKT-Bedingungen f¨ ur das RN LP (z ∗ ) herzuleiten, ohne die GCQ f¨ ur das RN LP (z ∗ ) vorauszusetzen. Allerdings haben

wir daf¨ ur im Gegensatz zu Korollar 4.20 nicht nur die MPEC-GCQ ben¨ otigt, sondern schon die GCQ f¨ ur das MPEC (1.1).

59

4.2.4 Zusammenfassung KKT-Punkte

An diesem Punkt ist bereits eine Menge passiert, weshalb wir kurz die wichtigsten Ergebnisse dieses Teilabschnittes in einer ¨ Ubersicht zusammenfassen:

Wir haben damit bereits drei notwendige Optimalit¨ atsbedingungen vom KKT-Typ erarbeitet. Unter der MPEC-GCQ haben wir gezeigt, dass eine L¨ osung

z ∗ des MPEC (1.1) KKT-Punkt bzgl. aller N LP ^(β 1 ,β 2 ) (z ∗ ) ist. Diese Bedin-

gung ist zwar unter der MPEC-GCQ sehr stark, aber unter Umst¨ anden sehr

aufw¨ andig, da man 2 |β| KKT-Systeme zu ¨ uberpr¨ ufen hat. Sp¨ ater, wenn wir

zur MPEC-Buchstabensuppe kommen, werden wir jene zul¨ assigen Punkte z ∗ des MPEC (1.1), f¨ ur welche eine Partition (β 1 , β 2 ) ∈ P(β) existiert, so dass z ∗ KKT-Punkt des N LP ^(β 1 ,β 2 ) (z ∗ ) ist, A-station¨ ar nennen.

Ebenfalls unter der MPEC-GCQ, haben wir erarbeitet, dass eine L¨ osung

z ∗ des MPEC (1.1) auch ein KKT-Punkt des T N LP (z ∗ ) ist. Diese Aussa-

ge ist zwar nicht aufw¨ andig zu ¨ uberpr¨ ufen, aber leider auch nicht beson-

60

ders aussagekr¨ aftig, weshalb die KKT-Punkte des T N LP (z ∗ ) innerhalb der

MPEC-Buchstabensuppe schwach station¨ ar bzw. W-station¨ ar genannt wer-den. Allerdings werden die KKT-Punkte des T N LP (z ∗ ) ein wichtiges Werk-zeug f¨ ur uns sein, da die Menge der Lagrangemultiplikatoren, welche die

KKT-Bedingungen f¨ ur das T N LP (z ∗ ) erf¨ ullen konvex ist.

F¨ ur eine L¨ osung des MPEC mit der GCQ haben wir die KKT-Bedingungen

f¨ ur das RN LP (z ∗ ) als notwendige Optimalit¨ atsbedingung herausgearbeitet.

Diese Optimalit¨ atsbedingung fordert zwar statt der MPEC-GCQ die st¨ arkere GCQ, aber daf¨ ur ist sie auch wesentlich st¨ arker als die anderen beiden.

Die KKT-Punkte des RN LP (z ∗ ) werden in der MPEC-Gemeinde als stark

station¨ are Punkte bezeichnet und werden im Anschluss aufgrund ihrer Wichtigkeit in einem separaten Kapitel behandelt.

61

4.3 Starke Stationarit¨ at

Der Begriﬀ der starken Stationarit¨ at ist in der MPEC-Gemeinde weit verbreitet und spielt eine bedeutende Rolle. So werden beispielsweise stark station¨ are Punkte sowohl von Fletcher, Leyﬀer, Ralph und Scholtes in [8] f¨ ur die lokale Konvergenz von SQP-Methoden, als auch von Raghunathan und Biegler in [14] f¨ ur die lokale Konvergenz des IPOPT vorausgesetzt. Streng genommen geh¨ ort die starke Stationarit¨ at eigentlich zu der MPEC-Buchstabensuppe, welche wir erst im n¨ achsten Kapitel kennenlernen werden, doch aufgrund Ihrer herausragenden Bedeutung wird sie hier in einem separaten Abschnitt vorgestellt.

Nachdem wir die starke Stationarit¨ at deﬁniert haben, werden wir zun¨ achst zeigen, dass stark station¨ are Punkte gerade die KKT-Punkte unseres MPEC (1.1) sind. Damit erhalten wir umgehend die starke Stationarit¨ at als notwendige Optimalit¨ atsbedingung unter der GCQ. Anschließend stellen wir noch einen alternativen Beweis dazu vor, bevor wir dann gegen Ende dieses Abschnittes zeigen, dass die Lagrangemultiplikatoren im KKT-Sytem (4.13) unter der MPEC-LICQ und der MPEC-SMFCQ sogar eindeutig sind. Wir starten mit der Deﬁnition der starken Stationarit¨ at, welche nichts ande-

res ist als die KKT-Bedingungen f¨ ur das RN LP (z ∗ ).

Deﬁnition 4.24 Ein zul¨ assiger Punkt z ∗ des MPEC (1.1) heißt stark station¨ ar genau dann, wenn z ∗ KKT-Punkt des RNLP(z ∗ ) (2.10) ist. D.h. ∃(λ, ν 1 , ν 2 ) ∈ R l × R p × R p , so dass (4.13) gilt.

Man bemerke hierbei, dass einige Autoren wie z.B. Kanzow und Flegel in [5]

stark station¨ are Punkte nicht als KKT-Punkte des RN LP (z ∗ ) identiﬁzieren, uberhaupt nicht mit dem RN LP (z ∗ ) arbeiten. In meinen Augen bietet da sie ¨

diese Identiﬁzierung jedoch eine bessere Anschauung, als die Deﬁnition nur anhand des KKT-Systems (4.13).

Wie in fast allen Ausf¨ uhrung zu stark station¨ aren Punkten (z.B. in [5], [8])

wollen wir nun ebenfalls zeigen, dass ein zul¨ assiger Punkt z ∗ genau dann

stark station¨ ar ist (4.13), wenn er ein KKT-Punkt f¨ ur das MPEC ist (4.10). Erinnern wir uns daf¨ ur zur¨ uck an Proposition 2.18, die ausgesagt hat, dass der linearisierte Tangentialkegel des MPEC dem linearisierten Tangential-kegel des RNLP(z ∗ ) entspricht, so ist diese Aussage auch leicht einzusehen,

denn es gilt:

F arkas ^4.8 ⇔ P rop. ^2.18 ⇔ F arkas ^4.8 ⇔

62

Dieser Vorgang (von oben nach unten) entspricht im Prinzip der Eliminierung des Lagrangemultiplikators ˆ ξ und somit der Eliminierung eines Freiheits-

grades in der Menge der Lagrangemultiplikatoren des KKT-Systems (4.10). F¨ ur die direkte Umrechnung der Lagrangemultiplikatoren zwischen den zwei KKT-Systemen deﬁnieren wir wie in [8] den Basismultiplikator ˆ ξ:

Deﬁnition 4.25 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1) und sei (λ, ν 1 , ν 2 ) ∈ R l × R p × R p , so dass (4.10) gilt. Dann deﬁnieren wir den Basismultiplikator: { ) } ( ) (

Mit Hilfe dieses Basismultiplikators sind wir nun in der Lage die Lagrange-multiplikatoren der zwei KKT-Systeme (4.10) und (4.13) direkt ineinander umzurechnen, was folgendes Theorem 4.26 zeigt.

Theorem 4.26 Ein zul¨ assiger Punkt z ∗ des MPEC(1.1) ist genau dann stark station¨ ar, wenn z ∗ KKT-Punkt des MPEC(1.1) ist. Außerdem sind die

Lagrangemultiplikatoren der beiden KKT-Systeme durch folgende Formeln direkt miteinander zu verkn¨ upfen:

Beweis: vgl. z.B. Fletcher, Leyﬀer, Ralph und Scholtes in [8].

Sei z ∗ ein KKT-Punkt des MPEC(1.1). D.h. ∃( ˆ ν 2 , ˆ ξ) ∈ R l × R p × R p × R λ, ˆ ν 1 , ˆ

d.d. (4.10) erf¨ ullt ist. Wegen H γ∪β (z ∗ ) = 0 und G α∪β (z ∗ ) = 0 setzen wir

gem¨ aß (4.14):

Wegen (4.10) zusammen mit (4.15) gelten nun bis auf die erste Zeile schon alle Bedingungen aus (4.13). Es bleibt somit nur noch zu zeigen, dass gilt:

63

∇ z L RN LP (z ∗ ) (z ∗ , λ, ν 1 , ν 2 ) = 0 und dann ist z ∗ schon stark station¨ ar.

∇ z L RN LP (z ∗ ) (z ∗ , λ, ν 1 , ν 2 ) =

( ) ∑ ∑

= ∇ z f (z ∗ ) −

^(4.15) ∇ z f (z ∗ ) −

=

∑

−

= ∇ z f (z ∗ ) −

+ ˆ ξ

^(4.10) = ∇ z L M P EC (z ∗ , ˆ ν 2 , ˆ λ, ˆ ν 1 , ˆ ξ) = 0

F¨ ur die Gegenrichtung sei jetzt z ∗ stark station¨ ar, d.h. ∃(λ, ν 1 , ν 2 ) ∈ R l ×R p × R p d.d. (4.13) gilt. Wir setzen unseren Basismultiplikator ˆ 4.25 und ( ˆ λ,

ˆ rung (4.14) die Gradienten der Lagrangefunktionen der zwei KKT-Systeme (4.10) und (4.13) gleich. Es bleiben also nur noch die Vorzeichenrestriktionen von (4.10) zu zeigen. Dabei folgt ˆ ν 2β ≥ 0 und ˆ ˆ ν 2α = 0 direkt aus (4.13). Schließlich gilt wegen der Wahl unseres Basismultiplikators ˆ ξ:

Damit ist der Beweis komplett.

4.3.1 Starke Stationarit¨ at unter der GCQ

Betrachten wir Korollar 4.12 zusammen mit obigem Theorem 4.26, so erhalten wir unmittelbar folgende Aussage.

Korollar 4.27 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die GCQ f¨ ur das MPEC (1.1) am Punkt z ∗ . Dann ist z ∗ stark station¨ ar.

Beweis: Folgt direkt aus Korollar 4.12 und Theorem 4.26.

64

Auf ¨ ahnliche Art und Weise zeigen auch Flegel in [2] oder Fletcher, Leyﬀer, Ralph und Scholtes in [8] die starke Stationarit¨ at, jedoch wird in [8] dies nur unter der MPEC-LICQ gezeigt. Man beachte an diesem Punkt, dass wir die starke Stationarit¨ at unter der GCQ bereits im vorangegangenen Abschnitt in Korollar 4.23 gezeigt haben, ohne daf¨ ur Korollar 4.12 oder Theorem 4.26 zu verwenden. Wir f¨ uhren nun einen weiteren Beweis derselbigen Aussage durch, welcher im Prinzip die gleichen Mittel verwendet, die wir schon f¨ ur Theorem 4.22 benutzt haben. Im Gegensatz zu Theorem 4.22 werden wir jedoch die Lagrangemultiplikatoren explizit identiﬁzieren, um sie f¨ ur die Beweise unter der MPEC-LICQ und MPEC-SMFCQ verwenden zu k¨ onnen.

Theorem 4.28 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die GCQ f¨ ur das MPEC (1.1) am Punkt z ∗ . Dann ist z ∗ stark station¨ ar.

Beweis: Der Beweis funktioniert im Prinzip analog zu dem Beweis von Theorem 4.9. Beachte jedoch, dass wir unter Verwendung der Proposition 2.18,

das Farkas Lemma auf den linearisierten Tangentialkegel des RN LP (z ∗ ) an-wenden und nicht auf den linearisierten Tangentialkegel des MPEC.

Nach Korollar 4.4 folgt unter obigen Voraussetzungen sofort, dass z ∗ lineari-

siert B-station¨ ar ist, d.h.:

∇ z f (z ∗ ) ∈ T lin M P EC (z ∗ ) ∗

Nach Proposition 2.18 gilt:

T lin = T lin

Also liegt der Gradient des Zielfunktionals auch im dualen linearisierten Tan-gentialkegel des RN LP (z ∗ ). Um das Farkas Lemma anzuwenden, setzen wir:

 

Beachte, dass somit gilt: T lin

Wegen b = ∇ z f (z ∗ ) ∈ T lin RN LP (z ∗ ) ∗ gilt: b T d ≥ 0, ∀d ∈ R n mit Ad ≥ 0.

65

Mit Farkas Lemma 4.8 folgt daher: ∃y ∈ R m d.d. gilt: A T y = b und y ≥ 0.

Identiﬁziere die Komponenten von y mit:

y T = (y A I T , y G,β T , y H,β T , y E + T , y E − T , y α + T , y α − T , y γ + T , y γ − T )

Und setze:



λ A I = y A I , ν 1,β = y G,β , ν 2,β = y H,β ,

Damit haben wir aber bereits die KKT-Bedingungen f¨ ur das RN LP (z ∗ )

(4.13), denn es gilt:



A T y = b ⇒

(4.16) ⇒

D.h. aber, dass z ∗ stark station¨ ar ist.

4.3.2 Starke Stationarit¨ at unter der MPEC-LICQ

Mit der starken Stationarit¨ at haben wir nun eine notwendige Optimalit¨ atsbedingung vom KKT-Typ. Im Vergleich zu den KKT-Bedingungen (4.10) f¨ ur das MPEC (1.1) hat die Menge der Lagrangemultiplikatoren bei der starken Stationarit¨ at einen Freiheitsgrad weniger. Unter der MPEC-LICQ k¨ onnen wir jetzt sogar zeigen, dass die Lagrangemultiplikatoren im KKT-Sytem (4.13)

des RN LP (z ∗ ) eindeutig sind.

Proposition 4.29 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die MPEC-LICQ f¨ ur das MPEC (1.1) am Punkt z ∗ . Dann ist z ∗ stark station¨ ar und der

Lagrangemultiplikator (λ, ν 1 , ν 2 ) in (4.13) ist eindeutig.

Beweis: Nach Korollar 3.18 ist die MPEC-LICQ bereits hinreichend f¨ ur die GCQ. Daher folgt mit vorangegangenem Theorem 4.28 unter obigen Voraus-

setzungen bereits, dass z ∗ stark station¨ ar ist. Es bleibt nur noch zu zeigen,

dass der Lagrangemultiplikator (λ, ν 1 , ν 2 ) in (4.13) unter der MPEC-LICQ

66

eindeutig ist. Betrachte dazu die erste Zeile von (4.17): ∑

∇ z L RN LP (z ∗ ) (z ∗ , λ, ν 1 , ν 2 ) = ∇ z f (z ∗ ) −

Wegen der MPEC-LICQ zusammen mit Lemma 3.13 gilt die LICQ f¨ ur das

RNLP(z ∗ ) und somit sind die Gradienten der aktiven Nebenbedingungen in

(4.18) linear unabh¨ angig. Betrachten wir jetzt die letzte Spalte von (4.16), so sehen wir, dass die Lagrangemultiplikatoren f¨ ur alle inaktiven Nebenbe-

dingungen 0 sind. Dies liefert zusammen mit den LICQ f¨ ur das RNLP(z ∗ )

die Eindeutigkeit der Koeﬃzienten der aktiven Nebenbedingungen in (4.18). Insgesamt folgt, dass (λ, ν 1 , ν 2 ) eindeutig ist.

4.3.3 Starke Stationarit¨ at unter der MPEC-SMFCQ

Auch unter der MPEC-SMFCQ k¨ onnen wir mit ¨ ahnlichen Mitteln wie in Proposition 4.29 die Eindeutigkeit der Lagrangemultiplikatoren zeigen.

Proposition 4.30 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die MPEC-SMFCQ f¨ ur das MPEC (1.1) am Punkt z ∗ . Dann ist z ∗ stark station¨ ar und

der Lagrangemultiplikator (λ, ν 1 , ν 2 ) in (4.13) ist eindeutig.

Beweis: Nach Theorem 3.17 ist die MPEC-SMFCQ bereits hinreichend f¨ ur die GCQ. Daher folgt mit Theorem 4.28 unter obigen Voraussetzungen bereits,

dass z ∗ stark station¨ ar ist. Es bleibt noch zu zeigen, dass der Lagrangemul-tiplikator (λ, ν 1 , ν 2 ) in (4.13) unter der MPEC-SMFCQ eindeutig ist. Dazu liefern uns die MPEC-SMFCQ: 

Im Vergleich zu dem Fall der MPEC-LICQ fehlt uns hier nur die lineare Un-abh¨ angigkeit der ∇ z c i (z ∗ ), ∀i ∈ A I \ A I ⁺ . Wegen der Deﬁnition der Index- ⁺ (z ∗ )gilt jedoch: λ A I \A I ⁺ = 0. Nach der letzten Spalte von (4.16) menge A I

sind die Lagrangemultiplikatoren f¨ ur alle inaktiven Nebenbedingungen ebenfalls 0. Betrachten wir wieder die erste Zeile von (4.17) und eliminieren wir

67

die Summanden dessen Koeﬃzienten 0 sind, dann erhalten wir: ∑

∇ z L RN LP (z ∗ ) (z ∗ , λ, ν 1 , ν 2 ) = ∇ z f (z ∗ ) −

∑

−

Nach (4.19) sind aber alle Gradienten dieser strikt aktiven Nebenbedingungen linear unabh¨ angig und somit folgt die Eindeutigkeit der Lagrangemultiplika-toren λ E∪A I ⁺ , ν 1,α∪β und ν 2,γ∪β . Da alle anderen Lagrangemultiplikatoren 0 sind, ist der Beweis komplett.

Wir haben in diesem Abschnitt gezeigt, dass die starke Stationarit¨ at unter der GCQ, MPEC-LICQ und MPEC-SMFCQ eine notwendige Optimalit¨ atsbedingung f¨ ur unser MPEC (1.1) darstellt. Wie wir jedoch im folgenden Kapitel sehen werden, ist die MPEC-MFCQ im Allgemeinen nicht hinreichend um die starke Stationarit¨ at herzuleiten.

68

4.4 Alternative Stationarit¨ atskonzepte

Wir beginnen dieses Kapitel, indem wir unsere Aufmerksamkeit erneut auf das Beispiel 3.19 richten, das zwar die MPEC-MFCQ erf¨ ullt, nicht jedoch die GCQ. Wir werden dabei sehen, dass die im vorangegangen Abschnitt vorgestellte starke Stationarit¨ at keine notwendige Optimalit¨ atsbedingung f¨ ur dieses Beispiel darstellt. Diese Tatsache motiviert das Ziel dieses Kapitels, alternative Stationarit¨ atsbedingungen zu ﬁnden, welche unter der MPEC-MFCQ bzw. der MPEC-GCQ notwendige Optimalit¨ atsbedingungen darstellen.

Beispiel 4.31

Das Minimum dieses Problems liegt bei z ∗ = (0, 0, 0) und wie am Ende des Abschnitts 3.3.1 bereits gezeigt, gilt bei z ∗ die MPEC-MFCQ, nicht jedoch uberpr¨ ufen, ob die L¨ osung z ∗ auch stark station¨ ar die GCQ. Nun wollen wir ¨

ist. Dazu betrachten wir den Gradienten der Lagrangefunktion des entspre-chenden RN LP (z ∗ ) und setzen ihn gleich 0:

     

∇ z L RN LP (z ∗ ) (z ∗ , λ, ν 1 , ν 2 ) =

Angenommen z ∗ sei stark station¨ ar, dann gilt insbesondere λ ≥ 0 und somit

folgt aus obigem Gleichungssystem:



}

Das widerspricht jedoch der Bedingung ν 2,β ≥ 0 in (4.13) und somit ist z ∗

nicht stark station¨ ar.

69

Insgesamt zeigt dieses Beispiel, dass die starke Stationarit¨ at im Allgemeinen unter der MPEC-MFCQ keine notwendige Optimalit¨ atsbedingung f¨ ur unser MPEC (1.1) ist. Dies motiviert den weiteren Verlauf dieses Kapitels, in dem wir alternative Stationarit¨ atsbegriﬀe entwickeln werden. Dabei gehen wir zun¨ achst auf Stationarit¨ atsbegriﬀe ein, welche der Form von KKT-Bedingungen entsprechen und welche in der MPEC-Gemeinde scherzhaft auch oft mit ’the alphabet soup of stationarity concepts’ bezeichnet werden. In dieser MPEC-Buchstabensuppe wird neben der starken Stationarit¨ at vor allem die M-Stationarit¨ at eine zentrale Rolle spielen. Wie Flegel in [2] gezeigt hat, ist die M-Stationarit¨ at unter der MPEC-GCQ eine notwendige Optimalit¨ atsbedingung. Da dieser Beweis sehr aufw¨ andig ist, habe ich in diesem Zusammenhang eine neue Beweisidee verfolgt. Dabei habe ich versucht eine Konvexkombination aus den Lagrangemultiplikatoren

der KKT-Punkte der N LP ^(β 1 ,β 2 ) (z ∗ ) zu ﬁnden, welche M-station¨ ar ist. Pro-

jiziert man dieses Problem auf den 2|β|-dimensionalen Raum, so handelt es sich um eine konvexe Menge, welche entweder gewisse Koordinatenebenen oder bestimmte positive Orthanden schneiden muss. Leider ist es mir nicht gelungen, dieses anfangs trivial wirkende Problem zu l¨ osen. Wie wir sehen werden, eint jene alternativen Stationarit¨ atskonzepte alle ein entscheidender Nachteil, denn sie schließen nicht aus, dass es von dem betreﬀenden station¨ aren Punkt aus eine zul¨ assige Abstiegsrichtung gibt. Somit sind sie zwar notwendige Optimalit¨ atsbedingungen, aber aufgrund ihrer geringen Aussagekraft ist es fraglich, ob sie bei der Suche nach einem Minimum hilfreich sein k¨ onnen. Vielmehr berichten Leyﬀer und Munson in [11] davon, dass sie ein Hindernis darstellen, da NLP-L¨ oser dazu tendieren gegen diese Punkte zu konvergieren, obwohl sie nicht B-Station¨ ar sind. Deshalb werden wir uns gegen Ende dieses Abschnittes noch einmal der MPEC-linearisierten B-Stationarit¨ at widmen, welche zwar sehr aufw¨ andig zu testen ist, aber daf¨ ur stellt sie unter der MPEC-GCQ eine notwendige Optimalit¨ atsbedingung dar, die zul¨ assige Abstiegsrichtungen ausschließt.

4.4.1 Die MPEC-Buchstabensuppe

Die nun folgenden Stationarit¨ atsbegriﬀe sind notwendige Optimalit¨ atsbedingungen vom KKT-Typ f¨ ur das MPEC (1.1). Deshalb w¨ are es eigentlich auf den ersten Blick naheliegend f¨ ur die Deﬁnitionen dieser Stationarit¨ atsbegriffe, auch die in Deﬁnition 4.10 deﬁnierte Lagrangefunktion des MPEC (1.1) zu verwenden. Die MPEC-Gemeinde verwendet daf¨ ur jedoch stillschweigend immer die Lagrangefunktion eines der Hilfsprobleme, was bei einigen dieser Begriﬀe dazu f¨ uhrt, dass sie zu KKT-Bedingungen eines Hilfsproblems werden. Durch meine bewusst so gesetzte Vorzeichenwahl f¨ ur die Summanden

70

der Lagrangefunktion, haben alle Hilfsprobleme die gleiche Lagrangefunktion und somit k¨ onnen wir f¨ ur die folgenden Bedingungen stets die gleiche Lagrangefunktion verwenden.

Deﬁnition 4.32 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Dann deﬁ-

nieren wir folgende Stationarit¨ atsbegriﬀe:

(i) z ∗ heißt W-station¨ ar bzw. schwach station¨ ar, falls ein (λ, ν 1 , ν 2 ) ∈ R l × R p × R p existiert, so dass gilt: 

(ii) z ∗ heißt A-station¨ ar, falls ein (λ, ν 1 , ν 2 ) ∈ R l × R p × R p existiert, das

(4.22) erf¨ ullt und zus¨ atzlich gilt:

ν 1,i ≥ 0 ∨ ν 2,i ≥ 0, ∀i ∈ β (4.23)

(iii) z ∗ heißt C-station¨ ar, falls ein (λ, ν 1 , ν 2 ) ∈ R l × R p × R p existiert, das

(4.22) erf¨ ullt und zus¨ atzlich gilt:

ν 1,i ν 2,i ≥ 0, ∀i ∈ β (4.24)

(iv) z ∗ heißt M-station¨ ar, falls ein (λ, ν 1 , ν 2 ) ∈ R l × R p × R p existiert, das

(4.22) erf¨ ullt und zus¨ atzlich gilt:

ν 1,i > 0 ∧ ν 2,i > 0, oder ν 1,i ν 2,i = 0, ∀i ∈ β (4.25)

(v) z ∗ heißt S-station¨ ar bzw. stark station¨ ar, falls ein (λ, ν 1 , ν 2 ) ∈ R l × R p × R p existiert, das (4.22) erf¨ ullt und zus¨ atzlich gilt:

ν 1,i ≥ 0 ∧ ν 2,i ≥ 0, ∀i ∈ β (4.26)

Diese Stationarit¨ atsbegriﬀe unterscheiden sich nur in ihren Anforderungen an die Lagrangemultiplikatoren der biaktiven Komplementarit¨ atsbedingungen. Das ’A’ in A-station¨ ar steht f¨ ur ’alternative’, da in jeder biaktiven Komponente nur einer der beiden Lagrangemultiplikatoren gr¨ oßer gleich Null sein muss. Zum ersten Mal wurde A-station¨ ar von Flegel und Kanzow in [3] benutzt. Die Begriﬀe der C-Stationarit¨ at und M-Stationarit¨ at stammen von

71

den Namen Clarke und Mordukhovich, deren Techniken bei der Entwicklung dieser Stationarit¨ atsbegriﬀe eine wichtige Rolle spielten. Dabei kam die C-Stationarit¨ at erstmals bei Scheel und Scholtes in [16] auf, welche sie f¨ ur den etwas allgemeineren Fall des MPCC, als Fritz-John-type condition einf¨ uhrten. S-station¨ ar ist identisch zu unserer starken Stationarit¨ at, welche wieder-um ¨ aquivalent ist zu den KKT-Bedingungen des RN LP (z ∗ ). Analog dazu

ist W-station¨ ar, also die schwache Stationarit¨ at, ¨ aquivalent zu den KKT-Bedingungen des T N LP (z ∗ ), wie auch schon Ye in [17] angemerkt hat. Ein

weiterer sehr interessanter Zusammenhang besteht zwischen A-station¨ ar und

den KKT-Bedingungen f¨ ur das auf (β 1 , β 2 )-reduzierte N LP ^(β 1 ,β 2 ) (z ∗ ), wie fol-

gende Proposition zeigt:

Proposition 4.33 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Dann ist z ∗ genau dann A-station¨ ar, wenn ∃(β 1 , β 2 ) ∈ P(β), so dass z ∗ KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ) ist.

Beweis: Sei z ∗ KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ), d.h. ∃(λ, ν 1 , ν 2 ) ∈ R l × R p × R p , so dass gilt: 

Da die Lagrangefunktionen aller Hilfsprobleme gleich sind, impliziert dies

(4.22) und wegen β 1 ∪β 2 = β folgt direkt (4.23). z ∗ ist damit also A-station¨ ar. Sei andererseits z ∗ ein A-station¨ arer Punkt mit zugeh¨ origen Lagrangemulti-plikator (λ, ν 1 , ν 2 ) ∈ R l × R p × R p , d.h. insbesondere:

ν 1,i ≥ 0 ∨ ν 2,i ≥ 0, ∀i ∈ β (4.28)

W¨ ahle:

β 1 := {i ∈ β | ν 1,i < 0 }; β 2 := β \ β 1 ,

Wegen β 1 ∪ β 2 = β zusammen mit (4.28) und (4.22) gilt (4.27). Also ist z ∗ KKT-Punkt des auf (β 1 , β 2 )-reduzierten N LP ^(β 1 ,β 2 ) (z ∗ ).

72

Kurz zusammengefasst erhalten wir damit f¨ ur die W-, A- und S-station¨ aren Punkte:

z ∗ ist S-station¨ ar ⇔ z ∗ ist KKT-Punkt des RN LP (z ∗ ) z ∗ ist A-station¨ ar ⇔ z ∗ ist KKT-Punkt eines N LP ^(β 1 ,β 2 ) (z ∗ ) z ∗ ist W-station¨ ar ⇔ z ∗ ist KKT-Punkt des T N LP (z ∗ )

Aus ¨ asthetischen Gr¨ unden deﬁnieren wir jetzt f¨ ur alle Stationarit¨ atsbegriﬀe die Mengen der Lagrangemultiplikatoren:

Deﬁnition 4.34 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann deﬁnie-

ren wir folgende Mengen:

(i) Λ W (z ∗ ) := { x ∈ R l+2p | x erf¨ ullt (4.22) } heißt die Menge der schwach station¨ aren Lagrangemultiplikatoren am Punkt z ∗ .

(ii) Λ A (z ∗ ) := { x ∈ R l+2p | x erf¨ ullt (4.22) und (4.23) } heißt die Menge der A-station¨ aren Lagrangemultiplikatoren am Punkt z ∗ .

(iii) Λ C (z ∗ ) := { x ∈ R l+2p | x erf¨ ullt (4.22) und (4.24) } heißt die Menge der C-station¨ aren Lagrangemultiplikatoren am Punkt z ∗ .

(iv) Λ M (z ∗ ) := { x ∈ R l+2p | x erf¨ ullt (4.22) und (4.25) } heißt die Menge der M-station¨ aren Lagrangemultiplikatoren am Punkt z ∗ .

(v) Λ S (z ∗ ) := { x ∈ R l+2p | x erf¨ ullt (4.22) und (4.26)} heißt die Menge der stark station¨ aren Lagrangemultiplikatoren am Punkt z ∗ .

Vergleichen wir diese Mengen bzgl. der Bedingungen (4.22) - (4.26), so ist leicht einzusehen, dass folgende Aussagen gelten:

Lemma 4.35 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1), dann gilt:

(i) Λ W (z ∗ ) ist konvex

(ii) Λ A (z ∗ ) ⊆ Λ W (z ∗ ), Λ C (z ∗ ) ⊆ Λ W (z ∗ )

(iii) Λ M (z ∗ ) = Λ A (z ∗ ) ∩ Λ C (z ∗ )

(iv) Λ S (z ∗ ) ⊆ Λ M (z ∗ )

(v) F¨ ur β = ∅ gilt: Λ W (z ∗ ) = Λ A (z ∗ ) = Λ C (z ∗ ) = Λ M (z ∗ ) = Λ S (z ∗ )

73

Beweis: zu (i): Λ W (z ∗ ) ist konvex, denn man kann (4.22) umformulieren zu einem Ungleichungssystem der Form: Aˆ x ≥ 0. (ii) - (v) folgen direkt aus Deﬁnition 4.32.

Daraus ergibt sich nun folgende ¨ Ubersicht f¨ ur die Zusammenh¨ ange zwischen den Begriﬀen: { ⇒ A − station¨ ar ⇒

Abb. 18: A-, C-, M- und S-station¨ are Punkte f¨ ur j ∈ β

Obige Abbildung verdeutlicht noch einmal, welche Lage die Lagrangemulti-plikatoren der station¨ aren Punkte bzgl. jeder biaktiven Komponente haben m¨ ussen.

Im Zusammenhang mit diesen Stationarit¨ atskonzepten wurde bereits viel Arbeit geleistet. So haben Scheel und Scholtes in [16] f¨ ur den etwas allgemeineren Fall des MPCC gezeigt, dass die C-Stationarit¨ at eine notwendige Optimalit¨ atsbedingung unter den MPEC-MFCQ darstellt. Wir haben bereits gezeigt, dass die S-Stationarit¨ at eine notwendige Optimalit¨ atsbedingung unter der GCQ ist. Zudem haben wir ebenfalls bewiesen, dass die A-Stationarit¨ at und somit auch die W-Stationarit¨ at eine notwendige Optimalit¨ atsbedingung unter der MPEC-GCQ darstellt (siehe Korollar 4.20 und Korollar 4.21). Was jetzt noch bleibt, ist die C- und M-Stationarit¨ at unter der MPEC-GCQ. Hat man bewiesen, dass die M-Stationarit¨ at eine notwenige Optimalit¨ atsbedingung unter der MPEC-GCQ ist, so folgt nach Lemma 4.35 selbiges sogleich f¨ ur die C-Stationarit¨ at.

74

4.4.2 M-Stationarit¨ at unter der MPEC-GCQ

Bereits Flegel gelang es in [6], mit Hilfe der sogenannten Mordukhovich-Kegel zu zeigen, dass die M-Stationarit¨ at eine notwendige Optimalit¨ atsbedingung unter der MPEC-GCQ darstellt. Dieser Beweis ist jedoch sehr aufw¨ andig und umfangreich. Schon relativ fr¨ uh war ich der ¨ Uberzeugung,

dass diese Aussage auch wesentlich einfacher zu zeigen ist. Wesentlicher Be-standteil dieser Intuition war Korollar 4.20, das aussagt, dass jede L¨ osung

z ∗ des MPEC (1.1) unter der MPEC-GCQ ∀(β 1 , β 2 ) ∈ P(β) KKT-Punkt des N LP ^(β 1 ,β 2 ) (z ∗ ) sein muss. D.h. n¨ amlich, dass wir f¨ ur eine L¨ osung z ∗ ∀(β 1 , β 2 ) ∈ P(β) einen Lagrangemultiplikator x(β 1 , β 2 ) ∈ Λ A (z ∗ ) bekommen. Wir haben also schon 2 |β| (nicht notwendigerweise verschiedene) A-station¨ are

Lagrangemultiplikatoren x(β 1 , β 2 ) mit entsprechenden Vorzeichenrestriktionen (ν ^1β 2 (β 1 , β 2 ) ≥ 0 und ν ^2β 1 (β 1 , β 2 ) ≥ 0). Die Beweisidee ist nun, dass man unter Ausnutzung der Konvexit¨ at von Λ W (z ∗ ) eine Konvexkombination der x(β 1 , β 2 ) ∈ Λ A (z ∗ ) ⊆ Λ W (z ∗ ) ﬁndet, welche M-station¨ ar ist. Wegen der Konvexit¨ at von Λ W (z ∗ ) sind all jene Konvexkombinationen bereits schwach

station¨ ar (4.22) und wir m¨ ussen nur noch die Bedingungen (4.25) an die biaktiven Komponenten ¨ uberpr¨ ufen. Leider ist es mir nicht gelungen, zu zeigen, dass es eine solche Konvexkombination gibt. Ich m¨ ochte dennoch kurz aufzeigen, wie diese Beweisidee funktioniert h¨ atte. Projizieren wir das Problem auf den 2|β|-dimensionalen Raum, so lautet unsere Behauptung in MPEC-unabh¨ angiger Form:

Lemma 4.36 Sei p ∈ N und β ⊆ {1, . . . , p} eine Indexmenge. F¨ ur jede Partition (β 1 , β 2 ) ∈ P(β) sei genau ein Punkt x(β 1 , β 2 ) ∈ R ^2|β| gegeben mit: ( )

x(β 1 , β 2 ) :=

ν 1i (β 1 , β 2 ) ≥ 0 ∀i ∈ β 2 ,

ν 2i (β 1 , β 2 ) ≥ 0 ∀i ∈ β 1 ,

Weiterhin deﬁnieren wir uns folgende Mengen:

 

C := conv

M :=

^(δ 1 ,δ 2 )∈P(β)

Behauptung: C ∩ M ̸ = ∅

75

Die Punkte x(β 1 , β 2 ) entsprechen dabei den Lagrangemultiplikatoren der

KKT-Punkte der N LP ^(β 1 ,β 2 ) (z ∗ ) und C ist die konvexe H¨ ulle dieser Punk-

te. Die Menge M ist unabh¨ angig von den Punkten x(β 1 , β 2 ) und beschreibt die Menge, welche im 2|β|-dimensionalen Raum die Bedingung (4.25) erf¨ ullt. Wie bereits erw¨ ahnt, war es mir leider nicht m¨ oglich Lemma 4.36 zu zeigen. W¨ urde die Behauptung des obigen Lemmas stimmen, so k¨ onnten wir die M-Stationarit¨ at unter der MPEC-GCQ wie folgt zeigen:

Beweis der M-stationarit¨ at unter der Annahme von Lemma 4.36:

Als Voraussetzung haben wir eine L¨ osung z ∗ des MPEC (1.1) mit der MPEC-GCQ. Wir wollen zeigen, dass z ∗ M-station¨ ar ist. Nach Korollar 4.20 wissen wir, dass z ∗ ∀(β 1 , β 2 ) ∈ P(β) KKT-Punkt des N LP ^(β 1 ,β 2 ) (z ∗ ) ist. Damit haben wir ∀(β 1 , β 2 ) ∈ P(β) A-station¨ are Lagran-gemultiplikatoren x(β 1 , β 2 ) ∈ Λ A (z ∗ ) der N LP ^(β 1 ,β 2 ) (z ∗ ).

Unter der Annahme, dass Lemma 4.36 gilt, existiert eine Konvexkombination

x ∗ dieser x(β 1 , β 2 ), welche (4.25) erf¨ ullt. Schließlich bekommen wir wegen der Konvexit¨ at von Λ W (z ∗ ) (Lemma 4.35) auch die Bedingungen der schwachen Stationarit¨ at (4.22) f¨ ur x ∗ . Insgesamt folgt also x ∗ ∈ Λ M (z ∗ ) und z ∗ ist somit M-station¨ ar. ()

Die Aussage des Lemmas w¨ urde den Beweis von Flegel in [2] also erheblich vereinfachen. Es folgt nun eine Diskussion ¨ uber die Aussage des Lemmas.

Wir starten mit der Betrachtung des Spezialfalls |β| = 1:

Beispiel 4.37 |β| = 1:

F¨ ur |β| = 1 gibt es lediglich die beiden Partitionen ({1}, ∅) und (∅, {1}). Nach Voraussetzung haben wir folgende zwei Punkte im R ² gegeben:

Wir k¨ onnen nun folgende vier F¨ alle f¨ ur die Lage der Punkte x und y unterscheiden:

Abb. 19: M¨ ogliche Lage der A-station¨ aren Lagrangemultiplikatoren

76

Dabei entspricht der grau markierte Bereich der Menge M und die Verbindungslinie zwischen den Punkten x und y entspricht der Menge C. Oﬀensichtlich gilt also f¨ ur |β| = 1: C ∩ M ̸ = ∅

Motiviert durch diesen Spezialfall betrachten wir f¨ ur |β| > 1 die Projektion unseres Problems auf die Komponenten (ν 1j , ν 2j ) f¨ ur ein j ∈ β. Dazu f¨ uhren wir f¨ ur j ∈ β folgende Notation ein:

Analog zum Spezialfall folgt:

C j ∩ M j ̸ = ∅ ∀j ∈ β (4.30)

Leider folgt daraus im Allgemeinen nicht C ∩M ̸ = ∅. Das ist im Wesentlichen

der Grund daf¨ ur, warum das Problem nicht trivial ist. Man bemerke dabei jedoch, dass (4.30) sehr schwach ist, denn das k¨ onnten wir bereits folgern, wenn wir f¨ ur jede Komponente einen Punkt h¨ atten, welcher nur an dieser Komponente nicht negativ ist. Wir sollten also ausnutzen, dass wir f¨ ur jede m¨ ogliche Kombination von |β| Komponenten (aus 2|β| Komponenten) einen Punkt haben, welcher an all diesen |β| Komponenten nicht negativ ist.

Das Problem scheint also von kombinatorischer Natur zu sein. Ich habe versucht dieser Kombinatorik den Wind aus den Segeln zu nehmen, indem ich den Satz von Helly aus der Konvexgeometrie angewendet habe. Nach dem Satz von Helly gilt, dass eine endliche Familie von konvexen Mengen im R k

nichtleeren Durchschnitt hat, falls je k + 1 dieser Mengen nichtleeren Durchschnitt haben. Zwar ist die Menge M nicht konvex, sie besteht aber aus konvexen Zusammenhangskomponenten und ich habe versucht je nach Lage der Punkte x(β 1 , β 2 ) die richtigen Zusammenhangskomponenten zu w¨ ahlen. Leider ist auch dieser Versuch gescheitert.

Abschließend m¨ ochte ich noch bemerken, dass wir auf dem Weg zur Voraussetzung des Lemmas nichts verloren haben, denn es gilt:

z ∗ B-station¨ ar + MPEC-GCQ

⇔ z ∗ MPEC-linearisiert B-station¨ ar

⇔ z ∗ ist KKT-Punkt des N LP ^(β 1 ,β 2 ) (z ∗ ) ∀(β 1 , β 2 ) ∈ P(β) ⇔ ∀(β 1 , β 2 ) ∈ P(β) ∃x(β 1 , β 2 ) mit ν ^1β 2 (β 1 , β 2 ) ≥ 0 und ν ^2β 1 (β 1 , β 2 ) ≥ 0

Wir formulieren nun noch einmal die Kernaussage dieses Teilabschnittes als Theorem und verweisen f¨ ur den Beweis auf die Ausf¨ uhrungen [2] und [6]:

77

Theorem 4.38 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die MPEC-GCQ am Punkt z ∗ , dann ist z ∗ M-station¨ ar.

Beweis: siehe [2] oder [6].

Damit folgt nach Lemma 4.35 sofort, dass auch die C-Stationarit¨ at eine notwendige Optimalit¨ atsbedingung unter der MPEC-GCQ ist.

Korollar 4.39 Sei z ∗ eine L¨ osung des MPEC (1.1) und gilt die MPEC-GCQ am Punkt z ∗ , dann ist z ∗ C-station¨ ar.

Beweis: Folgt direkt aus Theorem 4.38 und Lemma 4.35.

Insgesamt haben wir also mit Theorem 4.38 unter der schw¨ achsten bisher bekannten CQ, die zweit st¨ arkste Optimalit¨ atsbedingung aus der MPEC-Buchstabensuppe als eine notwendige Optimalit¨ atsbedingung f¨ ur das MPEC (1.1) erhalten. Wie wir jedoch sehen werden, ist selbst die M-Stationarit¨ at zu schwach, um zul¨ assige Abstiegsrichtungen auszuschließen. Dies motiviert eine erneute Betrachtung der MPEC-linearisierten B-Stationarit¨ at.

78

4.4.3 MPEC-linearisierte B-Stationarit¨ at

Wir beginnen diesen Teilabschnitt mit einem Beispiel aus [11], welches aufzeigt, dass es an M-station¨ aren Punkten zul¨ assige Abstiegsrichtungen geben kann:

Beispiel 4.40

f (z) := (z 1 − 1) ² + z 2 2 + z ³ min

z

s.t. G(z) = z 1 ≥ 0, H(z) = z 2 ≥ 0,

G(z)H(z) = z 1 z 2 = 0.

Das Minimum dieses Problems liegt bei z ∗ = (1, 0). Der Ursprung ¯ z = (0, 0)

ist M-station¨ ar, denn f¨ ur ν 1 = −2 und ν 2 = 0 gilt:

∇ z L N LP (¯ z) (¯ z, ν 1 , ν 2 ) = ∇ z f (¯ z) − ∇ z G(¯ z) − ∇ z H(¯ z) (4.31)

( −2 ) ( ) ( )

Damit erf¨ ullen (¯ z, ν 1 , ν 2 ) (4.22) und (4.25). ¯ z ist also M-station¨ ar und somit

auch A- und C-station¨ ar. Vergleichen wir die Werte des Zielfunktionals an

den Punkten z ∗ und ¯ z, so sehen wir, dass es vom Punkt ¯ z die zul¨ assige

Richtung (1, 0) gibt, bzgl. welcher der Wert des Zielfunktional echt vermindert wird: f (¯ z) = 1 > 0 = f (z ∗ )

Man bemerke im obigen Beispiel, dass ¯ z zwar ein KKT-Punkt des N LP ({1},∅) (¯ z)

ist, nicht jedoch KKT-Punkt des N LP (∅,{1}) (¯ z), weil ν 1 = −2 und ν 2 = 0 das einzige Paar ist, welches (4.31) erf¨ ullt. z ∗ hingegen hat keine biaktive Kom-

ponente und ist somit sogar stark station¨ ar.

Wenden wir unsere Aufmerksamkeit nun auf die MPEC-linearisierte B-Stationarit¨ at und pr¨ ufen, ob sie zul¨ assige Abstiegsrichtungen erlaubt:

79

D.h. im Gegensatz zur M-Stationarit¨ at, erlaubt die MPEC-linearisierte B-Stationarit¨ at keine zul¨ assigen Abstiegsrichtungen. Wir haben also auf unserem Weg von der MPEC-linearisierten B-Stationarit¨ at zur M-Stationarit¨ at Stationarit¨ atsanforderungen verloren, was dazu gef¨ uhrt hat, dass es an Mstation¨ aren Punkten zul¨ assige Abstiegsrichtungen geben kann. Die MPEC-linearisierte B-Stationarit¨ at basiert auf dem MPEC-linearisierten

M P EC (z ∗ ), welcher an biaktiven Punkten nicht konvex ist. Tangentialkegel F lin

Somit k¨ onnen wir das Farkas Lemma nicht direkt anwenden, um eine Optimalit¨ atsbedingung vom KKT-Typ zu bekommen. In Theorem 4.19 haben wir dieses Problem umgangen, indem wir F lin

N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) ausgedr¨ uckt haben und dann Farkas der konvexen Kegel T lin

Lemma auf jeden dieser Kegel angewendet haben. Damit ist es also hinrei-chend f¨ ur die MPEC-linearisierte B-Stationarit¨ at, wenn z ∗ KKT-Punkt aller N LP ^(β 1 ,β 2 ) (z ∗ ) ist. Diese Bedingung w¨ urde die ¨ Uberpr¨ ufung von 2 |β| KKT-

Systemen erfordern und kann somit sehr aufw¨ andig zu testen sein. Eine weitere M¨ oglichkeit die MPEC-linearisierte B-Stationarit¨ at zu ¨ uberpr¨ ufen zeigt folgende Proposition auf:

Proposition 4.41 Sei z ∗ ein zul¨ assiger Punkt des MPEC (1.1). Dann ist z ∗ genau dann MPEC-linearisiert B-station¨ ar, wenn d = 0 die L¨ osung des

folgenden LPEC (linear program with equilibrium constraints) ist:

Beweis:

In der MPEC-Gemeinde ist diese Formulierung relativ weit verbreitet und wird meist als B-station¨ ar verkauft, obwohl diese Formulierung nur unter der MPEC-GCQ der eigentlichen B-Stationarit¨ at entspricht. Man bemerke, dass die ¨ Uberpr¨ ufung der MPEC-linearisierten B-Stationarit¨ at mittels (4.32)

wiederum der L¨ osung von 2 |β| linearen Programmen bedarf. Somit bleibt die

MPEC-linearisierte B-Stationarit¨ at in allen Varianten, je nach der M¨ achtig- keit von β, sehr aufw¨ andig zu ¨ uberpr¨ ufen. Sie hat jedoch den wesentlichen Vorteil, dass sie auf dem Tangentialkegel F

lin Gegensatz zur starken Stationarit¨ at auch ohne die GCQ eine Optimalit¨ atsbedingung erster Ordnung liefert, welche keine Abstiegsrichtungen zul¨ asst.

80

4.5 Hinreichende Optimalit¨ atsbedingungen 2. Ordnung

In diesem Abschnitt werden wir uns mit hinreichenden Optimalit¨ atsbedingungen zweiter Ordnung besch¨ aftigen, welche meist f¨ ur Konvergenzbeweise vorausgesetzt werden, um superlineare Konvergenz zu erreichen. Leider werden diese sogenannten second order suﬃcient conditions [SOSC] in der MPEC-Gemeinde auf unterschiedlichste Weise deﬁniert, bezeichnet und verwendet. Meine Deﬁnitionen stammen im Wesentlichen von Ralph und Wright in [15], wobei ich jedoch die strong second order suﬃcient conditions [SSOSC] weggelassen habe und eine schw¨ achere SOSC, speziell f¨ ur MPEC-linearisierte B-station¨ are Punkte, neu hinzugef¨ ugt habe.

Wie bei allen Optimalit¨ atsbedingungen zweiter Ordnung, werden auch hier bereits Optimalit¨ atsbedingungen erster Ordnung vorausgesetzt. Da die SOSC ja hinreichend sein sollen, ist es naheliegend, dass sich die W-, A-, C- und M-Stationarit¨ aten nicht eignen, da diese Begriﬀe wie besprochen zul¨ assige Abstiegsrichtungen erlauben. Wir werden also nur bei der starken Stationarit¨ at und bei der MPEC-linearisierten B-Stationarit¨ at ansetzen k¨ onnen. Wir beginnen mit der sogenannten RNLP-SOSC, welche auf der starken Stationarit¨ at aufbaut und wie die starke Stationarit¨ at eng mit dem RNLP zusammenh¨ angt. So deﬁnieren wir zun¨ achst den Kegel der kritischen Richtungen f¨ ur das RNLP:

Deﬁnition 4.42 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1) mit zugeh¨ origem Lagrangemultiplikator (λ ∗ , ν ∗

gel des RNLP am Punkt (z ∗ , λ ∗ , ν ∗ 1 , ν ∗

C RN LP (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) :=  

        

        

Dieser Kegel entspricht dem kritischen Kegel ¯ S in [15]. In [8] und [14] wird,

abgesehen von der Normierung, ebenfalls dieser Kegel verwendet. In [8] enth¨ alt

der Kegel zwar die zus¨ atzliche Bedingung ∇ z f (z ∗ ) T d = 0, aber da wir einen

81

stark station¨ aren Punkt z ∗ vorausgesetzt haben, gilt wegen (4.13) ohnehin:

( )

∇ z f (z ∗ ) =

^(4.33) ⇒ ∇ z f (z ∗ ) T d = 0, ∀d ∈ C RN LP (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗

2 )

Damit ist auch folgende hinreichende Optimalit¨ atsbedingung zweiter Ordnung analog zu der MPEC-SOSC in [8], der MPCC-SOSC in [14] bzw. der RNLP-SOSC in [15].

Deﬁnition 4.43 Ein stark station¨ arer Punkt (z ∗ , λ ∗ , ν ∗ 1 , ν ∗

erf¨ ullt die RNLP-SOSC, falls ∀d ∈ C RN LP (z ∗ ) (z ∗ , λ ∗ , ν ∗

d T ( ∇ 2 )

z L RN LP (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗

2 ) d > 0 (4.34)

Analog zu Anitescu in [1] k¨ onnten wir an dieser Stelle noch eine second order necessary condition [SONC] einf¨ uhren, indem wir in obiger Deﬁnition das > durch ein ≥ ersetzen. Wir werden uns aber im Rahmen dieser Ar-beit auf hinreichende Optimalit¨ atsbindingungen zweiter Ordnung (SOSC) beschr¨ anken. Man bemerke, dass die starke Stationarit¨ at ¨ aquivalent ist zu

den KKT-Bedingungen f¨ ur das RN LP (z ∗ ). Damit erhalten wir nach [12]

bereits folgende Aussage:

Theorem 4.44 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1), der die RNLP-SOSC erf¨ ullt, dann ist z ∗ eine strikt lokale L¨ osung des RN LP (z ∗ ).

Beweis: siehe [12].

Nach Korollar 2.15 ist das lokale Minimum z ∗ des RN LP (z ∗ ) auch ein lo-

kales Minimum des MPEC. D.h. wir haben mit der RNLP-SOSC an einem stark station¨ aren Punkt bereits eine hinreichende Optimalit¨ atsbedingung f¨ ur unser MPEC gefunden. Diese Bedingung eignet sich f¨ ur MPECs unter der GCQ. F¨ ur MPECs, welche die GCQ nicht erf¨ ullen, ist sie jedoch in der Regel zu stark.

Fahren wir nun fort mit der etwas schw¨ acheren MPEC-SOSC, welche sich von der RNLP-SOSC nur in der Wahl des kritischen Kegels unterscheidet.

82

Deﬁnition 4.45 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1) mit zugeh¨ origem Lagrangemultiplikator (λ ∗ , ν ∗ 1 , ν ∗

gel des MPEC am Punkt (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) deﬁniert durch:

C M P EC (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) :=  

                     

Deﬁnition 4.46 Ein stark station¨ arer Punkt (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) des MPEC (1.1)

erf¨ ullt die MPEC-SOSC, falls ∀d ∈ C M P EC (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) gilt: d T ( ∇ 2 )

z L RN LP (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗

2 ) d > 0 (4.36)

Wie bereits erw¨ ahnt werden wir hier im Gegensatz zu Ralph und Wright in [15] nicht auf die strong second order suﬃcient conditions eingehen. Stattdessen deﬁnieren wir eine neue noch schw¨ achere SOSC, welche meines Wissens bisher noch von niemanden zuvor deﬁniert wurde. Eigentlich m¨ usste diese neue Bedingung aus meiner Sicht den Namen MPEC-SOSC tragen, aber weil dieser Name nun schon vergeben ist, werden wir sie schwache MPEC-SOSC [MPEC-WSOSC] nennen. Die Idee dabei ist, dass wir eine hinreichende Optimalit¨ atsbedingung 2. Ordnung aufstellen, welche keinen stark station¨ aren Punkt mehr voraussetzt, sondern nur noch einen MPEC-linearisiert B-station¨ aren Punkt. Das hat den Vorteil, dass sich die MPEC-WSOSC dann auch f¨ ur MPECs eignet, welche die GCQ nicht erf¨ ullen, sondern nur die MPEC-GCQ. Dazu deﬁnieren wir uns zun¨ achst die kritischen Kegel der

N LP ^(β 1 ,β 2 ) (z ∗ ).

83

Deﬁnition 4.47 Sei z ∗ ein MPEC-linearisiert B-station¨ arer Punkt des MPEC (1.1). Dann deﬁnieren wir ∀(β 1 , β 2 ) ∈ P(β) den kritischen Kegel des N LP ^(β 1 ,β 2 ) (z ∗ ) mit zugeh¨ origen Lagrangemultiplikator (λ ∗ , ν ∗ Punkt (z ∗ , λ ∗ , ν ∗ 1 , ν

∗ C N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) :=

 

        

        

Man bemerke, dass z ∗ wegen der MPEC-linearisierten B-Stationarit¨ at KKT-Punkt von allen N LP ^(β 1 ,β 2 ) (z ∗ ) ist. Die Lagrangemultiplikatoren (λ ∗ , ν ∗ 1 , ν ∗ 2 )

k¨ onnen f¨ ur jedes N LP ^(β 1 ,β 2 ) (z ∗ ) verschieden sein und ich habe jene lediglich der ¨ Ubersichtlichkeit halber nicht in Abh¨ angigkeit von (β 1 , β 2 ) notiert.

Gibt es einen Lagrangemultiplikator (λ ∗ , ν ∗ 1 , ν ∗ 2 ), f¨ ur welchen am Punkt z ∗ die

KKT-Bedingungen (4.11) f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ) erf¨ ullt sind, so ist z ∗ stark

station¨ ar. Das wollen wir jedoch f¨ ur unsere MPEC-WSOSC nicht voraussetzen.

Deﬁnition 4.48 Sei z ∗ ein MPEC-linearisiert B-station¨ arer Punkt des MPEC (1.1). D.h. z ∗ ist KKT-Punkt f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ) mit zugeh¨ origen Lagrangemultiplikator (λ ∗ , ν ∗ 1 , ν ∗ 2 ). Dann erf¨ ullt z ∗ die MPEC-WSOSC,

falls ∀(β 1 , β 2 ) ∈ P(β) mit zu (β 1 , β 2 ) geh¨ origen Lagrangemultiplikator (λ ∗ , ν ∗ 1 , ν ∗ 2 )

und ∀d ∈ C N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) gilt: d T ( ∇ 2 )

z L RN LP (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗

2 ) d > 0 (4.38)

Erinnern wir uns daran, dass L RN LP (z ∗ ) = L N LP (β 1 ,β 2 ) (z ∗ ) , so ist leicht einzusehen, dass die Deﬁnition 4.48 den SOSCs f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ) ent-

spricht. Auf den ersten Blick mag diese Deﬁnition ¨ ahnlich zu der Deﬁnition der MPEC-SSOSC in [15] aussehen. Diese unterscheiden sich jedoch wesentlich, da Ralph und Wright in [15] einen stark station¨ aren Punkt voraussetzen und dar¨ uber hinaus ganz andere kritische Kegel benutzen, f¨ ur welche im All-

gemeinen noch nicht einmal C N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) 2 ) ⊆ T lin

gilt. Vielmehr ist die MPEC-WSOSC verwandt zu der MPEC-SOSC, was folgendes Lemma zeigt.

84

Lemma 4.49 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1), dann erf¨ ullt z ∗ genau dann die MPEC-SOSC, wenn z ∗ die MPEC-WSOSC erf¨ ullt.

Beweis: Sei z ∗ ein stark station¨ arer Punkt mit zugeh¨ origen Lagrangemulti-plikator (λ ∗ , ν ∗ 1 , ν ∗

gemeinsamen Lagrangemultiplikator (λ ∗ , ν ∗

Die MPEC-WSOSC gilt also genau dann, wenn gilt:

∪

D.h. aber gerade, dass die MPEC-SOSC am Punkt z ∗ gilt.

Dieses Lemma zeigt auf, dass es ausreichend w¨ are, lediglich die MPEC-WSOSC zu deﬁnieren, welche unter der st¨ arkeren Voraussetzung eines stark station¨ aren Punkts dann ohnehin der herk¨ ommlichen MPEC-SOSC entspricht. Da jedoch die Deﬁnition der MPEC-SOSC leichter zu verstehen ist, habe ich hier beide separat deﬁniert.

Jetzt bleibt noch zu zeigen, dass die MPEC-WSOSC auch wirklich eine hinreichende Optimalit¨ atsbedingung ist. Viele Schlussfolgerungen dieses Beweises ﬁnden sich auch in anderen SOSC-Beweisen wie beispielsweise in [12]. F¨ ur die MPEC-WSOSC m¨ ussen wir jedoch an einigen Punkten noch etwas zus¨ atzliche Arbeit leisten.

Theorem 4.50 Sei z ∗ ein MPEC-linearisiert B-station¨ arer Punkt des MPEC (1.1), der die MPEC-WSOSC erf¨ ullt, dann ist z ∗ eine strikt lokale L¨ osung

des MPEC (1.1).

Beweis: Zur Vereinfachung der Notation innerhalb dieses Beweises setzen wir: L = L RN LP (z ∗ ) .

Wegen der MPEC-WSOSC und weil C N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) kompakt

ist, existiert ∀(β 1 , β 2 ) ∈ P(β) ein σ(β 1 , β 2 ) > 0, derart dass f¨ ur alle d ∈ C N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) gilt: d T ( ∇ 2 )

z L(z ∗ , λ ∗ , ν ∗ 1 , ν ∗ d ≥ σ(β 1 , β 2 ) > 0 2 ) (4.39)

Sei nun σ := min σ(β 1 , β 2 ). Wir wollen nun zeigen, dass f¨ ur jede Folge

^(β 1 ,β 2 )∈P(β)

von zul¨ assigen Punkten {z k } ∈ Z M P EC mit z k → z ∗ gilt:

σ f (z k ) ≥ f (z ∗ ) + ||z k − z ∗ || 2

f¨ ur alle hinreichend große k (4.40)

² 4

85

Sei also {z k } ∈ Z M P EC mit z k → z ∗ beliebig. Dann existiert eine Teilfolge von {z k } mit:

Nach Lemma 2.16 gilt: T M P EC (z ∗ ) =

D.h. aber gerade, dass ein (β 1 , β 2 ) ∈ P(β) existiert mit:

d ∈ T N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ ) ⊆ T lin N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ )

(4.42)

Sei nun jenes (β 1 , β 2 ) ∈ P(β) ﬁxiert, dann ist nach Voraussetzung z ∗ insbesondere KKT-Punkt dieses N LP ^(β 1 ,β 2 ) (z ∗ ) mit zugeh¨ origem Lagrangemulti-plikator (λ ∗ , ν ∗ 1 , ν ∗ 2 ). Deshalb gilt:

∇ z L(z ∗ , λ ∗ , ν ∗ 1 , ν ∗

2 ) = 0, ( ) ∑ ∑

L(z ∗ , λ ∗ , ν ∗ 1 , ν ∗

Damit gilt f¨ ur die Lagrangefunktion am Punkt (z k , λ ∗ , ν ∗ 1 , ν ∗ 2 ) nach Taylor:

L(z k , λ ∗ , ν ∗ 1 , ν ∗

= f (z ∗ ) +

Wir behalten diese Aussage im Hinterkopf und unterscheiden zwei F¨ alle:

∈ C N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 1.Fall:

d / Wegen (4.41) gilt ||d|| 2 = 1 und mit (4.42) gilt d ∈ T lin

gibt es nur folgende drei M¨ oglichkeiten f¨ ur d /

oder ∃ j ∈ {i ∈ β 2 | ν ∗

oder ∃ j ∈ {i ∈ β 1 | ν ∗

86

O.E. gelte (4.44). (Die anderen beiden F¨ alle folgen analog.) Wir ﬁxieren ein

⁺ (z ∗ ) mit λ ∗ j ∇ z c j (z ∗ ) T d > 0 und erhalten mit Taylor am Punkt z k : j ∈ A I

λ ∗ j c j (z k ) = λ ∗

Damit gilt f¨ ur die Lagrangefunktion am Punkt z k :

L(z k , λ ∗ , ν ∗ 1 , ν ∗

Nach Umstellen und Einsetzen der Taylorabsch¨ atzung (4.43) erhalten wir:

f (z k ) ≥ f (z ∗ ) +

≥ f (z ∗ ) + ||z k − z ∗ || 2 λ ∗

Wegen (4.44) ist dies bereits hinreichend f¨ ur unsere Behauptung (4.40).

2.Fall: d ∈ C N LP (β 1 ,β 2 ) (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) Wegen (4.39) gilt: d T ( ∇ 2 )

z L(z ∗ , λ ∗ , ν ∗ 1 , ν ∗ d ≥ σ > 0 2 )

Wegen L(z k , λ ∗ , ν ∗ 1 , ν ∗ 2 ) ≤ f (z k ) folgt mit der Taylorabsch¨ atzung (4.43):

2 d T ( ∇ 2 )

f (z k ) ≥f (z ∗ ) +

≥f (z ∗ ) +

Insgesamt folgt also, dass z ∗ eine strikte lokale L¨ osung ist.

Da die MPEC-WSOSC die schw¨ achste SOSC ist, folgt mit obigem Theorem 4.50 auch, dass die MPEC-SOSC und die RNLP-SOSC hinreichende Optimalit¨ atsbedingungen zweiter Ordnung f¨ ur das MPEC (1.1) sind.

Korollar 4.51 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1), der die MPEC-SOSC oder die RNLP-SOSC erf¨ ullt, dann ist z ∗ eine strikte lokale

L¨ osung des MPEC (1.1).

87

Beweis: Wegen C M P EC (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) ⊆ C RN LP (z ∗ ) (z ∗ , λ ∗ , ν ∗ 1 , ν ∗ 2 ) gilt:

RNLP-SOSC ⇒ MPEC-SOSC

Da z ∗ stark station¨ ar ist, ist z ∗ insbesondere MPEC-linearisiert B-station¨ ar.

Somit ist wegen Lemma 4.49 zusammen mit Theorem 4.50 die MPEC-SOSC bereits hinreichend f¨ ur eine strikte lokale L¨ osung.

Wir haben in diesem Teilabschnitt mit der MPEC-WSOSC eine neue hinreichende Optimalit¨ atsbedingung entwickelt, welche schw¨ acher ist als alle bisher bekannten SOSCs. Zwar ist die MPEC-WSOSC, ¨ ahnlich wie die MPEClinearisierte B-Stationarit¨ at, sehr aufw¨ andig zu testen, aber ich denke, sie hat einen großen theoretischen Wert. vor allem im Hinblick auf Leyﬀers und Munsons neueste Ausf¨ uhrungen in [11], wo ein komplett neuer Algorithmus speziell f¨ ur MPECs entwickelt wird, welcher dabei weder die MPEC-LICQ noch einen stark station¨ aren Punkt voraussetzt. Bevor wir aber zu numerischen L¨ osungsans¨ atzen kommen, werden wir noch einmal alle Optimalit¨ atsbedingungen dieses Kapitels ¨ ubersichtlich zusammenfassen.

88

4.6 Zusammenfassung Optimalit¨ atsbedingungen

In diesem Kapitel sind eine Reihe von Optimalit¨ atsbedingungen erster und zweiter Ordnung vorgestellt worden, welche nun noch einmal ¨ ubersichtlich

zusammengefasst werden. Wir starten dabei mit den notwendigen Optimalit¨ atsbedingungen erster Ordnung:

⇐ ⇔

⇐ z ∗ S-station¨ ar z ∗ M-station¨ ar

⇐

⇒

z ∗ A-station¨ ar z ∗ C-station¨ ar

⇐ ⇐

Abb. 21: ¨ Ubersicht: Optimalit¨ atsbedingungen erster Ordnung

Unter der Voraussetzung eines lokalen Minimums des MPEC (1.1) sind wir an einem geometrischen Standpunkt gestartet und haben zun¨ achst gezeigt, dass die B-Stationarit¨ at eine notwendige Optimalit¨ atsbedingung erster Ordnung darstellt. Von diesem Punkt aus haben wir, abh¨ angig von der erf¨ ullten

CQ am Punkt z ∗ , zwei Richtungen, in die wir gehen k¨ onnen.

Unter der GCQ sind die Begriﬀe B-station¨ ar und linearisiert B-station¨ ar ¨ aquivalent. Linearisiert B-station¨ ar ist nach Farkas Lemma ¨ aquivalent zu

den KKT-Bedingungen f¨ ur das RN LP (z ∗ ) und somit zur starken Stationa-

rit¨ at. Wir haben damit also gezeigt, dass die S-Stationarit¨ at f¨ ur das MPEC (1.1) unter der relativ schwachen GCQ eine notwendige Bedingung erster Ordnung ist. Dar¨ uber hinaus haben wir bewiesen, dass der Lagrangemulti-

plikator im KKT-System (4.13) des RN LP (z ∗ ) unter der MPEC-SMFCQ

89

und somit auch unter der MPEC-LICQ eindeutig ist.

Unter der MPEC-GCQ ist die B-Stationarit¨ at ¨ aquivalent zur MPEC-linearisierten B-Stationarit¨ at. Man bemerke, dass die MPEC-GCQ die schw¨ achste aller bisher bekannten CQs f¨ ur MPECs ist. Da die MPEC-linearisierte

M P EC (z ∗ ) B-Stationarit¨ at auf dem im Allgemeinen nicht konvexen Kegel F lin

beruht, kann man nicht ohne weiteres das Farkas Lemma anwenden, um eine Optimalit¨ atsbedingung vom KKT-Typ zu erhalten. Wir haben daher eine Reihe von alternativen Stationarit¨ atsbegriﬀen vom KKT-Typ vorgestellt, welche notwendigerweise an einem MPEC-linearisiert B-station¨ aren Punkt erf¨ ullt sein m¨ ussen. Wesentlicher Bestandteil dieser Theorie ist dabei ein Resultat aus [2], welches aussagt, dass jeder MPEC-linearisiert B-station¨ are Punkt insbesondere M-station¨ ar ist. Ich habe versucht, diese Aussage auf eine einfache und anschauliche Weise zu beweisen, was mir jedoch leider nicht gelungen ist. Außerdem haben wir in diesem Zusammenhang aufgezeigt, dass die Stationarit¨ atsbegriﬀe W-, A-, C- und M-station¨ ar triviale Abstiegsrichtungen zulassen, was ihren Nutzen in der Praxis fraglich macht. Im Gegensatz dazu gibt es an einem MPEC-linearisiert B-station¨ aren Punkt keine zul¨ assi-gen Abstiegsrichtungen, da dieser KKT-Punkt f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ) ist.

Des Weiteren haben wir in diesem Kapitel folgende hinreichende Optimalit¨ atsbedingungen zweiter Ordnung erarbeitet:

Abb. 22: ¨ Ubersicht: Optimalit¨ atsbedingungen zweiter Ordnung

Die am weitesten verbreitete SOSC ist dabei die RNLP-SOSC, auch wenn diese in verschiedenen Ausf¨ uhrungen anders bezeichnet wird. Die RNLP-SOSC entspricht insbesondere einer hinreichenden Optimalit¨ atsbedingung f¨ ur das

RN LP (z ∗ ) und ist somit unter Umst¨ anden zu stark. Die MPEC-SOSC ar-

beitet zwar mit einem kritischen Kegel, welcher zu dem MPEC-linearisierten Tangentialkegel passt, durch die Voraussetzung eines gemeinsamen Multipli-

kators aller N LP ^(β 1 ,β 2 ) (z ∗ ) setzt die MPEC-SOSC jedoch implizit einen stark

90

station¨ aren Punkt voraus und ist daher ebenfalls zu stark, falls das MPEC

an dem Punkt z ∗ die GCQ nicht erf¨ ullt. Daher haben wir mit der MPEC-WSOSC eine neue schw¨ achere hinreichende Optimalit¨ atsbedingung zweiter Ordnung eingef¨ uhrt, welche keinen stark station¨ aren Punkt ben¨ otigt, sondern nur einen MPEC-linearisiert B-station¨ aren Punkt. Die MPEC-WSOSC

fordert dabei die SOSC f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ). Man bemerke dabei, dass die

MPEC-WSOSC meines Wissens nach die erste SOSC f¨ ur MPECs ist, welche keinen stark station¨ aren Punkt voraussetzt und sich somit auch f¨ ur MPECs eignet, welche die GCQ nicht erf¨ ullen, sondern nur die MPEC-GCQ.

91

5 Numerische L¨ osungsans¨ atze

Nachdem wir uns bisher auf die theoretische Analyse von MPECs konzentriert haben, werden wir jetzt noch einen kurzen Blick auf eine Auswahl numerischer L¨ osungsans¨ atze f¨ ur MPECs werfen und dabei auf m¨ ogliche Anwendungen unserer bisherigen Ergebnisse eingehen. Die Verletzung der Standard-CQs f¨ uhrt dazu, dass die direkte Anwendung von herk¨ ommlichen NLP-L¨ osern auf MPECs meist scheitert.

Die erste Idee, dieses Problem zu umgehen, war die Regularisierung der Komplementarit¨ atsbedingung durch einen positiven Parameter t, wodurch ein von t abh¨ angiges Standard NLP N LP (t) entsteht (siehe z.B. [15]). Um die L¨ osung des MPEC (1.1) zu erhalten, l¨ ost man dann eine Folge von N LP (t) mit t → 0. Ralph und Wright pr¨ asentieren in [15] außerdem noch ein Penalisie-

rungsschema f¨ ur das MPEC (1.1). Numerische Tests dieser zwei Strategien waren bisher jedoch entmutigend.

Nachdem Standard NLP-L¨ oser, insbesondere SQP-Methoden, in der Lage waren, einige MPECs als NLPs zu l¨ osen, hat man viel Arbeit und Zeit investiert, um zu analysieren, welche MPECs von NLP-L¨ osern gel¨ ost werden k¨ onnen ([7]). Weiterhin hat man mit Hilfe von Regularisierungs- und Penalisierungsans¨ atzen jene Standard NLP-L¨ oser modiﬁziert, um die Anzahl der l¨ osbaren MPECs zu erh¨ ohen und die Performance f¨ ur die Anwendung auf MPECs zu verbessern ([14], [10]). Die Anwendung dieser Standard NLP-L¨ oser, wie SNOPT oder IPOPT, hat den Vorteil, dass diese L¨ oser bereits hochentwickelt sind. Der Nachteil an diesen Standard NLP-L¨ osern ist jedoch, dass sie mit dem linearisierten Tangentialkegel des MPEC arbeiten und sich daher nur f¨ ur MPECs eignen, welche die GCQ, MPEC-LICQ oder MPEC-SMFCQ erf¨ ullen.

Am Ende dieses Kapitels werden wir dann noch einen neuen Algorithmus vorstellen, welcher von Leyﬀer und Munson speziell f¨ ur MPECs entwickelt worden ist ([11]). Dieser SLPEC-EQP Algorithmus l¨ ost in jedem Schritt ein linear program with equilibrium constraints [LPEC] innerhalb einer trust region und anschließend ein equality constrained quadratic program [EQP]. Der wesentliche Vorteil dieser Methode ist dabei, dass sie mit dem MPEClinearisierten Tangentialkegel arbeitet und sich daher besser f¨ ur MPECs eignet, insbesondere falls das MPEC die GCQ nicht erf¨ ullt.

92

5.1 Regularisierung und Penalisierung

In diesem Teilabschnitt werden eine Reihe von Regularisierungsschemata und ein Penalisierungsschema vorgestellt. Wie bereits erw¨ ahnt wird beim Regularisierungsansatz die Komplementarit¨ atsbedingung des MPEC (1.1) durch einen positiven Parameter t regularisiert, wodurch ein von t abh¨ angiges Standard-NLP N LP (t) entsteht. Ralph und Wright pr¨ asentieren in [15] folgende unterschiedlichen Arten, diese Regularisierung vorzunehmen.



RegComp(t) :

RegEq(t) :

Man bemerke, dass die Probleme (5.1) - (5.3) f¨ ur t = 0 alle ¨ aquivalent zu unserem MPEC (1.1) sind, w¨ ahrend sie sich f¨ ur t > 0 voneinander unterscheiden. Um eine L¨ osung des MPEC (1.1) zu erhalten, l¨ ost man eine Folge dieser N LP (t) mit t → 0. Ralph und Wright konzentrieren sich in [15] auf

das Schema Reg(t) und beweisen folgende Konvergenzaussagen.

Theorem 5.1 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1) und sei die MFCQ f¨ ur das RN LP (z ∗ ) erf¨ ullt. Weiter sei die MPEC-SOSC am Punkt z ∗ erf¨ ullt. Dann existieren positive Konstanten r 0 , t 0 und M 0 , so dass f¨ ur alle t ∈ (0, t 0 ] und f¨ ur alle L¨ osungen z(t) des lokalisierten Problems Reg(t) mit der zus¨ atzlichen Bedingung ||z − z ∗ || 2 ≤ r 0 gilt:

||z(t) − z ∗ || 2 ≤ M 0 t 1

(5.4) 2

Beweis: siehe [15].

93

Dabei ist anzumerken, dass die MPEC-MFCQ in [15] wie in obigem Theo-rem die MFCQ des RN LP (z ∗ ) fordert und somit schw¨ acher ist als unsere

MPEC-MFCQ. Interessant w¨ are an diesem Punkt, ob man in Theorem 5.1 die Voraussetzungen der starken Stationarit¨ at und der MPEC-SOSC durch die MPEC-linearisierte B-Stationarit¨ at und die MPEC-WSOSC ersetzen k¨ onnte. Leider ist dies nicht m¨ oglich, da ein MPEC-linearisiert B-station¨ arer Punkt im Allgemeinen kein KKT-Punkt f¨ ur das Reg(0) ist. Unter st¨ arkeren Voraussetzungen k¨ onnen wir lineare Konvergenz erreichen, was folgendes Theorem zeigt:

Theorem 5.2 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1) mit der

MPEC-SMFCQ und der RNLP-SOSC. Dann existieren positive Konstanten r 0 , t 0 und M 0 , so dass f¨ ur alle t ∈ (0, t 0 ] und f¨ ur alle L¨ osungen z(t) des lokalisierten Problems Reg(t) mit der zus¨ atzlichen Bedingung ||z − z ∗ || 2 ≤ r 0

gilt:

||z(t) − z ∗ || 2 ≤ M 0 t

(5.5)

Beweis: siehe [15].

Ralph und Wright setzen in [15] f¨ ur dieses Theorem 5.2 die MPEC-LICQ voraus, um im Beweis die Eindeutigkeit der Lagrangemultiplikatoren zu erhalten. Nach Proposition 4.30 sind aber bereits die MPEC-SMFCQ hinreichend f¨ ur die Eindeutigkeit der Lagrangemultiplikatoren, weshalb ich die Voraussetzung entsprechend abgeschw¨ acht habe.

Nach [15] gelten die Theoreme 5.1 und 5.2 auch f¨ ur RegComp(t), w¨ ahrend f¨ ur RegEq(t) lediglich noch schw¨ achere Konvergenzaussagen m¨ oglich waren. Der Vorteil von Reg(t) im Gegensatz zu dem Schema RegComp(t) ist, dass die L¨ osungen z(t) unter der RNLP-SSOSC in einer Umgebung von t = 0 eindeutig sind (siehe [15]).

Insgesamt sind die Konvergenzaussagen f¨ ur die Regularisierungsans¨ atze relativ schwach und es bleibt die Frage, wie exakt man die Reg(t) f¨ ur jedes t l¨ osen muss. Ralph und Wright sprechen in ihrem Ausblick in [15] die m¨ ogliche Anwendung einer SQP-Methode auf das Schema Reg(t) an, welche f¨ ur jedes t lediglich einen SQP-Schritt vorsieht. Konvergenzaussagen einer derartigen Methode sind mir jedoch nicht bekannt. Nichts desto trotz spielen die Regularisierungsschemata eine wichtige Rolle bei der Anpassung von Standard NLP-L¨ osern f¨ ur MPECs. So wenden z.B. Raghunathan und Biegler in [14] das Regularisierungsschema Reg(t) in einem modiﬁzierten Innere Punkte Al-gorithmus an.

94

Außerdem pr¨ asentieren Ralph und Wright in [15] folgendes Penalisierungsschema, bei dem die Verletzung der Komplementarit¨ atsbedingung mit einem positiven Faktor ρ multipliziert als Strafterm zu dem Zielfunktional addiert wird. 

Um zu zeigen, dass Penalisierungsmethoden f¨ ur MPECs theoretisch funktionieren, zeigen Ralph und Wright in [15] folgende Theoreme.

Theorem 5.3 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1), dann gilt

f¨ ur hinreichend große ρ:

i) z ∗ ist KKT-Punkt des P F (ρ).

ii) Erf¨ ullt z ∗ die MPEC-MFCQ (MPEC-SMFCQ, MPEC-LICQ), dann erf¨ ullt z ∗ auch die MFCQ (SMFCQ, LICQ) f¨ ur das P F (ρ).

iii) Gilt die MPEC-SOSC am Punkt z ∗ , dann gilt die SOSC am Punkt z ∗

f¨ ur das P F (ρ).

Beweis: siehe [15].

Dabei habe ich die Aussage ¨ uber die MPEC-SMFCQ in ii) selbst hinzugef¨ ugt, da sie analog zu den entsprechenden Aussagen f¨ ur die MPEC-MFCQ und MPEC-LICQ zu zeigen ist. W¨ ahrend obiges Theorem zeigt, dass f¨ ur bestimmte CQs und Optimalit¨ atsbedingungen des MPEC auch entsprechende CQs und Optimalit¨ atsbedingungen f¨ ur das Schema P F (ρ) erf¨ ullt sind, zeigt folgendes Theorem unter der exakten Komplementarit¨ at entgegengesetzte Aussagen.

Theorem 5.4 Sei z ∗ ein KKT-Punkt des P F (ρ) mit G(z ∗ ) T H(z ∗ ) = 0,

dann gilt:

i) z ∗ ist stark station¨ arer Punkt des MPEC (1.1).

ii) Erf¨ ullt z ∗ die LICQ f¨ ur das P F (ρ), dann erf¨ ullt z ∗ die MPEC-LICQ.

iii) Gilt die SOSC am Punkt z ∗ f¨ ur das P F (ρ), dann gilt die MPEC-SOSC am Punkt z ∗ und z ∗ ist ein striktes lokales Minimum des MPEC (1.1).

95

Beweis: siehe [15].

Bei erneuter Betrachtung des Schemas P F (ρ) wird klar, dass ein lokales Mini-mum des P F (ρ) f¨ ur ein hinreichend großes ρ die Bedingung G(z ∗ ) T H(z ∗ ) = 0 erf¨ ullen muss. Wir fordern nun an einem stark station¨ aren Punkt z ∗ des

MPEC (1.1) mit der MPEC-LICQ die sogenannte partial strict complemen-

tarity [PSC] an den eindeutigen Lagrangemultiplikator (λ ∗ , ν ∗ 1 , ν ∗ 2 ):

P SC : ν ∗ 1i > 0 ∨ ν ∗ 2i > 0 ∀i ∈ β(z ∗ )

(5.7)

Mit dieser zus¨ atzlichen Bedingung, erhalten wir folgende Aussage:

Proposition 5.5 Sei z ∗ ein stark station¨ arer Punkt des MPEC (1.1) mit der MPEC-LICQ und der PSC. Dann existiert eine Umgebung U von z ∗ und eine positive Konstante ρ ∗ > 0, so dass f¨ ur alle ρ ≥ ρ ∗ jeder KKT-Punkt des

P F (ρ) in U auch ein stark station¨ arer Punkt des MPEC (1.1) ist.

Beweis: siehe [15].

Damit ist gezeigt, dass Penalisierungsmethoden bei MPECs theoretisch funktionieren. Da man nicht weiß, wie groß man ρ w¨ ahlen muss, l¨ ost man eine Folge von P F (ρ) mit ρ → ∞. In der Praxis wurde dieser Penalisierungsansatz

z.B. schon von Leyﬀer, L` opez-Calva und Nocedal in [10] verfolgt, welche eine modiﬁzierte Innere Punkte Methode f¨ ur das Penalisierungsschema P F (ρ) entwickelt haben.

96

5.2 Anwendung von Standard NLP-L¨ osern

Die am weitesten verbreitete Strategie, MPECs zu l¨ osen, ist die Anwendung von Standard NLP-L¨ osern, welche zum Teil f¨ ur die Anwendung auf MPECs modiﬁziert worden sind. Diese Vorgehensweise hat den Vorteil, dass diese NLP-L¨ oser bereits seit einiger Zeit existieren und somit hochentwickelt sind. Wir konzentrieren uns in diesem Abschnitt auf lokale Konvergenzaussagen f¨ ur innere Punkte Methoden und sequential quadratic programming [SQP] Methoden. Dabei setzen wir folgende Konvergenzannahmen voraus:

Konvergenzannahmen:

[A1] f, c, G und H sind zweimal stetig diﬀerenzierbar.

[A2] z ∗ ist ein stark station¨ arer Punkt des MPEC (1.1) mit zugeh¨ origem Lagrangemultiplikator (λ ∗ , ν ∗ 1 , ν ∗ 2 ) und z ∗ erf¨ ullt die MPEC-LICQ und

die RNLP-SOSC.

[A3] Der Lagrangemultiplikator (λ ∗ , ν ∗ 1 , ν ∗ 2 ) erf¨ ullt folgende strikte Komplementarit¨ atsbedingungen:

λ ∗ ∀i ∈ A I (z ∗ ),

Die Konvergenzannahmen [A1] und [A2] ﬁnden sich in allen mir bekannten Arbeiten, welche die lokale Konvergenz von auf MPECs angewendeten NLP-L¨ osern untersuchen (z.B. [1], [8], [10], [14]). Dabei bezeichnen einige, wie schon erw¨ ahnt, unsere RNLP-SOSC als MPEC-SOSC oder MPCC-SOSC. Lediglich in [A3] unterscheiden sich die unterschiedlichen Ausf¨ uhrungen. Man bemerke dabei, dass unsere Version von [A3] genau dem entspricht, was die Deﬁnition der strikten Komplementarit¨ at f¨ ur die Lagrangemultiplikato-ren aus [12] f¨ ur das RN LP (z ∗ ) fordern w¨ urde. Somit sind mit [A1], [A2] und

[A3] alle Konvergenzannahmen erf¨ ullt, welche nach [12] sowohl die SQP, als auch die Innere Punkte Methoden f¨ ur eine superlineare lokale Konvergenz

ben¨ otigen, wenn man sie auf das RN LP (z ∗ ) anwendet. Korollar 2.15 sagt aus, dass jedes lokale Minimum des RN LP (z ∗ ) auch ein lokales Minimum

des MPEC (1.1) ist, und nach Proposition 2.18 ist der linearisierte Tangen-

tialkegel des MPEC am Punkt z ∗ identisch mit dem des RN LP (z ∗ ). Zwar hat man damit noch keine L¨ osungsstrategie, da z ∗ und dessen aktive Mengen a priori nicht bekannt sind und somit auch das RN LP (z ∗ ) nicht a priori

vorliegt, aber in meinen Augen liefert diese Tatsache eine Anschauung daf¨ ur, wie nicht modiﬁzierte NLP-L¨ oser bei der Anwendung auf MPECs unter der

97

GCQ funktionieren k¨ onnen. Wie wir sp¨ ater sehen werden, wird in [8] unter bestimmten Voraussetzung gezeigt, dass die SQP-Methode, angewendet auf das RNLP ¨ aquivalent ist, zu der SQP-Methode, angewendet auf das MPEC. In obigen Konvergenzannahmen k¨ onnten wir in den meisten F¨ allen und evtl. auch in allen F¨ allen die MPEC-LICQ mit der MPEC-SMFCQ abschw¨ achen. Da jedoch die MPEC-SMFCQ nicht so weit verbreitet ist und alle Ausf¨ uhrungen, auf die wir uns in diesem Teilabschnitt beziehen werden, mit der MPEC-LICQ arbeiten, setzen wir auch die MPEC-LICQ voraus. Meines Wissens gibt es jedoch bisher keine Konvergenzaussagen f¨ ur NLP-L¨ oser unter der MPEC-MFCQ. Das liegt daran, dass die MPEC-MFCQ nicht hinreichend sind f¨ ur die GCQ und somit der linearisierte Tangentialkegel des MPEC die tats¨ achliche Beschaﬀenheit des zul¨ assigen Bereichs nicht mehr korrekt beschreibt. Das f¨ uhrt dazu, dass ein B-station¨ arer Punkt nicht mehr notwendigerweise ein linearisiert B-station¨ arer Punkt bzw. stark station¨ arer Punkt ist. Alle Konvergenzaussagen herk¨ ommlicher NLP-L¨ oser beschr¨ anken sich jedoch auf die Konvergenz zu linearisiert B-station¨ aren Punkten. Deshalb scheint die direkte Anwendung herk¨ ommlicher NLP-L¨ oser auf MPECs nur unter der Voraussetzung eines stark station¨ aren Punktes Sinn zu machen. Da die starke Stationarit¨ at nur unter der GCQ, MPEC-SMFCQ oder MPEC-LICQ eine notwendige Optimalit¨ atsbedingung darstellt, nicht aber unter der MPEC-MFCQ (siehe Beispiel 3.19), ist die MPEC-MFCQ eine zu schwache Anforderung an ein zu l¨ osendes MPEC, wenn man einen herk¨ ommlichen NLP-L¨ oser auf das MPEC direkt anwenden will.

5.2.1 Innere Punkte Methoden f¨ ur MPECs

Direkte Anwendungen von Innere Punkte Methoden auf MPECs sind ineﬃzient. Der Grund daf¨ ur liegt in der Tatsache, dass der zul¨ assige Bereich des MPEC aufgrund der Komplementarit¨ atsbedingung kein striktes Inneres hat. Dadurch kommen Innere Punkte Methoden in einen Konﬂikt, denn einerseits versuchen sie die Iterierten vom Rand fern zu halten und andererseits sind nur die Punkte am Rand zul¨ assig f¨ ur das MPEC. Es ist jedoch gelungen diese Problematik zu umgehen, indem man die Innere Punkte Methode auf ein Regularisierungsschema oder Penalisierungsschema des MPEC anwendet.

Raghunathan und Biegler pr¨ asentieren in [14] eine Barrieremethode f¨ ur das Regularisierungsschema Reg(t), und untersuchen die lokale Konvergenz die-

98

ses Verfahrens angewendet auf ein MPEC der Form:

wobei z 1 , z 2 ∈ R p und z 0 ∈ R m−2p (m ≥ 2p) und f : R m → R, c : R m → R |E|∪|I| zweimal stetig diﬀerenzierbar sind. Es ist allgemein bekannt, dass

diese Formulierung (5.10) ¨ aquivalent zu unserem MPEC (1.1) ist, wenn man Schlupfvariablen einf¨ uhrt (siehe z.B. [8]). In [14] wird wiederum eine leicht abge¨ anderte Formulierung des MPEC verwendet, welche die standard inequalities c I durch die Bedingung z 0 ≥ 0 ersetzt. In meinen Augen ist eine

derartige Formulierung jedoch ein Spezialfall eines MPECs, da sie Vorzeichenbedingungen an alle Komponenten enth¨ alt. Im weiteren Verlauf werden wir mit (5.10) arbeiten, da alle Ergebnisse aus [14] auf diese Formulierung ubertragbar sind. ¨

Raghunathan und Biegler verwenden in [14] eine Barrieremethode, um das MPEC (5.10) zu l¨ osen. Das Hauptproblem dabei ist, dass der zul¨ assige Bereich eines MPEC wegen der Komplementarit¨ atsbedingung kein Inneres besitzt, Barrieremethoden dies aber ben¨ otigen. Deshalb wird das Problem wie folgt regularisiert: 

     

Reg(t) :

     

Anhand dieses regularisierten Problems wird folgendes Barriereproblem mit Barriereparameter µ > 0 und Regularisierungsparameter t > 0 aufgestellt:

|I| Dabei sind s I ∈ R >0 und s cc ∈ R p >0 zus¨ atzliche Schlupfvariablen, welche es

erm¨ oglichen die Ungleichheitsbedingung c I (z 0 , z 1 , z 2 ) ≥ 0 und z 1i z 2i ≤ t in

99

(5.11) zu Gleichheitsbedingungen umzuwandeln. Die Barrierefunktion φ µ in (5.12) ist deﬁniert durch: ∑

φ µ (z 0 , z 1 , z 2 , s I , s cc ) := f (z 0 , z 1 , z 2 ) − µ

L¨ ost man eine Folge von Barriereproblemen (5.12) f¨ ur (µ, t) → 0, so erh¨ alt

man eine L¨ osung des MPEC [14]. Die Barriereprobleme k¨ onnen mit einer Innere Punkte Methode gel¨ ost werden. Da es jedoch zu aufw¨ andig w¨ are jedes Barriereproblem exakt zu l¨ osen, wird dieser Ansatz in einen Innere Punkte Algorithmus integriert. Dabei werden nach jedem primal-dual Schritt des Algorithmus der Barriereparameter µ k und der Regularisierungsparameter t k in Abh¨ angigkeit zu einem Maß f¨ ur die Verletzung der KKT-Bedingungen ge¨ andert. Raghunathan und Biegler zeigen in [14], dass dieses Verfahren unter den Konvergenzannahmen [A1], [A2] und [A3] lokal quadratisch konvergiert. Außerdem haben sie diesen Ansatz in den Innere Punkte Algorithmus IPO-PT integriert und numerische Tests durchgef¨ uhrt. Dieser neue modiﬁzierte Algorithmus wird mit IPOPT-C bezeichnet und wurde an einer Reihe von Modellproblemen der MacMPEC test suite von Leyﬀer erfolgreich getestet. Einige Probleme konnten nicht gel¨ ost werden aufgrund eines Fehlers in der Restaurationsphase des IPOPT-C. Alle anderen Modellprobleme der MacMPEC test suite, welche nicht gel¨ ost werden konnten, haben obige Konvergenzannahmen nicht erf¨ ullt. Außerdem konnte der IPOPT-C auch einige Probleme l¨ osen, welche obige Konvergenzannahmen nicht erf¨ ullt haben.

Leyﬀer, L` opez-Calva und Nocedal verfolgen in [10] einen ¨ ahnlichen Ansatz. Sie wenden jedoch die Barrieremethode nicht auf das Regularisierungsschema Reg(t) an, sondern auf ein entsprechendes Penalisierungsschema des MPEC (5.10): 

Anhand dieses Penalisierungsschemas wird folgendes Barriereproblem mit Barriereparameter µ > 0 und Penalisierungsparameter ρ > 0 aufgestellt:

|I| Dabei ist s I ∈ R >0 wieder eine zus¨ atzliche Schlupfvariablen und die Barrierefunktion ψ µ in (5.14) ist deﬁniert durch:

ψ µ (z 0 , z 1 , z 2 , s I , ρ) := f (z 0 , z 1 , z 2 ) + ρ z T 1 z ² ∑ ∑ ∑

L¨ ost man eine Folge von Barriereproblemen (5.14) f¨ ur µ → 0 und ρ → ∞, so

bekommt man unter bestimmten Voraussetzungen eine L¨ osung des MPEC (5.10). Leyﬀer, L` opez-Calva und Nocedal stellen in [10] zun¨ achst einen klassischen Ansatz vor, bei welchem in jedem Schritt f¨ ur (µ k , ρ k ) ein Barriereproblem mit Hilfe eines Innere Punkte Algorithmus approximativ gel¨ ost wird. Dabei gehen sie sowohl auf globale, als auch auf lokale Konvergenzaussagen f¨ ur dieses Verfahren ein. Insebsondere zeigen sie lokal superlineare Konvergenz unter den Annahmen [A1], [A2], [A3] und der zus¨ atzlichen Voraussetzung: λ i ̸ = 0, ∀i ∈ E.

Anschließend wird noch ein weiterer Algorithmus vorgestellt, welcher den Penalisierungsparameter nach jedem primal-dual Schritt updatet, wenn die Verletzung der Komplementarit¨ at (z k T 1 z k 2 > 0) eine gewisse Toleranz ¨ uberschreitet. Beide Algorithmen wurden mit dem Innere Punkte Algorithmus IPM-D implementiert und an einer Reihe von Modellproblemen der MacM-PEC test suite (quelle 17 in 9) erfolgreich getestet. Diese numerischen Tests ergaben, dass der Algorithmus mit der dynamischen Updatestrategie des Penalisierungsparameters die beste Performance lieferte, w¨ ahrend sich die ﬁxe Wahl eines sehr großen Penalisierungsparameters als unvorteilhaft erwiesen hat.

Insgesamt zeigen die numerischen Ergebnisse aus [14] und [10], dass Innere Punkte Methoden ein eﬃzientes und robustes Werkzeug zur L¨ osung eines MPEC sein k¨ onnen, sofern man sie nicht direkt auf das MPEC anwendet, sondern auf ein Regularisierungs- oder Penalisierungsschema. Nach [14] ist die Performance des IPOPT-C f¨ ur die MacMPEC test suite wesentlich schlechter als die Performance des SQP-Algorithmus ﬁltermpec. Raghunathan und Biegler berichten jedoch, dass Innere Punkte Methoden f¨ ur

101

sehr große MPECs mit vielen inequality constraints und einer hohen Anzahl an Komplementarit¨ atsbedingungen schneller sind als entsprechende SQP-Methoden.

5.2.2 SQP-Methoden f¨ ur MPECs

Im Gegensatz zu den Innere Punkte Methoden, lieferte die direkte Anwendung nicht modiﬁzierter SQP-Methoden auf MPECs von Anfang an ermutigende Ergebnisse (siehe z.B. [7]). Zwar ist bei MPECs durch die Verletzung der MFCQ die Stabilit¨ at von Standard NLP-L¨ osern nicht mehr garantiert, aber in der Praxis ist es SQP-Methoden gelungen, eine Vielzahl an MPECs zu l¨ osen. Fletcher, Leyﬀer, Ralph und Scholtes geben in [8] erstmals auch eine theoretische Erkl¨ arung, warum SQP-Methoden, angewendet auf MPECs, unter bestimmten Vorraussetzungen lokal quadratisch konvergieren, obwohl die MFCQ nicht erf¨ ullt ist. Dabei untersuchen sie die direkte Anwendung einer reinen SQP-Methode auf ein MPEC der Form:

wobei z 1 , z 2 ∈ R p und z 0 ∈ R m−2p (m ≥ 2p) und f : R m → R, c : R m → R |E|∪|I| zweimal stetig diﬀerenzierbar sind. Wie bereits bei (5.10) erw¨ ahnt, ist

die Formulierung mit Hilfe von Schlupfvariablen ¨ aquivalent zu dem MPEC (1.1). Die Formulierung mit Schlupfvariablen verhindert nach [8], dass SQP-Methoden gegen nicht station¨ are Punkte konvergieren. Die Formulierung 1 z 2 ≤ 0 als inneres Produkt reduziert im Gegensatz zu der komponentenwei- z T

sen Formulierung in (5.10) die Anzahl der Ungleichheitsbedingung und eignet 1 z 2 ≤ 0 nicht durch sich daher besser f¨ ur SQP-Methoden. Ebenso sollte man z T z T 1 z 2 = 0 ersetzen, da dies die Geschwindigkeit von SQP-Methoden verringern w¨ urde.

SQP-Methoden l¨ osen, wie der Name schon sagt, eine Folge von quadratischen Subproblemen. In [8] wird eine SQP-Methode betrachtet, welche eine Folge

102

von quadratischen Problemen QP M P EC (z ^(k) ) der folgenden Form l¨ ost: 

        

QP M P EC (z ^(k) )

        

wobei d = (d 0 , d 1 , d 2 ) ∈ R m mit d 1 , d 2 ∈ R p und ˆ

∇ zz L M P EC (z ^(k) , ˆ λ ^(k) , ˆ

entspricht also der quadratischen Approximation des MPEC-Zielfunktionals am Punkt z ^(k) und der zul¨ assige Bereich des QP M P EC (z ^(k) ) entspricht dem linearisierten zul¨ assigen Bereich des MPEC (5.15). Das quadratische Subproblem QP M P EC (z ^(k) ) kann mit einer aktive Mengen Methode gel¨ ost werden, um die n¨ achste Iteration (z ^(k) +d ^(k) , ˆ ^(k+1) , ˆ ^(k+1) , ˆ λ ^(k+1) , ˆ ξ ^(k+1) ) zu erhalten. ν 1 ν 2

Herk¨ ommliche Konvergenzaussagen f¨ ur SQP-Methoden ben¨ otigen Standard-CQs, wie die LICQ, welche bei MPECs an keinem zul¨ assigen Punkt erf¨ ullt sind. Fletcher, Leyﬀer, Ralph und Scholtes ist es in [8] jedoch gelungen zu zeigen, dass obiges Verfahren unter folgenden Voraussetzungen lokal quadratisch konvergiert:

[A1], [A2] und [A3].

[A4] λ ∗ i ̸ = 0 ∀i ∈ E(z ∗ ).

[A5] Der QP-L¨ oser w¨ ahlt immer eine linear unabh¨ angige Basis.

[A6] Die QP-Approximationen QP M P EC (z ^(k) ) sind alle konsistent.

Der Beweis ist in zwei Teile untergliedert. Der erste Teil behandelt den Fall (k) T (k) 2 = 0, d.h. die Iterierte z ^(k) erf¨ ullt die Komplementarit¨ atsbedingung z z

1

exakt. Dieser Fall ben¨ otigt lediglich die Konvergenzannahmen [A1], [A2], [A3] und [A5]. [A5] ist nach [8] in der Praxis keine starke Einschr¨ ankung, da die meisten modernen SQP-L¨ oser auf aktive Mengen QP-L¨ osern basieren, welche das garantieren k¨ onnen. Die Beweisidee ist dabei zu zeigen, dass die SQP-Methode, angewendet auf das MPEC (5.15), ¨ aquivalent ist zu der SQP-Methode, angewendet auf das RNLP. Wendet man die SQP-Methode auf das RNLP an, so hat man statt QP M P EC (z ^(k) ) in jedem Schritt folgendes

103

quadratisches Problem zu l¨ osen: 

QP RN LP (z ^(k) ) (z ^(k) )

wobei H ^(k) = ∇ zz L RN LP (z ^(k) , λ ^(k) , ν ^{1 (k)} , ν ^{2 (k)} ). Des weiteren wird davon ausgegangen, dass z ^(k) bereits hinreichend nah an dem stark station¨ aren Punkt z ∗ ist, so dass gilt:

α(z ^(k) ) ⊇ α(z ∗ ), β(z ^(k) ) ⊆ β(z ∗ ), γ(z ^(k) ) ⊇ γ(z ∗ ).

(5.17)

Wegen [A3] gilt die strikte Komplementarit¨ atsbedingung der Lagrangemul-

tiplikatoren f¨ ur das RN LP (z ∗ ), wegen β(z ^(k) ) ⊆ β(z ∗ ) gilt Selbiges auch f¨ ur das RN LP (z ^(k) ) und nach [12] ﬁndet die SQP-Methode deshalb in einem Schritt die optimalen aktiven Mengen. Daraus folgt:

α(z ^(k+1) ) = α(z ∗ ), β(z ^(k+1) ) = β(z ∗ ), γ(z ^(k+1) ) = γ(z ∗ ).

(5.18)

Damit sind das RN LP (z ^(k+1) ) und das RN LP (z ∗ ) identisch und wegen

[A1], [A2] und [A3] konvergiert die SQP-Methode nach [12] lokal quadra-

tisch gegen den KKT-Punkt z ∗ des RN LP (z ∗ ). D.h. also insgesamt, dass die SQP-Methode, angewendet auf das RN LP (z ^(k) ), gegen den stark station¨ aren Punkt z ∗ des MPEC (5.15) konvergiert, falls z ^(k) (5.17) erf¨ ullt. Man bemerke hierbei, dass dies nur unter der Annahme eines stark station¨ aren Punktes z ∗

m¨ oglich ist, da sonst ein lokales Minimum des MPEC nicht notwendigerweise

ein KKT-Punkt des RN LP (z ∗ ) ist.

Da ein Standard SQP-Algorithmus jedoch nicht QP RN LP (z ^(k) ) (z ^(k) ), sondern QP M P EC (z ^(k) ) l¨ ost, zeigen Fletcher, Leyﬀer, Ralph und Scholtes in [8] noch, dass die beiden quadratischen Programme f¨ ur alle z ^(k) unter [A1], [A2], [A3] und (5.17) die gleiche L¨ osung haben. Damit ist gezeigt, dass f¨ ur den Fall (k) T ^(k) z z = 0 die SQP-Methode, angewendet auf das MPEC (5.15), ¨ aquiva-

1 2

lent ist zu der SQP-Methode, angewendet auf das RNLP, wenn man hinrei-chend nah an dem Punkt z ∗ ist. (l) T (l) 2 > 0 ∀l > k. Der zweite Teil des Beweises in [8] behandelt den Fall z z

1

F¨ ur diesen Fall m¨ ussen die zus¨ atzlichen Annahmen [A4] und [A6] getroﬀen werden. Dabei wird die SQP-Methode auf ein neues reduziertes Hilfsproblem

104

angewendet, das in Abh¨ angigkeit von der vom QP-L¨ oser gew¨ ahlten Basis aufgestellt wird. Die detaillierte Betrachtung dieses Falles w¨ urde jedoch den Rahmen dieser Kurzvorstellung sprengen.

Insgesamt wird in [8] also unter [A1]-[A6] lokal quadratische Konvergenz f¨ ur SQP-Methoden, angewendet auf das MPEC (5.15), gezeigt. Die Annahme [A6], dass alle QP M P EC (z ^(k) ) konsistent sein m¨ ussen (Z QP M P EC (z ^(k) ) = ∅), ist

(k) T ^(k) jedoch f¨ ur den Fall z z > 0 sehr stark und kann in der Praxis selbst

1 2

beliebig nah am Punkt z ∗ nicht gew¨ ahrleistet werden. In [8] wird deshalb eine Restaurationsphase vorgeschlagen, welche f¨ ur den Fall Z QP M P EC (z ^(k) ) = ∅

einen Punkt z ^(k+1) ﬁndet, welcher die Komplementarit¨ atsbedingung exakt erf¨ ullt und somit Z QP M P EC (z ^(k+1) ) ̸ = ∅ gilt.

Anitescu betrachtet in [1] die Anwendung des SQP-Algorithmus SNOPT auf das MPEC (5.15). Dabei umgeht SNOPT das Konsistenzproblem, indem es f¨ ur den Fall Z QP M P EC (z ^(k) ) = ∅ in den sogenannten elastic mode wechselt.

Beim elastic mode wird dann eine penalisierte und regularisierte Version des QP M P EC (z ^(k) ) f¨ ur alle Folgeiterationen gel¨ ost. Anitescu zeigt, dass der SNOPT (mit elastic mode), angewendet auf das MPEC (5.15), unter den Annahmen [A1]-[A5] lokal quadratisch konvergiert. Er hat damit also das Konsistenzproblem gel¨ ost. Man beachte dabei, dass Anitecu zwar explizit keinen stark station¨ aren Punkt voraussetzt, da er aber in seinen Konver-

genzannahmen eine L¨ osung z ∗ mit MPEC-LICQ voraussetzt, impliziert dies, dass z ∗ stark station¨ ar ist. Zudem hat Anitescu den SNOPT erfolgreich an

einer Reihe von Modellproblemen der MacMPEC test suite getestet, wobei der SNOPT in zwei F¨ allen in den elastic mode gewechselt ist.

Insgesamt scheinen sich SQP-Methoden auf den ersten Blick besser f¨ ur MPECs zu eignen als Innere Punkte Methoden, weil man sie im Gegensatz zu Innere Punkte Methoden unter der MPEC-LICQ direkt auf MPECs anwenden (k) T ^(k) kann. Das Konsistenzproblem f¨ ur unzul¨ assige Punkte (z z 2 > 0) k¨ onnen

1

SQP-Methoden bisher aber auch nur mit einem Regularisierungsansatz (elastic mode) oder einer Restaurationsphase umgehen. Numerische Tests in [14] haben gezeigt, dass die Performance des SQP-Algorithmus ﬁltermpec f¨ ur die MacMPEC test suite wesentlich besser ist als die Performance des Innere Punkte Algorithmus IPOPT-C. Es bleibt jedoch die Frage, ob sich f¨ ur sehr große Probleme nicht wieder die Innere Punkte Methoden besser eignen.

Trotz dieser Erfolge bei der Anwendung von Standard NLP-L¨ osern auf MPECs ist es fraglich, ob sich diese NLP-L¨ oser in der Praxis f¨ ur MPECs eignen, denn sie wurden urspr¨ unglich f¨ ur NLPs konzepiert, welche st¨ arkere CQs

105

erf¨ ullen. So berichten Leyﬀer und Munson in [11], dass Standard NLP-L¨ oser bei ung¨ unstig gew¨ ahlten Startpunkt gegen A-, C- oder M-station¨ are Punkte konvergieren k¨ onnen, von welchen aus es triviale Abstiegsrichtungen gibt. Leyﬀer und Munson beschreiben dieses Verhalten damit, dass NLP-L¨ oser nicht um biaktive Ecken sehen k¨ onnen. Durch die degenerierte Natur von MPECs k¨ onnte es beispielsweise sein, dass der zul¨ assige Bereich des MPEC aus zwei Segmenten besteht, welche nur einen biaktiven Punkt gemeinsam haben. Konvergiert nun der NLP-L¨ oser innerhalb eines Segments gegen den biaktiven Punkt und kommt dort in endlicher Zeit nie an, dann sieht er nicht, ob es von dem biaktiven Punkt aus eine zul¨ assige Abstiegsrichtung in das andere Segment gibt. Dieses Verhalten der NLP-L¨ oser tritt insbesondere

bei A-station¨ aren Punkten z ∗ auf, welche KKT-Punkte eines N LP ^(β 1 ,β 2 ) (z ∗ )

sind. Solange die Iterierten nicht biaktiv werden, fordern die KKT-Systeme nur Vorzeichenrestriktionen an je einen der beiden Lagrangemultiplikatoren ν 1i , ν 2i ∀i ∈ β und der Algorithmus denkt, dass er gegen einen KKT-

Punkt des MPEC konvergiert, obwohl er nur gegen einen KKT-Punkt des

N LP ^(β 1 ,β 2 ) (z ∗ ) konvergiert. In meinen Augen kann dieses Problem weder

durch einen Regularisierungs- noch durch einen Penalisierungsansatz gel¨ ost werden, da in beiden F¨ allen mit sinkenden Regularisierungsparameter t bzw. steigenden Penalisierungsparameter ρ die Iterierten wieder an den biaktiven A-station¨ aren Punkt gezogen werden. Diese Problematik motiviert den letzten Abschnitt, in welchem wir auf eine neue, eigens f¨ ur MPEC entwickelte Methode eingehen werden.

106

5.3 Ein SLPEC-EQP Algorithmus

Leyﬀer und Munson arbeiten in [11] an einem neuen, speziell f¨ ur MPECs entwickelten Algorithmus mit dem Name SLPEC-EQP. Dieser l¨ ost in jedem Schritt ein linear program with equilibrium constraints [LPEC] innerhalb einer trust region und anschließend ein equality constrained quadratic program [EQP]. Dabei liefert die L¨ osung des LPEC eine Abstiegsrichtung erster Ordnung und eine Sch¨ atzung der optimalen aktiven Menge. Anhand dieser aktiven Menge wird anschließend eine EQP aufgestellt und gel¨ ost, um superlineare Konvergenz zu erhalten. Diese Methode hat zwei wesentliche Vorteile im Gegensatz zur Anwendung von Standard NLP-L¨ osern. Zum Einen wird der am Ende des letzten Abschnittes beschriebene Fall verhindert, in dem die NLP-L¨ oser gegen biaktive A- oder C-station¨ aren Punkte mit trivialen Abstiegsrichtungen konvergieren. Der SLPEC-EQP Algorithmus w¨ urde in diesem Fall durch das L¨ osen des LPEC in einem Schritt zu dem biaktiven Punkt gelangen. Daher kann dieser Algorithmus um biaktive Ecken sehen und in anderen Segmenten nach weiteren Abstiegsrichtungen suchen. Zum Anderen ist diese Methode daf¨ ur konzepiert, gegen MPEC-linearisiert B-station¨ are Punkte zu konvergieren, weshalb sie auch unter der schwachen MPEC-MFCQ funktioniert.

Wenden wir diesen Ansatz auf das MPEC (5.15) an, so haben wir in jedem Schritt folgendes LP EC(z ^(k) , σ ^(k) ) innerhalb des trust region Radius σ ^(k) > 0 zu l¨ osen: 

LP EC(z ^(k) , σ ^(k) )

Sei d ^(k) die L¨ osung des LP EC(z ^(k) , σ ^(k) ). F¨ ur d ^(k) ̸ = 0 identiﬁzieren wir die

neuen aktiven Mengen:

A I (z ^(k) + d ^(k) ) := {i ∈ I | c i (z ^(k) ) + ∇ z c i (z ^(k) ) T d = 0},

α (k+ ¹ ^{(k) (k) (k) (k) )} := α(z ^(k) + d ^(k) ) := {i ∈ {1, . . . , p} | z 1i = 0 ∧ z 1i + d 2i + d 2i > 0}, ² β (k+ ¹ ^{(k) (k) (k) (k) )} := β(z ^(k) + d ^(k) ) := {i ∈ {1, . . . , p} | z 1i = 0 ∧ z 1i + d 2i + d 2i = 0}, ² γ (k+ ¹ ^{(k) (k) (k) (k) )} := γ(z ^(k) + d ^(k) ) := {i ∈ {1, . . . , p} | z 1i > 0 ∧ z 1i + d 2i + d 2i = 0}. 2

107

Anhand dieser aktiven Mengen wird dann folgendes EQP gel¨ ost: 

     

EQP (z ^(k) + d ^(k) )

     

H ^(k) = ∇ zz L M P EC (z ^(k) , ˆ ^(k) , ˆ wobei ˆ ^(k) , ˆ λ ^(k) , ˆ ξ ^(k) ). Man bemerke dabei, dass ν 1 ν 2

das EQP durch L¨ osen eines linearen Gleichungssystems gel¨ ost werden kann.

Die vollst¨ andige L¨ osung des LPEC k¨ onnte hingegen die L¨ osung von 2 |β| li-

nearen Programmen erfordern und stellt deshalb einen potentiellen Schwachpunkt dieses Verfahrens dar. Diese Sichtweise ist jedoch sehr pessimistisch, wie wir sp¨ ater sehen werden. Man beachte, dass der Tangentialkegel des LP EC(z ^(k) , σ ^(k) ) am Punkt z ^(k) genau dem MPEC-linearisierten Tangentialkegel F lin M P EC (z ^(k) ) entspricht. Daraus folgt, dass f¨ ur eine L¨ osung d ^(k) = 0 des LP EC(z ^(k) , σ ^(k) ) der Punkt z ^(k) ein MPEC-linearisiert B-station¨ arer Punkt des MPEC (5.15) ist. D.h. im Gegensatz zu Standard NLP-L¨ osern konvergiert dieses Verfahren gegen einen MPEC-linearisierten Punkt und eignet sich daher besser f¨ ur MPECs.

Um globale Konvergenz zu erreichen, integrieren Leyﬀer und Munson in [11] einen dreidimensionalen Filter, der im Gegensatz zu klassischen Filtermethoden die Verletzung der Zul¨ assigkeit in zwei Komponenten aufteilt. Dabei misst eine Komponente die Verletzung der Komplementarit¨ atsbedingung und die andere Komponente ist ein Maß f¨ ur die Verletzung der Standardnebenbedingungen c.

Leyﬀer und Munson untersuchen in [11] zun¨ achst die globale Konvergenz eines SLPEC-Filter Algorithmus, also eines Algorithmus, welcher in jedem Schritt nur das LP EC(z ^(k) , σ ^(k) ) l¨ ost, aber nicht das EQP. Dabei wird gezeigt, dass der SLPEC-Filter Algorithmus, angewendet auf das MPEC (5.15), unter folgenden Konvergenzannahmen linear gegen einen MPEC-linearisiert B-station¨ aren Punkt konvergiert:

[A1] Die Iterationen bleiben innerhalb einer kompakten Menge Z.

[A2] f und c sind zweimal stetig diﬀerenzierbar auf einer oﬀenen Menge, welche Z enth¨ alt.

[A3] Jeder H¨ aufungspunkt z erf¨ ullt die MPEC-MFCQ.

[A4] Jedes LPEC wird vollst¨ andig gel¨ ost.

108

Diese Konvergenzannahmen sind sehr schwach und fordern insbesondere nicht die MPEC-LICQ, sondern nur die MPEC-MFCQ. Dabei ist anzumerken, dass die MPEC-MFCQ in [11] schw¨ acher sind als unsere MPEC-MFCQ, da sie nur die MFCQ f¨ ur alle N LP ^(β 1 ,β 2 ) (z) und nicht f¨ ur das T N LP (z) fordern. Die MFCQ f¨ ur alle N LP ^(β 1 ,β 2 ) (z) sind jedoch ebenfalls hinreichend f¨ ur die MPEC-ACQ und passen daher auch zu unserer Theorie aus Kapitel 3. [A1] ist noch die st¨ arkste Voraussetzung. Sie kann jedoch gew¨ ahrleistet werden, falls das MPEC von einem bilevel optimization problem stammt, dessen inneres Optimierungsproblem die MFCQ erf¨ ullt. In [11] ist [A4] eine wesentlich schw¨ achere Bedingung, welche im Rahmen dieser Kurzvorstellung durch eine hinreichende Bedingung ersetzt worden ist.

An einer lokalen Konvergenzaussage eines SLPEC-EQP-Filter Algorithmus wird noch gearbeitet. Die Autoren scheinen jedoch zuversichtlich zu sein, dass dieser Algorithmus lokal quadratisch konvergiert. Interessant w¨ are dabei, ob hier unsere neue Deﬁnition der MPEC-WSOSC zur Anwendung kommen k¨ onnte. Man bemerke, dass alle herk¨ ommlichen SOSC f¨ ur MPECs immer einen stark station¨ aren Punkt vorausgesetzt haben, w¨ ahrend die MPEC-WSOSC lediglich einen MPEC-linearisiert B-station¨ aren Punkt voraussetzen. Entsprechende Konvergenzannahmen f¨ ur lokale quadratische Konvergenz des SLPEC-EQP-Filter Algorithmus w¨ urden dann wie folgt aussehen:

[A1] Die Iterationen bleiben innerhalb einer kompakten Menge Z.

[A2] f und c sind zweimal stetig diﬀerenzierbar auf einer oﬀenen Menge, welche Z enth¨ alt.

[A3] z ∗ ist ein MPEC-linearisiert B-station¨ arer Punkt, welcher die MPEC-

MFCQ und die MPEC-WSOSC erf¨ ullt.

[A4] Jedes LPEC wird vollst¨ andig gel¨ ost.

Wie bereits erw¨ ahnt, k¨ onnte das vollst¨ andige L¨ osen des LP EC(z ^(k) , σ ^(k) ) sehr aufw¨ andig werden, da es dem L¨ osen von 2 |β| linearen Programmen ent-

spricht. Man bemerke dabei, dass die zul¨ assigen Bereiche dieser linearen Programme genau den am Punkt z ^(k) linearisierten zul¨ assigen Bereichen unserer N LP ^(β 1 ,β 2 ) (z ^(k) ) entsprechen. Erinnern wir uns an Lemma 2.17, so k¨ onnen wir folgenden Zusammenhang feststellen:

∪ T lin N LP (β 1 ,β 2 ) (z ^(k) ) (z ^(k) ) = F lin M P EC (z ^(k) ) = T LP EC(z ^(k) ,σ ^(k) ) (z ^(k) )

^(β 1 ,β 2 )∈P(β)

Nach [11] ist es f¨ ur die globale Konvergenz bereits hinreichend in einem der T lin (z ^(k) ) eine Abstiegsrichtung zu ﬁnden. Demnach muss man die

N LP (β 1 ,β 2 ) (z ^(k) )

109

LPECs nicht vollst¨ andig l¨ osen, sondern h¨ ochstens eine kleine Anzahl an linearen Programmen. An nicht A-station¨ aren Punkten, welche f¨ ur keines der N LP ^(β 1 ,β 2 ) (z ^(k) ) KKT-Punkte sind (siehe Proposition 4.33), ist es somit ausreichend, nur ein lineares Programm zu l¨ osen. Dar¨ uber hinaus existiert an Punkten z ^(k) , welche die GCQ, MPEC-SMFCQ oder MPEC-LICQ erf¨ ullen, ein gemeinsamer Lagrangemultiplikator f¨ ur alle N LP ^(β 1 ,β 2 ) (z ^(k) ) und wir ﬁnden wieder eine Abstiegsrichtung durch die L¨ osung eines einzigen linearen Programms. In ¨ ahnlicher Weise verh¨ alt sich der Algorithmus in der N¨ ahe ei-

ner L¨ osung z ∗ , welche die MPEC-SMFCQ erf¨ ullt. In diesem Fall gelangt der

Algorithmus wegen des gemeinsamen Lagrangemultiplikators durch L¨ osen

eines linearen Programms zu der L¨ osung z ∗ . D.h. also, dass das kombinato-rische Problem des LPEC nur an biaktiven Punkten auftritt, die A-station¨ ar sind oder die GCQ nicht erf¨ ullen. Beide F¨ alle stellen ein noch gr¨ oßeres Problem f¨ ur Standard NLP-L¨ oser dar. Einerseits tendieren NLP-L¨ oser dazu, gegen biaktive A-station¨ are Punkte mit trivialen Abstiegsrichtungen zu konvergieren und andererseits setzen alle bisherigen Konvergenzaussagen f¨ ur NLP-L¨ oser immer mindestens die MPEC-SMFCQ voraus.

Insgesamt haben wir in diesem Kapitel eine engere Auswahl von numerischen L¨ osungsans¨ atzen vorgestellt. Hierbei sind wir bei dem chronologisch ersten Ansatz der Regularisierung und Penalisierung gestartet. Anschließend sind wir zu der Anwendung von teilweise modiﬁzierten Standard NLP-L¨ osern ubergegangen. Diese NLP-L¨ oser haben den Vorteil, dass sie schon eine Wei¨

le existieren und daher dementsprechend hoch entwickelt sind. Wir haben dabei herausgestellt, dass Innere Punkte Algorithmen wie der IPOPT nur in Kombination mit einem Regularisierungs- oder Penalisierungsansatz eﬃzient funktionieren k¨ onnen. Im Gegensatz dazu haben SQP-Methoden wie der SNOPT eine Chance bei der direkten Anwendung auf das MPEC. Alle Standard NLP-L¨ oser eint jedoch der Nachteil, dass sie implizit mit dem linearisierten Tangentialkegel des MPEC arbeiten, weshalb sie sich nur unter der GCQ f¨ ur MPECs eignen. Dar¨ uber hinaus tendieren NLP-L¨ oser bei Ihrer Anwendung auf MPECs dazu, gegen biaktive A- oder C-station¨ are Punkte mit zul¨ assigen Abstiegsrichtungen zu konvergieren. Abschließend haben wir deshalb einen neuen, speziell f¨ ur MPECs entwickelten, Algorithmus vorgestellt, welcher mit dem MPEC-linearisierten Tangentialkegel arbeitet und sich somit auch f¨ ur MPECs eignet, welche die GCQ nicht erf¨ ullen.

110

6 Schlusswort und Ausblick

Der Schwerpunkt dieser Diplomarbeit lag in der theoretischen Analyse eines MPEC der Form (1.1). Inspiriert durch Arbeiten von Kanzow und Flegel ([2], [4], [5]) betrachtete ich die Tangentialkegel des MPEC und seiner Hilfsprobleme, sowie deren Zusammenh¨ ange. Dabei bezog ich im Gegensatz zu Kanzow und Flegel auch die Tangentialkegel des TNLP und RNLP mit ein. Unter anderem stellten wir in diesem Zusammenhang fest, dass der Tangentialkegel des MPEC darstellbar ist als eine endliche Vereinigung der Tangentialke-gel der N LP ^(β 1 ,β 2 ) (z ∗ ). In ¨ ahnlicher Weise entspricht der MPEC-linearisierte (z ∗ ). Außerdem zeigte ich, Tangentialkegel der Vereinigung aller T lin

N LP (β 1 ,β 2 )

dass der linearisierte Tangentialkegel des MPEC identisch ist mit dem linearisierten Tangentialkegel des RNLP. Dieses einfache Resultat scheint in der MPEC-Gemeinde bislang ¨ ubersehen worden zu sein.

Ausgehend von diesem geometrischen Standpunkt f¨ uhrten wir geometrische Constraint Qualiﬁcations ein, welche sicherstellen, dass die jeweils linearisierten Tangentialkegel die tats¨ achliche Beschaﬀenheit des zul¨ assigen Bereichs auch richtig beschreiben. Eine wesentliche Rolle spielte dabei die lange Zeit in Vergessenheit geratene Guignard Constraint Qualiﬁcation [GCQ], welche von Kanzow und Flegel in [5] wiederentdeckt worden ist. Mit der GCQ fanden wir eine schwache nicht MPEC-speziﬁsche CQ, welche f¨ ur eine große Klasse von MPECs erf¨ ullt werden kann. Im weiteren Verlauf gingen wir auf die in der MPEC-Gemeinde weit verbreiteten MPEC-speziﬁschen Standard-CQ wie die MPEC-LICQ, MPEC-SMFCQ und MPEC-MFCQ ein. Neu war in diesem Zusammenhang ein direkter Beweis daf¨ ur, dass die MPEC-SMFCQ hinreichend f¨ ur die ACQ und somit auch f¨ ur die GCQ ist. Dieses Resultat konnte nach [4] bisher nur indirekt gezeigt werden. In einem weiteren Schritt deﬁnierten wir dann, wie Kanzow und Flegel in [5], sogenannte MPEC-speziﬁsche geometrische CQs und fanden mit der MPEC-GCQ die bislang schw¨ achste CQ f¨ ur MPECs.

Das vierte Kapitel begannen wir mit der geometrischen Boulingand-Stationarit¨ at, welche in ihrer urspr¨ unglichen Form einen notwendige Optimalit¨ atsbedingung erster Ordnung unabh¨ angig von jeglichen CQs ist. Dabei unterschieden wir wie Flegel und Kanzow in [4] zwischen der B-Stationarit¨ at, der linearisierten B-Stationarit¨ at und der MPEC-linearisierten B-Stationarit¨ at. Leider ist es in der MPEC-Gemeinde weit verbreitet, die MPEC-linearisierte B-Stationarit¨ at als B-station¨ ar zu bezeichnen, welche jedoch nur unter der MPEC-GCQ der urspr¨ unglichen Form der B-Stationarit¨ at entspricht. Die linearisierte B-Stationarit¨ at beruht auf dem linearisierten Tangentialkegel des MPEC und stellt daher unter der GCQ eine notwendige Optimalit¨ atsbedingung erster Ordnung dar. Durch Anwendung des Farkas Lemma erhielten wir

111

damit die KKT-Bedingungen f¨ ur das MPEC als notwendige Optimalit¨ atsbedingung. Da der linearisierte Tangentialkegel des MPEC identisch ist mit dem linearisierten Tangentialkegel des RNLP, konnten wir an diesem Punkt auf eine einfache und schnelle Weise zeigen, dass auch die KKT-Bedingungen des RNLP unter der GCQ eine notwendige Optimalit¨ atsbedingung erster Ordnung f¨ ur unser MPEC darstellt. Die MPEC-linearisierte B-Stationarit¨ at beruht hingegen auf dem nicht konvexen MPEC-linearisierten Tangentialkegel, weshalb wir an diesem Punkt das Farkas Lemma nicht direkt anwenden konnten. Wir umgingen dieses Problem, indem wir den MPEC-linearisierten Tangentialkegel als Vereinigung der konvexen Kegel T lin

N LP (β 1 ,β 2 )

und dann das Farkas Lemma auf jeden dieser Kegel T lin

ten. Damit erhielten wir unter der MPEC-GCQ als notwendige Optimalit¨ ats-bedingung erster Ordnung, dass ein lokales Minimum z ∗ des MPEC jeweils KKT-Punkt f¨ ur alle N LP ^(β 1 ,β 2 ) (z ∗ ) sein muss.

In einem weiteren Schritt stellten wir alternative Stationarit¨ atsbegriﬀe der sogenannten MPEC-Buchstabensuppe vor. Die intensive Betrachtung der KKT-Punkte aller Hilfsprobleme f¨ uhrte unter anderem dazu, dass wir die

stark station¨ aren Punkte als KKT-Punkte des RN LP (z ∗ ) identiﬁzieren konn-ten. Ebenso waren wir somit in der Lage, A-station¨ are Punkte als KKT-Punkte eines N LP ^(β 1 ,β 2 ) (z ∗ ) und schwach station¨ are Punkte als KKT-Punkte des T N LP (z ∗ ) zu identiﬁzieren. Des Weiteren stellten wir ein Resultat von

Flegel in [2] vor, welches aussagt, dass die sogenannte M-Stationarit¨ at eine notwendige Optimalit¨ atsbedingung unter der MPEC-GCQ darstellt. Ich habe versucht diese Aussage auf eine wesentlich einfachere und anschauliche Weise zu zeigen. Dieser Versuch ist jedoch leider an dem Beweis des Lemmas 4.36 gescheitert.

Abgesehen von der starken Stationarit¨ at, schließen alle Stationarit¨ atsbegriﬀe der MPEC-Buchstabensuppe die Existenz von zul¨ assigen Abstiegsrichtungen nicht aus. Damit ist ihre Anwendbarkeit in der Praxis fraglich und aus theoretischer Sicht w¨ urde ich die MPEC-linearisierte B-Stationarit¨ at vorziehen, da diese keine trivialen Abstiegsrichtungen zul¨ asst. Die ¨

Uberpr¨ ufung der MPEC-linearisierten B-Stationarit¨ at erfordert jedoch die ¨ Uberpr¨ ufung

von 2 |β| KKT-Systemen und kann damit sehr aufwendig sein.

Am Ende des vierten Kapitels stellten wir schließlich hinreichende Optimalit¨ atsbedingungen zweiter Ordnung vor. Die am weitesten verbreitete SOSC f¨ ur MPECs ist dabei die RNLP-SOSC, welche unter der Voraussetzung eines

stark station¨ aren Punktes z ∗ die SOSC des RN LP (z ∗ ) fordert. Neu hinge-

gen war an diesem Punkte meine Deﬁnition der MPEC-WSOSC, welche im

Prinzip die SOSC aller N LP ^(β 1 ,β 2 ) (z ∗ ) fordert. Damit ist die MPEC-WSOSC

meines Wissens die erste hinreichende Optimalit¨ atsbedingung zweiter Ord-

112

nung, welche keinen stark station¨ aren Punkt voraussetzt, sondern nur einen MPEC-linearisiert B-station¨ aren Punkt.

Abschließend stellte ich im letzten Kapitel eine engere Auswahl an numerischen L¨ osungsans¨ atzen f¨ ur MPECs vor. Ziel dieses Kapitels war es, die Ideen und Unterschiede bereits bestehender L¨ osungsans¨ atze kurz zusammenzufassen. Dabei gingen wir auf Regularisierungs- und Penalisierungsans¨ atze, sowie auf die Anwendung teilweise modiﬁzierter Standard NLP-L¨ oser auf MPECs ein. Wichtig erschien es mir an diesem Punkt hervorzuheben, warum sich die NLP-L¨ oser trotz der numerischen Erfolge in [7], [14], [10], [8] und [1] eigentlich nicht besonders gut f¨ ur die Anwendung auf MPECs eignen. Zum einen basieren diese L¨ oser auf dem linearisierten Tangentialkegel des MPECs und eignen sich daher nur f¨ ur MPECs, welche die GCQ erf¨ ullen. Zum anderen tendieren NLP-L¨ oser auch unter der GCQ dazu, gegen biaktive A-, C- oder M-station¨ are Punkte mit zul¨ assigen Abstiegsrichtungen zu konvergieren. Dadurch motiviert stellten wir abschließend mit dem SLPEC-EQP [11] einen speziell f¨ ur MPECs entwickelten Algorithmus vor, welcher auf dem MPEClinearisierten Tangentialkegel beruht und sich daher besser f¨ ur MPECs eignet.

F¨ ur die Zukunft w¨ are ein Beweis f¨ ur Lemma 4.36 hilfreich, da dies Flegels Beweis zur M-Stationarit¨ at unter der MPEC-GCQ [2] wesentlich vereinfachen w¨ urde. Zudem sollte die Weiterentwicklung des SLPEC-EQP Al-gorithmus von Leyﬀer und Munson [11] aufmerksam verfolgt werden, da sich dieser Ansatz aus theoretischer Sicht im Vergleich zu den mir sonst bekannten Ans¨ atzen am besten zur L¨ osung eines MPEC eignet. Insbesondere sollte man in diesem Zusammenhang pr¨ ufen, ob man mit Hilfe der von mir neu entwickelten MPEC-WSOSC an einem MPEC-linearisiert B-station¨ aren Punkt lokal superlineare Konvergenz f¨ ur den SLPEC-EQP zeigen kann. In einem etwas globaleren Zusammenhang w¨ are es dar¨ uber hinaus interessant, inwiefern man die hier vorgestellte Theorie auf den unendlich dimensionalen Fall erweitern kann.

113

Literatur

[1] Anitescu, M. On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15, 4 (2005), 1203-1236.

[2] Flegel, M. L. Constraint Qualications and Stationarity Concepts for Mathematical Programs with Equilibrium Constraints. PhD thesis, Julius-Maximilians-Universit¨ at W¨ urzburg, 2005.

[3] Flegel, M. L., and Kanzow, C. A Fritz John approach to ﬁrst order optimality conditions for mathematical programs with equilibrium constraints. Optimization 52, 3 (2003), 277-286.

[4] Flegel, M. L., and Kanzow, C. Abadie-type constraint qualiﬁcation for mathematical programs with equilibrium constraints. J. Optimization Theory Appl. 124, 3 (2005), 595-614.

[5] Flegel, M. L., and Kanzow, C. On the Guignard constraint qualiﬁcation for mathematical programs with equilibrium constraints. Optimization 54, 6 (2005), 517-534.

[6] Flegel, M. L., Kanzow, C., and Outrata, J. r. V. Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints. Set-Valued Anal. 15, 2 (2007), 139-162.

[7] Fletcher, R., and Leyffer, S. Solving mathematical programs with complementarity constraints as nonlinear programs. Optim. Methods Softw. 19, 1 (2004), 15-40.

[8] Fletcher, R., Leyffer, S., Ralph, D., and Scholtes, S. Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17, 1 (2006), 259-286.

[9] Geiger, C., and Kanzow, C. Theory and numerics of constrained problems of optimization. (Theorie und Numerik restringierter Optimierungsaufgaben.). Berlin: Springer. xii, 2002.

[10] Leyffer, S., L´ opez-Calva, G., and Nocedal, J. Interior methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17, 1 (2006), 52-77.

[11] Leyffer, S., and Munson, T. S. A globally convergent ﬁlter method for MPECs, 2009. Preprint ANL/MCS-P1457-0907.

114

[12] Nocedal, J., and Wright, S. J. Numerical optimization. 2nd ed. Springer Series in Operations Research and Financial Engineering. New York: Springer. xxii, 2006.

[13] Pang, J.-S., and Fukushima, M. Complementarity constraint qualiﬁcations and simpliﬁed B-stationary conditions for mathematical programs with equilibrium constraints. Comput. Optim. Appl. 13, 1-3 (1999), 111-136.

[14] Raghunathan, A. U., and Biegler, L. T. An interior point method for mathematical programs with complementarity constraints (MPCCs). SIAM J. Optim. 15, 3 (2005), 720-750.

[15] Ralph, D., and Wright, S. J. Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 5 (2004), 527-556.

[16] Scheel, H., and Scholtes, S. Mathematical programs with complementarity constraints: Stationarity, optimality and sensitivity. Mathematics of Operation Research 25, 1 (2000), 1-22.

[17] Ye, J. J. Necessary and suﬃcient optimality conditions for mathematical programs with equilibrium constraints. J. Math. Anal. Appl. 307, 1 (2005), 350-369.

115

Danksagung

An dieser Stelle m¨ ochte ich mich bei Frau Priv. Doz. Dr. Luise Blank f¨ ur die ansprechende Themenstellung und die Freiheit bei der Ausarbeitung dieser Diplomarbeit bedanken. Insbesondere m¨ ochte ich mich dabei f¨ ur die vielen Hilfestellungen und zahlreichen Diskussionen ¨ uber MPECs bedanken.

Des Weiteren bedanke ich mich bei Prof. Dr. Harald Garcke f¨ ur interessante und hilfreiche Anregungen in meinen Seminarvortr¨ age und in pers¨ onlichen Unterhaltungen.

Besonderer Dank gilt zudem meiner Kommilitonin Agathe Thellmann f¨ ur Diskussionen im Bereich der Optimierung und viele Tips zur Erstellung dieser Diplomarbeit.

Zu guter Letzt m¨ ochte ich mich bei meinen Eltern Barbara und Peter Schinabeck, sowie bei meiner Freundin Ursula Stelzer f¨ ur ihre seelische Unterst¨ utzung bei meinem monatelangen Kampf mit Lemma 4.36 bedanken.

Kompletter Text

Beschreibung

Ähnliche Arbeiten

Kommentare

Kommentieren

Neuigkeiten

So funktioniert's

Ähnliche Arbeiten

Facebook

Neuigkeiten

Bücher zum Thema

Autor

Kompletter Text

Beschreibung

Ähnliche Arbeiten

Kommentare

Kommentieren

Neuigkeiten

So funktioniert's

Ähnliche Arbeiten

Facebook

Neuigkeiten

Bücher zum Thema

Registrieren oder einloggen

Neu hier?

Einloggen

Die Alternative

Passwort vergessen?

Neues Passwort anfordern