Optimierung

Volker John

19. Juli 2006

Inhaltsverzeichnis

1 Einfuhrung 3

I Lineare Optimierung 6

1 Grundlagen 7

2 Geometrische Deutung des Linearen Programms 10

3 Basislosungen eines linearen Programms in Normalform 14

4 Hauptsatz und Optimalitatskriterium der Simplexmethode 18

5 Die Simplexmethode 23

6 Bestimmung einer ersten zulassigen Basislosung 28

7 Zur Ausartung 327.1 Die Methode der ε–Storung . . . . . . . . . . . . . . . . . . . . . . . 327.2 Die lexikographische Simplexmethode . . . . . . . . . . . . . . . . . 35

8 Zur Effizienz der Simplexmethode 368.1 Maße fur die Effizienz . . . . . . . . . . . . . . . . . . . . . . . . . . 368.2 Zur worst case Komplexitat der Simplexmethode . . . . . . . . . . . 37

9 Dualitatssatze der linearen Optimierung 43

10 Die duale Simplexmethode 48

11 Die duale Simplexmethode zur Losung rein ganzzahliger linearerProgramme 55

II Nichtlineare Optimierung 60

1 Einleitung 61

2 Nichtlineare Optimierung ohne Nebenbedingungen 642.1 Minimierung nichtglatter Funktionen in einer Variablen . . . . . . . 642.2 Differenzierbare Funktionen . . . . . . . . . . . . . . . . . . . . . . . 69

1

3 Konvexitat 703.1 Konvexe Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703.2 Konvexe und konkave Funktionen . . . . . . . . . . . . . . . . . . . . 723.3 Ungleichungen und konvexe Mengen . . . . . . . . . . . . . . . . . . 753.4 Extrema von konvexen Funktionen . . . . . . . . . . . . . . . . . . . 75

4 Optimalitatskriterien 774.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774.2 Lokale Minima fur Optimierungsprobleme ohne Einschrankungen an

das zulassige Gebiet . . . . . . . . . . . . . . . . . . . . . . . . . . . 784.3 Lokale Minima fur Optimierungsprobleme, bei denen das zulassige

Gebiet durch Ungleichungen gegeben ist . . . . . . . . . . . . . . . . 814.4 Globale Theorie der Lagrange–Multiplikatoren . . . . . . . . . . . . 85

5 Losungsverfahren 895.1 Projektionsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 895.2 Penalty–Verfahren (Strafverfahren) . . . . . . . . . . . . . . . . . . . 925.3 Barrieremethoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.4 SQP–Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

2

Kapitel 1

Einfuhrung

Die Optimierung untersucht im Prinzip die Fragestellung: Gesucht ist die optimaleLosung eines Problems unter irgendwelchen Bedingungen. Die mathematische For-mulierung ist: Gegeben seien Funktionen f : Rn → R, gi : S → R, i = 1, . . . , m,S ⊂ Rn, suche

f(x) → Extremum unter den Bedingungen gi(x) ≥ 0, i = 1, . . . , m.

Sind alle Funktionen linear, so hat man ein Problem der linearen Optimierung.Bei Optimierungsproblemen mussen folgende Fragestellungen untersucht wer-

den:

- Wie lauten notwendige und hinreichende Bedingungen fur die Existenz vonLosungen?

- Wie kann man Losungen mit moglichst geringem Aufwand berechnen? Wassind die effizientesten Algorithmen?

In der Einfuhrung werden einige typische Beispiele von Optimierungsproblemenangegeben.

Beispiel 1.1 Rundreiseproblem. Gegeben sind n verschiedene Orte Oi, i =1, . . . , n. Die Entfernung zwischen den Orten Oi und Oj sei aij . Anstelle der Ent-fernung konnen auch andere Parameter wie Kosten oder Zeit genommen werden.Man nimmt im allgemeinen auch aij 6= aji an. Das Rundreiseproblem oder auchTraveling–Salesman–Problem kann nun wie folgt formuliert werden:Ein Reisender, der in einem Ort startet, mochte alle restlichen Orte genau einmalbesuchen und zum Ausgangsort zuruckkehren. In welcher Reihenfolge hat er dieOrte zu besuchen, damit die Gesamtlange des Reiseweges minimal wird? 2

Beispiel 1.2 Landwirtschaft, Anbauoptimierung. Es stehen 100 ha Ackerlandzur Verfugung, die mit Kartoffeln x1 ha und Getreide x2 ha bestellt werden sollen.Ein Teil der Anbauflache kann auch brach bleiben. Die Betriebskosten sind wie folgt(GE = Geldeinheit):

Kartoffeln Getreide insgesamt verfugbarAnbaukosten GE/ha 10 20 1100 GEArbeitstage/ha 1 4 160 TageReingewinn GE/ha 40 120

Bei welcher Bewirtschaftung erzielt man den großten Gewinn?

3

Die mathematische Formulierung des Problems ist wie folgt:

z = 40x1 + 120x2 → max (1.1)

10x1 + 20x2 ≤ 1100 (1.2)

x1 + 4x2 ≤ 160 (1.3)

x1 + x2 ≤ 100 (1.4)

x1, x2 ≥ 0 (1.5)

Diese Aufgabe kann man graphisch losen.

(2)

(4)

(3)

(5)

(5)

100 160110

40

55

max

(1)

100

x1

x2

Abbildung 1.1: Darstellung der Nebenbedingungen und der Zielfunktion zum Bei-spiel 1.2.

Die Nebenbedingungen beschreiben Halbebenen und der Durchschnitt der Halb-ebenen ist gerade die Menge der Paare (x1, x2), in denen man das Maximum sucht.Zur graphischen Darstellung der Zielfunktion z wahle man sich einen beliebigenPunkt (x1, x2) und berechne die Gerade z durch diesen Punkt. In diesem Bei-spiel soll die Zielfunktion maximiert werden, das heißt, der Zielfunktionswert steigt,wenn man die Gerade orthogonal zu ihrem Anstieg nach oben verschiebt. Der letz-te Punkt, der alle Nebenbedingungen erfullt und der auf einer parallelen Geradenzur dargestellten Geraden liegt, ist der mit einem Kreis gekennzeichnete Punkt(x1, x2) = (60, 25). Die Losung dieses linearen Optimierungsproblems ist demzufol-ge x1 = 60 ha, x2 = 25 ha. 2

Beispiel 1.3 Ernahrungsprogramm. Es stehen die folgenden drei Nahrungsmit-tel zur Verfugung (alle Angaben jeweils fur 100 Gramm):

Eiweiß Fett Kohlenhyd. Wasser Preis1. Weißbrot 8 1 49 42 102. Wurst 12 20 0 68 803. Milch 3 3 5 89 7

Ein Ernahrungsprogramm wird nur zugelassen, wenn es folgende Mindestanfor-derungen erfullt: Eiweiß: 90 g, Fett: 80 g, Kohlenhydrate: 500 g, Wasser 2500 g. Zielist es, das kostengunstigste Ernahrungsprogramm zu finden, welches diese Anforde-

4

rungen erfullt. Das zugehorige Optimierungsproblem lautet:

z = 10x1 + 80x2 + 7x3 → min

8x1 + 12x2 + 3x3 ≥ 90

x1 + 20x2 + 3x3 ≥ 80

49x1 + 5x3 ≥ 500

42x1 + 68x2 + 89x3 ≥ 2500

x1, x2, x3 ≥ 0,

wobei die Maßeinheit fur x1, x2, x3 hier 100 g ist.Die (gerundete) Losung lautet: x1 = 7.71, x2 = 0, x3 = 24.45, also 771 g

Weißbrot und 2445 g Milch, das heißt vegetarisch. Die Kosten sind rund 248 GE. 2

Beispiel 1.4 Rucksackproblem. Ein Wanderer kann in seinem Rucksack ein Ge-samtgewicht von N tragen. Er hat n Gegenstande, die er mitnehmen mochte undjeder Gegenstand hat einen gewissen Nutzen ni, i = 1, . . . , n. Das Gesamtgewichtaller Gegenstande ubersteigt das zulassige Maximalgewicht. Das Optimierungspro-blem des Wanderers besteht nun darin, eine Teilmenge von Gegenstanden mit ma-ximalem Nutzen zu finden, so dass das Gesamtgewicht dieser Teilmenge hochstensN ist. Dabei kann als zusatzliche Nebenbedingung auftreten, dass gewisse Losungs-komponenten ganzzahlig sein mussen, zum Beispiel die Anzahl der Paar Schuhe, dieer mitnehmen soll. 2

Beispiel 1.5 Zuordnungsproblem. In einer Firma stehen zur Fertigung von nProdukten n Maschinen zur Verfugung. Jede Maschine eignet sich zur Herstellungjedes Produktes unterschiedlich gut. Es ergeben sich je nach Zuordnung verschiede-ne Arbeitszeiten. Jeder Maschine soll genau ein Produkt zugeordnet werden. DasOptimierungsproblem besteht darin, die Gesamtfertigungszeit der Produkte zu mi-nimieren. 2

Bemerkung 1.6 Operations Research. In der Fachliteratur werden Optimierungs-aufgaben oft unter dem Begriff Operations Research (Optimalplanung) gefuhrt. 2

Literaturempfehlungen sind:

• Jarre and Stoer [JS04],• Borgwardt [Bor01],• Elster, Reinhardt, Schauble, Donath [ERSD77],• vor allem uber das Gebiet der linearen Optimierung gibt es auch eine Reihe

alterer Lehrbucher, die man verwenden kann.

5

Teil I

Lineare Optimierung

6

Kapitel 1

Grundlagen

Definition 1.1 Lineares Optimierungsproblem, lineares Programm. EineAufgabenstellung wird lineares Optimierungsproblem oder lineares Programm ge-nannt, wenn das Extremum einer linearen Funktion

z =n∑

i=1

cixi = cT x (1.1)

zu bestimmen ist, uber der durch das lineare Ungleichungssystem

n∑

j=1

aijxj ≤ (>) bi, i = 1, . . . , m (1.2)

xj ≥ 0, j = 1, . . . , n, (1.3)

definierten Punktmenge. 2

Seien x,y ∈ Rn. Dann wird die Bezeichnung

x ≥ (>)y ⇐⇒ xi ≥ (>)yi, ∀ i = 1, . . . , n,

verwendet.

Definition 1.2 Zulassiger Bereich. Die Menge M aller Punkte, die das Unglei-chungssystem (1.2) – (1.3) erfullen, heißt zulassiger Bereich. 2

Beispiel 1.3 Der zulassige Bereich, der durch lineare Nebenbedingungen beschrie-ben ist, ist der Durchschnitt von Halbraumen. Fur n = 2 sind das Halbebenen undein Beispiel ist in Abbildung 1.1 zu sehen. 2

Der zulassige Bereich ist nicht notwendig beschrankt. Er kann auch leer sein.

Definition 1.4 Konvexitat. Eine Punktmenge M heißt konvex, wenn mit belie-bigem x1, x2 ∈ M auch alle Punkte der Gestalt

λx1 + (1 − λ)x2, 0 ≤ λ ≤ 1,

zu M gehoren. 2

Fur den Rn bedeutet Konvexitat, dass mit zwei Punkten x1,x2 aus M auchihre Verbindungsstrecke in M liegt.

Satz 1.5 Die durch das lineare Ungleichungssystem (1.2) – (1.3) definierte Punkt-menge ist konvex.

7

Beweis: Seien x1,x2 ∈ M gegeben. Dann gelten

Ax1 ≤ b, x1 ≥ 0, Ax2 ≤ b, x2 ≥ 0.

Mit λ ∈ [0, 1] giltλAx1 ≤ λb, (1 − λ)Ax2 ≤ (1 − λ)b.

Addition und Linearitat der Matrizenmultiplikation ergibt

A (λx1 + (1 − λ)x2) ≤ b.

Analog folgtλx1 + (1 − λ)x2 ≥ 0.

Der Durchschnitt beliebig vieler konvexer Mengen ist wieder konvex. Ubungs-aufgabe

Definition 1.6 Konvexe Hulle. Die kleinstmogliche konvexe Menge M, die einevorgegebene Punktmenge P enthalt, heißt deren konvexe Hulle. 2

Beispiel 1.7 Die dick umrandete Menge ist die konvexe Hulle der dunn umrande-ten Menge.

2

Beispiel 1.8 Die Menge

M =

1

n: n ∈ N

ist nicht konvex, da sie aus diskreten Punkten besteht. Ihre konvexe Hulle ist (0, 1].2

Definition 1.9 Konvexe Linearkombination. Gegeben seien q Punkte x1, . . . ,xq.Betrachtet werden alle Punkte der Gestalt

x =

q∑

i=1

λixi, 0 ≤ λi ≤ 1,

q∑

i=1

λi = 1. (1.4)

Dann heißt die mit (1.4) erklarte Menge konvexe Linearkombination der Punktex1, . . . ,xq. 2

Welche Punkte einer konvexen Menge sollen ausgezeichnet werden?

Definition 1.10 Eckpunkt oder Extrempunkt einer konvexen Menge. Ge-geben sei eine konvexe Menge M. Der Punkt x ∈ M heißt Eckpunkt oder Extrem-punkt von M, wenn aus x = λx1 + (1 − λ)x2, x1,x2 ∈ M, 0 < λ < 1, folgtx = x1 = x2. 2

Man sagt, x lasst sich nicht als echte konvexe Linearkombination von x1,x2

darstellen.

8

Beispiel 1.11 Bei einem Viereck im R2 sind die Eckpunkte gerade die vier Ecken.Bei einer Kugel im Rn, n ≥ 1, sind alle Randpunkte Eckpunkte. 2

Definition 1.12 Konvexes Polyeder. Eine beschrankte Menge M 6= ∅ mit end-lich vielen Eckpunkten heißt konvexes Polyeder. 2

Beispiel 1.13 Konvexe Polyeder in Rd, d = 1, 2, 3. Ein konvexes Polyeder inR1 ist ein abgeschlossenes Intervall. In R2 und R3 kann man sich konvexe Polyedernoch gut vorstellen. Ein Beispiel in R2 findet man in Abbildung 1.1. 2

Satz 1.14 Sei M eine konvexe, abgeschlossene und beschrankte Menge, P sei dieMenge der Eckpunkte von M. Dann ist M die konvexe Hulle von P.

Beweis: Literatur. Beweisidee mit trennenden Hyperebenen siehe [ERSD77,Satz 2.48].

Satz 1.15 Ist der Losungsbereich

M = x : Ax ≤ b,x ≥ 0

beschrankt, so ist er ein konvexes Polyeder.

Beweis: Siehe spater, Folgerung 3.7.

9

Kapitel 2

Geometrische Deutung desLinearen Programms

In diesem Abschnitt wird gezeigt, dass sich das anschauliche Merkmal des zweidi-mensionalen linearen Programms aus Beispiel 1.2, namlich dass das Optimum aufdem Rand angenommen wird, verallgemeinern lasst.

Historie zur Untersuchung linearer Optimierungsprobleme:

- 1939 Leonid V. Kantorovitch (1912 – 1986); Methode der Auflosungskoeffi-zienten

- 1941 Frank L. Hitchcock, Transportproblem- 1949 George Dantzig (1914 – 2005), Simplexmethode

Definition 2.1 Lineares Optimierungsproblem in 1. Normalform, linearesProgramm in Normalform. Gesucht werden die Werte der n Variablen x1, . . . , xn

so, dass die lineare Funktion

z =

n∑

j=1

cjxj , = cT x (2.1)

die sogenannte Zielfunktion, unter den Nebenbedingungen

n∑

j=1

aijxj ≥ bi, i = 1, . . . , m, (Ax ≥ b) (2.2)

xj ≥ 0, j = 1, . . . , n, (x ≥ 0) (2.3)

ein Minimum annimmt. Alle Koeffizienten sind reell. Das System (2.1) – (2.3) heißtlineares Optimierungsproblem oder lineares Programm in 1. Normalform. 2

Bemerkung 2.2

1. Ob (2.1) in min– oder max–Form benutzt wird, ist im allgemeinen ohneBelang, in [JS04] wird beispielsweise die max–Form verwendet.

2. Die Relationen ≥, =, ≤ im System der Nebenbedingungen sind im wesentli-chen aquivalent.

3. Fehlt zum Beispiel fur einen Index k die Bedingung xk ≥ 0, so setzt manxk := xk − xk mit xk, xk ≥ 0. Man erhoht damit die Anzahl der Variablenum Eins.

2

Definition 2.3 Zulassiger Punkt. Ein Punkt x = (x1, . . . , xn)T heißt zulassig,wenn er die Nebenbedingungen (2.2), (2.3) erfullt. Die Gesamtheit aller zulassigenPunkte heißt zulassiger Bereich. 2

10

Fur die Losung von (2.1) – (2.3) kommen nur zulassige Punkte in Betracht. Derzulassige Bereich ist konvex. Ist er beschrankt, so ist er ein konvexes Polyeder. Istder zulassige Bereich nicht beschrankt ist, dann gilt:

- entweder ist (2.1) uber diesen Bereich selbst nicht beschrankt,Beispiel: Minimiere −2x1 − x2 im Bereich (x1, x2) : x1 ≥ 0, x2 ≥ 0,

- oder (2.1) ist uber dem unbeschrankten Bereich beschrankt. Dann kann manZusatzbedingungen an den zulassigen Bereich stellen, die das Optimum nichtandern, so dass der neue zulassige Bereich beschrankt ist.Beispiel: Minimiere 2x1 + x2 im Bereich (x1, x2) : x1 ≥ 0, x2 ≥ 0.

Weitere Beispiele findet man in Beispiel 2.6.Wenn von einem konvexen Polyeder gesprochen wird, ist ab sofort immer ein

abgeschlossenes konvexes Polyeder gemeint.

Satz 2.4 Extremwertannahme. Eine auf einem konvexen Polyeder definierte li-neare Funktion z = f(x) nimmt ihren kleinsten Wert in (mindestens) einem Eck-punkt an.

Beweis: Seien x1, . . .xp die Eckpunkte des konvexen Polyeders. Die Funktionf(x) nehme ihr Minimum in x0 an, das heißt

f(x0) ≤ f(x) (2.4)

fur alle Punkte x des konvexen Polyeders. Dass das Minimum angenommen wird,folgt nach dem Satz von Bolzano–Weierstrass (stetige Funktion in einem kompak-ten Gebiet nimmt ihre Extremwerte an). Ist x0 kein Eckpunkt, so existiert eineDarstellung (Satz 1.14)

x0 =

p∑

j=1

λjxj , 0 ≤ λj ≤ 1,

p∑

j=1

λj = 1.

Aus der Linearitat von f folgt

f (x0) = f

p∑

j=1

λjxj

=

p∑

j=1

λjf (xj) .

Sei ein Index l definiert durch

f(xl) = minj=1,...,p

f(xj).

Dann folgt

f (x0) ≥ f(xl)

p∑

j=1

λj = f(xl). (2.5)

Wegen (2.4) und (2.5) wird das Minimum fur xl angenommen.

Folgerung 2.5 Wird das Minimum in mehr als einem Eckpunkt des konvexen Po-lyeders angenommen, so wird es auf der konvexen Hulle dieser Eckpunkte angenom-men.

Beweis: Ohne Beschrankung der Allgemeinheit seien die Eckpunkte so nu-meriert, dass die Zielfunktion f(x) ihr Minimum in den Eckpunkten x1, . . . ,xq

annehme. Die konvexe Hulle dieser Eckpunkte ist

x : x =

q∑

i=1

λixi, 0 ≤ λi ≤ 1,

q∑

i=1

λi = 1

.

11

Aus der Linearitat von f folgt

f(x) = f

(q∑

i=1

λixi

)

=

q∑

i=1

λif(xi) = f(x1)

q∑

i=1

λi = f(x1) = min .

Geometrische Interpretation

Die Gleichung z = cT x− d mit einer vorgegebenen Konstanten d ist die Gleichungeiner Hyperebene in Rn. Fur n = 3, hat man beispielsweise die Normalform einerEbenengleichung, wobei c ein Normalenvektor der Ebene ist.

Sei z = cT x die Zielfunktion. Es ist gerade

c = ∇z =

(∂z

∂x1, . . . ,

∂z

∂xn

)T

.

Außerdem ist c orthogonal zu den Hyperebenen cT x = const. Sei ein beliebigerVektor einer Hyperebene gegeben, etwa zwischen den Punkten x und x, dann gilt

cT x = const, cT x = const, =⇒ cT (x − x) = 0.

Aus der Menge cT x = const wahlen wir diejenige Hyperebene, die einen vor-gegebenen Punkt x0, nicht notwendig einen Eckpunkt, enthalt: cT x = cT x0. Wirdefinieren

g := x : x = x0 + tc, t ∈ R .

Diese Gerade enthalt x0 und sie ist orthogonal zu cT x = const. Fur alle x ∈ g giltbezuglich der Zielfunktion

z = cT x = cT (x0 + tc) = cT x0 + t ‖c‖22 =: z0 + t ‖c‖2

2 ,

wobei z0 der Startwert der Zielfunktion ist. Sei t > 0. Dann folgt z > z0, das heißt,der Wert der Zielfunktion wachst streng monoton in Richtung von c. Wenn manz zu maximieren hat, so verschiebe man die Gerade in Richtung des Gradienten.Also, ausgehend von cT (x− x0) = 0 konstruiere man in Richtung von c eine Scharzu cT (x − x0) = 0 paralleler Hyperebenen mit dem Ziel, diejenige Hyperebene ausder Schar zu finden, die x : Ax ≤ b, x ≥ 0 beruhert mit der Eigenschaft, dassx : Ax ≤ b, x ≥ 0 ganz im negativen Halbraum der beruhrenden Hyperebeneliegt. Beruhrung bedeutet, dass x : Ax ≤ b, x ≥ 0 ∩

cT x = const

eine Teil-

menge des Randes des Polyeders ist, zum Beispiel ein Eckpunkt.

Beispiel 2.6 Beispiele fur Situationen die in linearen Programmen auf-treten konnen.

a) Es gibt unendlich viele Losungen (eine gesamte Kante).

x2

x1

z

12

b) Es gibt uberflussig Nebenbedingungen. Die Zielfunktion nimmt ihren Extrem-wert in (0, 0) an und die drei oberen Nebenbedingungen sind uberflussig.

x2

x1

z

c) Der zulassige Bereich ist leer.

x2

x1

d) Der Optimalwert ist nicht beschrankt.

zx1

x2

13

Kapitel 3

Basislosungen eines linearenProgramms in Normalform

Definition 3.1 Lineares Programm in 2. Normalform, einfache Normal-form. Gegeben sei das lineare Programm

z = cT x → min ! (3.1)

unter den folgenden Bedingungen

Ax = b (3.2)

x ≥ 0 (3.3)

mit x ∈ Rn, b ∈ Rm und A ∈ Rm×n. Dieses Problem wird lineares Programm in(2.) Normalform genannt.

Bemerkung 3.2 Wenn man die lineare Ungleichung

n′

∑

j=1

ai∗jxj ≤ bi∗

gegeben hat, so kann man eine sogenannte Schlupfvariable einfuhren

n′

∑

j=1

ai∗jxj + xn′+1 = bi∗ , xn′+1 ≥ 0.

Mit Hilfe der Schlupfvariablen gelingt es aus dem linearen Programm in 1. Normal-form ein lineares Programm in 2. Normalform zu machen. Diese sind aquivalent.Die Kosten der Einfuhrung von Schlupfvariablen bestehen darin, dass man die Di-mension des Losungsvektors erhoht.

Wir machen jetzt die folgenden Voraussetzungen:

1. m < n, das heißt weniger Nebenbedingungen als Unbekannte.2. rg(A) = m, das heißt, A hat vollen Zeilenrang.3. Ax = b, x ≥ 0 sei widerspruchsfrei, das heißt, der zulassige Bereich ist nicht

leer.

Definition 3.3 Basislosung. Basislosungen des linearen Programms (3.1) – (3.3)sollen die Losungsvektoren x = (xi1, . . . , xim, 0, . . . , 0)T heißen, fur die die m Va-riablen xi1, . . . , xim eine nicht singulare Koeffizientenmatrix

Am,m = (ai1, . . . , aim)

besitzen, wobei (aj) , j = 1, . . . , n, die Spaltenvektoren von A bezeichne.

14

Die ersten m Variablen einer Basislosung konnen beliebige reelle Zahlen sein.

Definition 3.4 zulassige Basislosung, ausgeartete (entartete) Basislosung.Gilt fur eine Basislosung x = (xi1, . . . , xim, 0, . . . , 0)T , dass xij ≥ 0 fur alle j =1, . . . , m, dann heißt sie zulassig. Verschwindet sie in mindestens einer Variablen, soheißt sie ausgeartet oder entartet.

Die Komponenten einer Basislosung werden Basisvariable genannt, die zugehori-gen Spaltenvektoren heißen Basisvektoren. Entsprechend spricht man von Nichtba-sisvariablen und Nichtbasisvektoren.

Beispiel 3.5

z = −x1 − x2 → min !

x1 + 3x2 + x3 = 3

3x1 + x2 + x4 = 3

x ≥ 0.

Zulassige, nicht ausgeartete Basislosungen sind (i1 = 3, i2 = 4)

x = (0, 0, 3, 3)T , A2,2 =

(1 00 1

)

, z = 0.

oder (i1 = 1, i2 = 2)

x = (3/4, 3/4, 0, 0)T , A2,2

(1 33 1

)

, z = −3

2.

z

x1

x2

31

(3

4,

3

4)1

3

Wir fuhren jetzt die weitere Nebenbedingung

x1 + x2 ≤ 3

2

ein. Die Nebenbedingungen des erweiterten linearen Programms haben die Gestalt

1 3 1 0 03 1 0 1 01 1 0 0 1

x1

x2

x3

x4

x5

=

33

1.5

.

Dann ist eine ausgeartete zulassige Basislosung des erweiterten linearen Programms(i1 = 1, i2 = 2, i3 = 5)

(3/4, 3/4, 0, 0, 0)T , A3,3 =

1 3 03 1 01 1 1

, z = −3

2.

15

Im Bild erkennt man, was Ausartung bedeutet. Die Ecke (3/4, 3/4) des zulassigenBereichs ist bereits durch die ersten beiden Nebenbedingungen bestimmt. Durch dieneue Nebenbedingung ist diese Ecke nun wahlweise durch die ersten beiden, durchdie erste und die dritte oder die zweite und die dritte Nebenbedingung bestimmt.Die Nebenbedingungen, die diese Ecke des zulassigen Bereichs bestimmen, sind nichtmehr eindeutig. 2

Satz 3.6 Ein Eckpunkt eines zulassigen Bereichs M = x : Ax = b, x ≥ 0 liegtgenau dann vor, wenn seine Koordinaten eine zulassige Basislosung bilden.

Beweis: a) Aus Basislosung folgt Eckpunkt. Sei x = (x1, x2, . . . , xm, 0, . . . , 0)T

eine zulassige Basislosung, das heißt

a1x1 + a2x2 + . . . + amxm = b,

die Vektoren a1, . . . , am sind linear unabhangig und die Nichtbasisvariablen xm+1, . . . , xn

sind gleich Null.Der Beweis wird indirekt gefuhrt, indem angenommen wird, dass

x = (x1, . . . , xm, 0, . . . , 0)

kein Eckpunkt ist. Dann gibt es Punkte x1,x2 ∈ M mit λx1 + (1 − λ)x2 = x,x1 6= x2, 0 < λ < 1. Da die letzten n − m Komponenten von x verschwinden,muss das auch fur entsprechenden Komponenten von x1 und x2 gelten, da alleKomponenten dieser Vektoren nichtnegativ sind. Seien nun

x1 =(

x(1)1 , x

(1)2 , . . . , x(1)

m , 0, . . . , 0)T

, x2 =(

x(2)1 , x

(2)2 , . . . , x(2)

m , 0, . . . , 0)T

.

Da diese Punkte zulassig sind, folgt

a1x(1)1 + a2x

(1)2 + . . . + amx(1)

m = b,

a1x(2)1 + a2x

(2)2 + . . . + amx(2)

m = b.

Wegen der linearen Unabhangigkeit der Vektoren a1, . . . , am folgt daraus x1 = x2,was im Widerspruch zur Annahme steht. Also ist x ein Eckpunkt.

b) Aus Eckpunkt folgt Basislosung. Sei x ein Eckpunkt des zulassigen Bereichsmit den nichtnegativen Koordinaten x1, . . . , xk, das heißt, es gilt

a1x1 + a2x2 + . . . + akxk = b, xj > 0 fur aj ∈ Rm j = 1, . . . , k ≤ n.

Ohne Beschrankung der Allgemeinheit seien die verschwindenden Komponenten diehinteren. Es ist zu zeigen, dass a1, . . . , ak linear unabhangig sind.

Der Beweis ist wieder indirekt. Wir nehmen also an, dass es ein y ∈ Rk gibt mit

a1y1 + a2y2 + . . . + akyk = 0

und mindestens einem yi 6= 0. Fur jede reelle Zahl µ gilt damit

k∑

j=1

aj (xj + µyj) = b und

k∑

j=1

aj (xj − µyj) = b.

Das bedeutet, die Punkte

x1 = (x1 + µy1, . . . , xk + µyk, 0, . . . , 0) ,

x2 = (x1 − µy1, . . . , xk − µyk, 0, . . . , 0)

16

erfullen die Nebenbedinungen (3.2). Falls man µ > 0 hinreichend klein wahlt, sindalle Komponenten dieser Punkte nichtnegativ und x1,x2 sind zulassig. Aus derKonstruktion von x1,x2 folgt, dass x = 0.5x1 + 0.5x2 gilt. Das ist im Widerspruchzur Eckpunktannahme von x. Diese Darstellung fur den Eckpunkt x kann nur exi-stieren, wenn x1 = x2. Da µ positiv ist, muss also y1 = . . . = yk = 0 gelten. Alsosind a1, . . . , ak linear unabhangig.

Die Basislosung verlangt jedoch m linear unabhangige Vektoren:

- Fall k > m. m + 1 Vektoren des Rm sind stets linear abhanging. Dieser Fallkann also nicht eintreten.

- Fall k = m. In diesem Fall besitzt die zulassige Basislosung m positivenKomponenten, sie ist also nicht ausgeartet.

- Fall k < m. In diesem Fall hat man eine zulassige Basislosung mit weniger alsm positiven Komponenten, also eine ausgeartete Basislosung. Aus den rest-lichen Spalten von A konstruiert man eine Menge von linear unabhangigenVektoren a1, . . . , am, fur welche offensichtlich

a1x1 + . . . + akxk + ak+10 + . . .am0 = b

gilt. Diese Konstruktion ist moglich, da rg(A) = m ist.

Folgerung 3.7 Satz 1.15. Ist der Losungsbereich

M = x : Ax = b,x ≥ 0

beschrankt, so ist er ein konvexes Polyeder.

Beweis: Man kann nur endlich viele Mengen von m linear unabhangigen Spal-tenvektoren der Matrix A bilden. (Maximalanzahl ist Ubungsaufgabe) Mit dem ebenbewiesenen Satz hat damit M nur endlich viele Ecken.

Eine weitere Folgerung des eben bewiesenen Satzes, zusammen mit Satz 2.4 istwie folgt.

Folgerung 3.8 Eine uber einem konvexen Polyeder M = x : Ax = b,x ≥0 definierte lineare Funktion z = cT x nimmt ihr Minimum fur wenigstens einezulassige Basislosung an.

Mit Hilfe der bisherigen Resultate konnen wir versuchen, ein Verfahren zurLosung von

minx∈Rn

z = cT x : Ax = b,x ≥ 0

zu konstruieren:

1. Aufstellung der

(nm

)

linearen Gleichungssysteme der Dimension m aus

Ax = b.2. Ist die so generierte Matrix Am,m regular?

3. Angabe der Losung fur regulare Am,m.4. Auswahl der zulassigen Losungen5. Bestimmung der Losung(en), die das Minimum liefern.

Diese Herangehensweise ist jedoch schon bei relativ kleiner Anzahl von Unbe-kannten und Nebenbedingungen viel zu aufwendig. Zum Beispiel hatte man bein = 20, m = 10 schon 184 756 Gleichungssysteme aufzustellen und diese zu unter-suchen.

Das Ziel wird nun sein, ein Verfahren zu finden, welches einen cleveren Weg zumOptimum findet, unter Nutzung von zulassigen Basislosungen.

17

Kapitel 4

Hauptsatz undOptimalitatskriterium derSimplexmethode

In diesem Abschnitt wird das wichtigste Verfahren zur Losung linearer Optimie-rungsprobleme eingefuhrt – die Simplexmethode. Es existiere fur

minx∈Rn

z = cT x : Ax = b,x ≥ 0

eine zulassige Basislosung mit x > 0.

Definition 4.1 Simplex. Ein Simplex ist die Menge aller Punkte x = (x1, . . . , xn)mit

n∑

i=1

xi ≤ 1, xi ≥ 0, i = 1, . . . , n.

2

Fur n = 2 ist das Dreieck mit den Eckpunkten (0, 0), (1, 0), (0, 1) ein Simplex.Bild

Das geometrische Prinzip der Simplexmethode ist wie folgt:

1. Man beginnt an einer Ecke des zulassigen Bereichs mit einer Startlosung x1

und dem Zielfunktionswert z(x1).2. Dann geht man entlang einer absteigenden Kante, dass heisst, bei welcher

der Zielfunktionswert kleiner wird, z(x1) > z(x2) zu einer sogenannten be-nachbarten Ecke x2.

3. Wiederhole Schritt 2 so lange, bis es keine absteigende Kante mehr gibt.

Wir werden spater diskutieren, dass man auch Simplexschritte ausfuhren kann, beidenen der Zielfunktionswert gleich bleibt. In diesem Fall ist die Beschreibung deszweiten Schritts auch abzuandern, da man nicht zu einer benachbarten Ecke geht,sondern auf der gegebenen Ecke die Basis andert. Diese Situation kann im Falle derAusartung eintreten. Man nennt zwei Basislosungen benachbart, wenn sie sich nurin einem Basisvektor unterscheiden.

Sei x = (x1, . . . , xm, 0, . . . , 0)T eine erste zulassige Basislosung. Es gilt

a1x1 + a2x2 + . . . + amxm = b. (4.1)

Dabei sind a1, . . . , am linear unabhangige Vektoren. Der Zielfunktionswert istdemzufolge

z0 = c1x1 + . . . + cmxm. (4.2)

18

Alle Nichtbasisvektoren am+1, . . . , an werden durch die Basis dargestellt

aj = x1ja1 + . . . + xmjam, j = m + 1, . . . , n. (4.3)

Mit diesen Darstellungskoeffizienten xij werden die Hilfsgroßen

zj = c1x1j + c2x2j + . . . + cmxmj , j = m + 1, . . . , n, (4.4)

eingefuhrt.

Satz 4.2 Hauptsatz der Simplexmethode. Sei z0 der Wert der Zielfunktion furdie zulassige Basislosung x = (x1, . . . , xm, 0, . . . , 0)T , xi > 0, i = 1, . . . , m. Gilt furein festes j = k, j = m + 1, . . . , n, dass zk − ck > 0, so existiert wenigstens einezulassige Basislosung mit einem Zielfunktionswert kleiner als z0.

Beweis: Sei θ > 0 vorerst beliebig gewahlt. Man multipliziere (4.3) und (4.4)fur j = k mit θ und bilde (4.1) - θ (4.3) und (4.2) - θ (4.4):

a1 (x1 − θx1k) + a2 (x2 − θx2k) + . . . + am (xm − θxmk) + θak = b, (4.5)

c1 (x1 − θx1k) + c2 (x2 − θx2k) + . . . + cm (xm − θxmk) + θck

= z0 − θzk + θck = z0 + θ (ck − zk) . (4.6)

In der Gleichung (4.5) steht ein Vektor, der Ax = b erfullt:

(x1 − θx1k, . . . , xm − θxmk, 0, . . . , θ, . . . , 0)T

.

Es wird in Lemma 4.3 gezeigt, dass man mit diesem Vektor eine Basislosung erhalt.Man hatte eine zulassige Basislosung, wenn xi − θxik ≥ 0, i = 1, . . . , m. Der zu-gehorige Zielfunktionswert ist durch die Gleichung (4.6) gegeben. Er ist kleiner alsz0 falls θ > 0 und zk − ck > 0.

Unter der Annahme, dass der Hauptsatz bereits vollstandig bewiesen ist, habenwir ein hinreichendes Kriterium um zu entscheiden, ob es eine zulassige Basislosungmit einem kleineren Zielfunktionswert gibt. Man benotigt jetzt noch eine Methodezur Konstruktion dieser zulassigen Basislosung. Diese erfolgt mit Hilfe von θ. DieseGroße wird definiert durch

θ = mini=1,...,m,xik>0

xi

xik=:

xl

xlk. (4.7)

Damit das funktioniert, brauchen wir ein xik > 0. Falls es kein solches xik gibt,dann folgt, dass die Zielfunktion nach unten unbeschrankt ist. Man kann namlichin diesem Fall θ beliebig groß wahlen, da stets xi − θxik ≥ 0. Aus (4.6) folgt dann,dass unter der Bedingung ck − zk < 0 die Zielfunktion unbeschrankt nach untenist. Fazit: Falls fur ein zk − ck > 0 alle xik ≤ 0, dann ist die Zielfunktion nicht vonunten beschrankt und man breche die Simplexmethode ab.

Wenn man Entartung ausschließt, dann ist θ eindeutig bestimmt, das heißt,das Minimum in (4.7) wird fur genau einen Index l angenommen. Es gilt auch dieUmkehrung, dass falls der Index l in (4.7) nicht eindeutig bestimmt ist, dann hatman Ausartung. Ausartung kann zur Folge haben, dass gilt z(xi) = z(xi+1) = . . ..Das nennt man einen Basiszyklus.

Sei der Index l in (4.7) eindeutig bestimmt. Dann hat man

a1

(

x1 −xl

xlkx1k

)

+ . . . + al−1

(

xl−1 −xl

xlkxl−1,k

)

+al+1

(

xl+1 −xl

xlkxl+1,k

)

+ . . . + am

(

xm − xl

xlkxmk

)

+xl

xlkak = b,

19

und die neue zulassige Losung

xi = xi −xl

xlkxik , i = 1, . . . , m, i 6= l, xk =

xl

xlk. (4.8)

Alle Komponenten sind auf Grund der Konstruktion nichtnegativ und bei Aus-schluss der Entartung sogar positiv. Man hat also die Komponente xl aus der Ba-sisliste gestrichen und durch die Komponente xk ersetzt.

Es gilt also, (4.8) ist eine zulassige Losung mit einem kleineren Zielfunktions-wert als die ursprungliche Losung. Damit bleibt nur noch die Basiseigenschaft vona1, . . . , al−1, ak, al+1, . . . , am zu prufen.

Lemma 4.3 Sei w1, . . . ,wm ein System linear unabhangiger Vektoren und sei

w =m∑

i=1

µiwi, µl 6= 0. (4.9)

Dann ist auch w1, . . . ,wl−1,w,wl+1, . . .wm ein System linear unabhangiger Vek-toren.

Beweis: Indirekter Beweis. Sei w1, . . . ,wl−1,w,wl+1, . . .wm kein Systemlinear unabhangiger Vektoren. Dann gibt es Zahlen α1, . . . , αl−1, αl+1, . . . , αm, α,von denen wenigstens eine ungleich Null ist, so dass

m∑

i=1,i6=l

αiwi + αw = 0.

In diese Gleichung wird (4.9) eingesetzt. Es folgt

m∑

i=1,i6=l

(αi + αµi)wi + αµlwl = 0.

Die Vektoren w1, . . . ,wm sind linear unabhangig, das heißt, alle Koeffizientenin dieser Gleichung mussen Null sein. Wegen µl 6= 0 folgt dann α = 0 und darausαi = 0 fur alle i. Damit ist gezeigt, dass w1, . . . ,wl−1,w,wl+1, . . .wm ein Systemlinear unabhangiger Vektoren ist.

Damit ist die Basiseigenschaft von a1, . . . , al−1, ak, al+1, . . . , am gewahrleistet.Im allgemeinen ist der Hauptsatz der Simplexmethode solange anzuwenden, wie

noch wenigstens ein zk−ck > 0 ist. Dabei kann man im allgemeinen nicht erwarten,falls noch q Großen zj − cj > 0 existieren, dass man noch q Schritte auszufuhrenhat. Gilt fur alle zj − cj ≤ 0, j – Index von Nichtbasisvariablen, so ist man in demSinne fertig, dass der Hauptsatz nicht mehr anwendbar ist. Der Hauptsatz gibt aberbisher nur ein hinreichendes und kein notwendiges Kriterium fur die Existenz einerBasislosung mit einem kleineren Zielfunktionswert. Im folgenden Satz wird gezeigt,dass das Kriterium auch notwendig ist.

Satz 4.4 Optimalitatskriterium. Eine zulassige Basislosung x ∈ Rn mit z0(x) =∑m

i=1 cixi ist optimale Basislosung, wenn fur alle j = m + 1, . . . , n gilt zj − cj ≤ 0.

Beweis: Sei x = (x1, . . . , xm, 0, . . . , 0)T . Des weiteren sei y = (y1, . . . , yn)T

eine beliebige zulassige Losung

a1y1 + a2y2 + . . . + anyn = b, y ≥ 0, (4.10)

mit z∗ =

n∑

i=1

ciyi. (4.11)

20

Zu zeigen ist, dass z0 ≤ z∗ fur alle y.Durch (4.3) ist jeder Nichtbasisvektor mit Hilfe der Basis dargestellt. Jetzt wird

diese Darstellung auf die Basisvektoren ausgedehnt

aj = x1ja1 + . . . + xmjam, j = 1, . . . , n,

wobei

xij =

1 fur i = j0 fur i 6= j

, i = 1, . . . , m. (4.12)

Weiter gilt die Darstellung (4.4) fur zj , j = m + 1, . . . , n. Mit (4.12) hat maneine analoge Darstellung fur j = 1, . . . , m, die sich letztlich auf zj = cj reduziert.Zusammen mit der Voraussetzung gilt jetzt zj ≤ cj , j = 1, . . . , n. Mit (4.11) folgtnun

n∑

i=1

ziyi ≤ z∗. (4.13)

Nun wird in (4.10) die Darstellung aller Spaltenvektoren durch die ersten m Spal-tenvektoren eingesetzt

y1

m∑

i=1

xi1ai + y2

m∑

i=1

xi2ai + . . . + yn

m∑

i=1

xinai = b.

Durch Umordnung nach den Basisvektoren folgt

a1

n∑

j=1

yjx1j + a2

n∑

j=1

yjx2j + . . . + am

n∑

j=1

yjxmj = b. (4.14)

Analog schreibt man (4.13) mit Hilfe von (4.4) und der entsprechenden Darstellungfur j = 1, . . . , m, mit (4.12) (zj = cj , j = 1, . . . , m)

c1

n∑

j=1

yjx1j + c2

n∑

j=1

yjx2j + . . . + cm

n∑

j=1

yjxmj ≤ z∗ (4.15)

Der Vektor x ist eine zulassige Basislosung, das heißt, es gilt

a1x1 + a2x2 + . . . + amxm = b. (4.16)

Da a1, . . . , am eine Basis ist, ist die Darstellung von b mit Hilfe dieser Vektoreneindeutig. Damit folgt aus (4.14) und (4.16)

xi =

n∑

j=1

yjxij , i = 1, . . . , m.

Setzt man dies in (4.15), so erhalt man

z0 =

m∑

i=1

cixi ≤ z∗.

An dieser Stelle sollen die Ergebnisse und Beobachtungen dieses Abschnitts zu-sammengefasst werden:

• minx∈RncT x : Ax = b, x ≥ 0 ist zu losen.

• Man braucht eine erste Basis AB = (a1, . . . , am) mit der Basislosung xB =(x1, . . . , xm)T . Damit hat man auch einen Nichtbasisanteil AN = (am+1, . . . , an)und xN = (xm+1, . . . , xn)T . Auch der Kostenvektor wird in dieser Form zer-legt cT =

(cT

B , cTN

)= (c1, . . . , cm, cm+1, . . . , cn)T .

21

• Aus Ax = b folgt

ABxB + ANxN = b =⇒ xB = A−1B b− A−1

B ANxN .

Dieser Ausdruck wird in die zu minimierende Zielfunktion eingesetzt

cTB

(A−1

B b − A−1B ANxN

)+ cT

NxN → min .

Das heisst

cT x = cTBA−1

B b︸ ︷︷ ︸

konstant

−(cT

BA−1B AN − cT

N

)xN → min .

• 1. Fall: β = cTBA−1

B AN − cTN < 0. Dann folgt

cT x = cTBA−1

B b−

βm+1︸ ︷︷ ︸

<0

xm+1 + . . . + βn︸︷︷︸

<0

xn

→ min .

Das heißt, der Zielfunktionswert kann mit xi > 0 fur i = m + 1, . . . , n nichtverkleinert werden. Damit hat man Optimalitat erreicht.

• 2. Fall: cTBA−1

B AN − cTN ≤ 0 und βj = 0 fur mindestens einen Index j. Dann

ist das Optimum nicht eindeutig bestimmt.

• 3. Fall: cTBA−1

B AN − cTN 6< 0. Dann bewirkt die Aufnahme einer Nichtbasis-

variablen in die Basis eine Verkleinerung der Zielfunktion. Nun ist noch dieFrage zu klaren, welche Nichtbasisvariable man in die Basis aufnehmen soll,falls es mehrere Indizes j mit zj − cj > 0 gibt. In diesem Falle wahle man

zk − ck = maxj∈NBV,zj−cj>0

zj − cj .

Der Index der Basisvariablen, die aus der bisherigen Basis entfernt werdensoll, ist durch (4.7) gegeben.

22

Kapitel 5

Die Simplexmethode

Es werden folgende Bezeichnungen verwendet:

- das untersuchte Problem ist minx∈Rn

z = cT x : Ax = b,x ≥ 0

,

- die erste zulassige Basislosung sei x = (x1, x2, . . . , xm, 0, . . . , 0)T, x ≥ 0, mit

z0 = cT x,

- die Basisvektoren sind AB = (a1, . . . , am),- die Nichtbasisvektoren sind AN = (am+1, . . . , an),- die Darstellung der Nichtbasisvektoren durch die Basis ist

aj = x1ja1 + . . . xmjam, j = m + 1, . . . , n,

- die Hilfsgroßen zj sind

zj = c1x1j + c2x2j + . . . + cmxmj , j = m + 1, . . . , n.

Diese Großen werden in der sogenannten Simplextabelle eingetragen:

m + 1 m + 2 . . . k . . . ni ci xi cm+1 cm+2 . . . ck . . . cn

1 c1 x1 x1,m+1 x1,m+2 . . . x1,k . . . x1,n

2 c2 x2 x2,m+1 x2,m+2 . . . x2,k . . . x2,n

......

......

......

......

...l cl xl xl,m+1 xl,m+2 . . . xl,k . . . xl,n

......

......

......

......

...m cm xm xm,m+1 xm,m+2 . . . xm,k . . . xm,n

z0 zm+1 − cm+1 zm+2 − cm+2 . . . zk − ck . . . zn − cn

Basisteil Nichtbasisteil

Bei der Simplexmethode folgt man jetzt im wesentlichen dem Beweis des Haupt-satzes. Sei zk −ck > 0. Gilt fur mehrere Indizes j ∈ m+1, . . . , n, dass zj −cj > 0,so nehme man zum Beispiel einen Index, bei dem die Differenz maximal ist

zk − ck := maxj=m+1,...,n,

zj − cj .

Dann liegt xk als Nichtbasisvariable vor, die in die Basis soll. Nun bestimmt man

θ = mini=1,...,m,xik>0

xi

xik=:

xl

xlk,

das heißt, xl soll aus der Basis raus.

23

Definition 5.1 Hauptspalte, Hauptzeile, Hauptelement, Pivotelement. DieSpalte k nennt man Hauptspalte, die Zeile l heißt Hauptzeile und das Element xlk

heißt Hauptelement oder Pivotelement.

Die neue Basislosung sei

(x1, . . . , xl−1, xk, xl+1, . . . , xm, 0, . . . , 0)T

. (5.1)

Nun mussen die Elemente der neuen Simplextabelle bestimmt werden:

1. Man benotigt insbesondere eine Darstellung von (5.1). Aus (4.8) erhalt man

xi = xi −xl

xlkxik, i = 1, . . . , m; i 6= l; xk =

xl

xlk. (5.2)

2. Aus (4.3) folgt fur j = k

al =1

xlk(ak − x1ka1 − . . . − xl−1,kal−1 − xl+1,kal+1 − . . . − xmkam)

= −x1k

xlka1 − . . . − xl−1,k

xlkal−1 +

ak

xlk− xl+1,k

xlkal+1 − . . . − xmk

xmam. (5.3)

Damit haben wir eine Darstellung des bisherigen Basisvektors al durch dieneue Basis und die neuen Elemente der alten Hauptspalte sind

xkl =1

xlk, xil = −xik

xlk, i = 1, . . . , m, i 6= k. (5.4)

3. Fur den Rest erhalt man, beispielhaft an an gezeigt, die folgende Darstellung,wobei man in der ersten Gleichung die alte Basisdarstellung (4.3) nutzt:

an = x1na1 + . . . + xl−1,nal−1 + xl+1,nal+1 + . . . + xmnan + xln al︸︷︷︸

(5.3)

=

(

x1n − x1kxln

xlk

)

a1 + . . . +

(

xl−1,n − xl−1,kxln

xlk

)

al−1 +xln

xlkak

+ . . . +

(

xmn − xmkxln

xlk

)

am.

Man erhalt also

xkj =xlj

xlk, j = m + 1, . . . , n, j 6= k, (5.5)

xij = xij −xlj

xlk︸︷︷︸

xkj

xik , i = 1, . . . , m, i 6= k, j = m + 1, . . . , n, j 6= l.(5.6)

4. Die Elemente z0, zm+1−cm+1, . . . , zn−cn transformieren sich ebenfalls nachden obigen Regeln.

Damit sind alle Elemente der neuen Simplextabelle berechnet. Zur Berechnungvon xij benotigt man die im Rechteck angeordneten Elemente xij , xlj , xlk und xik

der alten Simplextabelle. Deshalb spricht man auch von der Rechteckregel.Die Basisform der Simplexmethode ist wie folgt:

24

1. Normalform des linearen Programms herstellen.2. erste zulassige Basislosung angeben.3. Simplextabelle zu dieser Basislosung erstellen.4. Existieren Bewertungen zj − cj > 0? Wenn ja, gehe zu 6.

5. Sind alle Bewertungen zj − cj < 0? Wenn ja, einzige Optimallosung ge-funden, Simplexmethode beendet. Wenn nicht, gibt es außer negativen Be-wertungen zj − cj nur noch verschwindende, dann ist das Optimum nichteindeutig. Man hat ein Optimum gefunden, beende Simplexmethode.

6. Wahle die Hauptspalte, also die Spalte, zu der das großte zj − cj > 0,j = k gehort.

7. Falls xik ≤ 0 fur alle i = 1, . . . , m, so ist die Zielfunktion nach unten nichtbeschrankt, beende Simplexmethode.

8. Bestimme θ zur Festlegung der Hauptzeile und des Pivotelements.

9. Basistransformation:

9.1 Ersetze das Pivotelement durch seinen Kehrwert, siehe (5.4).9.2 Multipliziere die ubrigen Elemente der Hauptzeile mit diesem Kehr-

wert, einschließlich xl, siehe (5.2) und (5.5).9.3 Multipliziere die ubrigen Elemente der Hauptspalte mit dem nega-

tiven Kehrwert, siehe (5.4).9.4 Vermindere die nicht in einer Hauptreihe stehenden Elemente, ein-

schließlich der ubrigen Werte von xi und der letzten Zeile, umdas Produkt der zugehorigen Hauptreihenelemente (Rechteckregel).Dabei nimmt man fur das Pivotelement schon den neuen Wert undfur die ubrigen Elemente die alten Werte, siehe (5.2) und (5.6).

10. Gehe zu 4.

Beispiel 5.2 Wir betrachten das lineare Programm

z = −3x1 − 2x2 − 4x3 − x4 → min !

2 2 3 0 1 0 01 3 0 2 0 1 01 1 5 2 0 0 1

x1

x2

x3

x4

x5

x6

x7

=

700400500

x ≥ 0.

Bekannt sei eine erste zulassige Basislosung x1 = 350, x4 = 25, x7 = 100, die denZielfunktionswert z = −1075 besitzt. Die Basisvektoren sind demzufolge

a1 =

211

, a4 =

022

, a7 =

001

.

Gesucht ist nun die Darstellung der Nichtbasisvektoren durch die Basisvektoren.Setze AB = (a1, a4, a7) und AN = (a2, a3, a4, a5). Dann ist die Matrix X derSimplexkoeffizienten gesucht, fur die gilt

AN = ABX =⇒ X = A−1B AN .

Man erhalt hier

X =

1 3/2 1/2 01 −3/4 −1/4 1/2−2 5 0 −1

.

25

Daraus ergibt sich

z2 = c1x12 + c4x42 + c7x72 = −3 ∗ 1 + (−1) ∗ 1 + 0 ∗ (−2) = −4,

z3 = −9/2 + 3/4 + 0 = −15/4,

z5 = −3/2 + 1/4 + 0 = −5/4,

z6 = 0 − 1/2 + 0 = −1/2

und somit

z2 − c2 = −2, z3 − c3 = 1/4, z5 − c5 = −5/4, z6 − c6 = −1/2.

Damit erhalt man folgende Simplextabelle:

2 3 5 6i ci xi -2 -4 0 01 -3 350 1 3/2 1/2 04 -1 25 1 -3/4 -1/4 1/2

7 0 100 -2 5 0 -1

-1075 -2 1/4 -5/4 -1/2

Es gibt nur einen Index k mit zk−ck > 0, namlich k = 3. Damit ist die Hauptspaltebestimmt (Schritt 6). Zur Bestimmung der Hauptzeile (Schritt 8) berechnet man θ:

θ = minxi3>0,i∈1,4,7

(xi

xi3

)

= min

350

3/2,100

5

= 20

fur i = 7. Damit ist der Hauptzeilenindex l = 7 und das Pivotelement x73 = 5. Nunfuhrt man die Basistransformation aus (Schritt 9):

2 7 5 6i ci xi -2 0 0 01 -3 320 8/5 -3/10 1/2 3/104 -1 40 7/10 3/20 -1/4 7/203 -4 20 -2/5 1/5 0 -1/5

-1080 -19/10 -1/20 -5/4 -9/20

Den neuen Wert fur x1 erhalt man beispielsweise aus

x1 = 350− 3

2100

1

5= 350− 30 = 320.

Da in der neuen Simplextabelle alle Werte zj − cj < 0, j ∈ 2, 5, 6, 7, hat man die

einzige Optimallosung bestimme: x = (320, 0, 20, 40, 0, 0, 0)T. 2

Bemerkung 5.3 Angenommen, man hat in einer Simplextabelle mehrere zj−cj >0. Zu einer dieser Spalten mogen nur Koeffizienten xij ≤ 0 gehoren. Dann ist dieZielfunktion unbeschrankt. 2

Beispiel 5.4 Zur Ausartung. Wir betrachten das lineare Programm

z = −x1 → min !

(1 1 1 04 1 0 1

)

x1

x2

x3

x4

=

(14

)

x ≥ 0.

26

Eine zulassige Basislosung, die gleichzeitig ein Optimum ist, ist x = (1, 0, 0, 0)T .Wir nehmen als Basisvariablen x1 und x2. Da x2 verschwindet, ist die Basislosungausgeartet. Man hat

AB =

(1 14 1

)

, AN =

(1 00 1

)

und erhalt die Simplextabelle

3 4i ci xi 0 01 -1 1 -1/3 1/32 0 0 4/3 -1/3

-1 1/3 -1/3

Gemaß Simplexmethode muss x3 in die Basis anstelle von x2 eingefuhrt werden.Man erhalt die Simplextabelle

2 4i ci xi 0 01 -1 1 1/4 1/43 0 0 3/4 -1/4

-1 -1/4 -1/4

Damit ist das Optimalitatskriterium der Simplexmethode erfullt und diese wirdbeendet. Man hat fur das Optimum x = (1, 0, 0, 0)T mit diesen beiden Simplexta-bellen zwei unterschiedliche Basisdarstellungen. Der Zielfunktionswert hat sich imSimplexschritt nicht verandert, es wurde lediglich die Basis gewechselt. 2

27

Kapitel 6

Bestimmung einer erstenzulassigen Basislosung

Ein Problem, was man fur die Durchfuhrung der Simplexmethode losen muss, istdie Bestimmung einer ersten zulassigen Basislosung. Wie gut das geht, hangt auchvom konkreten Problem ab.

1. Fall. Liegtminx∈Rn

z = cT x : Ax ≤ b,x ≥ 0

vor und gilt b ≥ 0. Dann fuhrt man Schlupfvariablen ein und setzt x = (0, . . . , 0,bT )T .

2. Fall. Liegt das lineare Optimierungsproblem in der Gestalt

minx∈Rn

z = cT x : Ax = b,x ≥ 0

vor mit A = (aij) , i = 1, . . . , m; j = 1, . . . , n, b = (b1, . . . , bm)T, aij ≥ 0, bi ≥ 0

fur alle i, j. Dann kann man mit einer sogenannten Engpassmethode zur erstenzulassigen Basislosung gelangen:

1. Ordne die Variablen nach wachsenden Zielfunktionskoeffizienten ci, Beispiel

z = −10x1 − 6x2 − 4x3 − 3x4 − 5x5 → min !

2 0 4 0 2 1 0 0 02 3 1 0 0 0 1 0 05 0 0 2 1 0 0 1 00 0 0 3 0 0 0 0 1

x1

x2

...x9

=

86208

x ≥ 0.

Dann ist die Ordnung x1, x2, x5, x3, x4.2. In der festgelegten Reihenfolge werden die Variablen mit dem großtmoglichen

Wert genommen, so dass die Nebenbedingungen erfullt sind. Im Beispielbeginnt man mit x1 = 3

3. Man setzt diesen Wert ein und entfernt die Variable damit aus den Neben-bedingungen. Im Beispiel ergibt sich

0 4 0 2 1 0 0 03 1 0 0 0 1 0 00 0 2 1 0 0 1 00 0 3 0 0 0 0 1

x2

x3

...x9

=

2058

.

28

Aus der zweiten Gleichung folgt x2 = x3 = x7 = 0, welche Werte man auchgleich einsetzen kann. Damit vereinfacht sich das System der Nebenbedin-gungen zu

0 2 1 0 00 0 0 0 02 1 0 1 03 0 0 0 1

x4

x5

x6

x8

x9

=

2058

. (6.1)

4. Gehe zu 2.

Im Beispiel betrachtet man als nachstes x5, da ja bereits x2 = 0 gilt. Der maxi-male Wert von x5, so dass (6.1) erfullt ist, betragt x5 = 1. Einsetzen ergibt

0 1 0 02 0 1 03 0 0 1

x4

x6

x8

x9

=

048

. (6.2)

Damit folgt x6 = 0. Da ja auch schon x3 = 0 gilt, wird nun x4 betrachtet. Dermaximale Wert von x4, so dass (6.2) erfullt ist, ist x4 = 2. Man erhalt

(1 00 1

)(x8

x9

)

=

(02

)

.

Nun bestimmt man die letzten beiden Werte und erhalt als erste zulassige Ba-sislosung x = (3, 0, 0, 2, 1, 0, 0, 0, 2)T .

Bemerkung 6.1 Hat man bei der Engpassmethode nicht genugend Variablen,dann fuhrt man kunstliche Variablen ein. 2

Bemerkung 6.2 Anderes Ordnungsprinzip der Variablen im Fall, dass die Ko-effizienten von unterschiedlicher Großenordnung sind. Wir betrachten das lineareOptimierungsproblem

z = 10x1 + 20x2 + 30x3 + 40x4 + 50x5 → min !

(1 10 50 1 02 20 50 0 1

)

x1

x2

...x5

=

(100101

)

x ≥ 0.

Nach dem obigen Ordnungsprinzip hat man die Reihenfolge x1, x2, x3, x4, x5 underhalt mit der Engpassmethode die erste zulassige Basislosung Ubungsaufgabe

x1 =101

2, x4 =

99

2=⇒ z0 = 2485.

Man erhalt jedoch mit einer anderen Basislosung einen schon viel kleineren Ziel-funktionswert

x3 = 2, x5 = 1 =⇒ z0 = 110.

In diesem Fall ist das Ordnungsprinzip

minj,cj 6=0

cj mini,aij 6=0

bi

aij

gunstiger. 2

29

3. Fall. Die erste zulassige Basislosung soll jetzt

- ohne spezielle Voraussetzungen und- mit Hilfe der Simplexmethode

bestimmt werden. Dazu betrachten wir

n∑

j=1

cjxj = cT x → min ! (6.3)

Ax = b, (6.4)

x ≥ 0. (6.5)

und nehmen b ≥ 0 an. Das kann immer durch Multiplikation der entsprechendenGleichungen mit einer negativen Zahl erreicht werden. Dem Problem (6.3) – (6.5)wird die Hilfsaufgabe

m∑

i=1

xn+i → min ! (6.6)

n∑

j=1

aijxj + xn+i = bi, i = 1, . . . , m, (6.7)

xj ≥ 0, j = 1, . . . , m + n (6.8)

zugeordnet. Die Variablen xn+1, . . . , xn+m heißen kunstliche Variablen. Zur Bestim-mung der ersten zulassigen Basislosung von (6.3) – (6.5) wird eine Zweiphasenme-thode verwendet:

• 1. Phase. Wahle als erste zulassige Basislosung fur (6.6) – (6.8) xi = 0,i = 1, . . . , n, xn+i = bi, i = 1, . . . , m.

• 2. Phase. Lose (6.6) – (6.8) mit der Simplexmethode.

Es stellt sich nun die Frage, ob man auf diesem Wege schließlich eine erste zulassigeBasislosung fur (6.3) – (6.5) erhalt.

Im nachsten Satz wird gezeigt, dass die Losung von (6.6) – (6.8) nicht ausgeartetist.

Lemma 6.3 Unter der Annahme, dass (6.6) – (6.8) keine ausgearteten Basislosun-gen besitzt, liefert die Simplexmethode nach endlich vielen Schritten eine optimaleLosung des linearen Optimierungsproblems (6.6) – (6.8).

Beweis: Da Ausartung per Annahme ausgeschlossen ist, kann kein Basiszyklusauftreten. Es ist dann nur noch die Beschranktheit von unten der Zielfunktion (6.6)uber (6.7) bis (6.8) zu zeigen. Das ist offensichtlich, da (6.6) eine Summe nichtne-gativer reeller Zahlen ist, die durch Null nach unten beschrankt ist.

Nun wird eine Bedingung angegeben, mit welcher man aus dem Optimum desHilfsproblems (6.6) – (6.8) eine erste zulassige Basislosung von (6.3) – (6.5) erhalt.

Satz 6.4 Sei x0 eine Optimallosung der kunstlichen Aufgabe (6.6) – (6.8) mit demzugehorigen Zielfunktionswert z0. Gilt z0 = 0, so ist sind die ersten n Komponentenvon x0 eine zulassige Basislosung der Aufgabe (6.3) – (6.5). Gilt jedoch z0 > 0, sobesitzt (6.3) – (6.5) keine zulassige Basislosung.

Beweis: Aus z0 = 0 folgt xn+i = 0, i = 1, . . . , m, das heißt im Optimumverschwinden alle kunstlichen Variablen. Also hat x0 die Gestalt

x0 = (x1, . . . , xn, 0, . . . , 0︸ ︷︷ ︸

m

)T .

Da x0 mit der Simplexmethode konstruiert wurde, folgt dass x0 eine zulassige Ba-sislosung von (6.3) – (6.5) ist.

30

Sei nun z0 > 0. Der Beweis wird indirekt gefuhrt, das heißt, wir nehmen an,dass (6.3) – (6.5) die zulassige Basislosung x = (x1, . . . , xn)T besitzt. Dann besitztjedoch (6.6) – (6.8) die zulassige Basislosung (x1, . . . , xn, 0, . . . , 0)T mit dem zu-gehorigen Zielfunktionswert (6.6) z = 0. Das ist im Widerspruch zur Annahme dassz0 der minimale Wert ist.

4. Fall. Die M–Methode. Es wird das lineare Optimierungsproblem (6.3) – (6.5)betrachtet und diesem die folgende Hilfsaufgabe zugeordnet

n∑

j=1

cjxj + M

m∑

i=1

xn+i → min ! (6.9)

n∑

j=1

aijxj + xn+i = bi i = 1, . . . , m , (6.10)

x ≥ 0. (6.11)

Bei dieser Aufgabe muss der Straffaktor M > 0 hinreichend groß gewahlt wer-den, damit im Optimum die Variablen xn+1, . . . , xn+m verschwinden. Das Problembesteht darin, dass man im allgemeinen nicht von vornherein festlegen kann, wiegroß M zu wahlen ist. Moglich sind Aussagen folgender Gestalt:

Satz 6.5 Es existiert ein M0 > 0, so dass fur alle M > M0 aus der Losbarkeitvon (6.3) – (6.5) die Losbarkeit von (6.9) – (6.11) mit xn+1 = . . . = xn+m = 0folgt.

Beweis: Siehe Literatur.Der Vorteil der M–Methode im Vergleich zur Herangehensweise von Fall 3 wird

mit folgendem Satz beschrieben.

Satz 6.6 Falls (6.9) – (6.11) eine Losung

x = (x1, . . . , xn, 0, . . . , 0︸ ︷︷ ︸

m

)T .

besitzt, so ist x = (x1, . . . , xn)T bereits eine Optimallosung von (6.3) – (6.5).

Beweis: Siehe Literatur.

31

Kapitel 7

Zur Ausartung

Nach Definition 3.4 liegt Ausartung dann vor, wenn mindestens eine der Variablenxi, i = 1 . . . , m, einer zulassigen Basislosung verschwindet. Das dahinterliegendeProblem ist, dass die Zuordnung Ecke – zulassige Basislosung nicht eindeutig ist.Eine Ecke des Polyeders kann Basislosung zu verschiedenen Basen sein. Das kannaber nur bei ausgearteten Basislosungen auftreten. Aus der Ausartung einer zulassi-gen Basislosung folgt jedoch nicht unbedingt, dass zu der entsprechenden Ecke mehrals eine zulassige Basislosung gehort.

Beispiel 7.1 Betrachte das lineare Programm mit

z = x1 + x2 − x3 → min !, A =

(1 −1 00 0 1

)

, b =

(01

)

.

Der einzige Extremalpunkt ist x = (0, 0, 1)T . Zulassige Basen sind(

10

)

,

(01

)

und

(−10

)

,

(01

)

.

Der Grund fur die Nichteindeutigkeit der Basis besteht darin, dass es zu viele Un-gleichungen gibt, die den Extremalpunkt bestimmen. In diesem Beispiel ist er durchdie beiden Gleichungen

(1 00 1

)(x1

x2

)

=

(01

)

und

(−1 00 1

)(x1

x2

)

=

(01

)

gleichermaßen gegeben. Das haben wir bereits in den Beispielen 3.5 (2. Teil) und 5.4gesehen. 2

In der Praxis stellt sich heraus, dass die meisten zu losenden linearen Programmeausgeartet sind.

In der Simplexmethode ist es moglich, dass im Falle der Ausartung der zulassi-gen Basislosung nur ein Basiswechsel stattfindet, siehe Beispiel5.4. Das kann zueinem unendlichen Zyklus werden, einem sogenannten Basiszyklus. Es ist jedochmoglich, Ausartung prinzipiell auszuschließen beziehungsweise einen Basiszyklus zuumgehen. Im wesentlichen gibt es dazu zwei Techniken:

- die Methode der ε–Storung,- die lexikographische Simplexmethode.

7.1 Die Methode der ε–Storung

Wir betrachten das lineare Optimierungsproblem

minx∈Rn

cT x : Ax = b, x ≥ 0

. (7.1)

32

Sei x = (x1, . . . , xm, 0, . . . , 0)T eine zulassige Basislosung mit den Basisvektorena1, . . . , am:

a1x1 + . . . + amxm = b,

a1x1j + . . . + amxmj = aj , j = 1, . . . , n. (7.2)

Sei ε > 0 vorgegeben und sie AB = (a1, . . . , am) die Matrix der Basisvektoren.Dann betrachtet man anstelle (7.1) ein lineares Programm mit gestorten Nebenbe-dingungen

cT x → min !

ABx +

n∑

j=1

εj(7.2) = b =⇒ (7.3)

ABx +

n∑

j=1

εjaj = a1

x1 +

n∑

j=1

x1jεj

+ . . . + am

xm +

n∑

j=1

xmjεj

= b.

Mit den Nebenbedingungen (7.3) hat man fur hinreichend kleines ε die zulassigeBasislosung

x(ε)i := xi +

n∑

j=1

xijεj = xi + εi +

n∑

j=m+1

xijεj ,

da fur i = 1, . . . , m gilt xij = δij . Die Eigenschaft der Basislosung folgt daraus,dass die Basis nicht geandert wurde und die Nebenbedingung in (7.3) erfullt ist.Die Zulassigkeit folgt aus εi > 0 und εi εj fur i < j und hinreichend kleines ε.Der zugehorige Zielfunktionswert ist

z(ε)0 =

m∑

i=1

cixi +

m∑

i=1

ci

n∑

j=1

xijεj

=

m∑

i=1

cixi +

n∑

j=1

(m∑

i=1

cixij

)

εj

=

m∑

i=1

cixi +

n∑

j=1

zjεj .

Im Bild wird die Storung der Nebenbedingungen graphisch veranschaulicht. Imdicken Punkt schneiden sich drei Geraden. Das fuhrt dazu, dass die ZuordnungEcke – Basislosung nicht eindeutig ist. Man hat Ausartung. Durch die Storungder Nebenbedingungen (durchgezogene Geraden) erreicht man, dass es nur nochSchnittpunkte mit genau zwei Geraden gibt.

33

Bemerkung 7.2 Berechnung von θ. In der Simplexmethode benotigt man dieGroße θ, siehe (4.7). Sei zk − ck > 0. Dann berechnet sich θ in der Methode derε–Storung durch

θ = mini=1,...,m;xik>0

x(ε)i

xik= min

i=1,...,m;xik>0

xi + εi +∑n

j=m+1 xijεj

xik. (7.4)

2

Satz 7.3 Sei x = (x1, . . . , xm, 0, . . . , 0)T eine zulassige Basislosung der Original-aufgabe (7.1). Falls

θ = mini=1,...,m;xik>0

xi

xik= 0

gilt (Ausartung), dann gibt es ein ε > 0 dergestalt, dass

θ = mini=1,...,m;xik>0

x(ε)i

xik=

x(ε)l

xlk> 0 ∀ ε ∈ (0, ε) (7.5)

und der Index l ist im gestorten Problem (7.3) eindeutig bestimmt.

Beweis: Aus den Vorbetrachtungen folgt x(ε)i > 0 und damit θ > 0 in (7.5) fur

ε ∈ (0, ε).Die Eindeutigkeit von l wird indirekt bewiesen. Sei l also nicht eindeutig be-

stimmt, das heißt es gibt zwei Indizes l1 6= l2 mit

xl1 + εl1 +∑n

j=m+1 xl1jεj

xl1k=

xl2 + εl2 +∑n

j=m+1 xl2jεj

xl2k

fur alle ε ∈ (0, ε). Die beiden Terme sind Polynome in ε. Diese sind genau dann gleichfur alle ε ∈ (0, ε), wenn sie in allen Koeffizienten ubereinstimmen. Insbesonderemussen die Koeffizienten vor den Termen mit Potenz l1 und l2 gleich sein. Ist l1 6=l2, so ist fur den linken Term der Koeffizient vor εl1 ungleich Null und fur denrechten Term gleich Null. Fur den Koeffizienten vor εl2 gilt sinngemaß das gleiche.Diese Koeffizienten konnen nur dann gleich sein, wenn l1 = l2, im Widerspruch zurAnnahme.

Prinzipiell kann diese Manipulation in jedem Simplexschritt durchgefuhrt wer-den und man kann damit sichern, dass l stets eindeutig bestimmt ist. Diese Vorge-hensweise ist fur jeden Eckpunkt des zulassigen Bereichs ausgefuhrt zu denken. Dadie Anzahl der Eckpunkte endlich ist, erhalt man folgenden Satz.

Satz 7.4 Zu jedem linearen Optimierungsproblem existiert bei geeigneter Wahl vonε ∈ (0, ε∗) ein gestortes lineares Optimierungsproblem, so dass dieses keine ausgear-tete zulassige Basislosung besitzt. Fur ε → 0 konvergiert das Optimum des gestortenProblems (7.3) zum Optimum des Originalproblems (7.1).

Bemerkung 7.5 Praktische Umsetzung der Methode der ε–Storung. Trotz dieserschonen Theorie macht man das alles bei praktischen Problemen nicht. Fur diesewird vorgeschlagen: Falls in einer zulassigen Basislosung wenigstens ein Wert xi = 0bestimmt wurde, so kann θ = 0 sein. Wahle dann

l = minxik>0

i : xi = 0,

wobei i uber alle Basisvariablen lauft und k der Index der festgelegten Hauptspalteist, und transformiere mit diesem Index l. Theoretisch besteht die Gefahr einesZyklus, in der Praxis ist das aber eher unwahrscheinlich. 2

34

7.2 Die lexikographische Simplexmethode

Bei der lexikographischen Simplexmethode erfolgt die Auswahl der zu tauschendenBasisvektoren so, dass keine Wiederholungen auftreten konnen.

Definition 7.6 Lexikopositiver Vektor. Ein Vektor x ∈ Rn heißt lexikopositiv,falls x = (0, . . . , 0, xi, xi+1, . . . , xm)T mit i ≥ 1 und xi > 0. Das heißt, die erste vonNull verschwindende Komponente ist positiv. Die Schreibweise ist

x >l 0.

Sei y ∈ Rn. Dann ist y >l x genau dann, wenn y − x >l 0.

Wir betrachten das lineare Programm (7.1) mit rg(A) = m. Sei

xB = (x1, . . . , xm, 0, . . . , 0)T

eine zulassige Basislosung. Die zugehorige Matrix der Basisvektoren sei AB ∈ Rm×m

und die der Nichtbasisvektoren AN . Dann sind die Zeilen der Matrix

(b, A) := A−1B (b, A) = A−1

B (b, AB , AN ) ∈ Rm×(n+1)

lexikopositiv, daA−1

B (b, A) = (xB , Im, am+1, . . . , an) ,

xB ≥ 0 und Im die Einheitsmatrix des Rm×m ist. Falls die Basisvariablen nicht dieersten m Variablen sind, dann ordnet man sie nach vorn.

Anstelle von (4.7) wird bei der lexikographischen Simplexmethode der Index ldurch

θ = min>l;i=1,...,m,xik>0

eTi (b, A)

xik=:

eTl (b, A)

xlk

bestimmt, wobei ei ∈ Rm der Einheitsvektor ist, der in der i–ten Komponente eineEins hat. Das heißt, das Minimum wird bezuglich der lexikographischen Ordnunggenommen. Das obige Symbol bedeutet, dass man sich wie ublich alle Eintragemit xik > 0 ansieht, die zugehorigen Vektoren eT

i (b, A) bildet, durch xik dividiertund von den so erhaltenen Vektoren den lexikographisch kleinsten nimmt, um l zubestimmen. Es gilt, siehe beispielsweise [JS04]:

- Falls l in der allgemeinen Simplexmethode (4.7) eindeutig bestimmt ist,erhalt man bei der lexikographischen Simplexmethode den gleichen Index.

- Die lexikographische Simplexmethode definiert einen eindeutigen Index l.Man kann zeigen, dass eine Nichteindeutigkeit im Widerspruch zu rg(A) = msteht.

- Das Ergebnis eines lexikographischen Simplexschrittes ist wiederum eine le-xikopositive Basis.

- Bei der neuen Basislosung ist entweder der Zielfunktionswert kleiner oder dieDifferenz der Koeffizienten der Zielfunktion der neuen und der alten Basis istlexikopositiv. Im ersten Fall hat man die Ecke verlassen. Im zweiten Fall kannes bei weiteren lexikographischen Simplexschritten nicht passieren, dass diealte Basis noch einmal verwendet wird. Ein Basiszyklus ist ausgeschlossen.

Bei der lexikographischen Simplexmethode werden also ausgehend von einer le-xikopositiven Startlosung weitere lexikopositive Losungen erzeugt. Dieses Verfahrenist endlich. Es bricht entweder mit einer Losung des Optimierungsproblems ab, oderes wird gefunden, dass die Zielfunktion nicht nach unten beschrankt ist. Die Anzahlder Schritte kann n! nicht ubersteigen. Diese Schranke ist allerdings fur großereWerte von n fur die Praxis bedeutungslos.

35

Kapitel 8

Zur Effizienz derSimplexmethode

Die Simplexmethode ist ein Verfahren zur Bestimmung der Losung des linearenProgramms

minx∈Rn

cT x : Ax = b, x ≤ 0

.

Fur ihre praktische Anwendung muss untersucht werden, wie teuer die Berechnungdes Optimums ist. Dazu unterscheidet man zwei Situationen:

- Analyse des schlimmsten Falls, der bei der Losung eines linearen Programmsmit der Simplexmethode auftreten kann, worst case Modell,

- Analyse des in der Praxis zu erwartenden normalen Falls, der bei der Losungeines linearen Programms mit der Simplexmethode auftreten kann, real worldModell.

Die zweite Situation ist an sich interessanter. Das Problem besteht darin, ein realworld model aufzustellen. Diese Frage ist bis heute teilweise ungeklart. In der prak-tischen Anwendung der Simplexmethode hat man jedoch die Erfahrung gewonnen,dass sie im Normalfall hervorragend funktioniert. Wir werden hier nur das worstcase Modell untersuchen.

8.1 Maße fur die Effizienz

Das Grundanliegen besteht darin, den Aufwand zur Abarbeitung eines numerischenVerfahrens in Abhangigkeit vom Umfang der Eingangsdaten abzuschatzen.

Definition 8.1 compl(A,B). Die Komplexitat compl(A,B) eines Algorithmus Azur Losung von Aufgaben B (eines Problemkreises P) ist die Anzahl der elementarenOperationen auf einem Computer oder die benotigte Rechenzeit in Abhangigkeitvom Umfang der Eingangsdaten. 2

Der Wunsch ist naturlich, einen effizienten Algorithmus fur jedes praxisrelevan-te Optimierungsproblem zu konstruieren. Das geht aber im allgemeinen nicht, daschwierige und auch unlosbare Probleme existieren.

Definition 8.2 P(d). Bezeichne P ein Problem und d den Umfang seiner Ein-gangsdaten. Dann beschreibt P(d) die Menge aller Aufgaben P mit gleichem Um-fang d der Eingangsdaten. 2

36

Definition 8.3 Worst case Komplexitat eines Algorithmus. Die worst caseKomplexitat eines Algorithmus A zur Losung eines Problems P ist gegeben durch

w–compl(A, P ) = maxB∈P (d)

compl(A, B).

2

Man kann entsprechend eine average case Komplexitat von A bezuglich P er-klaren

a–compl(A, P ) = ErwartungswertB∈P (d)compl(A, B).

Definition 8.4 Worst case Komplexitat eines Problems. Sei AP die Mengealler Algorithmen zur Losung eines Problems P. Die worst case Komplexitat von Pist erklart durch

w–compl(P ) = minA∈AP

w–compl(A, P ).

2

Die Komplexitat wird im allgemeinen als Funktion der Menge der Eingangsdatenin der Form O(f(d)) angegeben.

Beispiel 8.5 Matrizenmultiplikation. Gegeben seien zwei Matrizen A, B ∈ Rn×n

und gesucht ist das Produkt C = AB. Ein Eintrag von C berechnet sich wie folgt

cij =

n∑

k=1

aikbkj ,

benotigt also n Multiplikationen und (n − 1) Additionen, dass heißt O(n) Opera-tionen. Die Anzahl der zu berechnenden Eintrage von C ist n2. Somit hat maninsgesamt O(n3) Operationen durchzufuhren.

Die Frage ist, ob der Aufwand von O(n3) optimal ist. Da man insgesamt n2

Großen zu berechnen hat, kann der minimale Aufwand der Matrizenmultiplikationnicht kleiner als O(n2) sein. Man kennt heute Verfahren, deren Aufwand fur große nwie O(n2.38) ist. (SIAM News 38, Vol. 9, 2005) 2

Definition 8.6 Gutartiges Problem. Probleme mit polynomialer KomplexitatO(dz), z ∈ R, heißen gutartig, Probleme mit exponentieller Komplexitat O(zd),z ∈ R, z > 1, bosartig. 2

8.2 Zur worst case Komplexitat der Simplexme-thode

In diesem Abschnitt wird ein Beispiel konstruiert, bei welchem der Aufwand derSimplexmethode exponentiell wachst. Das bedeutet, dass die Simplexmethode theo-retisch ein sehr ineffizientes Verfahren sein kann. Dieser Fall ist in der Praxis gluck-licherweise faktisch nicht zu beobachten.

Bei der worst case Komplexitat wird der schlechteste Fall betrachtet. Fur dieSimplexmethode bedeutet das, dass die schlechteste Wahl der Hauptspalte bezuglichder Anzahl der zulassigen Basislosungen betrachtet wird, die man beim Transfor-mationsprozess erzeugt.

Wie betrachten den n–dimensionalen Einheitswurfel [0, 1]n. Dieser hat 2n Ecken.Die Koordinaten des Einheitswurfels werden nun gestort

ε ≤ x1 ≤ 1 mit 0 < ε < 1/2,

εxj−1 ≤ xj ≤ 1− εxj−1 ≤ 1 j = 2, . . . , n.

37

Uber diesem gestorten Wurfel wird folgendes lineares Programm definiert:

−xn → min !

x1 − r1 = ε

x1 + s1 = 1

xj − εxj−1 − rj = 0 j = 2, . . . , n, (8.1)

xj + εxj−1 + sj = 1 j = 2, . . . , n,

xj , rj , sj ≥ 0 j = 1, . . . , n.

Die Matrix der Nebenbedingungen hat die Gestalt

A =

1 0 0 . . . 0 −1 0 . . . 0 0 0 . . . 0−ε 1 0 . . . 0 0 −1 . . . 0 0 0 . . . 0...

......

......

......

......

......

......

0 0 0 . . . 1 0 0 . . . −1 0 0 . . . 01 0 0 . . . 0 0 0 . . . 0 1 0 . . . 0ε 1 0 . . . 0 0 0 . . . 0 0 1 . . . 0...

......

......

......

......

......

......

0 0 0 . . . 1 0 0 . . . 0 0 0 . . . 1

∈ R2n×3n.

Lemma 8.7 Die Menge der zulassigen Basislosungen von (8.1) ist die Klasse derUntermengen von

(x1, . . . , xn, r1, . . . , rn, s1, . . . , sn) ,

bei denen alle xj > 0, j = 1, . . . , n, und entweder rj > 0 oder sj > 0 fur jedesj = 1, . . . , n. Alle Basislosungen sind nicht ausgeartet.

Beweis: Es wird erst die Zulassigkeit untersucht, dann die Basislosungseigen-schaft.

Zuerst wird gezeigt, dass fur zulassige Losungen alle xj , j = 1, . . . , n positivsein mussen. Ist x1 = 0, dann folgt aus der ersten Nebenbedingung r1 = −ε < 0.Ein Vektor mit x1 = 0 kann also nicht zulassig sein. Der Beweis erfolgt nun durchInduktion. Seien xj > 0 fur j = 1, . . . , k − 1 und xk = 0. Dann folgt aus denNebenbedingungen

0 = xk = rk + εxk−1︸ ︷︷ ︸

>0

=⇒ rk < 0,

im Widerspruch zur letzten Nebenbedingung. Also sind alle xj positiv, sie konnendamit keine Nichtbasisvariablen sein.

Nun werden die rj , sj betrachtet. Gelte fur ein j, dass rj = sj = 0. Fur j = 1folgt dann aus den ersten beiden Nebenbedingungen von (8.1) x1 = ε = 1. Dassteht im Widerspruch zur Wahl von ε. Sei j > 1. Dann gelten

xj − εxj−1 = 0,

xj + εxj−1 = 1.

Subtraktion dieser Gleichungen ergibt

2εxj−1 = 1.

Da jedoch ε < 1/2 und xj−1 ≤ 1 ist die linke Seite echt kleiner als 1. Damit sindrj oder sj fur jedes j = 1, . . . , n, positiv. Da man genau 2n Basisvariablen hat

38

und bereits n davon durch die xj gegeben sind, ist entweder rj oder sj fur jedesj = 1, . . . , n, positiv.

Die Basiseigenschaft der soeben konstruierten Menge sieht man durch Umord-nung der Zeilen der Matrix A2n,2n. Fur jeden Index j vertauscht man die Zeilen jund j + n falls rj > 0, sj = 0. Damit wird die Matrix auf Dreiecksform gebracht,wobei in der Diagonalen ±1 stehen. Ihre Determinante ist somit ebenfalls ±1.

Die Menge der Indizes j fur die die Basislosungen rj > 0 erfullen wird mit Sbezeichnet. Sind dies beispielsweise die Indizes 1, 3, 7, so ist S = 1, 3, 7. Die zu-gehorigen Basislosungen werden als x(S) geschrieben, im Beispiel x(1,3,7). Der

Wert xj in x(S) wird mit x(S)j bezeichnet. Wegen der Zielfunktion betrachten wir

jetzt insbesondere den letzten Index n.

Lemma 8.8 Seien n ∈ S und n 6∈ S′. Dann ist x(S)n > x

(S′)n . Falls außerdem

S′ = S \ n gilt, folgt x(S′)n = 1 − x

(S)n .

Beweis: Sei n ∈ S, das heißt rn > 0, sn = 0. Dann folgt aus

x(S)n + εx

(S)n−1 + sn = 1 =⇒ x(S)

n = 1 − εx(S)n−1 > 1/2

wegen x(S)n−1 ≤ 1, ε < 1/2.

Andererseits gilt fur n 6∈ S′, dass rn = 0. Mit denselben Argumenten folgt

x(S′)n − εx

(S′)n−1 + rn = 0 =⇒ x(S′)

n = εx(S′)n−1 < 1/2.

Die Mengen in der zweiten Aussage des Lemmas unterscheiden sich nur dadurch,dass in S gilt rn > 0, sn = 0 und in S′ gilt rn = 0, sn > 0. Da alle anderen Indizesin S und S′ gleich sind und die Nebenbedingungen fur die Indizes kleiner n nichtvon xn, rn, sn abhangen, gilt insbesondere

x(S)n−1 = x

(S′)n−1.

Da rn = 0 fur S′ und sn = 0 fur S ist, folgt

x(S′)n = εx

(S′)n−1 = 1 −

(

1 − εx(S′)n−1

)

= 1 −(

1 − εx(S)n−1

)

= 1 − x(S)n .

Lemma 8.9 Die Untermengen von 1, 2, . . . , n seien so geordnet, dass

x(S1)n ≤ x(S2)

n ≤ . . . ≤ x(S2n )n

gilt. Diese Ungleichungen sind scharf, dass heißt es gilt <, und die zulassigen Ba-sislosungen x(Sj) und x(Sj+1) sind benachbart fur j = 1, . . . , 2n − 1, das heißt, sieunterscheiden sich nur in einem Basisvektor.

Beweis: Der Beweis erfolgt durch Induktion uber die Dimension n.Induktionsanfang. n = 1. Man hat zwei Eckpunkte. Aus

x1 − r1 = ε, x1 + s1 = 1

folgt(x1, r1, s1) = (ε, 0, 1− ε) ∨ (1, 1− ε, 0).

Diese Punkte sind naturlich benachbart und die Scharfe der Ungleichung wurde

bereits im letzten Lemma bewiesen (x(S)n > x

(S′)n ).

39

Induktionsannahme. Fur einen n–Wurfel sei alles korrekt. Die entsprechendeNumerierung sei S1, . . . , S2n .

Induktionsschritt. Man betrachtet jetzt 1, 2, . . . , n + 1. Offensichtlich gelten

Sj ⊂ 1, 2, . . . , n + 1 und n + 1 6∈ Sj , j = 1, . . . , 2n. Damit ist r(Sj )n+1 = 0. Aus der

entsprechenden Nebenbedingung folgt

x(Sj)n+1 = εx(Sj)

n .

Nach Induktionsannahme ist

x(S1)n < x(S2)

n < . . . < x(S2n )n ,

woraus nun folgt (Durchmultiplizieren mit ε)

x(S1)n+1 < x

(S2)n+1 < . . . < x

(S2n )n+1 . (8.2)

Die Reihenfolge dieser Untermengen bleibt also erhalten.

Nun betrachten wir die Losungen mit r(Sj )n+1 > 0. Sei S′

j = Sj ∪ n + 1. NachLemma 8.8 ist

x(Sj)n+1 = 1 − x

(S′

j)

n+1 =⇒ x(S′

j)

n+1 = 1 − x(Sj)n+1 j = 1, . . . , 2n, (8.3)

und speziell

x(S′

2n )n+1 > x

(S2n )n+1 . (8.4)

Aus (8.2), (8.3) und (8.4) resultiert

x(S1)n+1 < . . . < x

(S2n )n+1 < x

(S′

2n )n+1 < . . . < x

(S′

1)n+1.

Nun muss noch die Nachbarschaft der Basislosungen bewiesen werden. NachInduktionsannahme, sind x(S1), . . . ,x(S2n ) in n Dimensionen benachbart. In der(n + 1)–sten Dimension, erhalten diese Basislosungen alle noch den Spaltenvek-tor von sn+1. Sie bleiben damit benachbart. Die Basislosungen x(S2n ) und x(S′

2n )

unterscheiden sich nur im Basisvektor von sn+1 beziehungsweise rn+1. Sie sindalso auch benachbart. Die Basislosungen x(S′

2n ), . . . ,x(S′

1) sind benachbart, weilx(S1), . . . ,x(S2n ) benachbart sind.

Satz 8.10 Fur jedes n ≥ 1 existiert ein lineares Programm, bestehend aus 2n Glei-chungen und 3n Variablen, so dass die Simplexmethode 2n − 1 Iterationsschrittebraucht, um das Optimum zu bestimmen.

Die Struktur dieses linearen Programms kann so eingerichtet werden, dass alleKoeffizienten (zum Beispiel) ≤ 4 sind.

Beweis: Der erste Teil des Satzes wird durch das angegebene Beispiel (8.1)bewiesen. In Lemma 8.9 sind die 2n verschiedenen zulassigen Basislosungen strenggeordnet. Die Simplexmethode wird so angewendet, dass mit jeder Transformationnur die jeweils geringste Verbesserung des Zielfunktionswertes erreicht wird. Bei

x(1)n beginnend, sind somit 2n − 1 Transformationen notig.

Fur den zweiten Teil des Satzes wahle man ε = 1/4.

Beispiel 8.11 Wir betrachten das in diesem Abschnitt studierte Problem (8.1) fur

40

n = 3.

−x3 → min !

1 0 0 −1 0 0 0 0 0−ε 1 0 0 −1 0 0 0 00 −ε 1 0 0 −1 0 0 01 0 0 0 0 0 1 0 0ε 1 0 0 0 0 0 1 00 ε 1 0 0 0 0 0 1

x1

x2

x3

r1

r2

r3

s1

s2

s3

=

ε00111

,

x, r, s ≥ 0.

Die Ecken des Wurfels, des gestorten Wurfels und die Zielfunktionswerte sind wiefolgt

Nr. Wurfel gest. Wurfel z z fur ε = 1/4 Reihenfolge1 (0, 0, 0) (ε, ε2, ε3) −ε3 −0.015625 82 (0, 0, 1)

(ε, ε2, 1 − ε3

)−1 + ε3 −0.984375 1

3 (0, 1, 0)(ε, 1 − ε2, ε − ε3

)−ε + ε3 −0.234375 5

4 (0, 1, 1)(ε, 1− ε3, 1 − ε + ε3

)−1 + ε − ε3 −0.765625 4

5 (1, 0, 0)(1, ε, ε2

)−ε2 −0.0625 7

6 (1, 0, 1)(1, ε, 1− ε2

)−1 + ε2 −0.9375 2

7 (1, 1, 0)(1, 1 − ε, ε − ε2

)−ε + ε2 −0.1875 6

8 (1, 1, 1)(1, 1− ε, 1 − ε + ε2

)−1 + ε − ε2 −0.8125 3

Man beginnt mit der Startlosung

x =

εε2

ε3

=⇒ r =

000

, s =

1 − ε1 − ε2

1 − ε3

.

Das Transformationsprinzip der Simplexmethode wahlt jeweils die kleinste Verbes-serung der Zielfunktion. Die Eckpunkte des gestorten Wurfels werden in folgenderReihenfolge durchgegangen:

1 ⇒ 5 ⇒ 7 ⇒ 3 ⇒ 4 ⇒ 8 ⇒ 6 ⇒ 2.

3

1 5

2

4

6

8

7

2

41

Die Zusammenfassung dieses Kapitels ist wie folgt.

Satz 8.12 Die Simplexmethode besitzt als worst case Komplexitat mindestens O =(2n).

Diese tritt aber praktisch nicht auf. In der Praxis hat die Simplexmethode einepolynomiale Komplexitat.

Bemerkung 8.13 Innere–Punkt–Methoden. Seit 1984 hat sich eine weitere Klassevon Verfahren zur Losung linearer Programme etabliert, sogenannte Innere–Punkt–Methoden. Diese arbeiten mit Techniken der nichtlinearen Optimierung (Newton–Verfahren). Es ist derzeit ungeklart, welche Herangehensweise zur Losung linearerProgramme, Simplexmethode oder Innere–Punkt–Methoden, wirklich effizienter ist.Ein Vorteil von Innere–Punkt–Methoden liegt in ihren theoretischen Eigenschaf-ten, da man zeigen kann dass ihre worst case Komplexitat zur Berechnung einerNahrungslosung mit einer vorgegebenen Toleranz sich polynomial verhalt. EinigeInnere–Punkt–Methoden sind:

- Ellipsoid–Methode (O(n6)),- Algorithmus von Karmarkar (1984) (O(n7/2)),

- Verbesserung des Algorithmus von Karmarkar (Qi/Shi) (O(n3)),- Kurz–Schritt–Algorithmus (∼ O(n1/2)), siehe [JS04].

2

42

Kapitel 9

Dualitatssatze der linearenOptimierung

Sei

z = cT x → min !

Ax = b (9.1)

x ≥ 0

mit c,x ∈ Rn, b ∈ Rm, A ∈ Rm×n ein lineares Programm.

Definition 9.1 Duales lineares Programm. Das lineare Programm

z = bT y → max ! (9.2)

AT y ≤ c

mit y ∈ Rm wird das zu (9.1) duale lineare Programm genannt. Man nennt (9.1)primal. 2

Die Ziele dieses Abschnitts bestehen darin, die Existenz zulassiger Losungen desdualen linearen Programms, die Relationen der zulassigen Losungen des primalenund dualen linearen Programms, die Relationen zwischen den Optimallosungen unddie Verbesserung der numerischen Verfahren zu untersuchen. Ein duales Analogonzur Simplexmethode soll entwickelt werden.

Satz 9.2 Ist x eine zulassige Losung von (9.1) und ist y eine zulassige Losungvon (9.2), dann gilt z(x) ≥ z(y).

Beweis: Es gilt x ≥ 0 und cT ≥ yT A. Damit folgt

z(x) = cT x ≥ yT Ax = yT b = z(y).

Man nennt diesen Satz auch schwachen Dualitatssatz.

Folgerung 9.3 Ist x0 eine zulassige Losung von (9.1) und y0 eine zulassige Losungvon (9.2) und gilt z(x0) = z(y0), dann ist x0 eine Optimallosung von (9.1) und y0

eine Optimallosung von (9.2).

Satz 9.4 Starker Dualitatssatz. Das primale Problem (9.1) besitzt genau danneine endliche Optimallosung, wenn das duale Problem (9.2) eine endliche Opti-mallosung besitzt. In diesem Fall gilt zmin = zmax.

43

Beweis: 1.) Es existiere ein endliches Minimum des primalen Problems (9.1)

und dieses Minimum werde von x0 =(

x(0)1 , . . . , x

(0)m , 0, . . . , 0

)T

angenommen. Dann

sind erklart:

- Die zugehorigen Basisvektoren seien a1, . . . , am.- Mit X = (xij)i=1,...,m,j=1,...,n werden die Darstellungskoeffizienten fur alle

Spalten von A bezuglich dieser Basisvektoren bezeichnet.

- z = (z1, . . . , zn)T sei der Vektor, der durch zj =∑m

i=1 cixij , j = 1, . . . , n,erzeugt wird.

- A0 = (a1, . . . , am),

- c0 = (c1, . . . , cm)T .

Wegen des Optimalitatskriteriums der Simplexmethode gilt fur x0

z ≤ c (zk − ck ≤ 0, k = 1, . . . , n). (9.3)

Aus der Nebenbedingung und der Definition der Darstellungskoeffizienten folgt

A0x0 = b, A0X = A.

Daraus ergibt sichx0 = A−1

0 b, X = A−10 A. (9.4)

Weiter erhalten wir aus der Definition von z

cT0 X = zT ≤ cT . (9.5)

Jetzt setzen wir y0 = A−T0 c0 und zeigen, dass y0 eine Optimallosung des dualen

Problems (9.2) ist. Die Zulassigkeit von y0 folgt aus (9.4) und (9.5)

yT0 A = cT

0 A−10 A = cT

0 X ≤ cT .

Die Losung y0 ist optimal wegen

z(y0) = bT y0 = yT0 b = cT

0 A−10 b = cT

0 x0 = z(x0),

wobei (9.4) verwendet wurde. Damit liefert y0 einen Zielfunktionswert, der mit demvon x0 ubereinstimmt. Da x0 Optimum des primalen Problems ist, ist y0 wegenFolgerung 9.3 Optimum des dualen Problems.

2) Das Ziel besteht darin, diesen Teil des Beweises auf den ersten Teil zuruck-zufuhren, indem gezeigt wird, dass das duale Problem des dualen Problems (9.2)gerade das primale Problem (9.1) ist. Dazu wird das duale Problem so umgeformt,dass es die Gestalt eines primalen Problems annimmt. Bildet man dann aus dieserForm das duale Problem, erhalt man die Behauptung.

Es existiere ein endliches Maximum zmax des dualen Problems (9.2). Wir setzenfur einen beliebigen Vektor y ∈ Rm, der die Nebenbedingungen von (9.2) erfullt,y = y1 − y2, y1,y2 ∈ Rm, y1,y2 ≥ 0. Aus den Nebenbedingungen von (9.2) erhaltman

AT (y1 − y2) + y3 = c ∈ Rn,

mit den Schlupfvariablenvektor y3 ∈ Rn, y3 ≥ 0. Daraus bilden wir folgendeszu (9.2) aquivalentes Problem, wobei das Vorzeichen der Zielfunktion geandert wird

bT (y2 − y1) → min !

−AT y1 + AT y2 − y3 = −c

y1,y2,y3 ≥ 0.

44

Setzt man

w =

y1

y2

y3

∈ R2m+n, d =

−bb0n

∈ R2m+n,

A =(−AT , AT ,−In

)∈ Rn×(2m+n),

so kann man dieses System in der Form

dT w → min !

Aw = −c (9.6)

w ≥ 0

schreiben.Einerseits ist dieses Problem zum dualen Problem (9.2) aquivalent. Damit be-

sitzt (9.6) nach Voraussetzung ein endliches Optimum z(w)min, fur welches gilt z

(w)min =

zmax.Andererseits besitzt das Problem (9.6) die gleiche Gestalt wie das primale Pro-

blem (9.1). Die duale Aufgabe zu (9.6) hat nun folgende Gestalt: Gesucht ist x ∈ Rn

mit−cT x → max !, AT x ≤ d,

das heißt

cT x → min !

−Ax ≤ −b

Ax ≤ b

−x ≤ 0.

Aus den ersten beiden Nebenbedingungen folgt Ax = b. Damit ist gezeigt, dass (9.1)das duale Problem zu (9.2) ist. Aus dem ersten Teil des Beweises wissen wir, dassdie duale Aufgabe zu (9.6) ein endliches Maximum besitzt und das dieses Maximum

mit z(w)min = zmax ubereinstimmt.

Jetzt wird der Fall betrachtet, dass die Zielfunktion der primalen Aufgabe nachunten nicht beschrankt ist.

Satz 9.5 Ist die Zielfunktion z = cT x der primalen Aufgabe (9.1) auf der Mengeder zulassigen Losungen nach unten unbeschrankt, dann besitzt die zugehorige dualeAufgabe (9.2) keine zulassige Losung. Analog gilt, dass im Falle dass die Zielfunk-tion der dualen Aufgabe auf der Menge der zulassigen Losungen nicht nach obenbeschrankt ist, die primale Aufgabe keine zulassige Losung besitzt.

Beweis: Indirekter Beweis. Sei die Zielfunktion des primalen Problems nichtnach unten beschrankt und sei y eine zulassige Losung des dualen Problems, dasheißt es gilt AT y ≤ cT . Aus Satz 9.2 folgt dann aber z(x) ≥ z(y) und die Zielfunk-tion ware nach unten beschrankt.

Die zweite Aussage folgt aus der ersten Aussage und daraus, dass das primaleProblem (9.1) das duale Problem des dualen Problems (9.2) ist.

Folgerung 9.6 Eine zulassige Losung x0 des primalen Problems (9.1) ist genaudann optimal, wenn eine zulassige Losung y0 des dualen Problems (9.2) existiert,mit cT x0 = bT y0. Eine analoge Aussage gilt, wenn man vom dualen Problem aus-geht.

45

Satz 9.7 Komplementaritatssatz. Es sei x0 = (x(0)1 , . . . , x

(0)m , 0, . . . , 0)T eine

zulassige Basislosung des primalen Problems (9.1). Dann ist x0 genau dann op-timal, wenn es eine zulassige Losung y des dualen Problems (9.2) mit folgendenEigenschaften gibt:

1) fur alle Indizes i ∈ 1, . . . , m mit x(0)i > 0 gilt aT

i y = ci,

2) fur alle Indizes j ∈ 1, . . . , n mit aTj y < cj gilt x

(0)j = 0.

Beweis: i) Sei x0 optimal. Nach Folgerung 9.6 gibt es dann ein y0 mit cT x0 =bT y0. Einsetzen von Ax0 = b ergibt

cT x0 = xT0 AT y0︸ ︷︷ ︸

∈R

= yT0 Ax0 ⇐⇒

(cT − yT

0 A)x0 = 0.

Komponentenweise lautet diese Gleichung

n∑

j=1

(cj − yT

0 aj

)x

(0)j = 0.

Da y0 eine zulassige Losung des dualen Problems ist, sind alle Faktoren nichtnegativ.Damit die Summe Null wird, mussen alle Summanden verschwinden und wenigstens

jeweils einer der Faktoren Null sein. Ist x(0)j > 0, muss aT

j y0 = cj sein. Ist aTj y < cj ,

so muss x(0)j = 0 sein. Die Optimallosung y0 des dualen Problems erfullt also die

Bedingungen 1) und 2).ii) Es gibt einen Vektor y der die Bedingungen 1) und 2) erfullt. Wir nehmen

an, x0 sei nicht optimal. Dann gilt cT x0 > bT y. Analog zum ersten Teil erhalt man

n∑

j=1

(cj − yT aj

)x

(0)j > 0.

Aus den Bedinungen 1), 2) folgt jedoch, dass die Summe verschwindet. Damit istdie Annahme falsch und x0 ist optimal.

Bemerkung 9.8 Mit Hilfe der Dualitat ist die Moglichkeit der Bestimmung vonSchranken fur eine zulassige (optimale) Losung gegeben. Es gilt

z(x) ≥ z(x0) = z(y0) ≥ z(y),

wobei x eine zulassige Losung des primalen Problems (9.1), x0 eine Optimallosungvon (9.1), y eine zulassige Losung des dualen Problems (9.2) und y0 eine Opti-mallosung des dualen Problems ist. 2

Ein Spezialfall des dualen linearen Programms ist das symmetrische duale lineareProgramm. Gegeben sei das lineare Programm

z = cT x → min !

Ax ≥ b (9.7)

x ≥ 0.

Aus (9.7) wird

z = bT y → max !

AT y ≤ c (9.8)

y ≥ 0.

konstruiert. Man hat eine Nichtnegativitatsbedingung an die zulassigen Losungendes dualen Programms.

46

Satz 9.9 Die linearen Programm (9.7) und (9.8) sind duale lineare Programme imSinne von Definition 9.1.

Beweis: Aus (9.7) konstruieren wir das lineare Programm in Normalform

z = cT x → min !, Ax − v = b, x,v ≥ 0.

Aus Definition 9.1 ergibt sich das folgende duale lineare Programm

z = bT y → max !, AT y ≤ c, −Imy ≤ 0.

Die letzte Bedingung ist aquivalent zu y ≥ 0.

Satz 9.10 Komplementaritatssatz. Sind x0 eine zulassige Losung von (9.7) undy0 eine zulassige Losung von (9.8), so sind sie genau dann optimal, wenn die fol-genden Relationen erfullt sind:

yT0 (Ax0 − b) = 0, (9.9)

(yT

0 A − cT)x0 = 0. (9.10)

Beweis: 1) Seien x0 und y0 optimal. Dann folgt aus der Nebenbedingungvon (9.8), aus der Nichtnegativitat von x0 und aus Folgerung 9.6

yT0 (Ax0 − b) = yT

0 Ax0 − yT0 b ≤ cT x0 − yT

0 b = 0.

Andererseits gilt mit y0 ≥ 0 und der Nebenbedingung von (9.7)

yT0 (Ax0 − b) ≥ 0.

Aus beiden Ungleichungen zusammen folgt (9.9). Die Beziehung (9.10) beweist mananalog.

2) Gelten jetzt (9.9) und (9.10). Daraus folgt

cT x0 = yT0 Ax0 = yT

0 b.

Nach Folgerung 9.6 sind x0 und y0 optimal.Beispiel fur Anwendungen des Dualitatsprinzips werden in den Ubungsaufgaben

behandelt.

47

Kapitel 10

Die duale Simplexmethode

Bei der dualen Simplexmethode ist eine Startlosung oftmals leichter angebbar als beider Simplexmethode fur das ursprungliche lineare Programm, da man keine Nichtne-gativitatsanforderungen zu erfullen hat. Des weiteren ist die duale Simplexmethodeein wichtiges Verfahren zur Losung von ganzzahligen linearen Programmen, d.h.,von linearen Programmen, bei denen die Losung ganzzahlig sein soll.

Seien

z = cT x → min !

Ax = b (10.1)

x ≥ 0

das primale Programm und

z = bT y → max ! (10.2)

AT y ≤ c

das zugehorige duale Programm. Wir setzen voraus, dass z endlich ist.

Definition 10.1 Ecklosung. Ohne Beschrankung der Allgemeinheit sei AB =(a1, . . . , am) eine Basis. Ein Punkt y = (y1, . . . , ym)T heißt Ecklosung von (10.2),wenn

aTi y = ci fur i = 1, . . . , m, (10.3)

aTi y < ci fur i = m + 1, . . . , n

gilt. 2

Das heißt, die Nebenbedingungen, die durch die Basisvektoren von AB gegeben sind,sind mit Gleichheit erfullt und die Nebenbedingungen mit den Nichtbasisvektorenals echte Ungleichung.

Seien A−1B die Inverse von AB mit der Darstellung

A−1B =

b1

...bm

, dass heißt biaj = δij

und y = y1a1 + . . . + ymam ∈ Rm ein beliebiger Vektor. Dann folgt (man beachte,die bi sind Zeilenvektoren)

biy = y1bia1 + . . . + ymbiam = yi, i = 1, . . . , m.

48

Daraus erhalt man insbesondere die Darstellung

y = (b1y) a1 + . . . + (bmy) am. (10.4)

Die Ausartung in der dualen Simplexmethode, die im folgenden Satz ausge-schlossen ist, wird in seinem Beweis definiert, siehe auch Bemerkung 10.3.

Satz 10.2 Hauptsatz der dualen Simplexmethode. Sei z nach oben beschranktund sei Ausartung ausgeschlossen. Ist y ∈ Rm eine Ecklosung und gilt bib < 0 furwenigstens ein i = 1, . . . , m, so existiert eine Ecklosung y mit großerem Wert derZielfunktion z.

Beweis: Seien y eine Ecklosung, blb < 0 und θ > 0 beliebig. Es wird ein ykonstruiert, welches die Bedingungen des Satzes erfullt.

Man bildety = y − θbT

l .

Aus der Eckpunkteigenschaft (10.3) folgt

aTi y = aT

i y − θ aTi bT

l︸ ︷︷ ︸

=0

= aTi y = ci, i = 1, . . . , m, i 6= l, (10.5)

aTl y = aT

l y − θ aTl bT

l︸ ︷︷ ︸

=1

= aTl y − θ < cl. (10.6)

Es ist auchaT

i y = aTi y − θaT

i bTl < ci, i = m + 1, . . . , n,

und fur wenigstens einen Index i gilt aTi bT

l < 0. Anderenfalls, falls also aTi bT

l > 0fur i = m+1, . . . , n, sind die Nebenbedingungen fur beliebig großes θ erfullt. Damitware

z = bT y = bT y − θ bT bl︸ ︷︷ ︸

<0 n.V.

unbeschrankt im Widerspruch zur Voraussetzung.Wir wahlen

θ = mini=m+1,...,n;blai<0

(aT

i y − ci

blai

)

. (10.7)

Wir nehmen an, dass θ fur genau einen Index i = k angenommen wird. Sonst hatman Ausartung. Es gilt:

1.) y erfullt (10.5) und (10.6), das heißt, die Basisvektoren die in der Basisverbleiben erfullen die Nebenbedingung mit Gleichheit und die neu Nichtba-sisvariable mit Index l als echte Ungleichung.

2.) Fur den Index k, der in die Basis aufgenommen werden soll, gilt

aTk y = aT

k y − aTk y − ck

blakblak = ck,

3.) Aus der Wahl von θ folgt

aTi y = aT

i y − θaTi bT

l < ci, i = m + 1, . . . , n, i 6= k.

Falls aTi bT

l nichtnegativ ist, ist das Erfulltsein dieser Bedingung klar. An-sonsten wurde bei der Wahl von θ gerade der Index k ausgewahlt, der diek–te Nebenbedingung aT

k bTl < 0 fur y zu einer Gleichung werden lasst, ohne

dass die anderen Nebenbedingungen mit aTi bT

l < 0 verletzt werden.

49

Aus 1) – 3) folgt, dass y eine Ecklosung ist. Ferner gilt

z = bT y = bT y − θbT bTl > bT y.

Bemerkung 10.3 Ausartung im dualen Programm. Ist der Index k bei der Wahlvon θ in (10.7) nicht eindeutig, so liegt Ausartung vor. 2

Bemerkung 10.4 Unbeschranktheit der Zielfunktion. Die Unbeschranktheit derZielfunktion z ist an aT

j bTl ≥ 0 fur j = m + 1, . . . , n zu erkennen. 2

Satz 10.5 Optimalitatskriterium. Sei y eine Ecklosung von (10.2) und gel-te bib ≥ 0 fur alle i = 1, . . . , m. Dann ist y die Optimallosung von (10.2) unddie Großen xi = bib stellen die Basisvariablen der Optimallosung des primalenProblems (10.1) dar.

Beweis: Es gilt mit (10.3)

z =

m∑

i=1

cixi =

m∑

i=1

cibib =

m∑

i=1

yT aibib = yT

(m∑

i=1

aibi

)

︸ ︷︷ ︸

=Im

b = bT y = z.

Nach dem starken Dualitatssatz, Satz 9.4, folgt die Aussage des Satzes.Bemerkung zur Summe: Sei

∑mi=1 aibi = C mit einer unbekannten Matrix C.

Multiplikation diese Gleichung von rechts mit aj , j = 1, . . . , m, ergibt

Caj =

m∑

i=1

ai biaj︸︷︷︸

=δij

= aj

fur alle aj . Da die aj eine Basis des Rm bilden, gilt C = Im.Die duale Simplextabelle hat die Gestalt

m + 1 . . . k . . . ni ci Losung cm+1 . . . ck . . . cn

1 c1 b1b b1am+1 . . . b1ak . . . b1an

......

......

......

......

l cl blb blam+1 . . . blak . . . blan

......

......

......

......

m cm bmb bmam+1 . . . bmak . . . bman

z aTm+1y − cm+1 . . . aT

k y − ck . . . aTny − cn

Wie bei der Simplexmethode, wird die Zeile l Hauptzeile und die Spalte k Haupt-spalte genannt. Das Pivotelement ist blak . Aus den Nebenbedingungen des dualenlinearen Programms (10.2) folgt, dass die Eintrage in der letzten Zeile im Nichtba-sisteil nichtpositiv sind.

Bemerkung 10.6

- In der Schlusszeile stehen die Großen, die man zur Berechnung von θ in (10.7)benotigt.

50

- Die Spalte Losung enthalt eine Basislosung des primalen Problems. Sei x ∈Rm der Vektor mit den Basisvariablen des primalen Problems. Aus den Ne-benbedingungen des primalen Problems folgt

ABx = b =⇒ x = A−1B b =

b1b...

bmb

.

Diese Basislosung ist im allgemeinen nicht zulassig, da sie negative Kompo-nenten besitzt. Gilt jedoch bib ≥ 0 fur alle i = 1, . . . , m, dann ist sie primaleOptimallosung.

- Die Nichtbasisvektoren lassen sich als Linearkombination der Basisvektorendarstellen aj = ABa mit einem unbekannten Koeffizientenvektor a. Dieserlasst sich durch a = A−1

B aj berechnen, was in Komponentenschreibweise zu

aj =

m∑

i=1

(biaj) ai, j = m + 1, . . . , n

fuhrt, siehe (10.4).

- Falls man das Optimum des dualen Problems mit der dualen Simplexmetho-de gefunden hat, ist die Tabelle der dualen Simplexmethode eine Optimal-tabelle fur die primale Aufgabe.

2

Falls in der Spalte Losung wenigstens ein bib < 0 steht, zum Beispiel fur i = l,so transformiert man wie folgt:

- Setze a0 = b.

- Vertausche die Indizes l und k.- Pivotelement: bkal = 1/(blak)- Hauptspalte:

bial = −biak

blak, i = 1, . . . , m, i 6= l,

- Hauptzeile:

bkaj =blaj

blak, j = 0, m + 1, . . . , n, j 6= k,

- Rechteckregel:

biaj = biaj −blaj

blakbiak, i = 1, . . . , m, i 6= l, j = 0, m + 1, . . . , n, j 6= k.

Die Rechteckregel wird auch auf die letzte Zeile angewandt Ubungsaufgabe.

Das sind dieselben Regeln wie im primalen Fall !

Bemerkung 10.7 Begrundung der Transformationsregeln: Seien AB = (a1, . . . , am)

51

und AB = (a1, . . . , al−1, ak , al+1, . . . , am). Dann ist

A−1B AB =

b1

...bm

(a1, . . . , al−1, ak, al+1, . . . , am)

=

b1a1 b1a2 · · · b1ak · · · b1am

......

......

......

bla1 bla2 · · · blak · · · blam

......

......

......

bma1 bma2 · · · bmak · · · bmam

=

1 0 · · · 0 b1ak 0 · · · 00 1 · · · 0 b2ak 0 · · · 0...

......

......

......

...0 0 · · · 0 blak 0 · · · 0...

......

......

......

...0 0 · · · 0 bmak 0 · · · 1

=: I(k)m .

Sei

(

AB

)−1

=

b1

...

bm

,

dann ist

A−1B = I(k)

m

(

AB

)−1

,

oder

b1

...bl

...bm

=

b1 + (b1ak)bk

...

(blak)bk

...

bm + (bmak)bk

.

Damit stehen die Transformationsregeln da. Fur das Pivotelement gilt

bk =bl

blak=⇒ bkal =

blal

blak=

1

blak.

Fur die Hauptspalte erhalt man daraus

bi = bi − (biak) bk =⇒ bial = bial − (biak)(

bkal

)

= 0 − biak

blaki 6= l.

Fur die Hauptzeile ergibt sich umittelbar

bkaj =blaj

blak, j = 0, m + 1, . . . , n, j 6= k.

Die Rechteckregel ergibt sich damit

biaj = biaj − biakbkaj = biaj −blaj

blakbiak.

2

52

Beispiel 10.8 Wir betrachten noch einmal das Problem aus Beispiel 5.2:

z = −3x1 − 2x2 − 4x3 − x4 → min !

2 2 3 0 1 0 01 3 0 2 0 1 01 1 5 2 0 0 1

x1

...x7

=

700400500

x ≥ 0.

In Beispiel 5.2 hatten wir die Optimallosung x = (320, 0, 20, 40, 0, 0, 0)T

mit z =−1080 erhalten. Das duale Problem zum obigen linearen Programm lautet

z = 700y1 + 400y2 + 500y3 → max !

2 1 12 3 13 0 50 2 21 0 00 1 00 0 1

y1

y2

y3

≤

−3−2−4−1000

.

Wir nehmen uns die erste, dritte und funfte Nebenbedingung des dualen Pro-blems her und betrachte diese Bedingungen als Gleichungen:

2 1 13 0 51 0 0

y1

y2

y3

=

−3−40

=⇒ y =

0−11/5−4/5

.

Durch Einsetzen in die Nebenbedingungen verifiziert man, dass man damit eineEcklosung des dualen Problems gefunden hat. Es ist

AB = (a1, a3, a5) =

2 3 11 0 01 5 0

, A−1B =

0 1 00 −1/5 1/51 −7/5 −3/5

=

b1

b3

b5

,

b =

700400500

.

Damit sind alle Großen fur die duale Simplextabelle bestimmt:

2 4 6 7i ci Losung -2 -1 0 01 -3 400 3 2 1 03 -4 20 -2/5 0 -1/5 1/55 0 -160 -14/5 -4 -7/5 -3/5

-1280 -27/5 -5 -11/5 -4/5

Die Losung ist nicht optimal, da −160 < 0. Damit ist l = 5 die Hauptzeile. ZurBestimmung der Hauptspalte berechnet man

θ = minj∈2,4,6,7, blaj<0

(

aTj y − cj

blaj

)

= min

27

14,5

4,11

7,4

3

=5

4.

Damit ist die Hauptspalte k = 4. Mit den Transformationsregeln der Simplexme-thode erhalt man die neue duale Simplextabelle

53

2 5 6 7i ci Losung -2 0 0 01 -3 320 8/5 1/2 3/10 -3/103 -4 20 -2/5 0 -1/5 1/54 -1 40 7/10 -1/4 7/20 3/20

-1080 -19/10 -5/4 -9/20 -1/20

Damit ist das Optimum bestimmt. Die Optimallosung des primalen Problems findetman in der Spalte Losung ebenso den zugehorigen Zielfunktionswert.

Die Losung des dualen Problems y kann man im allgemeinen nicht direkt ausder dualen Simplextabelle ablesen. In der letzten Zeile steht namlich aT

j y− cj . Dasdirekte Ablesen geht nur, wenn cj = 0 und die aj Einheitsvektoren sind. Das ist indiesem Beispiel gegeben, namlich fur die Indizes 5, 6, 7. Die Losung des dualen Pro-blems ist also y = (−5/4,−9/20,−1/20)T , mit dem Zielfunktionswert z = −1080.Im allgemeinen muss man noch ein lineares Gleichungssystem losen, um die Losungdes dualen Problems zu berechnen. 2

54

Kapitel 11

Die duale Simplexmethodezur Losung rein ganzzahligerlinearer Programme

Wir betrachten folgendes Optimierungsproblem

z = cT x → min !

Ax = b (11.1)

x ≥ 0 (11.2)

xj ganz fur j = 1, . . . , n1 ≤ n, (11.3)

aij , bi ganz fur i = 1, . . . , m, j = 1, . . . , n. (11.4)

Definition 11.1 Ganzzahliges lineares Programm. Das lineare Programm(11.1) – (11.4) heißt rein ganzzahliges lineares Programm falls n1 = n. Ansonstenheißt es fur n1 > 0 gemischt ganzzahliges lineares Programm. 2

Bemerkung 11.2 Haufig enthalten ganzzahlige lineare Programme Bedingungender folgenden Art

0 ≤ xj ≤ 1, xj ganz,

fur gewisse Indizes j. 2

Beispiel 11.3 Wir betrachten

z = −8x1 − 4x2 → min !

−2x1 + 3x2 ≤ 6

8x1 + 3x2 ≤ 20

x ≥ 0

x1, x2 ganz.

Das Problem ohne die Ganzheitsforderung kann man graphisch losen, siehe Abbil-dung.

55

z

2

20

3

5

2

Das stetige Optimum ist

x =

(7

5,44

15

)

, z = −344

15.

Eine einfache Herangehensweise zur Bestimmung des ganzzahligen Optimums istRunden. Man erhalt damit x = (1, 3)T . Dieser Punkt ist jedoch nicht zulassig. DurchAbrunden folgt x = (1, 2)T . Man erhalt mit diesem Punkt den Zielfunktionswertz = −16. Dieser ist jedoch nicht optimal, da man mit x = (2, 1)T den Wert z = −20erhalt.

Runden ist also keine geeignete Losungstechnik. 2

Mit dem normalen Simplexverfahren kann man nicht arbeiten, da das Optimumein innerer Punkt des zulassigen Bereiches ist. Das konnte man durch die Bestim-mung der konvexen Hulle aller zulassigen Punkte andern. Dieses Vorgehen ist aberim allgemeinen viel zu aufwendig. Stattdessen versucht man in der Nahe des ste-tigen Optimums durch Abschneiden den gesuchten ganzzahligen optimalen Punktzu einem Eckpunkt zu machen. Dieses Schnittprinzip soll jetzt auf eine Art (nachGomory (1957)) realisiert werden.

Definition 11.4 Schnittbedingung. Die Nebenbedingung

n∑

j=1

βjxj ≤ β (11.5)

heißt Schnittbedingung, wenn folgendes erfullt ist:

i) Es sei x(0) ein Optimum mit den Nebenbedingungen (11.1) – (11.2). Dannerfullt x(0) die Bedingung (11.5) nicht, das heißt

n∑

j=1

βjx(0)j > β.

ii) Jede Losung, die die Nebenbedingungen (11.1) – (11.4) erfullt (11.5), dasheißt

x : x erfullt (11.1) − (11.4) ⊂ x : x erfullt (11.5).

2

56

Jetzt soll (11.1) – (11.4) durch die Einfuhrung von Schnittbedingungen gelostwerden. Es sei dazu zuerst (11.1) – (11.2) mit Hilfe der Simplexmethode gelost.

Das Optimum sei x(0) = (x(0)1 , . . . , x

(0)m , 0, . . . , 0)T . Dabei sei wenigstens ein x

(0)i ,

i ∈ 1, . . . , m, nicht ganz.Sei AB = (a1, . . . , am) die Matrix der Basisvektoren. Die Auflosung von (11.1)

nach den Basisvariablen liefert fur jedes zulassige x die Darstellung

xi = αi + αi,m+1(−xm+1) + . . . + αi,n(−xn), i = 1, . . . , m. (11.6)

Lemma 11.5 Die Koeffizienten von (11.6) bilden eine optimale Simplextabelle.

Beweis: Wir betrachten die Nebenbedingung (11.1) und zerlegen A = (AB |AN )

sowie x = (xB |xN )T. Wir wissen, dass AN = ABX , wobei X die Eintrage der

Simplextabelle sind. AusABxB + ANxN = b

folgtxB = A−1

B b + A−1B AN (−xN ) = A−1

B b︸ ︷︷ ︸

αi

+ X(−xN)︸ ︷︷ ︸

Rest von (11.6)

.

Sei jetzt fur i = p die Variable x(0)p nicht ganz, i ∈ 1, . . . , m. Falls mehrere x

(0)i

nicht ganz sind, wahle man einen dieser Indizes. Welches der beste ist, ist im all-gemeinen nicht zu beantworten. Das ist in Analogie zur Simplexmethode bezuglichder Auswahl von zk − ck > 0.

Sei a ∈ R. Dann bezeichnen wir

[a] = INT(a), a = a − [a] ,

wobei INT(a) der großte ganzzahlige Bestandteil von a ist. Es gilt a ∈ [0, 1).

Insbesondere gilt

x(0)p

> 0. Da fur das Optimum die Komponenten mit den

Indizes m + 1, . . . , n verschwinden, folgt damit auch

αp =[

x(0)p

]

︸ ︷︷ ︸

≥0

+

x(0)p

︸ ︷︷ ︸

>0

> 0.

Satz 11.6 Die Bedingung

s1 = −αp − αp,m+1 (−xm+1) − . . . − αp,n (−xn), s1 ≥ 0 (11.7)

stellt eine Schnittbedingung gemaß Definition 11.4 dar.

Beweis: Die Bedingungen von Definition 11.4 mussen gepruft werden. Wirfugen die Bedingung (11.7) zum System der Nebenbedingungen (11.1), (11.2) hinzuund setzen x(0) ein. Aus (11.5) folgt fur x(0)

s1 = −αp < 0,

also ist x(0) nicht zulassig.Nun ist zu zeigen, dass mit (11.7) keine bezuglich (11.1) – (11.4) zulassiger Punkt

weggeschnitten wird. Sei x = (x1, . . . , xn)T ein Punkt, der (11.1) – (11.4) erfullt.Dann folgt aus (11.7)

s1 = − (αp − [αp])︸ ︷︷ ︸

∈[0,1)

−n∑

j=m+1

(αp,j − [αp,j ])︸ ︷︷ ︸

∈(0,1)

(−xj)︸ ︷︷ ︸

≤0

.

57

Damit ist s1 > −1. Andererseits gilt

s1 = [αp] +

n∑

j=m+1

[αp,j ] (−xj)

︸ ︷︷ ︸

∈Z

−αp −n∑

j=m+1

αp,j (−xj)

︸ ︷︷ ︸

(11.6)=−xp∈Z

.

Damit ist s1 ∈ Z. Da s1 > −1 folgt s1 ≥ 0.Man hat mit der Schnittbedingung (11.7) das Optimum bezuglich der Neben-

bedingungen (11.1), (11.2) abgeschnitten, ohne dabei auch ganzzahlige Losungenwegzuschneiden. Folgendes lineare Programm ist jetzt zu losen:

z = cT x → min !

Ax = b

s1 = −αp −n∑

j=m+1

αp,j (−xj) (11.8)

x ≥ 0

s1 ≥ 0.

Zur Losung von (11.8) berechnet man zuerst die optimale Losung des linearen Pro-gramms ohne Ganzzahligkeitsbedingung mit Hilfe der dualen Simplexmethode. Hatman diese, und ist sie nicht ganzzahlig, betrachtet man im nachsten Schritt dieduale Simplextabelle mit

xi = αi, i = 1, . . . , m, s1 = −αp (11.9)

(beachte: in der Simplextabelle des dualen Problems steht xi = bib = αi). DerVektor (11.9) ist eine dual zulassige Losung, das heisst, die Nebenbedingungen desdualen Problems sind erfullt. Ubungsaufgabe Eventuell ist die Einfuhrung weite-rer Schnittbedingungen notig. Das oben beschriebene Vorgehen wird im nachstenBeispiel demonstriert.

Beispiel 11.7 Wir betrachten das lineare Programm

z = −x1 − 2x2 → min !

2 1 1 0 0−1 1 0 1 01 0 0 0 1

x1

...x5

=

1054

x ≥ 0

x ganz.

Die optimale duale Simplextabelle ist

3 4i ci Losung 0 01 -1 5/3 1/3 -1/3

2 -2 20/3 1/3 2/3

5 0 7/3 -1/3 1/3-15 -1 -1

Die Losung ist optimal, aber nicht ganzzahlig. Heuristisch wahlt man αp moglichstgroß, hier zum Beispiel 2/3. Es besteht allerdings die Gefahr, dass man an derfalschen Stelle abschneidet. Die Schnittbedingung lautet, siehe Lemma 11.5 fur dieKoeffizienten αp,j ,

s1 = −2

3− 1

3(−x3) −

2

3(−x4) ≥ 0.

Damit erhalt man die neue duale Simplextabelle

58

3 4i ci Losung 0 01 -1 5/3 1/3 -1/32 -2 20/3 1/3 2/35 0 7/3 -1/3 1/3

s1 0 -2/3 -1/3 -2/3

-15 -1 -1

Die Hauptzeile ist die Zeile von s1. Aus

θ = minj∈3,4

−1

−1/3,

−1

−2/3

=3

2

folgt, dass k = 4 die Hauptspalte ist. Der Simplexschritt fuhrt zu folgender Tabelle

3 s1

i ci Losung 0 01 -1 2 -1/2 -1/22 -2 6 0 15 0 2 -1/2 1/24 0 1 1/2 -3/2

-14 -1/2 -3/2

Damit hat man die Optimallosung des ganzzahligen linearen Programms gefunden.In der Praxis sind im allgemeinen mehr Schnittbedingungen notig. Die Endlich-

keit des Verfahrens ist nicht gesichert. 2

59

Teil II

Nichtlineare Optimierung

60

Kapitel 1

Einleitung

In diesem Abschnitt wird die Optimierung von Funktionen

minx∈Ω

f(x)

betrachtet, wobei Ω ⊂ Rn eine abgeschlossene Menge und f : Ω → R eine gegebeneFunktion ist. Die Funktion f heißt Zielfunktion und Ω sei durch endlich viele Ne-benbedingungen beschrieben. Bei den betrachteten Problemen konnen sowohl dieZielfunktion als auch die Nebenbedingungen nichtlinear sein.

Beispiel 1.1 Ausgleichsrechnung. Ein konkretes Beispiel fur einen Aufgabe derNichtlinearen Optimierung ist die Ausgleichsrechnung. Zur mathematischen For-mulierung von Gesetzmaßigkeiten, die ein technisches oder physikalisches Phano-men beschreiben, wird haufig eine Hypothese uber den moglichen funktionalen Zu-sammenhang bekannter und beobachteter Variablen formuliert. Diese enthalt imallgemeinen noch freie Parameter und hat etwa die Gestalt

z = g(x, λ), x ∈ Rn, λ ∈ Rp.

In diesem Modell ist λ ein unbekannter Parametervektor mit p Komponenten undz ist eine Variable, deren Abhangigkeit modelliert werden soll.

Nach Auswertung von m Experimenten kennt man m Paare von Variablenwerten(zi,xi), die unter Berucksichtigung moglicher Beobachtungsfehler εi die funktionaleAbhangigkeit annahernd erfullen sollen. Das heißt, bei passenden Parametern mussgelten

zi = g(xi, λ) + εi, i = 1, . . . , m.

Um moglichst kleine Abweichungen εi zu erhalten, versucht man, die unbekanntenParameter λ optimal anzupassen, indem man entsprechende Optimierungsaufgabenlost, zum Beispiel

minλ∈Rp

m∑

i=1

(zi − g(xi, λ))2

(Methode der kleinsten Quadrate) oder

minλ∈Rp

m∑

i=1

ωi |zi − g(xi, λ)|r ,

wobei r ≥ 1 eine ganze Zahl ist und ω ≥ 0. 2

61

Beispiel 1.2 Standortplanung. Eine Firma mochte n neue Lager der Kapazitat ai,i = 1, . . . , n, errichten. Gegeben sind die Standorte der Abnehmer (αj , βj) sowieder Bedarf bj , j = 1, . . . , m. In einigen Gebieten darf zudem nicht gebaut werden(εk–Umgebungen von (γk, δk), k = 1, . . . , p.)

Gesucht sind die Standorte der Lager (xi, yi), die den Lieferplan z optimieren.Mit den Bezeichnungen

- zij – Transportmenge vom Lager i zum Abnehmer j,- dij – Entfernung Lager i und Abnehmer j,

- ∆ik – Entfernung Lager i zum Mittelpunkt (γk, δk) der Verbotszone k,

lautet die Optimierungsaufgabe wie folgt:

n∑

i=1

m∑

j=1

dijzij → min !

m∑

j=1

zij ≤ ai, i = 1, . . . , n

n∑

i=1

zij = bj , j = 1, . . . , m

∆ik ≥ εk, i = 1, . . . , n, k = 1, . . . , p,

zij ≥ 0, i = 1, . . . , n, j = 1, . . . , m.

Diese Aufgabe kann fur verschiedene Entfernungsmaße gestellt werden, etwa fur

dij = |xi − αj | + |yi − βj |

oder die Euklidische Entfernung

dij =

√

(xi − αj)2+ (yi − βj)

2.

Wird sowohl fur dij als auch fur ∆ik die Euklidische Entfernung gewahlt, so erhaltman eine Optimierungsaufgabe mit quadratischer Zielfunktion und quadratischenNebenbedingungen. 2

Beispiel 1.3 Quadratische Zielfunktion uber konvexem Polyeder. Wir betrachtenein nichtlineares Programm mit quadratischer Zielfunktion und linearen Nebenbe-dingungen:

z = (x1 − 6)2

+ 2 (x2 − 3)2 → min !

x1 + x2 ≥ 2

x1 − x2 ≥ −2

x1 + x2 ≤ 6

x1 − 3x2 ≤ 2

x ≥ 0.

Durch die Zielfunktion werden konzentrische Ellipsen mit Mittelpunkt (6, 3)T be-schrieben. Die optimale Losung ist ein Punkt auf dem Rand ∂Ω von Ω, aber keinEckpunkt: xopt = (4, 2)T , zopt = 6.

62

6

(4, 2)

(6, 3)

2

2 6P1

P3

P4

P2

Betrachtet man eine andere Zielfunktion

z = (x1 − 2)2

+ 2 (x2 − 2)2 → min !,

dann ist das Optimum xopt = (2, 2)T , zopt = 0. Damit liegt das Optimum im Innerenvon Ω.

Eine andere quadratische Zielfunktion ist

z = 2 (x1 − 2)2

+ (x2 − 2)2 → max !

Bei dieser Zielfunktion gibt es eine Ellipse, die gleichzeitig durch P1 und P3 geht.Beide Eckpunkte von Ω sind lokales Maximum mit z = 4. Ein weiteres lokalesMaximum erhalt man in P4 mit z = 8. Das globale Maximum wird jedoch in P2 mitz = 19 angenommen. Ein simplexartiges Vorgehen, wobei man von Eckpunkt zuEckpunkt geht und in jedem Schritt den Zielfunktionswert verbessert (vergroßert),d.h. P1 → P4 oder P3 → P4 fuhrt hier nicht zum Ziel. 2

Beispiel 1.4 Unzusammenhangender zulassiger Bereich. Der zulassige Bereich Ωsei definiert durch

x21 + x2

2 ≥ 4

x1x2 ≤ 1

x ≥ 0.

Der zulassige Bereich besteht aus zwei getrennt liegenden Teilen. Beide sind nichtkonvex. Selbst bei einer linearen Zielfunktion konnen lokale Minima auftreten, diekeine globalen sind.

1

x

1

2

1 2

2

In der Vorlesung werden u.a. folgende Problemklassen innerhalb der nichtlinea-ren Programme nicht betrachtet:

- mehrere Zielfunktionen,- unendlich viele Nebenbedingungen (semi–infinite Programme),- stochastische Daten (stochastische Optimierung).

63

Kapitel 2

Nichtlineare Optimierungohne Nebenbedingungen

In diesem Abschnitt sollen im wesentlichen Verfahren zur Bestimmung des Mini-mums von nichtglatten Funktionen in einer Variablen im Detail vorgestellt werden,wobei der zulassige Bereich nicht durch Nebenbedingungen eingeschrankt ist. DieMinimierung glatter Funktionen ohne Nebenbedingungen kann auf die Bestimmungvon Nullstellen zuruckgefuhrt werden. Verfahren zur Losung dieser Aufgabe sindbereits aus der Grundvorlesung Praktische Mathematik bekannt.

2.1 Minimierung nichtglatter Funktionen in einerVariablen

Die Losung nichtlinearer Optimierungsaufgaben in einer Dimension tritt als Teil-problem in den meisten Verfahren zur Losung nichtlinearer Optimierungsproblemein hoheren Dimensionen auf.

Seien I ⊂ R ein gegebenes abgeschlossenes Intervall und f : I → R eine gegebeneFunktion. Dann sucht man ein x ∈ I , welches

f (x) = minx∈I

f(x) (2.1)

erfullt. Um ein solches Minimum mit Hilfe eines Verfahrens effizient bestimmen zukonnen, mussen einige einschrankende Bedingungen an f gestellt werden. Je nachEigenschaften der Funktion, ist dann ein entsprechendes Verfahren zu wahlen.

Definition 2.1 Unimodale Funktion. Eine Funktion f : I → R heißt unimodal,falls fur ein x ∈ I = [a, b] gilt, dass f streng monoton fallend auf [a, x] und strengmonoton steigend auf [x, b] ist.

a b

64

Unimodale Funktionen erlauben nach Auswertung der Funktion an zwei Stellenx < y mit a < x < y < b die Reduktion des Intervalls, in der man das Minimum zusuchen hat:

- 1. Fall: f(a) ≤ f(x), dann ist das Minimum in [a, x].- 2. Fall: f(a) > f(x) > f(y). Dann kann das Minimum nicht in [a, x] sein.

- 3. Fall: f(a) > f(x) und f(x) < f(y) und f(y) < f(b). Dann kann dasMinimum nicht in [y, b] sein.

- 4. Fall: f(y) ≥ f(b). Dann ist das Minimum in [y, b].

Alle anderen Falle widersprechen der Definition einer unimodalen Funktion.

Der goldene Schnitt

Wir wollen jetzt durch die rekursive Anwendung dieser Beobachtung einen Algo-rithmus zur Approximation des Punktes konstruieren, an dem das Minimum ange-nommen wird. Dafur stellen wir zunachst einige Forderungen an den Algorithmus:

1.) Im ersten Schritt sollen zwei Funktionswertauswertungen, in allen weiterenSchritten nur eine weitere Funktionswertauswertung im Restintervall verwen-det werden.

2.) Die Punkte x und y sind stets symmetrisch im Restintervall zu wahlen.3.) Der Reduktionsfaktor σ fur die Intervalllange sei konstant, σ ∈ (0.5, 1). Das

heißt, der Quotient der Lange des neuen Intervalls und der Lange des vorhe-rigen Intervalls ist σ = const.

Durch die symmetrische Wahl von x, y im Restintervall wird der Reduktions-faktor unabhangig von der konkreten Funktion f . Verlangt man einen konstantenReduktionsfaktor in allen Iterationen, so ist dieser eindeutig bestimmt.

Um diesen von f unabhangigen Reduktionsfaktor zu bestimmen, genugt es einestreng monoton wachsende Funktion f : [0, 1] → R zu betrachten. O.B.d.A. sei0 < x < y < 1. Daraus folgt y = σ, x = 1 − σ.

Im ersten Schritt wird das Intervall [0, 1] auf das Restintervall [0, y] reduziert.In diesem Restintervall wird dann ein Punkt z symmetrisch zu x gewahlt. Je nachWahl von y gilt z < x oder z ≥ x. Diese Falle entsprechen der Wahl von σ ausunterschiedlichen Intervallen.

1.Fall: σ < 2/3. Dann gilt x = 1 − σ > 1/3 und damit

z = y − x = σ − (1 − σ) < 1/3 < x.

Konstante Reduktion bedeutet nun

x

y=

y

1, =⇒ 0 = y2 − x = σ2 + σ − 1.

Die Losung dieser quadratischen Gleichung ist

σ =1

2

(√5 − 1

)

≈ 0.618 <2

3.

2. Fall: σ ≥ 2/3. Wird analog zum ersten Fall behandelt. Man erhalt keineLosung. Ubungsaufgabe

Der gefundene Reduktionsfaktor ist also unter den obigen Annahmen der einzigmogliche und er legt den Algorithmus fest.

Algorithm 2.2 Goldener Schnitt.

1. Initialisierung.

i := 0; a0 := a; b0 := b;xi := a + (1− σ)(bi − ai); yi := a + σ(bi − ai);

fx := f(xi); fy := f(yi);

65

2. Iteration.

Falls fx < fy, dann

ai+1 := ai; bi+1 := yi;xi+1 := ai+1 + (1− σ)(bi+1 − ai+1); yi+1 := xi;fy := fx; fx := f(xi+1);

sonst

ai+1 := xi; bi+1 := bi;xi+1 := yi; yi+1 := bi+1 − (1− σ)(bi+1 − ai+1);fx := fy; fy := f(yi+1);

i := i + 1;

3. Abbruch.

Falls (bi − ai)/2 > ε, dann

gehe zu 2.

sonst

~x = (ai + bi)/2;stop

In der Praxis fuhrt man erst den Vergleich fur den Abbruch durch und berechnetdann den neuen Funktionswert. Das spart im letzten Schritt eine Funktionswert-berechnung. Diese Einsparung kann sich akkumulieren, falls man das Verfahren imRahmen eines komplexen Problems oft aufruft.

Algorithmus 2.2 bricht ab, sobald der Funktionswert, fur den das Minimumangenommen wird, in einem Intervall der Lange ε eingeschachtelt ist. Da nach n+1Funktionswertauswertungen die Lange des Restintervalls σn(b− a) ist, kann man nin Abhangigkeit von ε a priori abschatzen.

Die Fibonacci–Suche

Wir wollen jetzt auf die Konstanz der Reduktion der Intervalllange verzichten unduntersuchen, ob es Modifikationen von Algorithmus 2.2 gibt, die bei gleicher An-zahl von Funktionswertauswertungen ein kleineres Restintervall liefern. Sei Ln diemaximale Lange eines Intervalls, welches man mittels n Funktionswertauswertun-gen in Ln auf L1 = 1 reduzieren kann. Seien x < y die beiden Stutzstellen inLn. Durch jede dieser Stutzstellen wird Ln in zwei Teilintervalle zerlegt. Betrachtetman die Stutzstelle x, so enthalt das linke Teilintervall hochstens n− 2 Stutzstellen(alle außer x und y) und das rechte Teilintervall hochstens n − 1 der Stutzstellen(alle außer x). Entsprechend sind die Langen dieser Teilintervalle hochstens Ln−2

beziehungsweise Ln−1. Damit gilt

Ln ≤ Ln−1 + Ln−2, n = 2, 3, . . . . (2.2)

Da mindestens zwei Stutzstellen fur eine Intervallreduktion notig sind, gilt L0 =L1 = 1. Mit der obigen Abschatzung hat man das großtmogliche Intervall Ln, fallseine Losung der Ungleichung (2.2) diese sogar als Gleichung erfullt.

Die Losung der Gleichungen

F0 = F1 = 1, Fn = Fn−1 + Fn−2

ist bekannt. Es sind die sogenannten Fibonacci–Zahlen. Die Darstellung dieser Zah-len in geschlossener Form ist

Fi =1√5

(

1 +√

5

2

)i+1

−(

1 −√

5

2

)i+1

.

66

Fur den Algorithmus der Fibonacci–Suche setzen wir noch F−2 := 1, F−1 := 0.Bei der Fibonacci–Suche wird die geforderte Lange des Intervalls, in dem x

eingeschachtelt werden soll, vorgegeben. Die Iterationspunkte bei einem beliebigenStartintervall [a, b] ergeben sich durch lineare Transformation mit dem Faktor

h =b − a

Fn. (2.3)

Die Lange des Restintervalls in der Iteration i = 0, 1, . . . , n − 1 ist Fn−ih. Im vor-letzten Restintervall [an−2, bn−2] der Lange 2h fallen die Stutzpunkte zusammen:xn−2 = yn−2 = an−2 + h. Da fur den Punkt x, in dem das Minimum angenommenwird, gilt x ∈ [an−2, bn−2], folgt somit |x − xn−2| ≤ h. Damit ist durch (2.3) beivorgegebenem h auch die Anzahl der Iterationen n gegeben.

Algorithm 2.3 Fibonacci–Suche.

1. Initialisierung.

gebe h vor, bestimme n, berechne die Fibonacci--Zahlen

F0, . . . , Fn

i := 0; a0 := a; b0 := b; h := (b− a)/Fn;x0 := a0 + Fn−2h; y0 := a0 + Fn−1h;fx := f(x0); fy := f(y0);

2. Iteration.

Falls fx < fy, dann

ai+1 := ai; bi+1 := yi;

xi+1 := ai+1 + Fn−i−3h; yi+1 := xi;fy := fx; fx := f(xi+1);

sonst

ai+1 := xi; bi+1 := bi;

xi+1 := yi; yi+1 := bi+1 − Fn−i−3h;fx := fy; fy := f(yi+1);

i := i + 1;

3. Abbruch.

Falls i < n− 2, dann

gehe zu 2.

sonst

~x = xi;stop

Analog wie beim Goldenen Schnitt kann man im letzten Schritt eine Funktionswert-berechnung sparen.

Beispiel 2.4 Fibonacci–Suche. Wir betrachten die Funktion f(x) = sin(x− 2) auf[a, b] = [0, 2]. Auf diesem Intervall ist die Funktion f unimodal und sie nimmt ihrMinimum in x = 2 − π/2 ≈ 0.4292037 an. Wir wollen die Fibonacci–Suche mitn = 6 durchfuhren. Die Fibonacci–Zahlen F0, . . . , F6 sind 1, 1, 2, 3, 5, 8, 13. Darausfolgt, dass man ein Restintervall der Lange

h =2

13≈ 0.1538462

findet.Die im Verfahren auftretenden Stutzstellen und Intervallgrenzen sind alle von

der Form a+kh mit k ∈ 0, 1, 2, 3, 5, 8, 13. Fur eine Stutzstelle t ∈ [a, b] nennt mandie entsprechende ganze Zahl k(t) := (t − a)/h den Fibonacci–Index von t. BeimStart gilt k(a0) = 0, k(x0) = Fn−2 = F4 = 5 , k(y0) = Fn−1, k(b0) = Fn.

67

Wahrend der Iteration werden die Funktionswerte f(xi) und f(yi) verglichen.Die Variable mit dem kleinerem Funktionswert bleibt Stutzstelle, die mit dem große-ren Funktionswert wird neue Intervallgrenze. Der Fibonacci–Index der neuen Stutz-stelle ergibt sich wegen der symmetrischen Lage der Stutzstellen im Restintervallaus k(xi+1) − k(ai+1) = k(bi+1) − k(yi+1). Ordnet man alle Werte einer Iterationzeilenweise in einer Tabelle an, so verschieben sich diese Werte beim Ubergang zurnachsten Iteration nach rechts beziehungsweise nach links ab der Position der neuenStutzstelle.

i k(ai) xi k(xi) yi k(yi) k(bi) f(xi) f(yi)0 0 0.7692308 5 1.2307692 8 13 - 0.9427456 - 0.69558281 0 0.4615385 3 0.7692308 5 8 - 0.9994773 - 0.94274562 0 0.3076923 2 0.4615385 3 5 - 0.9926266 - 0.99947733 2 0.4615385 3 0.6153846 4 5 - 0.9994773 - 0.98271834 2 0.4615385 3 0.4615385 3 4 - 0.9994773 - 0.9994773

Mit x4 = 0 + 3h bricht das Verfahren ab und fur das Minimum von f gilt

x ∈ [0.4615385− h, 0.4615385 + h].

2

Vergleich von Goldenem Schnitt und Fibonacci–Suche

Aus1 − σ = σ2 (2.4)

folgt induktiv (mit F−2 = 1, F−1 = 0)

σn = (−1)n (Fn−2 − Fn−1σ) .

Ubungsaufgabe Aus F0 = F1 = 1 und F1 = 1 < 1/σ < 2 = F2 erhalt man

F2 <σ2 + σ

σ2= 1 +

1

σ< F3.

Mit Hilfe von (2.4) folgt F2 < 1/σ2 < F3. Induktiv erhalt man fur n > 1 dieAbschatzung

1

Fn> σn >

1

Fn+1und lim

n→∞

Fn

Fn+1= σ.

Unter der Annahme, dass der rechte Grenzwert existiert, kann man diesen mitHilfe von (2.4) berechnen. Ubungsaufgabe Asymptotisch ist der Goldene Schnitt beigleichem Aufwand demnach von kaum geringerer Genauigkeit. Auf der anderen Seitemuss bei Fibonacci–Suche die gewunschte Genauigkeit a priori festgelegt werden,um n zu bestimmen.

Beide Verfahren reduzieren die Intervalllange linear, dass heisst es gilt

|bi+1 − ai+1||bi − ai|

≤ λ mit λ ∈ (0, 1).

Dabei ist der Reduktionsfaktor λ beim Goldenen Schnitt durch σ gegeben undbei der Fibonacci–Suche durch eine Schranke fur Fn−1/Fn. Soll das n–te Intervallkleiner als ein gegebenes ε sein, so erhalt man aus

ε ≥ λn(b − a) = λn(b0 − a0)

die Abschatzung

n ≥ log

(ε

b − a

)

/ log(λ).

68

2.2 Differenzierbare Funktionen

Sei f : Rn → R mit f ∈ C1(Rn) gegeben. Die notwendige Bedingung fur ein lokalesMinimum im Punkt x ∈ Rn ist

∇f(x) = 0.

Zur Berechnung von moglichen Werten fur x hat man damit ein nichtlineares Glei-chungssystem zu losen. Verfahren zur Losung nichtlinearer Gleichungssysteme wer-den in der Vorlesung Praktische Mathematik behandelt und deshalb soll hier nurdie Namen einiger Verfahren genannt werden:

- Bisektion falls n = 1,

- Gradientenverfahren (Verfahren des steilsten Abstiegs),- Fixpunktiteration, wobei die nachfolgenden Verfahren Spezialfalle sind,- Newton–Verfahren,- vereinfachtes und Quasi–Newton–Verfahren.

69

Kapitel 3

Konvexitat

3.1 Konvexe Mengen

Der Begriff der konvexen Menge ist bereits aus Definition 1.4, Teil I, bekannt.

Definition 3.1 Konvexer Kegel. Eine Menge Ω ⊂ Rn heißt konvexer Kegel,wenn mit x1,x2 ∈ Ω auch λ1x1 + λ2x2 ∈ Ω fur alle λ1, λ2 ≥ 0. 2

Beispiel 3.2 Fur λ1 = λ2 = 0 folgt, dass insbesondere 0 in einem konvexen Kegelenthalten sein muss.

Nicht jede konvexe Menge ist ein konvexer Kegel, zum Beispiel sind Kreise keinekonvexen Kegel.

Der Winkelraum mit Scheitel 0 ist ein konvexer Kegel. Der Winkelraum mitScheitel 6= 0 ist kein konvexer Kegel.

Sei a ∈ Rn, a 6= 0, α ∈ R und definiere die Hyperebene

H(a, α) =x ∈ Rn : aT x = α

.

Diese Hyperebene ist eine konvexe Menge. Ubungsaufgabe Ist α 6= 0, dann ist 0 6∈H(a, α) und H(a, α) ist kein konvexer Kegel. Im Falle α = 0 ist H(a, α) ein konvexerKegel H(a, α) = a⊥. Ubungsaufgabe

Analog gilt fur Halbraume

H+(a, α) =x ∈ Rn : aT x ≥ α

, H−(a, α) =

x ∈ Rn : aT x ≤ α

,

dass diese fur α = 0 konvexe Kegel sind und sonst nicht.Eine Menge, die durch Hyperebenen berandet ist, die allesamt den Punkt 0 ent-

halten, wird auch polyhedrischer Kegel genannt. Polyhedrische Kegel sind konvexeKegel, insbesondere

Rn+ = x ∈ Rn : x ≥ 0 .

2

Definition 3.3 Trennung von Mengen. Die Hyperebene H(a, α) trennt dienichtleeren Mengen Ω1, Ω2 ⊂ Rn, wenn gilt

aT x ≤ α ∀x ∈ Ω1 und aT x ≥ α ∀x ∈ Ω2.

Falls in beiden Relationen die echten Ungleichungen stehen, dann wird die Trennungstreng genannt. 2

Lemma 3.4 Sei Ω ⊂ Rn nichtleer, abgeschlossen und konvex und gelte 0 6∈ Ω.Dann existiert eine Hyperebene H(a, α) mit α > 0 , so dass aT x > α fur allex ∈ Ω.

70

Beweis: Wir werden eine konkrete Hyperebene angeben.Sei x1 ∈ Ω und B1 = x ∈ Rn : ‖x‖2 ≤ ‖x1‖2 eine Kugel mit Radius

‖x1‖2 und Mittelpunkt 0. Dann ist Ω ∩ B1 6= ∅ und der Durchschnitt ist kompakt(abgeschlossen und beschrankt). Damit nimmt die stetige Funktion d(x) = ‖x‖2 ihrMinimum uber Ω ∩ B1 6= ∅ in einem Punkt x0 an (Satz von Bolzano–Weierstrass),dass heißt es gilt

‖x‖2 ≥ ‖x0‖2 ∀ x ∈ Ω ∩ B1. (3.1)

Wegen 0 6∈ Ω ist ‖x0‖2 > 0. Da die Elemente von Ω, die nicht in Ω∩B1 liegen, einegroßere Norm als ‖x1‖2 ≥ ‖x0‖2 besitzen, gilt (3.1) fur alle x ∈ Ω.

Wegen der Konvexitat von Ω gilt somit fur alle x ∈ Ω und λ ∈ (0, 1]

‖(1 − λ)x0 + λx‖2 = ‖x0 + λ (x − x0)‖2 ≥ ‖x0‖2 > 0.

Quadratur dieser Ungleichung und Ausschreiben der Skalarprodukte ergibt

2λ (x − x0)T

x0 + λ2 (x − x0)T

(x − x0) ≥ 0.

Division durch λ und dann λ → 0 ergibt

xT x0 ≥ xT0 x0 = ‖x0‖2

2 >‖x0‖2

2

2> 0 ∀ x ∈ Ω.

Die Hyperebene mit a = x0 und α = ‖x0‖22 /2 erfullt nun die Bedingungen des

Lemmas.Eine Folgerung ist der nachfolgende Satz.

Satz 3.5 Erster Trennungssatz. Seien Ω1 6= ∅ abgeschlossen und konvex und Ω2

kompakt und konvex, Ω1, Ω2 ⊂ Rn, mit Ω1∩Ω2 = ∅. Dann existiert eine HyperebeneH(a, α), die Ω1 und Ω2 streng trennt.

Beweis: Seien

−Ω1 = x : x = −y,y ∈ Ω1 ,

Ω2 − Ω1 = x : ∃x1 ∈ Ω1,x2 ∈ Ω2 mit x = x2 − x1 .

Diese Mengen sind konvex und abgeschlossen. Da Ω1 und Ω2 einen leeren Durch-schnitt haben, gilt 0 6∈ Ω2 − Ω1. Nach Lemma 3.4 gibt es eine Hyperebene H(a, α)mit α > 0 und aT (x2 − x1) > α > 0 fur alle x1 ∈ Ω1,x2 ∈ Ω2. Damit gilt

infx2∈Ω2

aT x2 ≥ supx1∈Ω1

aT x1 + α > supx1∈Ω1

aT x1.

Jede Hyperebene H(a, β) mit

β ∈(

supx1∈Ω1

aT x1, infx2∈Ω2

aT x2

)

trennt damit Ω1 und Ω2 streng.Ubungsaufgabe: Notwendigkeit der Kompaktheitsvoraussetzung fur strenge Tren-

nung an Beispiel zeigen.

Satz 3.6 Jede abgeschlossene konvexe Menge Ω ⊂ Rn ist der Durchschnitt allerabgeschlossenen Halbraume, die Ω enthalten.

71

Beweis: Beweisskizze. Bezeichnen wir den Durchschnitt aller abgeschlossenenHalbraume, die Ω enthalten, mit D. Dann ist Ω ⊂ D klar (Durchschnitt beliebigvieler konvexer Mengen ist konvex). Zu zeigen bleibt D ⊂ Ω. Das geschieht in-direkt, wobei der Widerspruch mit einer trennenden Hyperebene hergeleitet wird(sogenannter zweiter Trennungssatz, Details siehe [ERSD77, Abschnitt 2.1.4]).

Der Eckpunkt oder Extrempunkt einer konvexen Menge wurde bereits in Defi-nition 1.10, Teil I, definiert als ein Punkt, fur den es keine echte konvexe Linear-kombination gibt. Dafur, dass x0 ∈ Ω ein Extrempunkt ist, reicht es bereits aus,dass man keine x1,x2 ∈ Ω findet, so dass

x0 =1

2x1 +

1

2x2. x1,x2 6= x0, Ubungsaufgabe

Satz 3.7 Jede nichtleere, kompakte, konvexe Menge Ω ∈ Rn besitzt mindestenseinen Extrempunkt.

Beweis: Da Ω kompakt ist, gibt es ein x0 mit ‖x0‖2 ≥ ‖x‖2 fur alle x ∈ Ω. Sei

x0 =1

2x1 +

1

2x2 = x1 +

1

2(x2 − x1) = x2 +

1

2(x1 − x2)

fur x1,x2 ∈ Ω, x1,x2 6= x0. Damit folgt

‖x1‖22 ≤ ‖x0‖2

2 = ‖x1‖22 +

1

4‖x2 − x1‖2

2 + (x2 − x1)T

x1

︸ ︷︷ ︸

≥0, da ‖x0‖2≥‖x1‖2

.

Das heißt‖x2 − x1‖2

2 ≥ −4 (x2 − x1)T x1

und analog‖x2 − x1‖2

2 ≥ −4 (x1 − x2)T x2 = 4 (x2 − x1)

T x2.

Addition der Ungleichungen ergibt

2 ‖x2 − x1‖22 ≥ 4 (x2 − x1)

T (x2 − x1) = 4 ‖x2 − x1‖22

und damit x2 = x1 = x0. Somit ist x0 ein Extrempunkt.

3.2 Konvexe und konkave Funktionen

Definition 3.8 Konvexe, konkave Funktion. Die Funktion f : Ω ⊂ Rn → R

heißt konvex, wenn fur beliebige x1,x2 ∈ Ω gilt

f ((1 − λ)x1 + λx2) ≤ (1 − λ)f(x1) + λf(x2) ∀ λ ∈ [0, 1].

Sie heißt konkav, wenn

f ((1 − λ)x1 + λx2) ≥ (1 − λ)f(x1) + λf(x2) ∀ λ ∈ [0, 1].

2

Gilt die echte Ungleichung spricht man von strenger Konvexitat (Konkavitat).

Beispiel 3.9 Die lineare Funktion f(x) = cT x mit c ∈ Rn ist konvex und konkavin Rn, jedoch nicht streng. 2

72

Beispiel 3.10 Jede uber Rn positiv semidefinite Bilinearform f(x) = xT Ax mitA = AT ∈ Rn×n ist konvex. Sei namlich

x = (1 − λ)x1 + λx2 = x1 + λ(x2 − x1), x1 6= x2 ∈ Rn,

dann gilt

xT Ax = xT1 Ax1 + 2λ(x2 − x1)

T Ax1 + λ2︸︷︷︸

≤λ

(x2 − x1)T A(x2 − x1)

︸ ︷︷ ︸

≥0

≤ xT1 Ax1 + 2λ(x2 − x1)

T Ax1 + λ(x2 − x1)T A(x2 − x1)

= xT1 Ax1 + λ(x2 − x1)

T A (x1 + x2)

= (1 − λ)xT1 Ax1 + λxT

2 Ax2.

Analog zeigt man, dass

- A ist positiv definit, dann ist f(x) streng konvex,- A ist negativ semidefinit, dann ist f(x) konkav,- A ist negativ definit, dann ist f(x) streng konkav.

2

Beispiel 3.11 Sind die Funktionen fj(x), j = 1, . . . , k, uber Ω ∈ Rn konvex, dannist auch die Linearkombination

f(x) =

k∑

j=1

αjfj(x), αj ≥ 0 ∀ j

konvex. 2

Zur Stetigkeit von konvexen Funktionen gibt es folgende Aussage.

Satz 3.12 Seien Ω ⊂ Rn konvex und das Innere der Menge, int(Ω), nichtleer. Dannist jede konvexe Funktion f : Ω → R stetig in int(Ω).

Beweis: Siehe Literatur, zum Beispiel [ERSD77, Satz 2.65]. Man pruft dieε–δ–Definition nach.

Beispiel 3.13 Nichtstetige konvexe Funktion uber konvexer Menge. Stetigkeit bisauf den Rand muss bei einer konvexen Funktion im allgemeinen nicht vorliegen. Diekonvexe Funktion f : [1, 2] → R mit

f(x) =

1/x fur x ∈ [1, 2)2 fur x = 2

ist ein Beispiel. 2

Jetzt werden einige Bedingung dafur gegeben, dass ein Funktion auf einer kon-vexen Menge konvex ist. Zunachst wird eine Monotonieaussage fur den Differenzen-quotienten gegeben.

Lemma 3.14 Seien Ω ⊂ Rn eine offene konvexe Menge, f : Ω → R mit f ∈ C1(Ω)eine konvexe Funktion, x0,h ∈ Ω, x0−νh ∈ Ω und x0+ρh ∈ Ω fur gewisse ν, ρ > 0.Dann gilt

f(x0) − f(x0 − νh)

ν≤ f(x0) − f(x0 − µh)

µ

≤ f(x0 + λh) − f(x0)

λ≤ f(x0 + ρh) − f(x0)

ρ

fur alle µ ∈ (0, ν], λ ∈ (0, ρ].

73

Beweis: UbungsaufgabeDamit ist fur konvexe Funktionen der Differenzenquotient im Punkt x0 in Rich-

tung h eine monoton wachsende Funktion von λ.

Satz 3.15 Sei Ω ⊂ Rn eine offene konvexe Menge und f : Ω → R mit f ∈ C1(Ω).Dann ist f auf Ω genau dann konvex, wenn fur alle x0,x1 ∈ Ω mit x0 6= x1 gilt

f(x1) − f(x0) ≥ (x1 − x0)T∇f(x0). (3.2)

Beweis: 1) Notwendigkeit von (3.2). Da f differenzierbar ist, gilt fur die Rich-tungsableitung in Richtung h ∈ Rn mit ‖h‖2 = 1

∂f

∂h(x0) = hT∇f(x0) = lim

λ→0

f(x0 + λh) − f(x0)

λ= − lim

λ→0

f(x0 − λh) − f(x0)

λ.

Nach Lemma 3.14 gilt alle ρ > 0 mit x0 + ρh ∈ Ω (nehme λ → 0 in Lemma 3.14 )

f(x0 + ρh) − f(x0)

ρ≥ hT∇f(x0)

oderf(x0 + ρh) ≥ f(x0) + ρhT∇f(x0).

Wahlt man x1 = x0 + ρh, so ergibt sich (3.2).2) Hinlanglichkeit von (3.2). Sei λ0 > 0 beliebig gewahlt, setzte λ1 = 1 − λ0.

Dann gilt fur x2 = λ0x0 + λ1x1 nach Voraussetzung

f(x0) − f(x2) ≥ (x0 − x2)T∇f(x2), f(x1) − f(x2) ≥ (x1 − x2)

T∇f(x2).

Damit folgt

λ0f(x0) + λ1f(x1) ≥ f(x2) +(

λ0(x0 − x2) + λ1(x1 − x2))T

∇f(x2)

= f(x2) +(

λ0x0 + λ1x1 − x2

)T

︸ ︷︷ ︸

=0

∇f(x2)

= f(x2) = f(λ0x0 + λ1x1)

fur alle x0,x1 ∈ Ω.Fur eine zweimal stetig differenzierbare Funktion f : Ω → R, Ω ⊂ Rn, offen, ist

die Hesse–Matrix

Hf (x) :=

(∂2f(x)

∂xi∂xj

)

i,j=1,...,n

symmetrisch.Liegt zusammen mit x0,x1 die Strecke [x0,x1] vollstandig in Ω, so gilt fur eine

geeignete Zahl λ ∈ (0, 1) nach dem Satz von Taylor

f(x1) = f(x0)+(x1−x0)T∇f(x0)+

1

2(x1−x0)

T Hf (x0+λ(x1−x0))(x1−x0). (3.3)

Satz 3.16 Seien Ω ⊂ Rn eine offene konvexe Menge und f : Ω → R mit f ∈ C2(Ω).Dann ist f auf Ω genau dann konvex, wenn Hf (x) positiv semidefinit ist fur allex ∈ Ω.

Beweis: 1.) Sei Hf (x) positiv semidefinit. Dann folgt aus (3.3) fur beliebigex0,x1 ∈ Ω und eine geeignete Zahl λ ∈ (0, 1)

f(x1)−f(x0)− (x1−x0)T∇f(x0) =

1

2(x1−x0)

T Hf (x0 +λ(x1 −x0))(x1 −x0) ≥ 0.

74

Aus Satz 3.15 folgt, dass f(x) konvex ist.2) Sei f(x) konvex auf Ω. Seien x0 ∈ Ω und h ∈ Rn beliebig gegeben. Da Ω

offen ist, gibt es eine Zahl θ0 > 0 so dass x0 + θh ∈ Ω fur alle θ ∈ (0, θ0]. Wahltman in (3.2) x1 = x0 + θh, erhalt man

f(x0 + θh) − f(x0) − θhT∇f(x0) ≥ 0 ∀ θ ∈ (0, θ0].

Aus (3.3) folgt nun

hT Hf (x0 + λθh)h ≥ 0 ∀ θ ∈ (0, θ0]

mit λ ∈ (0, 1). Da die Hesse–Matrix nach Voraussetzung stetig ist, folgt fur θ → +0

hT Hf (x0)h ≥ 0.

Da x0 ∈ Ω und h ∈ Rn beliebig gewahlt wurden, ist Hf (x) in jedem Punkt x ∈ Ωpositiv semidefinit.

Eine skalare Funktion einer skalaren Veranderlichen f : (a, b) → R mit f ∈C2(a, b) ist konvex, wenn f ′′(x) ≥ 0 in (a, b), zum Beispiel die Funktion f(x) = x2.

Bemerkung 3.17 Es gibt Verallgemeinerungen des Begriffs der komplexen Funk-tion, zum Beispiel quasi–konvex und explizit konvex, siehe Literatur. 2

3.3 Ungleichungen und konvexe Mengen

Satz 3.18 Die Funktion f : Ω ⊂ Rn → R sei konvex, Ω sei konvex und sei b ∈ R.Dann ist

V = x ∈ Ω : f(x) ≤ bkonvex.

Beweis: Zu zeigen ist: x1,x2 ∈ V =⇒ x = (1 − λ)x1 + λx2 ∈ V fur alleλ ∈ [0, 1]. Aus f(x1), f(x2) ≤ b folgt aus der Konvexitat von f

f(x) ≤ (1 − λ)f(x1) + λf(x2) ≤ b.

Damit ist x ∈ V .

Bemerkung 3.19 1.) Die Menge V aus Satz 3.18 heißt Unterhalbmenge von f(x)in Ω zum Wert b.

2.) Die Niveaumenge x ∈ Ω : f(x) = b der konvexen Funktion f(x) ist imallgemeinen nicht konvex. Zum Beispiel besteht die Niveaumenge zu b = 1 derkonvexen Funktion f(x) = x2, x ∈ R, aus den Punkten −1 und 1.

Folgerung 3.20 Sei f : Ω ⊂ Rn → R konkav, sei Ω konvex und sei b ∈ R. Dannist U = x ∈ Ω : f(x) ≥ b konvex.

Beweis: Nutze Satz 3.18 mit −f(x), da diese Funktion konvex ist.

3.4 Extrema von konvexen Funktionen

Es wird die Frage untersucht, unter welchen Bedingungen eine konvexe Funktionihr globales Minimum uber einer gegebenen konvexen Menge Ω annimmt.

Satz 3.21 Sei f : Ω → R eine konvexe Funktion uber einer konvexen Menge Ω.Dann ist ein lokales Minimum von f(x) in Ω zugleich das globale Minimum uber Ω.

75

Beweis: Indirekt. Nehme f(x) ein lokales Minimum in x0 ∈ Ω an. Sei weiterx∗ ∈ Ω mit f(x∗) < f(x0). Aus der Konvexitat von f(x) folgt

f((1 − λ)x0 + λx∗) ≤ (1 − λ)f(x0) + λf(x∗) = f(x0) + λ (f(x∗) − f(x0)) < f(x0)

fur alle λ ∈ (0, 1), da f(x∗) < f(x0). Aus der Konvexitat von Ω folgt, dass derFunktionswert im Zwischenpunkt wohldefiniert ist. Wahlt man λ < ε so ist derZwischenpunkt beliebig nahe an x0 und die obige Ungleichung steht im Widerspruchdazu, dass f(x) in x0 ein lokales Minimum annimmt.

Beispiel 3.22 Konvexe Funktion uber konvexer Menge ohne Annahme eines loka-len Minimums. Der obige Satz kann nur angewendet werden, wenn es ein lokalesMinimum gibt, das angenommen wird. Das muss nicht der Fall sein. Die konvexeFunktion aus Beispiel 3.13 nimmt ihr Minimum nicht an. 2

Folgerung 3.23 Die Menge Ω0, uber der eine konvexe Funktion f : Ω → R ubereiner konvexen Menge Ω das globale Minimum annimmt, ist konvex.

Beweis: Folgt aus Satz 3.18.

Satz 3.24 Sei f(x) ∈ C1(Ω) uber einer konvexen Menge Ω konvex. Dann nimmtf(x) in jedem x1 ∈ Ω mit ∇f(x1) = 0 sein globales Minimum uber Ω an.

Beweis: Es ist zu zeigen, dass alle Punkte x1 ∈ Ω mit ∇f(x1) = 0 wirklichExtremalpunkte sind und zudem Minima.

Sei x1 ∈ Ω mit ∇f(x1) = 0. Da f(x) konvex ist, gilt

f (λx2 + (1 − λ)x1) ≤ (1 − λ)f(x1) + λf(x2) = f(x1) + λ (f(x2) − f(x1))

fur alle x2 ∈ Ω und λ ∈ [0, 1]. Fur λ ∈ (0, 1] erhalt man daraus

f (x1 + λ(x2 − x1)) − f(x1)

λ≤ f(x2) − f(x1).

Nach dem Mittelwertsatz der Differentialrechnung gibt es ein θ ∈ [0, 1] mit

(x2 − x1)T ∇f (x1 + θλ(x2 − x1)) ≤ f(x2) − f(x1).

Fur λ → 0 folgt nun mit ∇f(x1) = 0

0 = (x2 − x1)T ∇f (x1) ≤ f(x2) − f(x1),

also f(x1) ≤ f(x2) fur alle x2 ∈ Ω.

76

Kapitel 4

Optimalitatskriterien

Als Optimalitatskriterien bezeichnet man notwendige oder hinreichende Bedingun-gen dafur, dass ein x0 ∈ Ω ⊂ Rn Losung eines Optimierungsproblems ist. DieseKriterien besitzen sowohl unter theoretischen als auch unter numerischen Aspek-ten Bedeutung. In diesem Kapitel werden lokale und globale Optimalitatskriterienhergeleitet.

4.1 Einleitung

Ein Gegenstand dieses Kapitels ist die Verallgemeinerung der Methode der La-grangeschen Multiplikatoren auf Probleme mit Bedingungsungleichungen und be-schrankten Variablen. Es wird der Zusammenhang zwischen der Losung eines Op-timierungsproblems und dem Sattelpunkt eines Lagrangeschen Funktionals herge-stellt.

Wir betrachten zunachst die Lagrangesche Methode fur ein Optimierungspro-blem mit Nebenbedingungen in Gleichungsform

f(x) : x ∈ Ω ⊂ Rn → min !, (4.1)

Ω = x ∈ Rn : hi(x) = 0, i ∈ 1, . . . , p, p < n .

Seien f(x) in Ω und hi(x), i = 1, . . . , p, in Rn differenzierbar. Fur beliebiges festesx ∈ Ω werden die Matrizen

H0(x) := (∇h1(x), . . . ,∇hp(x))T ∈ Rp×n, H(x) :=

(H0(x)∇f(x)T

)

∈ R(p+1)×n

definiert.Fur das Problem (4.1) wird die Lagrange–Funktion

L(x, λ) = λ0f(x) +

p∑

i=1

λihi(x), x ∈ Ω, λ ∈ Rp+1,

eingefuhrt. Die Zahlen λ0, . . . , λp nennt man Lagrangesche Multiplikatoren. Mankann beispielsweise folgendes Optimalitatskriterium fur Problem (4.1) beweisen.

Satz 4.1 Seien x0 ∈ Ω und rg(H0(x0)) = rg(H(x0)). Dann gilt: besitzt f(x) in x0

ein lokales Minimum bezuglich Ω, so existiert ein λ(0) =(

λ(0)0 , . . . , λ

(0)p

)T

∈ Rp+1,

mit λ(0)0 6= 0 und

∇xL(x0, λ(0)) = λ

(0)0 ∇f(x0) +

p∑

i=1

λ(0)i ∇hi(x0) = 0. (4.2)

77

Verallgemeinerungen dieser Aussage auf den Fall, dass die Matrizen unterschied-lichen Rang besitzen, sind moglich. Mit Hilfe des Gleichungssystems (4.2) hat manein Kriterium zur Bestimmung von Punkten, in denen f(x) ein lokales Minimum an-nehmen kann. Sofern dies moglich ist, berechnet man alle Losungen (x, λ) von (4.2).Im allgemeinen sind jedoch nicht alle Losungen auch lokale Extrempunkte.

Das heißt, man erweitert das gegebene Problem so, dass

- man fur die Losung des erweiterten Problems Standardkriterien, zum Beispieldass Ableitungen verschwinden, fur ein Minimum hat,

- die Losung des erweiterten Problems Ruckschlusse auf die Losung des gege-benen Problems zulasst.

4.2 Lokale Minima fur Optimierungsprobleme oh-ne Einschrankungen an das zulassige Gebiet

Wir betrachten das folgende Optimierungsproblem

z = minf(x) : x ∈ Ω (4.3)

mit f ∈ C1(Rn) (an sich reicht f ∈ C1(Ω) mit Ω ⊂ Ω, Ω offen). Fur diese Problemsollen im folgenden lokale Optimalitatskriterien hergeleitet werden.

Zunachst werden spezielle konvergente Folgen betrachtet.

Definition 4.2 Konvergent gegen x0 in Richtung y, gerichtet konvergent.Eine konvergente Folge xkk∈N, xk ∈ Rn, mit xk → x0 heißt konvergent gegen x0

in Richtung y ∈ Rn oder gerichtet konvergent, wenn gilt

limk→∞

xk − x0

‖xk − x0‖2

= y, ‖y‖2 = 1.

Die Schreibweise istxk

y−→ x0.

2

Beispiel 4.3 Sei xkk∈N mit

xk =

(1

k,1

k

)T

.

Dann ist x0 = (0, 0)T und es gilt

limk→∞

xk

‖xk‖2

= limk→∞

k√2

(1k1k

)

=1√2

(11

)

= y.

Ubungsaufgabe 2

Man kann aus jeder gegen x0 konvergenten Folge eine xkk∈N eine gerichtetkonvergente Teilfolge auswahlen, sofern unendlich viele Elemente der Folge ungleichx0 sind. Sei xk 6= x0 fur k ≥ k0, dann sind alle Glieder der Folge

yk :=xk − x0

‖xk − x0‖2

, k ≥ k0,

Elemente der kompakten Menge x ∈ Rn : ‖x‖2 = 1. Damit besitzt ykk∈N

einen Haufungspunkt in dieser Menge und man findet in ykk∈N eine konvergenteTeilfolge.

Die Aussage des folgenden Lemmas kann in gewisser Weise als Verallgemeine-rung der Richtungsableitung aufgefasst werden.

78

Lemma 4.4 Die Folge xkk∈N sei konvergent gegen x0 in Richtung y. Dann gilt:

1. Ist f : Rn → R in x0 stetig differenzierbar, so folgt

limk→∞

f(xk) − f(x0)

‖xk − x0‖2

= yT∇f(x0).

2. Ist f : Rn → R in x0 zweimal stetig differenzierbar, so gilt

limk→∞

f(xk) − f(x0) − (xk − x0)T∇f(x0)

‖xk − x0‖22

=1

2yT Hf (x0)y.

Beweis: Es wird nur die erste Aussage bewiesen, der Beweis der zweiten Aus-sage ist analog.

Da f(x) in x0 differenzierbar ist, also insbesondere alle Richtungsableitungenexistieren, gilt

limx→x0

(f(x) − f(x0)

‖x − x0‖2

− (x − x0)T

‖x − x0‖2

∇f(x0)

)

= 0.

Außerdem existiert nach Voraussetzung der Grenzwert

limxk→x0

(xk − x0)T

‖xk − x0‖2

∇f(x0) = yT∇f(x0).

Damit folgt

limxk→x0

f(xk) − f(x0)

‖xk − x0‖2

= limxk→x0

(xk − x0)T

‖xk − x0‖2

∇f(x0) = yT∇f(x0).

Definition 4.5 Tangentenkegel. Der Tangentenkegel T (x0) an die Menge Ω imPunkt x0 ∈ Ω ist gegeben durch

T (x0) :=

λy : ‖y‖2 = 1, ∃xkk∈N ∈ Ω,xky−→ x0, λ ≥ 0

.

2

Der Tangentenkegel T (x0) hat nur etwas mit dem zulassigen Gebiet Ω zu tun undnicht mit der zu minimierenden Funktion f(x). Er beschreibt die Richtungen, ausdenen man sich x0 mit einer Folge annahern kann, deren Glieder alle in Ω liegen. DerBegriff des Tangentenkegels ist eine Verallgemeinerung der Tangetialhyperebene.Die Menge T (x0) ist ein Kegel. Fur jeden inneren Punkt x0 ∈ Ω gilt T (x0) = Rn.Fur isolierte Punkte setzen wir T (x0) = 0.

Beispiel 4.6 Sei

Ω = x ∈ R2 : x21 + x2

2 = 1, x1 ≥ 0, 0 < x2 < 2.

Fur den Punkt x0 = (0, 1)T ∈ Ω erhalt man, direkt aus der geometrischen Anschau-ung,

T (x0) =

y ∈ R2 : λ

(10

)

, λ ≥ 0

.

Analytisches Nachrechnen: Ubungsaufgabe 2

Lemma 4.7 Fur jeden Punkt x0 ∈ Ω ist der Tangentenkegel T (x0) abgeschlossen.

79

Beweis: Siehe Literatur.Der folgende Satz gibt ein notwendiges Kriterium fur die Existenz eines lokalen

Minimums von f(x) bezuglich Ω an. Das lokale Minimum kann auf dem Rand vonΩ liegen und kein lokales Minimum fur eine Menge sein, die Ω umfasst, deshalb dieBezeichnung bezuglich Ω.

Satz 4.8 Sei f : Rn → R in x0 ∈ Ω stetig differenzierbar. Besitzt f(x) in x0 einlokales Minimum bezuglich Ω, dann gilt

yT∇f(x0) ≥ 0 ∀ y ∈ T (x0).

Beweis: Sei y ∈ T (x0). Fur y = 0 ist yT∇f(x0) = 0. Ansonsten existieren einλ ∈ R, λ > 0 und ein y∗ ∈ T (x0), ‖y∗‖2 = 1, mit y = λy∗. Ferner sei xkk∈N ⊂ Ω

eine Folge mit xky∗

−→ x0.Da f(x) in x0 ein lokales Minimum bezuglich Ω annimmt, gilt fur hinreichend

große k die Ungleichung f(xk) ≥ f(x0). Daraus folgt unter Beachtung von Lem-ma 4.4, 1)

limk→∞

f(xk) − f(x0)

‖xk − x0‖2

= (y∗)T ∇f(x0) ≥ 0

und damit auch yT∇f(x0) ≥ 0.Aus diesem Satz folgt nicht, dass f(x) in x0 ein lokales Minimum nur annehmen

kann, wenn ∇f(x0) = 0 gilt. Gilt jedoch ∇f(x0) = 0, dann hat man ein zweitesnotwendiges Kriterium.

Satz 4.9 Sei f : Rn → R in x0 ∈ Ω zweimal stetig differenzierbar. Besitzt f(x) inx0 ein lokales Minimum bezuglich Ω und gilt ∇f(x0) = 0, dann folgt

yT Hf (x0)y ≥ 0 ∀ y ∈ T (x0).

Beweis: Der Beweis ist analog zum Beweis von Satz 4.8, wobei jedoch jetztLemma 4.4, 2) verwendet wird. Aus (xk − x0)

T∇f(x0) = 0 und f(xk) ≥ f(x0) furhinreichend große Indizes k folgt dann

limk→∞

f(xk) − f(x0) − (xk − x0)T∇f(x0)

‖xk − x0‖22

=1

2(y∗)T Hf (x0)y

∗ ≥ 0.

Der folgende Satz enthalt eine hinreichende Bedingung fur die Existenz eineseigentlichen lokalen Minimums von f(x) bezuglich Ω.

Satz 4.10 Sei f : Rn → R in x0 ∈ Ω zweimal stetig differenzierbar. Gelten∇f(x0) = 0 und yT Hf (x0)y > 0 fur alle y ∈ T (x0),y 6= 0, dann besitzt f(x)in x0 ein isoliertes lokales Minimum bezuglich Ω.

Beweis: Indirekter Beweis. Wir nehmen an, dass f(x) in x0 kein isoliertes loka-les Minimum bezuglich Ω besitzt. Dann existiert eine Folge xkk∈N ⊂ Ω mit xk →x0, mit unendlich vielen Elementen, die ungleich x0 sind, und f(xk) ≤ f(x0), k ≥ 1.Es existiert eine Teilfolge von xk, die gegen ein y gerichtet konvergent ist. Ohne

Beschrankung der Allgemeinheit kann auch xky−→ x0 angenommen werden. Dann

folgt aus Lemma 4.4

limk→∞

f(xk) − f(x0)

‖xk − x0‖22

=1

2yT Hf (x0)y ≤ 0

mit y ∈ T (x0), im Widerspruch zur Voraussetzung.Fur jeden inneren Punkt x0 ∈ Ω gilt T (x0) = Rn und aus den Aussagen der

Satze 4.8 – 4.10 folgen die bekannten notwendigen und hinreichenden Bedingungenfur die Existenz lokaler Minima einer Funktion f : Rn → R.

80

4.3 Lokale Minima fur Optimierungsprobleme, bei

denen das zulassige Gebiet durch Ungleichun-gen gegeben ist

In diesem Abschnitt wird das Optimierungsproblem

z = minf(x) : x ∈ Ω mit Ω = x ∈ Rn : g(x) ≤ 0 (4.4)

mit f ∈ C1(Rn) und g : Rn → Rm, g ∈ C1(Rn). Unter Verwendung der Resultateaus Abschnitt 4.2 werden nun lokale Optimierungskriterien fur (4.4) hergeleitet.Dazu wird eine lokale Theorie von Lagrange–Multiplikatoren entwickelt.

Definition 4.11 Aktive Nebenbedingung. Eine Nebenbedingung gi(x) ≤ 0, i =1, . . . , m, wird im Punkt x0 ∈ Ω aktiv genannt, wenn gilt gi(x0) = 0. Bezeichnung:

I0 := i ∈ 1, . . . , m : gi(x0) = 0 .

2

Sei I0 6= ∅. Die in x0 aktiven Nebenbedingungen werden nun durch affine Funk-tionen ersetzt

(∇gi(x0))T

(x − x0) , x ∈ Rn, i ∈ I0,

beziehungsweise in Matrixnotation

(∇gI0(x0))T

(x − x0) , ∇gI0(x0) ∈ Rn×|I0|.

Der Gradient einer vektorwertigen Funktion g(x) ist wie folgt definiert:

∇g(x) =

(g1(x))x1 · · · (gm(x))x1

· · · · · · · · ·(g1(x))xn

· · · (gm(x))xn

∈ Rn×m.

Ausgehend von der Anschauung, konnte man die Menge

x : (∇gI0(x0))T (x − x0) ≤ 0, gI\I0(x0) +

(∇gI\I0(x0)

)T(x − x0) ≤ 0

als eine lineare Approximation der Menge Ω im Punkt x0 ansehen. Dies ist jedochin gewissen ausgearteten Punkten nicht zutreffend, siehe Beispiel 4.15

Definition 4.12 Linearisierter Kegel. Die Menge

K(x0) := y ∈ Rn : (∇gI0(x0))T

y ≤ 0

heißt linearisierter Kegel von Ω im Punkt x0 ∈ Ω. Fur I0 = ∅ setzen wir K(x0) =Rn. 2

Lemma 4.13 Es gilt T (x0) ⊆ K(x0).

Beweis: Fur I0 = ∅ gilt die Behauptung trivialerweise. Sei also I0 6= ∅. DerNullvektor gehort per Definition zu beiden Mengen. Sei y ∈ T (x0), y 6= 0. Dannexistieren ein y∗ ∈ T (x0), ‖y∗‖2 = 1 und ein λ > 0 mit y = λy∗ und eine Folge

xkk∈N ⊂ Ω mit xky∗

−→ x0. Wegen gi(xk) ≤ 0 fur alle i ∈ I0 und gi(x0) = 0 furalle i ∈ I0 hat man

limk→∞

gi(xk) − gi(x0)

‖xk − x0‖2

= ∇gi(x0)T y∗ ≤ 0 ∀i ∈ I0,

wobei Lemma 4.4, 1) verwendet wurde. Folglich gilt y ∈ K(x0).

81

Lemma 4.14 Es gilt K0(x0) := y ∈ Rn : (∇gI0(x0))T

y < 0 ⊆ T (x0).

Beweis: Siehe Literatur, zum Beispiel [ERSD77, S. 145].

Beispiel 4.15 Sei

Ω = x ∈ R2 : −x31 + x2 ≤ 0,−x2 ≤ 0,

d.h. die Menge Ω ist der begrenzt von der positiven x1–Achse und der Funktion x31.

Damit ist

g(x) =

(−x3

1 + x2

−x2

)

, (∇g(x))T

=

(−3x2

1 10 −1

)

.

Wir betrachten den Punkt x0 = (0, 0)T . In diesem Punkt sind beide Nebenbedin-gungen mit Gleichheit erfullt, also I0 = 1, 2. Es folgt

(∇gI0(x0))T =

(0 10 −1

)

, =⇒ K(x0) =

(y1

0

)

, y1 ∈ R.

Fur den Tangentialkegel gilt T (x0) = y ∈ R2 : y1 ≥ 0, y2 = 0. Es ist alsoT (x0) ( K(x0). Dieses Beispiel zeigt insbesondere, dass man fur den Punkt x0 =(0, 0)T mit K(x0) keine lineare Approximation von Ω erhalt. 2

Beispiel 4.16 Der linearisierte Kegel K(x0) ist im Gegensatz zum TangentenkegelT (x0) von der analytischen Darstellung von Ω abhangig. Die Menge aus Beispiel 4.15kann auch dargestellt werden durch

Ω = x ∈ R2 : −x31 + x2 ≤ 0,−x1 ≤ 0

In diesem Fall hat man

g(x) =

(−x3

1 + x2

−x1

)

, (∇g(x))T

=

(−3x2

1 1−1 0

)

.

und man erhalt fur x0 = (0, 0)T , dass I0 = 1, 2 und

(∇gI0(x0))T

=

(0 1−1 0

)

, =⇒ K(x0) =

(y1

0

)

, y1 ∈ R+.

Damit ist T (x0) = K(x0). 2

Fur den nachsten Beweis benotigen wir einen Hilfssatz.

Lemma 4.17 Alternativsatz von Gordan. Sei A ∈ Rm×n, dann hat von denbeiden Systemen

Ay < 0

undzT A = 0, z ≥ 0, z 6= 0

genau eines eine Losung.

Beweis: Literatur, Ubungsaufgabe ?.Seien die Voraussetzungen von Satz 4.8 erfullt und I0 6= ∅. Dann folgt wegen

K0(x0) ⊆ T (x0)

(∇gI0(x0))T

y < 0 =⇒ yT∇f(x0) ≥ 0 ∀ y ∈ K0(x0).

82

Diese Beziehung ist aquivalent damit, dass das Ungleichungssystem

(∇gI0(x0))T y < 0, yT∇f(x0) < 0

keine Losung y ∈ K0(x0) besitzt. Nach Lemma 4.17 besitzt dieses System genaudann keine Losung, wenn das System

η∇f(x0) + ∇gI0(x0)zI0 = 0,

(η

zI0

)

≥ 0, η ∈ R+, (4.5)

eine nichttriviale Losung besitzt. Hierbei ist zI0 ein |I0|–dimensionaler Vektor, des-sen Eintrage durch die Indizes der aktiven Nebenbedingungen (unter Beibehaltungder naturlichen Reihenfolge) bestimmt sind. Setzt man zi = 0 fur i 6∈ I0, so kannman (4.5) mit z ∈ Rm wie folgt formulieren:

η∇f(x0) + ∇g(x0)z = 0, g(x0) ≤ 0, zT︸︷︷︸

=0,i6∈I0

g(x0)︸ ︷︷ ︸

=0,i∈I0

= 0,

(ηz

)

≥ 0,

(ηz

)

6= 0.

Sei I0 = ∅ und hat f(x) in x0 ∈ Ω ein lokales Minimum, das heißt es geltenx0 ∈ int(Ω), z = 0 und ∇f(x0) = 0, dann besitzt dieses System eine Losungη > 0, z = 0.

Wir betrachten jetzt das Problem: Gesucht ist ein Paar (x0, z0)T ∈ Rn ×Rm

+ (≥0), η0 ≥ 0, (η0, z0)

T 6= 0, welches das System

η∇f(x) + ∇g(x)z = 0, g(x) ≤ 0, zT g(x) = 0,

(ηz

)

≥ 0 (4.6)

lost. Mit dem Lagrange–Funktional

Lη(x, z) = ηf(x) + zT g(x)

ergibt sich die aquivalente Formulierung

∇xLη(x, z) = 0, ∇zLη(x, z) ≤ 0, zT∇zLη(x, z) = 0,

(ηz

)

≥ 0. (4.7)

Der Zusammenhang zwischen den Problemen (4.4) und (4.6) ist wie folgt.

Satz 4.18 Seien f : Rn → R, g : Rn → Rm differenzierbar und x0 ∈ Ω Stelleeines lokalen Minimums von f(x) bezuglich Ω. Dann existieren ein z0 ∈ Rm

+ undein η0 ≥ 0, so dass (x0, z0)

T und η0 eine Losung von (4.6) bzw. von (4.7) sind.

Beweis: Literatur, Fritz John (1948).Damit haben wir fur den Fall η0 > 0 ein Optimalitatskriterium gefunden. Ist je-

doch η0 = 0, so kann der Funktionswert von f(x) in (4.6) beliebig sein. Es wird jetzteine Regularitatsbedingung eingefuhrt, die sichert, dass unter den Voraussetzungenvon Satz 4.18 fur jede Losung von (4.6) η0 > 0 gilt.

Regularitatsbedingung. Seien g : Rn → Rm differenzierbar und

K(x0) = T (x0). (4.8)

Bemerkung 4.19

- Fur Optimierungsprobleme mit ausschließlich affinen Nebenbedingungen istdie Regularitatsbedingung stets erfullt.

- Die Regularitatsbedingung stellt eine Bedingung fur die analytische Darstel-lung der Menge Ω dar, vergleiche Beispiele 4.15 und 4.16. In einem Fall istdie Bedingung erfullt, im anderen nicht.

83

- Man kann andere Regularitatsbedingungen formulieren, die die obige Bedin-gung implizieren, aber leichter zu uberprufen sind.

2

Anstelle von (4.6) betrachten wir jetzt das Optimierungsproblem: Finde ein Paar(x0, z0)

T ∈ Rn × Rm+ , welches das Problem

∇f(x) + ∇g(x)z = 0, g(x) ≤ 0, zT g(x) = 0, z ≥ 0 (4.9)

lost. Man bezeichnet (4.9) als lokale Kuhn–Tucker–Bedingung (Kuhn, Tucker (1951)).Unter Verwendung des Lagrange–Funktionals

L(x, z) := f(x) + zT g(x), (x, z)T ∈ Rn × Rm+

erhalt man eine zu (4.9) aquivalente Formulierung

∇xL(x, z) = 0, ∇zL(x, z) ≤ 0, zT∇zL(x, z) = 0, z ≥ 0. (4.10)

Die Optimierungsprobleme (4.9), (4.10) hat man aus (4.6), (4.7) durch die Festset-zung von η = 1 erhalten.

Lemma 4.20 Satz von Farkas. Seien A ∈ Rm×n und b ∈ Rn. Dann hat von denbeiden Systemen

Ax ≤ 0, bT x > 0,

undyT A = bT , y ≥ 0

genau eines eine Losung.

Beweis: Siehe Literatur.

Satz 4.21 Satz von Kuhn/Tucker. Seien f : Rn → R, g : Rn → Rm stetigdifferenzierbar und x0 ∈ Ω Stelle eines lokalen Minimums von f(x) bezuglich Ω. Istin x0 die Regularitatsbedingung (4.8) erfullt, dann existiert ein z0 ∈ Rm

+ , so dass(x0, z0)

T eine Losung von (4.9) bzw. von (4.10) ist.

Beweis: Sei I0 6= ∅. Per Definition des linearisierten Kegels gilt

(∇gI0(x0))T

y ≤ 0 ∀ y ∈ K(x0). (4.11)

Da (4.8) erfullt ist, folgt aus Satz 4.8 fur I0 6= ∅

(∇f(x0))T

y ≥ 0 =⇒ (−∇f(x0))T

y ≤ 0 ∀ y ∈ T (x0) = K(x0). (4.12)

Aus Lemma 4.20 folgt, dass (4.11) und (4.12) genau dann gleichzeitig gelten, wenndas System

∇gI0(x0)zI0 = −∇f(x0), zI0 ≥ 0

eine Losung besitzt. Setzt man zi = 0 fur i 6∈ I0, so folgt die Aussage des Satzesfur I0 6= ∅. Die Beziehung g(x0) ≤ 0 gilt per Definition des Optimierungsproblems.Aus der Konstruktion von z folgt schließlich zT g(x0) = 0.

Fur I0 = ∅ ist z = 0 eine Losung von (4.9).Im Falle x0 ∈ int(Ω) gilt wegen der Regularitatsbedingung (4.8) T (x0) =

K(x0) = Rn. Aus der Definition von K(x0) folgt dann, dass ∇g(x0) = 0 seinmuss, da die Bedingung fur jedes y ∈ Rn, insbesondere fur −y gelten muss. Ausder ersten Gleichung der Kuhn–Tucker–Bedingung (4.9) folgt dann die bekanntenotwendige Bedingung fur ein lokales Minimum: ∇f(x0) = 0.

84

Die Gultigkeit der Implikation von (4.11) nach (4.12) kann mit Hilfe eines linea-ren Programms uberpruft werden. Diese Implikation gilt genau dann, wenn 0 deroptimale Wert des Problem

z = zT∇f(x0) → min !

zT∇gI0(x0) ≤ 0

ist.Sind die Zielfunktion und die Nebenbedingungen zweimal differenzierbar, kann

man weitere Kriterien mit Hilfe der Hesse–Matrix formulieren.

4.4 Globale Theorie der Lagrange–Multiplikatoren

Wir betrachten das Optimierungsproblem

z = minf(x) : x ∈ GΩ mit GΩ = x ∈ Rn : g(x) ≤ 0, x ∈ Ω, (4.13)

wobei Ω ∈ Rn eine nichtleere Menge ist, f : Ω → R, g : Ω → Rm. Bei dieser soge-nannten konischen Formulierung der Menge GΩ ist x genau dann zulassige Losung,wenn x ∈ Ω und g(x) ≤ 0. Fur Ω = Rn haben wir als Spezialfall das Problem (4.4).Im folgenden werden Optimalitatskriterien in Form von Sattelpunktaussagen for-muliert.

Definition 4.22 Sattelpunkt. Die Funktion L(x, λ) mit x ∈ Ω, λ ∈ Dλ besitztin (x0, λ0) einen lokalen Sattelpunkt, wenn es ein ε > 0 gibt, so dass

L(x0, λ) ≤ L(x0, λ0) ≤ L(x, λ0) ∀ (x, λ) ∈ (Ω × Dλ) ∩ Uε(x0, λ0), (4.14)

wobei Uε(x0, λ0) eine ε–Umgebung von (x0, λ0) ist. Gilt (4.14) fur alle (x, λ) ∈Ω × Dλ, so hat L(x, λ) in (x0, λ0) einen globalen Sattelpunkt. 2

Zur Formulierung von globalen Optimalitatskriterien wird das folgende Sattel-punktproblem betrachtet: Gesucht ist x0 ∈ Ω und (η0,y0)

T ∈ Rm+1+ mit (η0,y0)

T 6=0, so dass fur das Lagrange–Funktional

Lη(x,y) := ηf(x) + yT g(x), (x,y)T ∈ Ω × Rm+ , (4.15)

giltLη0(x0,y) ≤ Lη0(x0,y0) ≤ Lη0(x,y0), ∀ (x,y)T ∈ Ω × Rm

+ .

Als nachstes soll ein notwendiges Optimalitatskriterium fur (4.13) bewiesen wer-den. Dazu benotigen wir folgendes Lemma.

Lemma 4.23 Seien Ω ⊆ Rn eine konvexe Menge, f : Ω → R, g : Ω → Rq konvexeFunktionen und h : Ω → Rr eine affine Funktion. Das System

f(x) < 0, g(x) ≤ 0, h(x) ≤ 0, x ∈ Ω

besitzt genau dann keine Losung, wenn ein Vektor (u,v,w)T ∈ R+ × Rq+ × Rr

+,(u,v,w)T 6= 0, existiert mit

uf(x) + vT g(x) + wT h(x) ≥ 0, ∀ x ∈ Ω.

Existiert ein x ∈ int(Ω) welches zusatzlich g(x) < 0 erfullt, dann gilt u 6= 0.

Beweis: Siehe Literatur.

85

Satz 4.24 Seien Ω ⊆ Rn eine konvexe Menge, f : Ω → R und g : Ω → Rm konvexeFunktionen. Ist x0 eine Losung von (4.13), so existieren ein η0 ∈ R+ und ein y0 ∈Rm

+ , so dass (x0, η0,y0)T ∈ Ω × Rm+1

+ eine Losung des Sattelpunktproblems (4.15)ist.

Beweis: Sei x0 eine Losung von (4.13). Dann besitzt das System

f(x) − f(x0) < 0, g(x) ≤ 0, x ∈ Ω

keine Losung. Nach Lemma 4.23, mit h(x) ≡ 0, existiert dann ein Vektor (η0,y0)T ∈

Rm+1+ , (η0,y0)

T 6= 0, mit

Lη0(x,y0) = η0f(x) + yT0 g(x) ≥ η0f(x0) ∀ x ∈ Ω.

Wegen g(x0) ≤ 0 und y ≥ 0 gilt damit

Lη0(x,y0) = η0f(x)+yT0 g(x) ≥ η0f(x0)+yT g(x0) = Lη0(x0,y) ∀ (x,y) ∈ Ω×Rm

+ .(4.16)

Setzt man in (4.16) rechts y = y0, ergibt sich

η0f(x) + yT0 g(x) ≥ η0f(x0) + yT

0 g(x0) = Lη0(x0,y0) ∀ x ∈ Ω.

Setzt man in (4.16) links x = x0, erhalt man

η0f(x0) + yT0 g(x0) ≥ η0f(x0) + yT g(x0) ∀ y ∈ Rm

+ .

Aus den letzten beiden Ungleichungen folgt die Behauptung.Die Aussage dieses Satzes hat in gewissem Sinne Ahnlichkeit mit der von Satz

4.18. Fur einen gegebenen zulassigen Bereich ist die notwendige Bedingung (nicht-negative Losung von (4.15)) fur beliebige Werte der Zielfunktion erfullt, falls η0 = 0ist. Analog wie bei den lokalen Lagrange–Multiplikatoren wird deshalb eine Regu-laritatsbedingung eingefuhrt, die η0 > 0 sichert.

Regularitatsbedingung. Seien die Menge Ω ⊆ Rn sowie die Funktionen gi :Ω → R, i ∈ 1, . . . , m =: I konvex. Es existiere ein x ∈ int(Ω) mit

gi(x) < 0 fur i ∈ IN , gi(x) ≤ 0 fur i ∈ IL. (4.17)

Hierbei ist IL die Menge aller i ∈ 1, . . . , m, fur die gi(x) eine affine Funktion istund IN die Menge aller Indizes, fur die gi(x) keine affine Funktion ist.

Unter dieser Regularitatsbedingung wird das Sattelpunktproblem: Finde einenSattelpunkt (x0,y0) ∈ Ω × Rm

+ des Lagrange–Funktional

L(x,y) := f(x) + yT g(x), (x,y)T ∈ Ω × Rm+ , (4.18)

betrachtet.

Satz 4.25 Seien die Menge Ω ⊆ Rn konvex, die Funktionen f : Ω → R, gi : Ω → R,i ∈ I, konvex und die Regularitatsbedingung (4.17) erfullt. Ist x0 ∈ Ω eine Losungvon (4.13), dann existiert ein y0 ∈ Rm

+ , so dass (x0,y0) ein Sattelpunkt von (4.18)ist.

Beweis: Da x0 eine Losung von (4.13) ist, ist das System

f(x) − f(x0) < 0, g(x) ≤ 0, x ∈ Ω

nicht losbar. Wegen der Regularitatsbedingung (4.17) ist jedoch das System

gIN(x) < 0, gIL

(x) ≤ 0, x ∈ int(Ω)

86

losbar. Nach Lemma 4.23 existiert ein (η0,y0)T ∈ Rm+1

+ , η0 6= 0, mit

η0 (f(x) − f(x0)) + yT0 g(x) ≥ 0 ∀ x ∈ Ω.

Man kann so skalieren, dass η0 = 1 gilt. Dann folgt

L(x,y0) = f(x) + yT0 g(x) ≥ f(x0) ∀ x ∈ Ω.

Wegen g(x0) ≤ 0 und y ≥ 0 gilt

L(x0,y) = f(x0) + yT g(x0) ≤ f(x0) ∀ y ∈ Rm+ .

Aus den letzten beiden Beziehungen folgt, indem man x = x0 beziehungsweisey = y0 setzt,

L(x0,y0) = f(x0).

Nach Definition ist (x0,y0)T somit ein Sattelpunkt des Lagrange–Funktionals (4.17).

Nun wird eine hinreichende Bedingung fur eine Losung von (4.13) formuliert.Dabei gilt eine gewisse Umkehrung von Satz 4.25, die ohne weitere Voraussetzungenan (4.13) gilt.

Satz 4.26 Sei (x0,y0)T ∈ Ω × Rm

+ ein Sattelpunkt von (4.18). Dann ist x0 eineLosung von (4.13).

Beweis: Zunachst wird gezeigt, dass x0 die Nebenbedingungen erfullt. AusL(x0,y) ≤ L(x0,y0) fur alle y ∈ Rm

+ folgt

(y − y0)T g(x0) ≤ 0 ∀ y ∈ Rm

+ . (4.19)

Es gilt Rm+ ⊂ y − y0 : y,y0 ∈ Rm

+. Somit gilt

yT g(x0) ≤ 0 ∀ y ∈ Rm+ .

Sei gi(x0) > 0. Dann wurde diese Beziehung nicht fur den i–ten Einheitsvektorgelten, der aber zu Rm

+ gehort. Damit folgt g(x0) ≤ 0.Nun wird gezeigt, dass f(x) in x0 ein globales Minimum annimmt. Aus (4.19)

folgt fur y = 0 die Ungleichung yT0 g(x0) ≥ 0. Da y0 ≥ 0 und g(x0) ≤ 0, kann das

Skalarprodukt nur nichtpositiv sein, also gilt yT0 g(x0) = 0. Mit dieser Beziehung

und L(x0,y0) ≤ L(x,y0) fur alle x ∈ Ω folgt

f(x0) ≤ f(x) + yT0 g(x) ∀ x ∈ Ω

und damit fur alle x ∈ GΩ

f(x0) ≤ f(x) + yT0

︸︷︷︸

≥0

g(x)︸︷︷︸

≤0

≤ f(x).

Bemerkung 4.27 Dualitatstheorie. Auch fur die nichtlineare Optimierung gibtes eine Dualitatstheorie. Die Dualitatstheorie fur lineare Programme ist darin alsSpezialfall enthalten.

Gegeben sei das primale Problem

z = minf(x) : x ∈ GΩ mit GΩ = x ∈ Rn : g(x) ≤ 0, x ∈ Ω, (4.20)

87

wobei Ω ⊆ Rn eine nichtleere Menge ist und f : Ω → R, g : Ω → Rm Abbildungensind. Dem Problem (4.20) wird unter Verwendung des Lagrange–Funktionals dasduale Problem

z = maxφ(y) : y ∈ Rm+

zugeordnet, wobei

φ(y) : Rm+ → R ∪ −∞, φ(y) = inf

x∈ΩL(x,y) = inf

x∈Ω

(f(x) + yT g(x)

).

Man kann wieder schnell zeigen, dass der Maximalwert des dualen Problems, falls erexistiert, kleiner oder gleich dem Minimalwert des primalen Problems ist. Gleichheitmuss im allgemeinen jedoch nicht gelten. Man spricht dann von einer Dualitatslucke.Des weiteren sind die Fragen bezuglich der Losbarkeit der beiden Probleme wesent-lich komplizierter zu beantworten als bei linearen Programmen. 2

88

Kapitel 5

Losungsverfahren

Dieses Kapitel gibt einen Uberblick uber Losungsverfahren fur nichtlineare Op-timierungsprobleme. Es wird vor allem auf die wesentlichen Ideen der Verfahreneingegangen und weniger auf Details.

5.1 Projektionsverfahren

Projektionsverfahren sind recht einfache Verfahren, die das Konzept von Abstiegs-verfahren zur Minimierung von Funktionen ohne Nebenbedingungen auf Minimie-rungsprobleme mit konvexen Nebenbedingungen ubertragen. Bei einem Abstiegs-verfahren wird, ausgehend von einer Iterierten x(k), die nachste Iterierte x(k+1) sogewahlt, dass sich der Wert der zu minimierenden Funktion verkleinert. Hat manein Problem mit Nebenbedingungen, so muss man naturlich zusatzlich darauf ach-ten, dass x(k+1) zum zulassigen Bereich gehort. Anderenfalls kann es zum Beispielvorkommen, dass die Zielfunktion gar nicht definiert ist. Projektionsverfahren pro-jizieren die Abstiegsrichtung fur die Zielfunktion in geeigneter Weise in die zulassigeMenge.

Wir betrachten das Optimierungsproblem

z = minf(x) : x ∈ Ω (5.1)

mit f ∈ C1(Rn) und die zulassige Menge Ω sei nichtleer, konvex und abgeschlossen.Von besonderer Bedeutung sind die Probleme, bei denen f(x) quadratisch ist

undΩ = x ∈ Rn : Ax ≤ b (5.2)

ein Polyeder ist, A ∈ Rm×n, b ∈ Rm. Solche Probleme treten als Teilprobleme beiden sogenannten SQP–Verfahren (sequential quadratic programming) auf, wo siewiederholt mit unterschiedlichen Daten A,b, f gelost werden mussen.

In anderen Anwendungen ist der zulassige Bereich sogar nur ein Quader (,,boxconstraints”):

Ω = ×ni=1[li, ui]. (5.3)

Fur x ∈ Rn sei PΩ(x) die Losung von

infy∈Ω

‖y − x‖2

die Projektion von x auf Ω bezuglich der Euklidischen Norm. Da die Menge Ωnach Voraussetzung abgeschlossen ist, kann man das Infimum durch das Minimumersetzen, also

PΩ(x) = argminy∈Ω

‖y − x‖2 .

89

Beispiel 5.1 Falls Ω durch (5.2) gegeben ist, muss man zur Berechnung der Pro-jektion y = PΩ(x) das konvexe quadratische Programm

y = argminy∈Ω

‖y − x‖22 : Ay ≤ b = argmin

y∈ΩyT y − 2yT x : Ay ≤ b

losen. Die Menge Ω ist ein konvexes Polyeder. Die Zielfunktion ‖y − x‖22 ist eine

konvexe Funktion, siehe Ubungsaufgabe.Ist der zulassige Bereich ein Hexaeder (5.3), kann man die Projektion kompo-

nentenweise berechnen:

(y)i =

xi falls xi ∈ [li, ui],ui falls xi > ui,li falls xi < li.

2

Definition 5.2 Stationarer Punkt. Der Punkt x0 wird stationarer Punkt desProblems (5.1) genannt, falls fur alle Punkte des Tangentenkegels y ∈ T (x0) dieUngleichung

yT∇f(x0) ≥ 0

gilt. 2

Ein stationarer Punkt erfullt also die im Satz 4.8 bewiesene notwendige Bedin-gung fur ein lokales Minimum bezuglich Ω.

Algorithm 5.3 Projektionsverfahren.

1. Initialisierung.

Bestimme x(0) ∈ Ω und wahle drei reelle Parameter 0 < β, µ < 1

und γ > 0.

2. Iteration. k = 0, 1, 2, . . .

Falls x(k) ein stationarer Punkt ist, dann

Stopp

sonst

Betrachte fur α > 0 den Pfad

x(k)(α) := PΩ

(

x(k) + α∇f(

x(k)))

Setze

x(k+1)(α) := x(k)(

α(k))

,

wobei α(k) = γβm(k)

und m(k) die kleinste naturliche Zahl

großer oder gleich Null ist mit

f(

x(k+1))

≤ f(

x(k))

+ µ∇f(

x(k))T (

x(k+1) − x(k))

(Armijo–Liniensuche)

Bemerkung 5.4 Armijo–Liniensuche. Seien f(x) eine zu minimierende Funk-tion, x(k) die gegenwartige Iterierte, s(k) eine irgendwie berechnete Abstiegsrich-tung, µ ∈ (0, 1) und γ > 0 eine Konstante. Im Falle, dass man keine Nebenbe-dingungen hat, wahlt man λ(0) ≥ γ

∥∥∇f(x(k))

∥∥

2und bestimme unter den Zahlen

λ(j) = 2−jλ(0), β = 1/2, die erste, fur die

f(

x(k) + λ(j)s(k))

≤ f(

x(k))

+ µλ(j)∇f(

x(k))T

s(k)

90

gilt. Die Motivation fur diese Herangehensweise kommt von der nach dem linearenGlied abgebrochenen Taylor–Entwicklung

f(

x(k) + λ(j)s(k))

≈ f(

x(k))

+ λ(j)∇f(

x(k))T

s(k).

Ist s(k) eine Abstiegsrichtung, dann findet man in dieser Richtung einen Funktions-wert von f(x), der kleiner als der Funktionswert f

(x(k)

)ist, falls λ(j) nur hinrei-

chend klein ist. Man fangt mit irgendeinem hinreichend großen λ(0) an. Dieses hangtvon

∥∥∇f

(x(k)

)∥∥

2ab. Ist

∥∥∇f

(x(k)

)∥∥

2klein, kann man vermuten in der Nahe eines

Minimums zu sein (dort ist ∇f(x(k)

)= 0) und man braucht vielleicht nur einen

kleinen Schritt. Man testet ob der Funktionswert sich verkleinert. Ist das nicht derFall, wird der Parameter λ(j) sukzessive halbiert, bis er klein genug ist. 2

Im Algorithmus 5.3 hat man einen gekrummten Pfad x(k)(α). Fur jedes α hatman im allgemeinen ein konvexes, quadratisches Minimierungsproblem uber Ω zulosen. Das ist recht teuer.

Falls Ω ein Polyeder ist, kann man eine Startiterierte x(0) mittels eines linearenProgramms bestimmen.

Da der Algorithmus 5.3 im wesentlichen ein Gradientenverfahren ist, kann manim allgemeinen nur langsame Konvergenz erwarten. Außerdem ist die Berechnungvon PΩ

(x(k) + α∇f

(x(k)

))fur allgemeine Polyeder aufwendig. Wir betrachten jetzt

noch eine Variante von Algorithmus 5.3, die zusatzlich leichter berechenbare Zwi-schenwerte x(k) ∈ Ω berechnet, bei denen der Funktionswert zumindest nicht an-steigt.

Algorithm 5.5 Modifiziertes Projektionsverfahren.

1. Initialisierung.

Bestimme x(0) ∈ Ω und wahle Parameter falls notig.

2. Iteration. k = 0, 1, 2, . . .

Bestimme x(k+1) = PΩ(x(k) + α∇f(x(k))

)entweder wie im Algorith-

mus 5.3 oder

bestimme x(k+1) ∈ Ω, so dass f(x(k+1)

)≤ f

(x(k)

).

Die Umsetzung der zweiten Strategie hangt von der Art der Nebenbedingungenab. Wir betrachten affine Nebenbedingungen (5.2). Bezeichne ai die Zeilen von A.Fur x ∈ Ω sei die Menge der aktiven Nebenbedingungen

I(x) =i ∈ 1, . . . , m : aT

i x = bi

.

Dann wird die zweite Strategie haufig so realisiert, dass I(x(k)) ⊆ I(x(k+1)) gilt.Man wahlt dazu in x(k) eine Abstiegsrichtung

v(k) ∈ L(

x(k))

:= v : AI(x(k))v = 0,

wobei AI(x(k)) die Teilmatrix von A mit den Zeilen ist, deren Indizes in I(x(k))enthalten sind. Die Abstiegseigenschaft wird dann nur in schwacher Form

∇f(

x(k))T

v(k) ≤ 0

verlangt. Die neue Iterierte besitzt die Gestalt x(k+1) = x(k) + αv(k) fur ein geeig-netes α. Aus der Wahl von v(k) folgt

A(

x(k+1))

= A(

x(k) + αv(k))

= Ax(k) + αAv(k).

91

Fur die aktiven Nebenbedingungen verschwindet der zweite Summand. Fur die an-deren Nebenbedingungen, i 6∈ I(x(k)), ist der erste Summand kleiner als bi und manfindet ein hinreichend kleines α > 0, so dass die Summe der beiden Summandenkleiner oder gleich bi bleibt. Mit

α(k) := supα : x(k) + αv(k) ∈ Ω

wird nun eine Liniensuche gestartet um einen Faktor α(k) und damit ein Argu-ment x(k+1) zu finden, so dass f

(x(k+1)

)≤ f

(x(k)

)gilt. Ist α(k) < α(k), dann ist

I(x(k)) = I(x(k+1)), sonst I(x(k)) ⊂ I(x(k+1)).

5.2 Penalty–Verfahren (Strafverfahren)

Wir betrachten wieder das Optimierungsproblem

z = minf(x) : x ∈ Ω, (5.4)

diesmal aber zunachst mit f ∈ C0(Rn) und die Menge Ω sei abgeschlossen. Um dieLosung von (5.4) mit einer Folge einfacherer Optimierungsprobleme ohne Nebenbe-dingungen zu approximieren, wird die Straffunktion

l : Rn → R+, l(x) =

> 0 fur x 6∈ Ω,= 0 fur x ∈ Ω

eingefuhrt. Diese Funktion bestraft Punkte, die nicht zum zulassigen Bereich gehoren,mit positiven Funktionswerten.

Beispiel 5.6 Fur

Ω = x ∈ Rn : gi(x) ≤ 0, i = 1, . . . , p; gi(x) = 0, i = p + 1, . . . , m

ist eine mogliche Straffunktion

l(x) =

p∑

i=1

(g+

i (x))α

+

m∑

i=p+1

|gi(x)|α

mit α > 0, g+i (x) = max0, gi(x). 2

Definition 5.7 Penalty–Funktion Die gewichtete Summe aus Zielfunktion undStraffunktion

p(x, r) := f(x) + rl(x), r ∈ R+, r > 0,

wird Penalty–Funktion genannt. Der Parameter r heißt Strafparameter. 2

Fur fest gewahlte Parameter r werden jetzt die Minimierungsprobleme ohneNebenbedingungen

minx∈Rn

p(x, r) (5.5)

betrachtet. Der Strafterm belegt die Punkte, die nicht zum zulassigen Bereichgehoren, mit positiven Werten, die fur große Strafparameter r groß sind. Deswe-gen hofft man, dass die Minima von (5.5) fur große Strafparameter im zulassigenBereich liegen und gute Naherungen fur die Minima von (5.4) sind.

Algorithm 5.8 Allgemeines Penalty–Verfahren.

1. Initialisierung.

Wahle r(1) > 0.

92

2. Iteration., k = 0, 1, 2, . . .

Bestimme ein lokales Minimum x(k) fur p(x, r(k))Falls x(k) ∈ Ω, dann Stopp

sonst wahle r(k+1) ≥ 2r(k)

Man kann zeigen, dass die x(k) unter gewissen Voraussetzungen tatsachlichNaherungen eines lokalen Minimums von (5.4) sind.

Satz 5.9 Seien f : Rn → R eine stetige Funktion, x0 ein striktes lokales Minimumund l : Rn → R+ eine stetige Straffunktion. Dann gibt es ein r0 > 0 so, dass furalle r > r0 die Penalty–Funktion p(x, r) ein lokales Minimum x(r) besitzt, dass furr → ∞ gegen x0 konvergiert.

Beweis: Literatur, [JS04, S. 294].

Bemerkung 5.10 Zwei Eigenschaften sind fur Penalty–Verfahren von Bedeutung:

1. In vielen Fallen ist die Zielfunktion f(x) differenzierbar. Damit die Anwen-dung eines Verfahrens vom Newton–Typ zur Bestimmung des Minimumsvon (5.5) moglich ist, muss die Straffunktion l(x) auch differenzierbar sein.

2. Damit das Verfahren nach endlich vielen Schritten abbricht, ist es wunschens-wert, wenn es bereits einen endlichen Wert r > 0 gibt, so dass ein lokalesMinimum x0 von (5.4) auch lokales Minimum fur jedes Problem ohne Ne-benbedingungen (5.5) mit r ≥ r ist. In diesem Fall nennt man die Penalty–Funktion exakt in x0.

Es stellt sich leider heraus, dass diese beiden wunschenswerten Eigenschaften in derRegel unvereinbar sind. Aus diesem Grunde werden Penalty–Verfahren in der Formvon Algorithmus 5.8 praktisch nicht genutzt. Stattdessen betrachtet man modifizier-te Penalty–Funktionen, die auf dem Konzept einer erweiterten Lagrange–Funktion(augmented Lagrange–Funktion) beruhen, siehe Literatur. 2

5.3 Barrieremethoden

Wir betrachten das Problemz = min

x∈Rnf(x) (5.6)

mit den Nebenbedingungen

gi(x) ≤ 0 fur 1 ≤ i ≤ p, gi(x) = 0 fur p + 1 ≤ i ≤ m. (5.7)

Dabei seien f, gi ∈ C2(Rn), i = 1, . . . , m, und wir nehmen an, dass (5.6) eineOptimallosung besitzt, die mit x0 bezeichnet wird.

Barrieremethoden sind eng verwandt mit den Penalty–Verfahren. Auch bei die-sen Methoden betrachtet man eine Folge von Hilfsproblemen, bei denen die Ziel-funktion f(x) durch gewichtete Strafterme erweitert wird. Die Barriereverfahrenerzeugen eine Folge von inneren Punkten, das heißt von Punkten die die Unglei-chungsrestriktionen sogar strikt erfullen, gi(x) < 0, i = 1, . . . , p, wahrend die Glei-chungsrestriktionen verletzt sein konnen.

Bezeichne

Ω := x ∈ Rn : gi(x) ≤ 0, i = 1, . . . pΩ0 := x ∈ Rn : gi(x) < 0, i = 1, . . . p.

Man beachte, die Menge Ω0 muss nicht notwendig die topologischen inneren Punktevon Ω enthalten, wahle zum Beispiel n = p = 1, g1(x) = 0. Dann sind Ω = R undΩ0 = ∅.

93

Barriereverfahren bestrafen solche Punkte aus Ω0, die sich dem Rand von Ω0

nahern. Die Gleichheitsnebenbedingungen werden direkt mit Hilfe von Linearisie-rungen behandelt. Diese Gleichheitsnebenbedingungen sind grundsatzlich einfacherzu behandeln als Ungleichungsnebenbedingungen. Die Strafterme in den Barrie-reverfahren, die sogenannten Barriereterme, sind in Ω0 endlich und wachsen zumRand dieser Menge nach unendlich an. Außerhalb von Ω besitzen sie den Wert ∞.Im Gegensatz zu den Penalty–Verfahren, bei denen die Strafterme sukzessive immerstarker gewichtet werden, siehe Algorithmus 5.8, muss bei den Barriere–Verfahrender Einfluss der Strafterme immer weiter abgeschwacht werden. Damit wird dasGewicht der Zielfunktion im Barriereproblem erhoht und man kann hoffen, dass dieMinima der Barriereprobleme unter geeigneten Voraussetzungen gegen ein Mini-mum von f(x) konvergieren. An der Eigenschaft, dass die Barriereterme außerhalbvon Ω unendlich sind, andert man nichts. Somit ist garantiert, dass die Minima derBarriereprobleme immer in Ω0 liegen.

Definition 5.11 Skalare Barrierefunktion. Eine skalare Barrierefunktion isteine streng monoton fallende, glatte, konvexe Funktion b : (0,∞) → R mit

limt→0+0

b(t) = ∞ und limt→0+0

b′(t) = −∞.

2

Außerdem wird stets b(t) = ∞ fur t ≤ 0 gesetzt, so dass b(t) formal eine auf R

definierte konvexe Funktion ist, b : R → R ∪ ∞.

Beispiel 5.12 Beispiele fur Barrierefunktionen sind

b(t) = − log t, b(t) =1

tα, α > 0.

Die logarithmische Barrierefunktion ist in gewisser Hinsicht optimal. 2

Zur Konstruktion von Barriereverfahren zur Losung von Problem (5.6) mit denNebenbedingungen (5.7) werden nun Hilfsprobleme der Form

infx

f(x) + µ

p∑

i=1

b (di − gi(x)) : gi(x) = 0, i = p + 1, . . . , m

(5.8)

betrachtet. In (5.8) ist µ > 0 ein Gewicht fur die Barriereterme und die Zahlen di ≥0, i = 1, . . . , p, sind Verschiebungen der Ungleichungsnebenbedingungen in (5.7), dasheisst anstatt gi(x) ≤ 0 ist nun gi(x) ≤ di erlaubt. Diese Verschiebungen gestattenes, dass man das Verfahren auch dann anwenden kann, wenn kein innerer Punktfur (5.6), (5.7) bekannt ist. Die Zielfunktion von (5.8) wird abkurzend mit

Φ(x; µ,d) = f(x) + µ

p∑

i=1

b (di − gi(x))

bezeichnet.Wir nehmen an, dass (5.8) ein endliches lokales Minimum besitzt. Die gewich-

tete Summe der Barriereterme in der Zielfunktion garantiert, dass jedes x mitΦ(x; µ,d) ∈ R die abgeschwachten Nebenbedingungen gi(x) < di, i = 1, . . . , p,erfullt.

Lemma 5.13 Falls f(x) und gi(x), i = 1, . . . , p konvex sind, so ist auch Φ(x; µ,d)konvex.

94

Beweis: Es ist bekannt, dass die Linearkombination konvexer Funktionen mitnichtnegativen Koeffizienten in der Linearkombination eine konvexe Funktion ist.Damit bleibt zu zeigen, dass die Funktionen b (di − gi(x)), i = 1, . . . , p, konvex sind.

Da die Funktionen, gi(x) konvex sind, gilt fur λ ∈ [0, 1]

di − gi (λx1 + (1 − λ)x2) ≥ di − (λgi (x1) + (1 − λ)gi (x2))

= λ (di − gi (x1)) + (1 − λ) (di − gi (x2)) .

Mit dieser Aussage, mit der Monotonie von b(t) und der Konvexitat von b(t) folgt

b (di − gi (λx1 + (1 − λ)x2)) ≤ b (λ (di − gi (x1)) + (1 − λ) (di − gi (x2)))

≤ λb (di − gi (x1)) + (1 − λ)b (di − gi (x2)) .

Weiterhin gilt folgende starkere Aussage.

Satz 5.14 Es gelten die Voraussetzungen von Lemma 5.13 und zusatzlich limt→∞ b′(t) =0, die Gleichheitsnebenbedingungen gi(x), i = p+1, . . . , m seien affin und die Men-ge der Optimallosungen von (5.6) sei nicht leer und beschrankt. Dann besitzt dasHilfsproblem (5.8) fur jedes µ > 0 eine Optimallosung und die Minima der Barrie-reprobleme nahern sich der Optimalmenge von (5.6).

Beweis: Siehe Literatur.Fur Probleme (5.6), die die Bedingungen dieses Satzes erfullen, kann man nun

das folgende Verfahren konstruieren.

Algorithm 5.15 Barrieremethode fur konvexe Probleme.

1. Initialisierung.

Bestimme x(0) ∈ Rn mit gi(x(0)) = 0 fur i = p + 1, . . . , m. Wahle

µ(0) > 0 und d(0) ≥ 0 so dass d(0)i > gi(x

(0)) fur i = 1, . . . , p.

2. Iteration. k = 1, 2, . . .

Wahle λ(k) ∈ (0, 1) so, dass mit(µ(k),d(k)

):= λ(k)

(µ(k−1),d(k−1)

)

gilt

gi

(

x(k−1))

< d(k)i

, fur i = 1, . . . , p.

Ausgehend von x(k−1) fuhrt man nun einige Schritte des New-

ton-Verfahrens (mit Liniensuche) zum losen des Barrierepro-

blems aus. Das Ergebnis ist x(k).

Im ersten Schritt der Iteration werden sowohl das Gewicht als auch der Ver-schiebevektor verkleinert. Der Verkleinerungsfaktor wird so gewahlt, dass mit demneuen Verschiebevektor noch alle Ungleichungsnebenbedingungen erfullt sind. DasMinimum x0

(µ(k),d(k)

)des Barriereproblems (5.8) zu den Parametern

(µ(k),d(k)

)

wird im zweiten Schritt approximiert. Da die Barriereterme das Minimum vom

Rand der Menge x : gi(x) ≤ d(k)i abstoßen, kann man nach der Berechnung der

Naherung x(k) von x0

(µ(k),d(k)

)die Verschiebeparameter d

(k)i in der folgenden

Iteration wieder etwas verkleinern.Die Schwierigkeiten von Algorithmus 5.15 bestehen darin, dass das Newton–

Verfahren fur µ(k) → 0 oft schlecht konvergiert. Deshalb wird diese Basisherange-hensweise nicht genutzt. Man kann diese Herangehensweise durch Verfeinerung derBarrieremethode verbessern.

95

5.4 SQP–Verfahren

In diesem Abschnitt wird ein Zugang vorgestellt, der Punkte berechnet, die dienotwendige Optimalitatsbedingung, die im Satz 4.21 (Kuhn/Tucker) formuliert ist,erfullen, die sogenannten SQP–Verfahren (sequential quadratic programming). Eswird also eine Iteration durchgefuhrt, bei welcher in jedem Schritt ein quadratischesOptimierungsproblem gelost wird.

Wir betrachten wieder das Optimierungsproblem (5.6) mit den Nebenbedin-gungen (5.7) und den gleichen Regularitatsvoraussetzungen wie im Abschnitt 5.3.Seien x0 ein lokales Minimum von (5.6), (5.7) und z0 der zugehorige Lagrange–Multiplikator zum Lagrange–Problem (4.10). Insgesamt erfullen (x0, z0) das Pro-blem, siehe (4.10),

Φ(x0, z0) =

(∇xL(x0, z0)

zT0 g(x0)

)

=

(

∇f(x0) + (∇g(x0))T

z0

zT0 g(x0)

)

= 0 (5.9)

mit z0 ≥ 0. Da die Gleichheitsbedingungen ohnehin verschwinden, kann man (5.9)sogar wie folgt schreiben

Φ(x0, z0) =

∇f(x0) + (∇g(x0))T

z0

z0,1g1(x0)...

z0,pgp(x0)gp+1(x0)

...gm(x0)

= 0. (5.10)

SQP–Verfahren wollen das nichlineare Problem (5.10) mit einem Verfahren vomNewton–Typ losen. Dazu benotigt man die Jacobi–Matrix von Φ(x, z), die durch

Ψ (x, z, HL,x(x, z))

=

HL,x(x, z) ∇g1(x) · · · ∇gp(x) ∇gp+1(x) · · · ∇gm(x)z1(∇g1(x))T g1(x)

.... . . 0

zp(∇gp(x))T gp(x)(∇gp+1(x))T

... 0 0(∇gm(x))T

∈ R(n+m)×(n+m)

gegeben ist. Ein wesentliches Merkmal eines SQP–Verfahrens besteht darin, dassdie teure Hesse–Matrix HL,x(x, z) in der Regel durch eine einfacher zu berechnendeMatrix ersetzt wird.

Unter geeigneten Voraussetzungen gilt, dass die Jacobi–Matrix Ψ (x0, z0, HL,x(x0, z0))nichtsingular ist und dass das Newton–Verfahren zur Nullstellenbestimmung vonΦ(x, z) quadratisch konvergiert. Sei eine aktuelle Iterierte (x(k), z(k))T gegeben.Die Newton–Korrektur (∆x(k), ∆z(k))T berechnet sich als Losung des Gleichungs-systems

Ψ(

x(k), z(k), HL,x(x(k), z(k)))(

∆x(k), ∆z(k))T

= −Φ(x(k), z(k)).

Beim Newton–Verfahren kann man im allgemeinen jedoch nur lokale Konvergenzerwarten, dass heisst, der Startwert muss nahe genug an der (unbekannten) Losung

96

sein. Speziell fur die Funktion Φ(x, z) kann man auch nicht garantieren, dass alle Ite-

rierten die Ungleichungen gi(x(k)) ≤ 0 und die Nichtnegativitatsbedingung z

(k)i ≥ 0

erfullen. Damit ist es moglich, dass das Newton–Verfahren gegen eine nicht zulassigeLosung von Φ(x, z) = 0 konvergiert, bei der Nebenbedingungen nicht erfullt sindoder die Lagrange–Multiplikatoren negativ sind. Die Konvergenz gegen eine solcheLosung muss verhindert werden. Dazu wird anstelle des Newton–Verfahrens dasSystem

Ψ(

x(k), z(k+1), B(k))(

∆x(k), ∆z(k))T

= −Φ(x(k), z(k)) (5.11)

betrachtet, wobei ∆x(k), ∆z(k) und z(k+1) = z(k) + ∆z(k) die zusatzlichen Forde-rungen

z(k+1)i ≥ 0 fur i = 1, . . . , p, (5.12)

gi

(

x(k))

+ ∇(

gi

(

x(k)))T

∆x(k) ≤ 0 fur i = 1, . . . , p (5.13)

erfullen. Im Vergleich zum Newton–Verfahren ersetzt man HL,x(x(k), z(k)) durcheien Matrix B(k), die in der Regel durch gewisse Quasi–Newton–Korrekturen (so-genannte Broyden–Verfahren) erzeugt wird. Des weiteren wird der Vektor z(k) aufder linken Seite durch z(k+1) ersetzt. Man erhalt ein implizites Gleichungssystem,welches nicht mehr linear bezuglich der Lagrange–Multiplikatoren ist. Außerdemwerden noch die linearen Ungleichungsbedingungen (5.12), (5.13) an ∆x(k) und∆z(k) gestellt.

Ausgeschrieben besagt (5.11) – (5.13)

∇f(

x(k))

+ B(k)∆x(k) +m∑

i=1

z(k+1)i ∇gi

(

x(k))

= 0,

z(k+1)i

(

gi

(

x(k))

+(

∇gi

(

x(k)))T

∆x(k)

)

= 0, i = 1, . . . , p, (5.14)

gi

(

x(k))

+(

∇gi

(

x(k)))T

∆x(k) = 0, i = p + 1, . . . , m.

Wir betrachten das folgende quadratische Programm

z = mins∈Rn

(

∇f(

x(k)))T

s +1

2sT B(k)s (5.15)

unter den Nebenbedingungen

gi

(

x(k))

+(

∇gi

(

x(k)))T

s ≤ 0, i = 1, . . . , p, (5.16)

gi

(

x(k))

+(

∇gi

(

x(k)))T

s = 0, i = p + 1, . . . , m. (5.17)

Erfulle dieses Problem die Voraussetzungen des Satzes 4.21 (Kuhn/Tucker). Dannsind die notwendigen Bedingungen fur ein Minimum gerade die Gleichungen (5.14).Ubungsaufgabe Damit ergibt sich folgendes Verfahren:

Algorithm 5.16 SQP–Algorithmus (Grundform).

1. Initialisierung.

Wahle x(0) ∈ Rn, B(0) =(B(0))T (≈ HL,x

(x(0), z(0)

))fur ein z(0) ∈ Rm

mit z(0)i

> 0, i = 1, . . . , p

2. Iteration. k = 0, 1, 2, . . .

97

Bestimme die Losung s von (5.15) - (5.17) und einen zugehorigen

Lagrange-Multiplikator z. Setze

x(k+1) = x(k) + s, z(k+1) = z.

Bestimme eine symmetrische Matrix

B(k+1) ≈ HL,x

(

x(k+1), z(k+1))

.

Falls B(k) positiv semidefinit ist, dann ist (5.15) – (5.17) ein konvexes quadra-tisches Programm. In diesem Fall sind die Bedingungen des Satzes 4.21 notwendigund hinreichend fur ein globales Minimum, siehe auch Satz 3.24. Zur Losung kannman beispielsweise ein Projektionsverfahren nehmen, siehe Abschnitt 5.1.

98

Literaturverzeichnis

[Bor01] Karl Heinz Borgwardt. Optimierung, Operations Research, Spieltheorie.Birkhauser Verlag Basel Boston Berlin, 2001.

[ERSD77] K.-H. Elster, R. Reinhardt, M. Schauble, and G. Donath. Einfuhrungin die nichtlineare Optimierung, volume 63 of Mathematisch–Naturwissenschaftliche Bibliothek. BSB B.G. Teubner VerlagsgesellschaftLeipzig, 1977.

[JS04] F. Jarre and J. Stoer. Optimierung. Springer–Verlag Berlin Heidelberg,2004.

99

Index

aktive Nebenbedingung, 81, 91Armijo–Liniensuche, 90Ausartung, 18, 26, 32

duales Programm, 50ausgeartete Basislosung, 15Ausgleichsrechnung, 61

Barrierefunktionskalare, 94

Barrieremethoden, 93Basislosung, 14Basiszyklus, 32benachbart, Basislosung, 18

duales lineares Programm, 43symmetrisch, 46

duales Problem, 88Dualitatssatz

schwacher, 43starker, 43

Engpassmethode, 28entartete Basislosung, 15

Fibonacci–Suche, 67Fibonacci–Zahlen, 66Funktion

konkav, 72konvex, 72unimodal, 64

goldener Schnitt, 65großter ganzzahliger Bestandteil, 57

Hauptelement, 24Hauptspalte, 24, 50Hauptzeile, 24, 50Hesse–Matrix, 74Hyperebene, 70

Innere–Punkt–Methoden, 42

Kegelkonvexer, 70

Komplementaritatssatz, 46, 47Komplexitat, 36

worst case, eines Algorithmus, 37worst case, eines Problems, 37

konvergentgerichtet, 78

konvex, 7konvexe Hulle, 8konvexe Linearkombination, 8konvexe Menge

Eckpunkt, 8Extrempunkt, 8

konvexes Polyeder, 9Kuhn–Tucker–Bedingung, 84

Lagrangesche Methode, 77Lagrangesche Multiplikatoren, 77lineares Optimierungsproblem, 7lineares Optimierungsproblem in 1.

Normalform, 10lineares Programm, 7

ganzzahlig, 55lineares Programm in 2. Normalform,

14lineares Programm in Normalform, 10linearisierter Kegel, 81

M–Methode, 31Methode der ε–Storung, 32

Operations Research, 5Optimalitatskriterium, 50

Penalty–Funktion, 92Penalty–Verfahren, 92Pivotelement, 24, 50primales lineares Programm, 43primales Problem, 87Projektionsverfahren, 89

Rechteckregel, 24

Sattelpunkt, 85Schlupfvariable, 14, 28Schnittbedingung, 56Simplex, 18Simplexmethode

duale, 48

100

Hauptsatz, 19Hauptsatz der dualen, 49lexikographische, 35

Simplextabelle, 23dual, 50duale, 50

SQP–Verfahren, 96stationarer Punkt, 90Strafparameter, 92

Tangentenkegel, 79Trennung von Mengen, 70Trennungssatz, erster, 71

unimodal, 64Unterhalbmenge, 75

Variablenkunstliche, 30

Vektorlexikopositiv, 35

Zielfunktion, 10, 61zulassige Basislosung, 15zulassiger Bereich, 7, 10zulassiger Punkt, 10Zweiphasenmethode, 30

101