Optimierung I

Vortragender: Bredies, Univ.-Prof. Dipl.-Math. Dr.

Mitschrift von Andreas Wenger

Sommersemester 2014

Inhaltsverzeichnis
I

Lineare Optimierung
1
Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1
Anwendungsbeispiele fr lineare Programmierung . . . . . . . . . . . . .
2
Basislsungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Konvexitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
Pivotelemente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Der Simplex Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Knstliche Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1
2 Phasenmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Matrix-Form der Simplex-Methode . . . . . . . . . . . . . . . . . . . . . . . . . .
8
Revidierter Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Duale lineare Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.1
Beispiele zu dualen Programmen . . . . . . . . . . . . . . . . . . . . . . .
9.2
Zusammenhang zwischen revidiertem Simplex Algorithmus und Satz 6
9.3
Sensitivitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.4
Optimalittsbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . .
10 Darstellung der zulssigen Vektoren . . . . . . . . . . . . . . . . . . . . . . . . .
10.1 Nullvariablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2 Nichtextremale Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

3
3
5
7
9
12
16
18
19
19
20
23
24
27
28
29
30
31
32

II Innere-Punkt-Verfahren fr lineare Programme

33
1
Allgemeine Innere-Punkt-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
III Unrestringierte nichtlineare Programmierung
1
Allgemiene Theorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Optimalittsbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Abstiegsverfahren und Schrittweitensteuerung . . . . . . . . . . . . . . . . . . . .
3.1
Schrittweitenstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Armijo und polynomiale Modelle . . . . . . . . . . . . . . . . . . . . . . . .
4
Konvergenzgeschwindigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1
Q- und R-Konvergenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Gradientenverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1
Verfahren des steilsten Abstiegs . . . . . . . . . . . . . . . . . . . . . . . . .
5.2
Gradientenhnliche Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Verfahren der konjugierten Gradienten fr quadratische Probleme . . . . . . . .
6.1
Prkonditionierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1
Ungenauigkeiten in Funktions-, Gradiente- und Hessematrixauswertung
7.2
Varianten des Newton-Verfahrens . . . . . . . . . . . . . . . . . . . . . . . .
7.3
Nichtlineare Ausgleichsprobleme . . . . . . . . . . . . . . . . . . . . . . . .
Literaturempfehlungen

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

44
44
45
51
53
55
59
60
66
66
69
69
72
74
75
77
78
82

I Lineare Optimierung
1 Einleitung
Ein lineares Programm ist die Aufgabe, ein lineares Funktional unter linearen Gleichheits- und
Ungleichheitsbedingungen zu minimieren.
Definition 1 (Lineares Programm in Standardform). text
Seien m, n N , A Rmn , b Rm , c R.

minn c x

xR
Dann ist die Aufgabe (1)

Ax = b

mit

x0

ein lineares Programm in Standardform.

Notation:
n

Wir schreiben: c x = ci xi
i=1

Die Gleichung Ax = b gilt in Rn .

x 0 gilt komponentenweise: xi 0

i {1 , . . . , n}

Die Standardform lsst allgemeine lineare Programme zu!

minn c x

xR
Betrachte (2)

Ax b

mit

x 0m
Dann: Ax b y R y 0 Ax + y = b
Gleichheitsbedingungen und Ungleichheitsbedingungen fr

(1 )

wobei
c=

min

(x,y)T Rn+m

c
0

und

x
y

mit

x
.
y

x = b
A
y
x
0
y

= (A I)
A

Bemerkung: y heit Schlupfvariable

Dann gilt:

ist Lsung von (2)

x

(
x, b A
x)T ist Lsung von (1 )

Beweis. text

x
y = b A
x und A
= A
x + b A
x=b
y
0 klar und y = b A
x
x 0 da A
x b.

<cx

cx

Angenommen (
x, y) mit A
x + y = b

0
y 0

x
Lsung von (2)
Ist x

Dann:

A
xb

0
x

Lsung von (2)

da x

Damit ist (
x, b A
x) Lsung von (1 )
T

Analog: Ist (
x, y) Lsung von (1 )

ist Lsung von (2)

x
qed

text

minn c x

xR
Betrachte (3)

Ax b

mit

x 0m
Dann: Ax b y R y 0 Ax y = b

= (A I)
Standardform ergibt sich Analog zu obigen Beispiel mit A

Ax = b
(4)
mit
T

xR
(x
)

x
2
n

Keine Ungleichheitsbedingung an x1 x1 freie Variable.

Beispiel: minn c x

Nun sei fr x1 R eine Darstellung x1 = u1 v1 mit u1 , v1 0. Setze ein in (4)

u1 v1
u1 0
x
n
2

=b
min
c1 (u1 v1 ) + ci xi mit A
v1 0

u1 ,v1 ,x2 ,..., xn R
i=2

xi 0
i = 2,..., n
xn
c1
c
1

Standardform ergibt sich mit:

c=
c2



cn

= (A1 A1 A2 An )
A

Alternative: Betrachte Aufgabe (4)

Angenommen ai1 0 fr ein i {1 , . . . , m}
Dann Ax = b
Einsetzen in (4)

x1 =

1
ai1

[bi aij xj ]
j=2

x1 kann eliminiert werden Standardform (1)

u1
v
1

=
x
x2



xn

Konkretes Beispiel:

min x1 + 3x2 + 4x3

x1 ,x2 ,x3 R

x1 + 2x2 + x3 = 5

2x1 + 3x2 + x3 = 6

x2 0 x3 0

x1 = 5 2x2 x3

quivalentes Problem:
min x2 + 3x3

x2 ,x3 R

mit

x2 + x3 = 4
x2 0

x3 0

1.1 Anwendungsbeispiele fr lineare Programmierung

Anwendungsbeispiel 1: [Ditproblem]
Aufgabe: Kostengnstigste Versorgung mit Nhrstoffen
Kosten: Preis im Supermarkt, Energie, etc.
Gegeben:
n Nahrungsmittel mit Kosten c1 , . . . , cn
m Nhrstoffe mit b1 , . . . , bm erforderlichen Einheiten in der Dit
Wissen: Nahrungsmittel i enthlt aji Einheiten des Nhrstoffes j

1in
1jm

Damit x1 , . . . , xn Einheiten des jeweiligen Nahrungsmittels:

x1 , . . . , xn 0
n

aji xi bj
i=1

Gesamtkosten: ci xi
i=1

Nahrung kann nur zugefhrt werden

die Dit muss eingehalten werden

minn c x

xR
Ditproblem damit

Ax b

mit

x0

Anwendungsbeispiel 2: [Transportproblem]
Aufgabe: Kostengnstigster Transport eines Produkts vom Produzenten an den Verbraucher
Gegeben:
1 Produkt
a1 , . . . , am Einheiten des Produkts in m Produktionssttten
Bedarf: b1 , . . . , bn Einheiten fr n Kufer
Transportkosten cij von Produktionssttte i zum Kufer j

Gesucht: xij optimaler Frachteinsatz fr Transport i j

x11

x1n

a1

xm1 xmn am
b1

bn

Bedingungen:
n

xij = ai
j=1
m

xij = bj
i=1

fr i = 1 , . . . , m

alles muss weg

fr j = 1 , . . . , n

Bedarf muss gedeckt werden

Zuatzbedingung:

i=1

j=1

ai = bj

1im

xij 0

nur Transport von Produktionssttte zum Kufer

1jm
n

Gesamtkosten: cij xij

j=1 i=1

Lineares Programm ergibt sicht damit durch:

T

= (x11 x1n x21 x2n xmn ) Rmn

x

=
A

1
= Rn
1

0
0

(m+n)(mn)

R

T
I

I Rnn

b = (a1 am b1 bn )

c = (c11 c1n c21 c2n cmn )

min
cx

mn

xR
x =
Transportproblem damit

b
A

mit

Anwendungsbeispiel 3: [Lagerhallenproblem]
Aufgabe: Plane Einkauf und Verkauf eines Produkts bei begrenzter Lagerkapazitt
Gegeben:
n Zeiteinheiten

 Lagerkapazitt c
Lagerhaltungskosten r pro Zeiteinheit und Stck
Kosten fr Kauf/Verkauf pi pro Stck zum Zeitpunkt i
Bedingung: Zu Beginn und am Ende soll das Lager leer sein
Gesucht:
Einkaufsplan: ui Einheiten zum Zeitpunkt i
Verkaufsplan: si Einheiten zum Zeitpunkt i
Modell: xi Lagerauslastung zum Zeitpunkt i
Dann: xi+1 = xi + ui si
Klar: xi 0

1in

x 1 = xn = 0

xi c 2 i n

Profit: pi si pi ui rxi
i=1

Damit Profitmaximierung: max pi si pi ui rxi

i=1

mit

xi+1 = xi + ui xi
x1 = 0

1in1

xn + un sn = 0

0 xi c

2in1

u1 , . . . , un , s1 , . . . , sn 0

2 Basislsungen
Sei im folgenden x Rn , b Rm , A Rmn .
Betrachte die Gleichung: Ax = b (5).

Annahme: rang(A) = m (H)

Sei m n, ansonsten knnen Zeilen von A eliminiert werden, ohne das sich die Lsungsmenge
von (5) ndert.

o. B. d. A. seien die ersten m Spalten von A linear unabhngig (ansonsten

vertausche Indizes von x). Damit A = (B C)

Also ist BxB = b eindeutig lsbar

B GLm (R).

xB
ist Lsung von (5).
0

Definition 2 (Basislsungen). text

Gegeben Ax = b

mit A Rmn rang(A) = m b Rm .

Es sei B Rmm eine regulre Untermatrix von A, d. h.

B = (aj1

ajm ) fr Indizes j1 , . . . , jm und det(B) 0. Dann heit B Basis. Die Lsung xB von BxB = b heit

k = j fr ein i {1 , . . . , m}
(xB )ji
n
Basisvariable. Der Vektor x R , gegeben durch xk =

0
sonst

heit Basislsung bezglich B.

Eine Basislsung x heit degeneriert, falls mindestens eine Komponente der Basisvariable gleich
0 ist.

Definition 3 (zulssige Lsungen). text

Rn zulssig fr Ax = b
In der Situation von Def inition 2 heit x
0.
x

A
x = b

x 0, falls

Analog definiert man zulssige Basislsungen und zulssige, degenerierte

Basislsungen.

Satz 1 (Fundamentalsatz der linearen Programmierung). text

min c x

xRn

Sei ein lineares Programm gegeben, d. h. (1)

Ax = b

mit

x 0
(i) Falls eine zulssige Lsung von Ax = b

Dann gilt:

x 0 existiert, existiert eine zulssige Basisl-

sung.
(ii) Falls eine Lsung von (1) existiert, so existiert eine zulssige Basislsung die (1) minimiert.
Beweis. text
(i) Schreibe A = (a1 an ) Spaltenmatrix.
n

Sei x Rn zulssige Lsung von Ax = b

x 0, also gilt: b = xi ai

Angenommen p der n Koordinaten von x sind positiv.

x1 , . . . , xp > 0 fr p n

i=1

und

xi 0.

b = xi ai .
i=1

Fall 1: a1 , . . . , ap sind linear unabhngig p m

Fr p = m ist x Basislsung
Fr p < m enhlt {ap+1 , . . . , an } m p Vektoren aj1 , . . . , ajmp , sodass
{a1 , . . . , ap , aj1 , . . . , ajmp } linear unabhngig ist. Zu der assoziierten Basis B ist
x eine zulssige, degenerierte Basislsung.
Fall 2: a1 , . . . , ap sind linear abhngig.
p

(y1 , . . . , yp ) 0 mit yi ai = 0
Es gilt

(xi yi )ai = b

i=1

o. B. d. A. yj > 0 fr ein j {1 , . . . , p}.

i=1

R. Whle so, dass x y 0 und (x y) = 0

fr ein k {1 , . . . , p}. Dazu = min { xyii yi > 0} (Minimum existiert, da yj > 0)

Fr i mit yi 0

xi yi xi 0

Fr i mit yi > 0

xi yi xi

xi
yi yi

xk
yk

Also gilt: x y 0. Fr k so, dass

=0
xk yk = 0.

x y ist eine zulssige Lsung mit hchstens p 1 positiven Komponenten. Falls Fall
2 in dieser Situation gltig, fhre eine weitere Reduktion durch.
Nach endlich vielen Reduktionen tritt schlielich Fall 1 ein

(i).

(ii) Sei x eine Lsung von (1), dann ist x zulssig fr Ax = b

x 0.

Wieder x1 , . . . , xp > 0 xp+1 , . . . , xn = 0 fr ein p n.

x Basislsung [siehe (i)]

Falls a1 , . . . , ap linear unabhngig

Wenn a1 , . . . , ap linear abhngig, whle wieder (y1 , . . . , yp ) 0, sodass yi ai = 0.

i=1

o. B. d. A. yj > 0 fr ein j. Mit aus (i) ist x y zulssig.

-) c y > 0

c (x y) = c x (c y) < c x

-) c y > 0

whle =

min { xyii

zur Optimalitt von x

yi < 0} wenn Minimum existiert sonst = 1.

Dann ist x + y zulssig und c (x + y) = c x + (c y) < c x

Also muss gelten c y = 0 und x y zulssig x y ist ebenfalls Lsung von (1) mit
hchstens p 1 positiven Komponenten. Analgo zu (i) folgt die Aussage von (ii).
qed
text
Bemerkung:
n
n
) Basislsungen.
) Mglichkeiten m Vektoren von n zu whlen hchstens (m
Es gibt (m
n
Dann sind nicht alle zulssig hchstens (m) zulssige Basislsungen.
Falls (1) eine Lsung besitzt, muss eine dieser zulssien Basislsungen eine Lsung von (1)
sein.

3 Konvexitt
Motivation: Untersuche Struktur der Lsungsmenge
Definition 4. text
Eine Menge C X, mit X reeller Vektorraum, heit konvex, wenn x, y C

[0, 1]

x + (1 )y C.
Der Punkt x C heit Extremalpunkt, falls es kein Paar x1 , x2 C gibt mit x1 x2 und
x = x1 + (1 )x2

(0, 1).

Satz 2. Sei A Rmn , rang(A) = m

K = {x Rn Ax = b

b Rm .

x 0} . Dann gilt:

x ist Extremalpunkt von K

x ist zulssige Basislsung zu Ax = b

Beweis. Offensichtlich: K konvex

Sei x eine zulssige Basislsung von Ax = b
o. B. d. A. x = (x1 xm 0 0)
m

xi ai

i=1

mit a1 , . . . , am linear unabhngig.

x 0.

x0

Angenommen: x = y + (1 )z
Insbesondere: y 0
0 = yi + (1 )zi
m

fr y, z K y z

(0, 1)

z 0. Fr die Komponenten i {m + 1 , . . . , n} folgt:

yi = zi = 0.
m

Weiters gilt: yi ai = b = zi ai = b
i=1

i=1

x = y = z da a1 , . . . , am linear unabhngig

Sei x Extremalpunkt von K

o. B. d. A.

xi > 0

1ik

xi = 0

i>k

kn

xi ai = b
i=1

Wir zeigen a1 , . . . , ak sind linear unabhngig.

k

Angenommen, dies ist nicht der Fall, dann (y1 , . . . , yk ) 0) mit ai yi = 0.

i=1

Schreibe y = (y1 yk 0 0) R
Da xi > 0 fr i = 1 , . . . , k existiert ein > 0 mit x + y 0
Klar auch A(x y) = b

1
1
2 (x y) + 2 (x + y)

x y 0.

x y K

= x und x y x + y

zu x ist Extremalpunkt
qed

text
Definition 5. text
R Rn heit polyedrische Menge, falls endlich viele ai Rn
sodass R = {x R

ai x bi

bi R

i = 1 , . . . , N exisiteren,

1 i N }.

Ist R zustzlich beschrnkt, so heit R Polyeder.

Korollar 1. text
(i) Falls K

K enthlt Extremalpunkte.

(ii) Falls eine endliche optimale Lsung vom (1) existiert, so existiert eine optimale Lsung,
die Extremalpunkt von K ist.
(iii) K enthlt hchstens endlich viele Extremalpunkte.
Beweis. text
(i) folgt aus Satz 1(i) + Satz 2
(ii) folgt aus Satz 1(ii) + Satz 2
(iii) folgt aus Bemerkung am Ende von 2 + Satz 2
qed

10

Bemerkung: Falls K beschrnkt, so ist K ein Polyeder.

k1 , . . . , kN K Extremalpunkte mit:
xK

x = i ki

f r (i 0

i=1

i = 1)
i=1

Nach Satz 2 sind diese Extremalpunkte zulssige Basislsungen.

Beispiel:
x1 + x2 + x3 = 1

x1 , x 2 , x 3 0

3 Extremalpunkte
Basislsungen

x1 + x2 + x3 = 1
2x1 + 3x2 = 1
x1 , x 2 , x 3 0
2 Extremalpunkte
Basislsungen:

2

1

0

1/2 0
1
0 ; /3

1/2 2/3

nicht zulssig Extremalpunkte

x1 + 83 x2 4
x1 + x2 2
2x1 3
x1 , x 2 0

5 Extremalpunkte P, Q, R, S, T

11

3 Schlupfvariablen y1 , y2 , y3 0
Basislsungen:

x1 + 38 x2 + y1 = 4

x1 + x2 + y2 = 2

2x1 + y3 = 3

y2 = y3 = 0

x1 3/2

x2 = 1/6

y1 7/6

y1 = y2 = 0

x1 4/5

x2 = 6/5

y3 7/5

x1 = y1 = 0

x2 3/2

y2 = 1/2

y3 3

x2 = y3 = 0

x1 3/2

y1 = 5/2

y2 1/2

x1 = x2 = 0

y1 4

y2 = 2

y3 3

Bemerkung: Die Aufgabe min c x kann durch Finden eines Extremalpunktes gelst werden,
xR2

ohne dass man das lineare Programm auf Standardform bringt.

4 Pivotelemente
Motivation: Lineares Programm

finde optimale zulssige Basislsung

Dazu: Wechsel von Basislsungen.

Wieder gelte die Annahme: (5) + (H)
Interpretation:
ai x = bi fr 1 i m (5 ).
a1

Fr A = rang(A) = m a1 , . . . , am sind linear unabhngig.

am
dim ({x Rn Ax = b}) = n m

o. B. d. A. A = (B C)

12

det(B) 0

Durch Gau-Elimination ist (5 ) quivalent zu

x1
x2

+y1,m+1 xm+1 + . . . + y1,n xn

= y1,0

+y2,m+1 xm+1 + . . . + y2,n xn

= y2,0

xm +ym,m+1 xm+1 + . . . + ym,n xn = ym,0

yi,j
mit geeigneten

yi,0

m+1j n

1im

1im

Nun soll Basisvariable xp durch xq ersetzt werden

Bedingung: yp,q 0

1pm

m+1q n

Gau-Elimination

=
1. Schritt: yp,j

yp,j
yp,q

j = 0,..., n

2. Schritt: yi,j
= yi,j

Dann xi,q = pi

yp,j
yp,q yi,q

(6a)

ip

0jn

(6b)

xq neue Basisvariable.

Beispiel:
+x4 + x5 x6

x1

=5

+x4 3x5 + x6 = 3

x2

x3 x4 + 2x5 x6 = 1
(x1 , x2 , x3 ) Basisvariablen
Tableau:
x1 x2 x3

Ziel

(x4 , x5 , x6 ) neue Basisvariablen

x1 x4 :

x4

x5

x6

x1

x2 x3 x4

x5

x6

x3

x4 x5 x6

1 1

x2 x5 :
x3 x4 x5

x3 x6 :

x1

x2

x6

3/5

1/5

2/5

18/5

2/5

1/5

3/5

7/5

1/5

3/5

1/5 1/5

x1

x2

1 2

2 3

3 5

text
Interpretation: Die Lsungen von Ax = b sind nicht eindeutig.
Whlt man Basisvariablen x1 , . . . , xm

xm+1 = . . . = xn = 0

eindeutige Baislsung.

Lsungen x1 , . . . , xm sind gegeben durch die rechte Spalte im Tableau.

Basiswechsel xp xq ist mglich, wenn xp,q 0

xp = xm+1 = . . . = xq1 = xq+1 = . . . = xn .

x1 , . . . , xp1 , xp+1 , . . . , xn , xq gegeben durch rechte Seite im Tamblean nach der Umformung.

13

Nchster Schritt: Zulssigkeitsbedingung x 0 einbinden.

Nichtdegeneriertheitsbedingung: (N D) Jede zulssige Basislsung ist nicht degeneriert.
Es gelte (N D). Sei eine zulssige Basislsung (x1 , . . . , xm , 0 , . . . , 0) gegeben.
(N D)

xi > 0

1 i m.

Wir wollen Wechsel xp xq durchfhren.

Rechte Spalte im Tableau:

yp,0
=

yp,0
yp,q

yp,q > 0

Damit kommen nur poitive Pivotelemente in Betracht.

Sei yp,q > 0.

yi,0
= yi,0

yp,0
yp,q

>0

fr i p

yi,q

>0

Falls yi,q 0

yi,0

0
yi,0

Falls yi,q > 0

Damit q so, dass
Also:

yp,0
yp,q

yi,0
yi,q

yp,0
yp,q

= min { yi,0
yi,q > 0}
i,q

Whle p, q so, dass yp,q > 0

und

yp,0
yp,q

= min { yi,0
yi,q > 0}
i,q

(7). Dieses Minimum

) neue zulssige Basislsung.

, . . . , ym,0
muss existieren. Dann (y1,0

Beispiel:

1 0 0

4 6 4

0 1 0

2 3 3

zulssige Pivotelemente

0 0 1 1 2 1 1
Nchster Schritt: Wahl des Pivotelementes welches c x verringert.
Ausgangssituation:
Tableau:

A = (a1 an )

rang(A) = m

a1 am

am+1

an

y1,m+1

y1,n

y1,0

b Rm

1 ym,m+1 ym,n ym,0

Zulssige Basislsung (xB , 0)
xB = (y1,0 , . . . , ym,0 ) yi,0 > 0
Funktionalwert: c x = cB xB

mit cB (c1 , . . . , cm )

14

c Rn

Basiswechselschritt:

Whle (xm+1 , . . . , xn ) 0.

Dadurch mssen x1 , . . . , xm angepasst werden.

n

x1 = y1,0 y1,j xj

j=m+1

(8)

xm = ym,0 ym,j xj

j=m+1

Wie verhlt sich der Funktionalwert:

m

i=1

i=m+1

z = c x = ci xi + ci xi =

n
n
m
m
n
n

= ci yi,0 yi,j xj + ci xi = yi,0 ci yi,j xj ci + ci xi =

i=m+1
i=1
j=m+1
i=1
i=1 j=m+1
i=m+1

n
m
n

= z0 + ci yj,i cj xi = z0 + (ci zi )xi

i=m+1
j=1
i=m+1

wobei zi = y1,i c1 + y2,i c2 + . . . + ym,i cm

Definiert man

rj = cj yi,j ci = cj zj
i=1

fr m + 1 i n
z = z0 + rm+1 xm+1 + . . . + rn xn

(9)

rj heien relative Kostenkoeffizienten. Ziel: rm+1 xm+1 + . . . + rn xn < 0.

Fr Basiswechsel ist nur ein xj 0 m + 1 j n

Funktionalabstieg, sobald rj 0.

Satz 3. Sei x = (x1 xm 0 0) zulssige, nicht degenerierte Basislsung mit Kosten

z0 = c x. Angenommen, es existiert ein j {m + 1 , . . . , n} mit rj < 0, dann existiert eine
zulssige Lsung mit Kostenfunktionalwerte z < z0 .
Falls der Wechsel xp xj zulssig ist fr ein p, so ergibt dieser einen geringeren Funktionalwert.
Anderenfalls sind K und {c x x K} unbeschrnkt (d. h. (1) besitzt keine Lsung).
Beweis. text
Ist rj < 0, so kann man xj = min { yxiji yi,j > 0
anderenfalls whle
Da xi > 0
1im

xj

1 i m} whlen, falls Minimum exisiert,

> 0 beiliebig.

1im

xj 0 und x = (x1 , . . . , xm , 0 , . . . , xj , . . . , 0) mit xi = xi yi,j xj

ist zulssig. Nach (9) Funktionalwert z = z0 + rj xj < z0 .

<0

Falls nun der Wechsel xp xq fr ein p zulssig ist, liefert die Konstruktion fr x die neue
zulssige Basislsung Aussage.
Anderenfalls ist yi,j 0

fr i = 1, . . . , m und xj > 0 kann beliebig gro gewhlt werden K

unbeschrnkt.
Sei x ein Minimierer

min c x z = z0 + rj xj
xK

xj > 0.

Da rj < 0, ist die rechtes Seite unbeschrnkt nach unten

qed

15

Satz 4. Falls rj 0

j {m + 1 , . . . , n}, so ist x optimal.

Beweis. text

Falls x zulssig, so gilt nach (8) und (9)

c x = z0 + rj xj z0 = c x
j=m+1

x optimal.
qed

5 Der Simplex Algorithmus

Ziel: Wende Basiswechselstrategie aus Unterkapitel 4 an.
Zunchst: Berechne rj und z0 .
m

rj = cj yi,j ci

m+1j n

und

z0 = yi,0 ci

i=1

j=1

a1 am

am+1

an

y1,m+1

y1,n

y1,0

Schreibt man

c1

ym,m+1 ym,n ym,0

cm

cm+1

und eliminiert c1 , . . . , cm

cn

a1 am

am+1

an

y1,m+1

y1,n

y1,0

in der letzten Zeile,

so ergibt sich

(10)

ym,m+1 ym,n ym,0

rm+1

rn

z0

Simplex Algorithmus:
Voraussetzungen:
A Rmn

b Rm

rang(A) = m

c c Rn

mn

(N D) jede zulssige Basislsung ist nicht degeneriert

Schritt 0: Bilde Tableau der Form (10)
Schritt 1: Falls rj 0

j {1 , . . . , n}

Schritt 2: Whle q mit rq < 0

Schritt 3: Berechene

yi,0
yi,q

STOP, denn Lsung ist gefunden.

neue Basisvariable
yi,q > 0

Falls yi,,q 0 i {1 , . . . , m}
Anderenfalls, whle p so, dass

STOP, es existiert keine Lsung.

yp,0
yp,q

= min { yi,0
yi,q > 0}
i,q

16

 Schritt 4: Pivotisiere bezglich yp,q , d. h. fhre Basiswechsel xp xq durch

(mit letzter Zeile im Tableau)

Schritt 1

Bemerkung:
Schritt 0 kann nicht trivial sein und muss gegebenfalls von Fall zu Fall angepasst werden. In der
Praxis A, b, c gegeben. Eine mgliche Strategie ist die Ermittlung einer zulssigen Basislsung
auf Gut Glck.
a1 am

am+1

an

y1,m+1

y1,n

y1,0

c1

=
(A b)

ym,m+1 ym,n ym,0

cm

cm+1

cn

a1 am

am+1 an

y1,0

Whle m Basiskomponenten und eliminiere

ym,0

(Spaltenpermutation)

> 0 !!!
, . . . , ym,0
Wichtig: Es muss gelten y1,0

Ansonsten ist Lsung nicht zulssig oder degeneriert

andere Basislsung versuchen.

Falls Bedingung erfllt, eliminiere die entsprechenden Koeffizienten in der untersten Zeile
Schritt 1
Manchmal ist die Wahl einer anfnglichen zulssigen Basis offensichtlich.
Beispiel:

max 60x1 + 40x2

x1 ,x2

mit

2x1 + x2 70
x1 + x2 40
x1 + 3x2 90
x1 0

Tableau mit Schlupfvariablen:

Schritt 0

x2 0

a1
a2 a3 a4 a5 b

2
1
1 0 0 70

1
1
0 1 0 40

1
3
0 0 1 90

60 40 0 0 0 0

kein Rechnung ntig

Basisvariable x3 , x4 , x5 .

17

Pivotisiere:
60 < 0

rj 0

70
2

x1 hineinnehmen

40
= 35

90

x3 herausnehmen

a1

a2

a3

a4 a5

a1 a2

a3

a4

a5

1/2

1/2

35

30

1/2

1/2

10

5/2

1/2

55

30

10

30

2100

20

20

2200

j {1, 2, 3, 4, 5}

Lsung

x1 30
=
x2 10

Funktionalwert: 2200 (da Maximierungsaufgabe)

6 Knstliche Variablen
Motivation: Finde zulssige Basislsung

Schritt 0

Bemerkung:

min c x

xRn

Betrachte lineares Proramm der Form

Ax b

mit

x 0

min c x

xRn

.
Dieses ist quivalent zu

Ax + y = b

mit

x 0 y 0
Fr x = 0 y = b ergibt sich eine zulssige Basislsung.

Finde x Rn mit Ax = b
x 0 (11).
m

minn yi

xRm

i=1

yR

(12)

Ax + y = b

mit

x 0 y 0

o. B. d. A. b 0.

18

mit bi > 0

1 i m.

Nun gilt: (x, y) ist Lsung von (12)

y=0

y=0

Ax + y = b

x 0 y 0

Ax = b

x 0

y=0

x lst (11)

(12) ist ein lineares Programm.

6.1 2 Phasenmethode
1. Lse (12)

x ist zulssige Basislsung

2. Simplex-Algorithmus mit x als Startbasislsung

Beispiel: Lse

2x1 + x2 + 2x3 = 4

x1 , x 2 , x 3 0
3x1 + 3x2 + x3 = 3
Knstliche Variablen: x4 0 x5 0
2x1 + x2 + 2x3 + x4 = 4

min
x4 + x5
mit 3x1 + 3x2 + x3 + x5 = 3
x1 ,x2 ,x3 ,x4 ,x5

xi 0

a1 a2 a3 a4 a5

...
x1 =

1
2

x2 = 0

Ausrechenen relative Kosten

4/3

1 2/3

1/3

1/3

4/3 0

5/3

3
2

1 0

0 1

...

5 4 3 0 0 7

0 1

x3 =

1i5

0 3/4 1

5/4

3/4

0 1/4
0

1/2

3/2

1/2

1/2

Lsung

7 Matrix-Form der Simplex-Methode

Ax = b
Betrachte: minn c x
mit
(1).

xR

Hier: A = (B D) mit G GLm (R) Basis

xB
cB
c=
xD
cD
Beobachtung: Die Wahl der Basisvariablen bestimmt eindeutig des Tableau im Simplex-Algorithmus.
x=

19

Denn: Angenommen, Basis (x1 , . . . , xm )

(1)

BxB + DxD = b
mit

xB 0 xD 0

min cB xB + cD xD

xB ,xD

(13)

xB
xB = B 1 b ist Basislsung und xD = 0.
0
Fr allgemeine xD liefert (13)
xB = B 1 b B 1 DxD

Ist x =

z = c x = cB xB + cD xD = cB [B 1 b B 1 DxD ] + cD xD =
= cTB B 1 b + [cTD cTB B 1 D] xD = z0 + rD xD
T
mit rD
= cTD cTB B 1 D

I
B 1 D
B 1 b

Tableau: T =

0 cTD cTB B 1 D cTB B 1 b

Bis aus Permutation der Spalten hat das Tableau im Simplex-Algorithmus genau diese Form.

8 Revidierter Simplex-Algorithmus
Heuristische Beobachtung: Simplex-Algorithmus knovergiert nach

3m
2

Pivotschhritten

Aktualisierung des Tableaus rechenaufwendig.

Motivation: Fhre nur die essentiellen Rechenschritte durch Matrix-Form ist hilfreich.
Revidierter Simplex-Algorithmus
Gegeben:
Basisvariablen x1 , . . . , xm
B 1 (Inverse der zugehrigen Basis)
xB = B 1 b
T
Schritt 1: Berechne rD
= cTD cTB B 1 D

(a) T = cTB B 1
T
(b) rD
= cTD T D

Ralls rD 0

STOP

Schritt 2:
Berechne Pivotpunkte q mit (rD )q < 0
Berechne yq = B 1 aq

yq entspricht genau der Pivotspalte im Tableau

20

 Schritt 3: Falls yi,q 0 i

Ansonsten whle p so, dass

STOP
xp
yp,q

= min { yxi,qi yi,q > 0}

Schritt 4: Aktualisiere B 1 und xB = B 1 b durch Pivot-Operation,

z. B. durch Gau-Elimination [ B 1 xB

yq ]

[ (B 1 ) xB

ep ]

Weiter mit Schritt 1.

Man sieht: berflssie Rechnungen werden vermieden.
Bemerkung: Revidiertes Verfahren erlaubt eine einfache Reinitialisierung.
Durch Rundungsfehler kann die Eigenschaft BxB = b verletzt werden. Falls BxB b > fr eine Toleranz > 0

Neuberechnung von B 1 und xB = B 1 b durch ein unabhngiges Verfahren.

Beispiel:
a1 a2 a3 a4 a5 a6

cT = (3 1 3 0 0 0)

2 2 1 0 0 1 6
Basisvariablen (BV ) x4 , x5 , x6

zulssige Lsung
B 1

BV

xB

I. T = cTB B 1 = cTB = (0 0 0)
T
rD
= cTD T D = cTD = [ 3 1 3]

x1
Also x2 in die Basis nehmen

x2

x3

y2 = B 1 a2 = (1 2 2)
B 1

BV

xB

y2

2 5 6
min { , , }
1 2 2

B 1

BV
p=1

Aktualisierung

21

xB

 1 0 0

II. = (1 0 0) 2 1 0 = (1 0 0)

2 0 1
T

T
rD

2 1 1

= (3 3 0) (1 0 0) 1 3 0 = (3 3 0) (2 1 1) = (1 2 1)

2 1 0
1 0 0 1 1

B a3 = 2 1 0 3 = 1

2 0 1 1 1
1

x3 in die Basis aufnehmen

B 1

BV

xB

y3

1
B 1

BV
P ivotisierung

2 1
min { , }
1 1

xB

3 1 0

III. = (1 3 0) 2 1 0 = (3 2 0)

4 1 1
T

T
rD

2 1 0

= (3 0 0) (3 2 0) 1 0 1 = (3 0 0) (4 3 2) = (7 3 2)

2 0 0

x1 in die Basis aufnehmen

B 1

BV

3 1 0 2 5

B a1 = 2 1 0 1 = 3

4 1 1 2 5
1

xB

y3

BV
P ivotisierung

22

B 1

xB

1/5 0

1/5

3/5

1/5

2/5

8/5

 3/5 1/5 0

IV. = (3 3 0) 1/5 2/5 0 = (6/5 3/5 0)

1
0 1
T

T
rD

= (1 0 0) (6/5 3/5

1 1 0

=
0)
2 0 1
2 0 0

= (1 0 0) (12/5 6/5 3/5) = (7/5

text

Lsung:

6/5

3/5)

ST OP

1/5
0


8/5

x=
0


0

4

9 Duale lineare Programme

Motivation: Besseres Verstndnis von linearen Programmen und deren Lsungen
duales Programm
P rimalesP rogramm
Wir betrachten:

minn c x

xR

AR

mn

bR

cR

DualesP rogramm

Ax b

max
b
m

x0

AT c

(14)

Die Darstellungen in (14) werden symmetrische Dualittsformen gennant. Primales und duales
Programm knnen folgendermaen ineinander berfhrt werden:
(i) Vertauschen von Kosten c und Nebenbedingungen b
(ii) Transposition von A
(iii) Umkehren der Ungleichheitsbedingung
(iv) Vertauschen von min und max
Bemerkung: Das primale und duale Programm sind nicht in der blichen Standardform gegeben.

min c x

xRn

Ax

b
A

= x =

(1) minn c x
mit Ax b

b
Ax

xR

mit

A
b

x0

x 0

23

b
max

R2m

T c
Damit das duale Programm:

mit

=(u,v)T

max b u b v

u,vRm

T
T

A u A v c

mit

u 0 v 0

mit AT
c
max b

Rm

Denn jedes
Rm ist als
=uv
u 0 v 0 darstellbar.
P rimalesP rogramm
DualesP rogramm

(15)
Ax = b
c

AT
max b
minn c x

Rm
xR
x0
asymmetrische Dualittsformen

9.1 Beispiele zu dualen Programmen

Beispiel 1: [Duales Ditenproblem]

Ax b
Primales Programm: minn c x mit

xR

x 0
x1 , . . . , xn Nahrungsmittel mit Kosten c1 , . . . , cn
aij Nhrstoff i in Nahrungsmittel j
b Ditanforderung

A c
Apothekerproblem

Duales Programm: max

b

mit

Rm

Interpretation: Ein Apotheker produziert zu den m Nhrstoffen m Pillen, die zu den Preisen

1 , . . . , m verkauft werden. Um konkurrenzfhig zu sein, drfen sie nicht mehr kosten als die
Nahrungsmittel die sie ersetzten AT c.
Da b den Bedarf angibt maximiere b .
Beispiel 2: [Duales Transportproblem]

Primales Programm:

m n

min cij xij

xij R i=1 j=1

xij = ai

j=1

m
mit x = b
ij
j

i=1

xij 0

1im
1jn
i, j

asymmetrische Dualittsform. Gleichheitsbedingung u Rm v Rn

24

u
v

Duales Programm:

ui + vj cij

mit 1 j n

1 i m

max a u + b v

uRm
vRn

Interpretation:

m Produktionssttten, n Verkaufsstellen. Bisherige Kosten i j gegeben durch cij .

Unternehmer: Angebot
Kaufe alle Produkte von Produktionssttte i zum Preis ui
Verkaufe alle Produkte an Verkaufsstelle j zum Preis vj
Das Angebot ist nur attraktiv, falls ui + vj cij .
(ui + vj ist der Preis den der Hersteller beim Rckkauf zahlen muss).
Der Unternehmer maximiert Gewinn durch max a u + b v
u,v

mit ui + vj cij

Lemma 1. Sind x und zulssig fr (15), so gilt: c x b .

Beweis. Es gilt: Ax = b
AT x c x

x 0 und

AT c

b = bt = xT AT = AT x c x
qed

Interpretation:
x zulssig
zulssig

c x ist Abschtzung fr max

b
m
R

b ist Abschtzung fr minn c x

xR

AT c

Ax = b

x 0

Korollar 2. Falls x0 und 0 zulssig fr (15) und cx0 = b0 , so folgt x0 und 0 sind Lsungen
des primalen und des dualen Programms.
Beweis. text
x0 zulssig

b 0 = c x0 max
b
m
R

AT c

0 ist Lsung der dualen Aufgabe.

Analog: x0 ist Lsung der primalen Aufgabe.

qed
Die Umkehrung ist auch wahr, d. h. es gibt keine Lcke zwischen prmalen und dualen Programm.
C

Satz 5. Sei C Rn konvex und y C .

Dann a Rn {0} a y < inf a x
xC

falls Infimum existiert.

25

Beweis. Nach Voraussetzung ist = inf x y > 0.

xC

R R
f
=
inf
f (x) = min f (x) = f (x0 )

xCB2 (y)

xCB2 (y)
x

Dann klar: x0 y x y x C. Setze a = x0 y.

fr ein x0 C B2 (y).

Nun gilt fr ein x C und [0, 1] x0 + (x x0 ) C. x0 + (x x0 ) y2 x0 y2

2

2(x x0 ) (x0 y) + x x0 0
2

[0, 1]

lim 2(x x0 ) (x0 y) + x x0 = 2(x x0 ) (x0 y) 0

0

Also: (x0 y) x (x0 y) x0 = x0 y2 + (x0 y) y = (x0 y) y + 2

a y + 2 inf a x
xC

qed

text
Satz 6. text
Falls das primale oder duale Programm in (15) eine optimale,zulssige Lsung besitzt, so besitzt
das jeweilige andere Programm ebenfalls eine zulssige, optimale Lsung und die Funktionalwerte
stimmen berein.
Falls ein Problem in (15) nach unten bzw. oben unbeschrnkt ist, so besitzt keines der Probleme
eine Lsung.
Beweis. text
Ist das primale Programm unbeschrnkt nach unten und existiert eine duale Lsung
Rm , dann existiert ein zulssiges x Rn , mit c x b

zu Lemma 1.

Also mus das duale Problem nach oben unbeschrnkt sein.

Angenommen, x0 ist ein Lsung des primalen Programms.
Setze z0 = c x0 und C = {(r, w) Rn+1 r = tz0 c x

w = tb Ax

x0

t 0}.

Wir zeigen C ist konvex.

t1 0
Seien (r1 , w1 ), (r2 , w2 ) C, d. h.

t2 0

x1 0 r1 = t1 z0 c x1

w1 = t1 b Ax1

x2 0 r2 = t2 z0 c x2

w2 = t2 b Ax2

Fr [0, 1] ist:
r1 + (1 )r2 = [t1 + (1 )t2 ]z0 c [x1 + (1 )x2 ]
w1 + (1 )w2 = [t1 + (1 )t2 ]b A[x1 + (1 )x2 ]
t1 + (1 )t2 0

x1 + (1 )x2 0

(r1 , w1 ) + (1 )(r2 , w2 ) C

C ist konvex
Man zeigt weiter:
C ist abgeschlossen
C ist ein Kegen, d. h. (r, w) C und 0

26

(r, w) C

Wir behaupten: (1, 0) / C. Dazu: Sei (1, 0) = (r, w) C.

Falls w = t0 b Ax0 = 0
r
t0

= z0 c

x0
t0

fr x0 0 t0 > 0

= z0 c x =

c x0

cx0

Falls (r, w) = (1, 0) und w = Ax0 = 0

Damit ist

x0 +x0

x=
x0

da

x zulssig

x0
t0

optimal

fr x0 0

zulssig fr jedes > 0 und

t0 = 0

c(x0 +x0 ) =

r1
r = 1 = c x0
cx0 +cx0 < cx0

(1, 0) / C
Nach Satz 5 existiert (s, ) Rn+1 mit s < inf sr + w = .
(r,w)C

(r, w) C mit sr + w < 0

s < (sr + w)
(0, 0) C
=0

und

(r, w) C

0 nach Definition des Infimums

s<0

sr + w 0

(r, w) C

w 0 (r, w) C
s
r +
w 0 (r, w) C

mit
= s

(tz0 c x) +
(tb Ax) 0

x 0

t 0

(c AT
) x + t
b tz0 0 x 0 t 0
Fr t = 0 (c AT
) x 0
x 0
T
T
cA 0 A c
ist zulssig fr das duale Problem
Fr t = 1 x = 0

b z0 0
b z0 = c x

ist optimal fr das duale Problem

Korollar 2

Die Umkehrung fr duale Programme folgt analog!

qed
text
9.2 Zusammenhang zwischen revidiertem Simplex Algorithmus und Satz 6

min c x

Fr
(P ) lautet das duale Problem

Ax
=
b

mit

n
Sei nun x R optimal fr (P ).
xRn

Vertausche Variablen x = (xB , 0),

xB Rm ,

A = (B D)

27

(D)

mit AT c

max b

Rm

B GLm (R)

Da x optimal relative Kostenkoeffizienten rD 0

T
rD
= cTD cTB B 1 D 0

Whle T = cTB B 1 , dann

AT c

cTB B 1 D cTD

T 1
T A = (T B T D) = (cTB CB
B D) (cTB cTD ) = cT
zulssig fr das duale Problem (D).

Nun gilt: b = cTB B 1 b = cTB xB = c x

Korollar 2

optimal fr (D).

Satz 7. Ist x eine zulssige optimale Lsung von (P ) zur Basis B, dann ist = (B 1 )T cB eine
zulssige optimale Lsung von (D) und die Kostenfunktionalwerte stimmen berein.

Damit: Lsungsalgorithmus fr (D)

(1) Fhre Simplex-Algorithmus fr (P ) durch
1 T

(2) Berechne = (B ) cB

B 1 inverse Basis

cB assoziierte Kosten

duale Lsung

9.3 Sensitivitt
Motivation: Wie verhalten sich die Lsungen bei Strung von b?

min c x

xRn

(P )
Betrachte

Ax = b

mit

n
Insbesondere: Es sei x R optimale Lsung, B die dazugehrige Basis und die Lsung sei nicht
degeneriert. Lsung des dualen Problems = (B 1 )T cB .
Betrachte nun (P ) mit b + b statt b. Definiere x = sup xi .
i=1,...,m

Whle =
b .

1
1
B 1
2

[ min xi ] > 0
i=1,...,m

mit Zeilensummennorm und b Rm mit

Mit dieser Wahl gilt:

min [B 1 (b + b)]i [ min [B 1 b]i ] B 1 b

i=1,...,m

i=1,...,m

[ min xi ] B 1 b [ min xi ] B 1 =
i=1,...,m

i=1,...,m

Damit (B 1 (b + b) 0) ist zulssig. Weiter ist

1
[ min xi ] > 0
2 i=1,...,m

T
rD
= cTD cTB B 1 D 0 unabhngig von den

Daten b + b. Da B 1 inverse Basis zu ursprnglicher Lsung x = (B 1 (b + b) 0) ist

min c x

xRn

optimale Lsung fr
falls b .

Ax = b + b

mit

x 0

28

Optimale Kosten:

c x = cB xB + cTB B 1 b = z0 + z

z = cTB B 1 b = T b = b

Damit: Die Sensitivitt vom optimalen Funktionalwert ist durch die Gre der Komponenten
der dualen Lsung gegeben entspricht marginalen Kosten.
9.4 Optimalittsbedingungen
Betrachte die symmetrische Dualittsform (14)
max b

A c
mit

min c x

Ax b
mit

x 0
xRn

Rm

text
Bezeichnung:

A = (a1 an ) Spaltenmatrix

a1

A = Zeilenmatrix

am

Satz 8 (Optimalitt fr symmetrische Dualittsform). text

Seien x, zulssige fr das primale und duale Prolem.
x, sind optimal

(a) xi (ci ai ) = 0

i = 1, . . . , n

(b) j (a x bj ) = 0

j = 1, . . . , m

Beweis. text

Aus (a) folgt:

(cT T A) x = 0

Aus (b) folgt:

T (Ax b) = 0

Zusammen folgt:

c x = cT x = T A x = T b = b

Analog zu Korollar 2

x, optimal

Da x, optimal
Zulssigkeit:

Ax b und T A cT

T b T Ax cT x
T (Ax b) = 0
0

cx=b
T b = T Ax = cT x

j (aj x bj ) = 0

j = 1, . . . , m

(cT T A) x = 0
0

xi (ci ai ) = 0

i = 1, . . . , n

qed

29

Korollar 3. Fr die asymmetrische Dualittsform (15)

min c x

Ax = b
mit

x 0
xRn

max b

Rm

mit AT c

gilt: Sind x, zulssig so ist

(x, ) optimal

Beweis. Folgt aus Ax = b

(a) xi > 0

ai = ci

(b) ai < ci

Ax b
Ax b

i = 1, . . . , n

xi = 0

j = 1, . . . , m

Satz 8
qed

text
Bemerkung: Die Vektoren (x, ) Rn+m lsen das primale und duale System

Ax = b
AT + s = c

(16)
s Rn
x0
s0

xi si = 0
i = 1, . . . , n

Ax = b
Denn: zulssig

x0

Ax = b

s R

A c

x0
A +s=c

Falls (x, ) zulssig, (x, ) optimal

xi > 0 ai = ci
Korollar 3

i = 1, . . . , n

ai < ci xi = 0

xi > 0 s i = 0
si =ci ai

i = 1, . . . , n
s i > 0 xi = 0

s i xi = 0

i = 1, . . . , n

10 Darstellung der zulssigen Vektoren

Motivation:
Finde mglichst einfache Beschreibung der Menge S = {x Rn Ax = b

x 0}.

Schon gesehen: Extremalpunkte von S =

Basislsungen
Weitere Eigenschaften:

Ax = b
Definition 6. Die Bedingungen

x 0
T
gibt mit A = 0 und b = 0.

enthalten redundante Gleichungen falls es ein Rm

30

 redundante Gleichungen knnen entfernt werden

maximaler Rang in A

10.1 Nullvariablen
Definition 7. text
Die Variable xi heit Nullvariable, falls gilt: Ax = b
Beispiel:

A=

2 3 4
1 1 1

b=

6
3

Ax = b

x0

xi = 0

x0

2x1 + 3x2 + 4x3 = 6

x1 , x 2 , x 3 0
II
x 1 + x2 + x3 = 3
I 2II = x2 + 2x3 = 0 x2 = x3 = 0 x2 , x3 Nullvariablen

Satz 9 (Nullvariablen). Es sei S . Dann gilt:

xi ist eine Nullvariable

Rm AT 0

b=0

(AT )i > 0

Beweis. text
Es sei Rm mit AT 0
Sei x S.
x0

AT 0

b=0

AT x = Ax = b = 0

(AT )j xj = 0

Sei i so, dass

j = 1, . . . , n

Ax = 0

x0

= minn xi

xR

Betrachte

Ax = b

mit

x 0

xi = 0

(AT )i > 0.

(AT )i >0

xi = 0

x S

. Da S und xi Nullvariable

= 0.

Damit sind alle zulssigen x optimal.

max b
Satz 6
Rm
hat eine Lsung Rm und b = 0.
AT ei

Insbesondere: AT () ei AT () 0 (AT ())i > 0

b () = 0
qed

31

10.2 Nichtextremale Variablen

Beispiel:

A=

Falls Ax = b
II I

1 3 4
2 1 3

und

x0

4
6

b=

x1 + 3x2 + 4x3 = 4

II

2x1 + x2 + 3x3 = 6

x1 = 2 + 2x2 + x3 2

x1 , x 2 , x 3 0

Bedingung x1 0 ist stets erfllt, falls x2 , x3 0 und Ax = b

Definition 8. Die Variable xi heit nichtextremal fr Ax = b

(Ax = b)

(xj 0

j i)

kann eliminiert werden.

x 0, falls gilt:
xi 0

Satz 10 (Nichtextremale Variablen). text

Es sei S . Dann gilt:

xj ist nichtextremal

Rm

dj = 1

n
und d R mit di 0
i j

b = fr ein 0

Beweis. text
Es erfllen , d, die geforderten Eigenschften und es sei x Rn
(Ax = b) (xi 0
Dann Ax = b

mit

i j)

d x = AT x = Ax = b =

xj = + di xi 0
ij

Bezeichne A = (a1 an ) . Sei xj nichtextremal.

Ax = b
Betrachte minn xj mit

xR

ij

xi 0
Da S und xj nicht extremal, existiert eine optimale Lsung x des Problems mit
Funktionalwert 0.
Satz 6

duales Problem besitzt eine optimale Lsung

ai 0 i j
max
b

mit

Rm

aj = 1
T
und d = A () erfllen die geforderten Bedingungen.
qed

32

II Innere-Punkt-Verfahren fr lineare Programme

Motivation: Schnelle Lsung von groen linearen Progarmmen.
(Simplex-Verfahren kann dafr sehr langsam sein)
Betrachte:

Primales Progarmm (P )
min c x

Ax = b
mit

x 0
xRn

Duales Programm (D)

max n b
sR

A + s = c
mit

s 0
Rm

Optimalittsbedingungen:

(x, ) lst primale-duale Aufgabe

s R

Ax = b

T
A +s=c

xi s i = 0

x0
s0

(1)

i = 1, . . . , n

Idee des Inneren-Punkt-Verfahren:

Ersetze xi si = 0

i = 1, . . . , n durch xi si =

i = 1, . . . , n (2) fr ein > 0, und lse das

Ax = b

A + s = c
oder
Gleichungssystem: Finde (x, , s) Rn Rm Rn (3)

x
s
=

i
=
1,
.
.
.
,
n

i
i

x > 0 s > 0
approximiere eine Lsung.
Frage: Existiert eine Lsung von (3)?

Definition 1. Falls Lsungen (x , , s ) von (3) fr jedes > 0 existieren, so heit eine Abbildung (x , , s ) Zentraler Pfad.

x1 + x2 = 0
Beispiel: min x1 + x2
mit
x1 ,x2

x1 , x2 0
Optimale Lsung x1 = x2 = 0 xi si = 0 i = 1, 2

(3) hat keine Lsung.

Ziel: Finde hinreichende Bedingung fr die Existenz eines zentralen Pfades.

33

Dazu betrachte Barriereprobleme:

Primales Barriereproblem:
n

min c x log (xi )

xRn

i=1

Ax = b
mit

x > 0

Duales Barriereproblem:
n

max

Rm

sRn

b + log (si )
i=1

(4)

A + s = c
mit

s > 0

(5)

Diese Probleme sind mit (3) verknpft.

Lemma 1. Es sei C Rn konvex, offen, nicht leer und f C R sei konvex und stetig
differenzierbar. Dann gilt fr x C f (x) + f (x)(y x) f (y)

y C.

Beweis. Fr x, y C und (0, 1] ist x = x + (y x) C.

Da f konvex f (x ) (1 )f (x) + f (y)
Mit 0

f (x )f (x)
lim

f (x )f (x)

f (y) f (x)

= f (x)(y x) f (y) f (x)

qed

text
Satz 1. Sei > 0. Die folgenden Aussagen sind quivalent:
(a) (4) besitzt eine optimale Lsung x
(b) (5) besitzt eine optimale Lsung ( , s )
(c) (3) besitzt eine Lsung (x , , s )
Beweis. text
(a) (c)

Sei x optimal fr (4)

Ax = b

x>0

Whle y1 , . . . , yN Basis von ker(A) und bezeichne das Funktional in (4) mit f. Dann
f (x) f (x + tyi ) fr t > 0 hinreichend klein

f (x+tyi )f (x)
lim
t
t0

Analog:

f (x) yi 0

f (x+tyi )f (x)
t

f (x) yi 0
f (x) yi = 0

Da Basiselement yi beliebig f (x) ker(a)

Da ( ker(A)) = range (AT ) Rm AT = f (x). Nun ist f (x)i = c

Whlt man si = xi si > 0 i = 1, . . . , n und si xi =

AT + s = c

Ax = b
Insgesamt
(3)

x
s
=

i
=
1,
.
.
.
,
n

i
i

x > 0 s > 0

34

i = 1, . . . , n.

xi .

 (c) (a)
Falls (x, , s) gegeben wie in (3)

f (x) ( ker(A)) .

AT = f (x)

Nun ist f konvex auf {x Rn x > 0} offen, konvex, nicht leer.

Fr y > 0 mit Ax = b ist y x ker(A).
f (x) + f (x)(y x) f (y)

f (x) f (y)

x lst (4)

=0

(b) (c)

Sei (, s) Lsung von (5), d. h.

Rm
AT + s = c.

n
b
A
analog

Setzt man f (, s) = b + log (si )

f (, s) = range
I
( si )
i=1

n
x R Ax = b und ( si ) = xi x > 0 und xi si = i = 1, . . . , n.
i

(x, , s) lst (3)

(c) (a)

s>0

analog zu (c) (a)

[f ist konvex]
qed

text
Zeige Existenz von Lsungen von (4).
Wir bezeichnen F = {(x, , s) Rn Rm Rn

Ax = b

primale-duale zulssige Menge. F = {(x, , s) F x > 0

0

AT + s = c

x 0 s 0}

s > 0} primale-duale strikt zuls-

sige Menge.
Klar: (3) besitzt eine Lsung (x , , s )

(x , , s ) F 0

Die Umkehrung gilt auch!

Satz 2. Es sei F 0 und > 0. Dann besitzt (4) eine Lsung.
Beweis. text

s) F 0
Sei > 0 und (
x, ,
n

+ s = c
AT

A
x=b

x
>0

s > 0

Sei B (x) = c x log (xi )

i=1

Behauptung: L = {x > 0 Ax = b
Sei x L :

B (x) B (
x)} ist kompakt in Rn+ .

(Ax b) log (xi ) =

B (x) = c x log (xi ) = c b
i=1

i=1
n

i=1

i=1
n

x+b
log (xi ) = c x (c s) x + b
log (xi ) =
= c x AT
log (xi ) B (
= s x + b
x)
i=1

35

= 0
si xi log (xi ) B (
x) b
i=1

Da si > 0

>0

si xi log (xi )

xi 0
xi

und si xi log (xi ) log ( si ) = i

si xi log (xi ) 0 j
ji

xi [li , ri ] fr 0 < li < ri <

L [li , ri ] Rn+ . Da B stetig auf Rn+

i=1

min B (x)

xL

i = 1, . . . , n

es existiert ein Minimierer x L von

x lst min B (x) mit Ax = b.

x>0

qed

text
Satz 3 (Zentraler Pfad). text
Es gelte F 0 . Dann existiert eine Abbildung (x , , s ) auf R+ , sodass (x , , s )
Lsung von (3) ist fr > 0. Die Gren x , s sind eindeutig bestimmt. Falls A vollen Rang
besitzt, so ist eindeutig.
Beweis. Nach Satz 2 existiert fr jedes > 0 ein x welches (4) lst. Satz 1 liefert dann , s ,
sodass (x , , s ) Lsung von (3) ist.
Zeige: B ist strikt konvex, d. h. B (x + (1 )y) < B (x) + (1 )B (y) fr jedes zulssige
y x und (0, 1).
log (xi + (1 )yi ) < log (xi ) (1 ) log (yi )

falls xi yi

(0, 1)

i=1

i=1

i=1

log (xi + (1 )yi ) < [ log (xi )] + (1 ) [ log (yi )]

(0, 1) x, y > 0.

falls x y und

Weiter: Ax = Ay = b A(x + (1 )y) = b falls [0, 1].

Sowie
c (x + (1 )y) = (c x) + (1 )(c y)
Zusammen: x, y > 0 Ax = Ay = b

x y (0, 1)
x + (1 )y zulssig und B (x (1 )y) < B (x) + (1 )B (y)
Ist x ein weiterer Minimierer von B .
x

B ( 12 x

1
)
2 x

Damit x eindeutige Lsung

<

1
1

2 B (x ) + 2 B (x )

(s )i (x )i =

s > 0 eindeutig.

36

= minn c x log (xi )

xR

(s )i =

i=1

(x )i

Ax = b

x > 0

i = 1, . . . , n bestimmt

Ist m n und hat A vollen Rang AT + s = c

AT = c s

c s ist eindeutig bestimmt und AT injektiv eindeutig bestimmt

qed
text

1 Allgemeine Innere-Punkt-Verfahren
Idee: Lse (3) mittels Newton-Verfahren
Allgemein: Lse F (w) = 0
Newton-Verfahren: Linearisiere um wk und lse linearisiertes Problem.
Finde wk+1 , sodass F (wk ) + F (wk )(wk+1 wk ) = 0

wk+1 = wk F (wk )1 F (wk )

wk

falls F (wk )1 existiert.

F (wk ) wk = F (wk )

wk+1 = wk + wk
Um globale Konvergenz zu erhalten, wird eine zustzliche Schrittweite (tk > 0) eingefhrt. Damit
wk+1 = wk + tk wk . Zur Lsung von (3) sei w = (x, , s)

(3)

F (w) = 0

fr x, s > 0.

AT + s c

F (x, , s) = Ax b = 0

XS

1

wobei X = diag(x1 , . . . , xn ) , S = diag(s1 , . . . , sn ) und = .

1
0 AT I

Wir rechenen: F (x, , s) = A 0

(6)
0

S 0 X
Um das Newton-Verfahren anzuwenden wird die Existenz von

Satz 4. Es sei w = (x, , s) Rn Rm Rn

F (w)1 .

x, s > 0.

Die Matrix A besitze vollen Rang. Dann existiert F (w)1 fr jedes > 0.
Beweis. Wir zeigen F (w) ist injektiv.
Sei dazu p = (p1 , p2 , p3 )T Rn Rm Rn und F (w)p = 0.

37

AT p 2
+p3 = 0

Wegen (6) bedeudet das Ap1

=0

1
3

+Xp = 0

Sp
0 = (AT p2 + p3 ) p1 = p2 Ap1 +p3 p1 = p3 p1 = 0
=0

Weiter: p3 p1 = X 1 Sp1 p1 = 0
X 1 S = diag ( xs11 , . . . , xsnn )
p1 = 0

si
xi

X 1 S positiv definit

> 0 i = 1, . . . , n

p3 = X 1 Sp1 = 0

AT p2 = 0

A vollen Rang

p2 = 0
qed

text
Whle nun k und tk in jedem Schritt.
Newton Verfahren:

0 AT I xk AT k sk + c

k
k

(7)
Fk (wk ) wk = Fk (wk ) A
0
0

Ax + b
k
k
k
k
k
S
0 X s S X + k
k
k k k
k
k
k
mit w = (x , , s ) w = (x , , sk ) X k = diag(xk1 , . . . , xkn ) S k = diag(sk1 , . . . , skn )
Angenommen (xk , k , sk ) F 0

Rechte Seite in (7) dann

0

k
k
S X + k

AT k + sk = 0
A xk = 0

AT k+1 + sk+1 c = AT k + sk c + tk (AT k + sk ) = 0

Axk+1 b = Axk b + tk A xk = 0

(xk+1 , k+1 , sk+1 ) F 0 falls tk > 0 so, dass xk+1 , sk+1 > 0.
Algorithmus: Innerer-Punkt-Verfahren
Schritt 0: Whle w0 = (x0 , 0 , s0 ) F 0

(0, 1)

k=0

Schritt 1: Berechen k = n1 (xk sk )

Ist k

ST OP

Schritt 2: Whle k [0, 1]

Lse fr wk = (xk , k , sk )

0 AT

A
0

k
S
0

I xk
0

0
0

k
k k
k
S X + k k
s
X

Schritt 3: Setze wk+1 = wk + tk wk fr tk > 0, sodass xk+1 > 0

Weiter mit Schritt 1 und k k + 1.

38

sk+1 > 0.

(8)

Bemerkungen:
Fr jedes k N gilt: xk > 0
Axk = b

x0

sk > 0

(xk , k , sk ) F 0 .

AT k c

xk sk = xk (c AT k ) = c xk b k 0
Falls xk sk = 0

xk , k optimal.

xk sk misst die primale-duale Lcke. xk sk

xk , k optimal bis auf .

Nach Satz 4 ist (8) lsbar.

k
k

x + tk x > 0
Ist x , s > 0 tk > 0 mit

k
k

s + tk s > 0
wk ist fr alle k wohldefiniert.
k

Algorithmus hat Freiheitsgrade k , tk

k Centering Parameter
k 0 Iterierte nher an Lsung von (1). Allerdings muss tk beliebig klein gewhlt
werden.
k 1 Iterierte ist nher an zentralen Pfad zu k
Im folgenden k , tk so, dass
Abstand zum zentramen Pfad abnimme
k 0
Wir betrachten den Schritt wk wk+1 in Abhngigkeit von tk .
Also: (xk (t), k (t), sk (t)) = (xk , k , sk ) + t(xk , k , sk )
k (t) = n1 xk (t) sk (t)
Lemma 2. Es gilt:
(a) xk sk = 0
(b) k (t) = (t t(1 k ))k
Beweis. text
(8)

(a) xk sk = xk AT k = A xk k = 0
(b) Mit (8) folgt: S k xk + X k sk = X k S k + k k
Aufsummieren:

sk xk + xk sk = xk sk + k k n = (k 1)xk sk
xk xk

xk (t) sk (t) = xk sk + t (sk xk + xk sk ) + t2 xk sk = (1 t(1 k ))xk sk

k (t) = (1 t(1 k ))k

(1k )xk sk

=0

qed

39

Satz 5. Sei (0, 1) beliebig und {(xk , k , sk )} durch das Iterationsverfahren erzeugt, sodass
k+1 (1 n ) k
k und > 0 , > 0.
Angenommen, der Startvektor (x0 , 0 , s0 ) F 0 erfllt 0 =
K mit K = O(n log ()) und k

> 0, so existiert ein Index

k K.

Beweis. text
Fr k beiebig: k+1 (1 n ) k log (k+1 ) log (1 n ) + log (k )
Daher: log (k+1 ) k log (1 n ) + log (0 ) k log (1 n ) log () k n log ()
[Dazu: log (1 + )
fr > 1]
Damit ist k < , falls

k
log () log ()
n

n
(1 + ) log ()

n
(1 + ) log ()

Whlt man K = n (1 + ) log () = O(n log ()), so folgt die Behauptung.

qed
Strategie: Whle k , tk so, dass k+1 (1

)
n k

k N

Ein zulssiges Pfad-Verfolgungs-Verfahren:

N () = {(x, , s) F 0 xi si

fr i = 1, . . . , n } mit = n1 x s und (0, 1).

Ansatz:
Whle zu k die grte Schrittweite tk > 0 mit (xk (t), k (t), sk (t)) N ()
Whle aus [min , max ] mit min > 0 und max < 1.

Algorithmus:
Schritt 0:
Whle (0, 1),

0 < min < max < 1,

Schritt 1: Ist k = n1 xk sk
Schritt 2: Whle
0 AT

Lse A
0

k
S
0

w0 = (x0 , 0 , s0 ) N (),

ST OP

k [min , max ]. wk = (xk , k , sk )

0
I xk

k
=

0
0

k
k k
k
s
S X + k k
X

Schritt 3: Whle tk = max (xk (t), k (t), sk (t)) N ()

t>0

Setze wk+1 = wk + tk wk

Schritt 1

40

(0, 1)

k=0

Zeige Konvergenz Technische Hilfsmittel

Lemma 3. Seien u, v Rn mit u v 0.

Dann gilt: U V 2 2

3
2

u + v22

wobei U = diag(u1 , . . . , un )

Beweis. Klar: + 14 ( )2 = 41 ( + )2

V diag(v1 , . . . , vn ).

, R.

Wir teilen u v 0 auf:

P = {i ui vi 0}
M = {i ui vi < 0}
Dann 0 u v = ui vi + ui vi = ui vi ui vi
iP

iM

iP

iM

[ui vi ]iM 1 [ui vi ]iP 1

Nun ist 2 1 , also gilt:

1

U V 2 = [[ui vi ]iP 22 + [ui vi ]iM 22 ] 2

1
1

[[ui vi ]iP 21 + [ui vi ]iM 21 ] 2 [2 [ui vi ]iP 21 ] 2 = 2 [ui vi ]iP 1

3
1
3
2
2
2 [[ui + vi ]2 ]iP = 2 [ui + vi ]iP 22 = 2 u + v22
4
1

qed
text
Sei X k = diag(xk1 , . . . , xkn ) und S k = diag(sk1 , . . . , skn )

wobei (xk , k , sk )

Lsung von (8). Im Fall (xk , k , sk ) N () haben wir:

Lemma 4. Sei (xk , k , sk ) N ().
Dann gilt:

3
2

X k S k 2 2

(1 + 1 ) nk

Beweis. text
S k xk + X k sk = X k S k + k k
k

1
1
1
1
x1
xk
k
Setze D = diag ( sk , . . . , skn ) = (X k ) 2 (S k ) 2 = (S k ) 2 (X k ) 2 und multipliziere auf beiden
Aus (8) folgt:

Seiten von links mit (S k X k )

1
2

= (X k S k )

(Dk )1 xk + Dk sk = (X k S k )

1
2

1
2

= diag ( 1k k , . . . ,
x1 s 1

1
)
xkn skn

(X k S k + k k )

Setze u = (Dk )1 xk und v = Dk sk

u v = ((Dk )1 xk ) (Dk sk ) = xk sk = 0

nach Lemma 2(a).

41

Nun X k S k = diag ([xki ski ]i ) = diag ([((Dk )1 xk )i (Dk sk )i ]i ).

3
2

Lemma 3

X k S k 2 = U V 2 2

3
2

=2

(X k S k )
=2

3
2

1
2

(Dk )1 xk + Dk sk 2 =
3
2

(X k S k + k k ) = 2
2

1
2
2
[ X k S k 2 2 ((X k S k )

(X k S k )

1
2

+ k k (X k S k ) 2 =
2

1
2

1
2

) (k k (X k S k ) ) +k2 2k (X k S k ) ]
2

2k k

xk sk

n
k1 k
i=1 xi si

Wir haben:
xk sk = nk

=n

xki ski k
k (0, 1)
3
2

X k S k 2 2

[nk 2k k n + k2 2k n 1 ] = 2

3
2

(1 2k +

k2
) nk

3
2

(1 + 1 ) nk
qed

text
Nchster Schritt: Abschtzung an tk
Lemma 5. Sei (xk , k , sk ) N ().
(xk (t), k (t), sk (t)) N ()

Dann gilt:

t [0, tk ]

wobei tk = 2 2 nk 1
1+

Beweis. text
Aus (8) folgt:
Lemma 4

xki

ski xki + xki ski = xki ski + k k

ski

(x , , s ) N ()
k

3
2

X S 2 2

xki ski

(1 +

i = 1, . . . , n
1
) nk

i = 1, . . . , n

i = 1, . . . , n

xki (t) ski (t) = (xki + t xki )(ski + t ski ) =

= xki ski + t(ski xki + xki ski ) + t2 xki ski (1 t)xki ski + tk k t2 xki ski
3
2
1
(1 t)k + tk k t2 2 (1 + ) nk

Lemma 2

k (t) = (1 t(1 k ))k

Also xki (t)ski (t) k (t) , falls

3
2

(1 t)k + tk k t2 2

(1 + 1 ) nk (1 t(1 k ))k

Forme quivalent um:

(1 )tk k t2 2

3
2

1
(1 + ) nk

t (1 )k 2

42

3
2

3
1
k 1
2
=2
= tk
n1+
n 1+

Zeige also (xk (t), k (t), sk (t)) F 0

T k
k

A (t) + s (t) = c
Klar:
Weiters: tk 2 2 (1 )

Ax (t) = b

Damit: xki (t) ski (t) (1 t(1 k ))k > 0

22
4

<1

xk (t) > 0

falls t tk

sk (t) > 0
qed

text
Dies ermglicht die Anwendung von Satz 5
Satz 6. text
Fr Folge {(xk , k , sk )} gilt:
Beweis. text

k+1 (1 n ) k

k N und > 0 unabhngig von k.

tk tk = 2 2 nk 1
1+

Lemma 5

k+1 = k (tk ) = (1 tk (1 k ))k (1 tk (1 k ))k = (1 2 2 nk 1

1+ (1 k )) k
Auf [min , max ] nimmt (1 ) das Minimum an in min oder max
k (1 k ) min {min (1 min ) , max (1 max )} > 0
k N
3

{min (1 min ) , max (1 max )}

Mit = 2 2 1
1+ min

folgt die Behauptung

qed

text

Satz 7. Fr {(xk , k , sk )} mit (x0 , 0 , s0 ) so, dass 0

K N

K = O(n log ())

> 0 gilt:

k K

Beweis. Satz 5 und Satz 6

qed

text
Bemerkungen:
Da jeder Newton-Schritt polynomiale Komplexitt in n hat, besitzt das Verfahren polynomiale Komplexitt
(um auf Toleranz > 0 zu kommen)
Man kann andere Umgebungen vom zentralen Pfad benutze.
z. B N2 () = {(x, , s) F 0 XS 2 } fr (0, 1)
Analog: Whle grte Schrittweite tk > 0 mit (xk (t), k (t), sk (t)) N2 ()
Wieder gilt, falls tk tk t und t > 0 unabhngig von k mit O(n ) fr > 0, dann
folgt Konvergenz und polynomiale Komplexitt. (Satz 5)

43

 Weitere Mglichkeit: unzlssige Verfahren

Idee: AT 0 + s0 = c

Ax0 = b

ist in einigen Fllen schwer zu lsen

erlaube Iterierte, die diese Bedingung verletzen (unzulssige Lsungen),

d. h. Axk b = rbk
AT k + sk c = rck wobei (rbk , rck ) klein.
0 AT I xk

rck

inexakte Nexton-Schritte: A
rbk
0
0

S k 0 X k sk S k X k + k k
Die Menge N () wird dann erweitert.

(rb0 , rc0 )

N (, ) = (x, , s) (rb , rc )
,

fr 1

x>0,

s>0,

xi si

(0, 1)

Dann: Auch Konvergenz Analysis ist aufwendiger

III Unrestringierte nichtlineare Programmierung

1 Allgemiene Theorie

min f (x)
Aufgabe: (1) xX

f X R

f r X R
n
Falls X = R
unrestringierte Aufgabe. Anderenfalls: restringierte Aufgabe.
(triviale) Bemerkung:

max f (x)
xX

min f (x)
xX

Beispiel 1: 1 Parameterschtzung
n

min 12 y(tj ) yi 2

xR2 j=1

x = (c, k)

y + cy + ky = 0

mit

y(0) = y0
y (0) = 0

n+1

0 < t1 < . . . < tn

yR
y(t1 )

Lsungtheorie fr ODE, (c, k) wohldefiniert.

y(tn )
Aufgabe hat die Form (1) und ist unrestringiert.

44

Beispiel 2: 1 X = X1 X2 X3
X1 = {x Rn ci (x) = 0
i I1 }
X2 = {x R

X3 = {X R

ci (x) 0
xi Z

ci Rn R

i I2 }

i I1 I2

i I1 }

stetige Optimierung
X2 Ungleichheitsrestriktion

}
X3 (semi-)diskrete Menge diskrete Optimierung
X1 Gleichheitsrestriktion

Definition 1. Sei (1) gegeben und x X, dann heit

(i) x ein globaler Minimierer, falls f (x ) f (x)

x X.

x ein strikter globaler Minimierer, falls f (x ) < f (x)

x X {x }.

(ii) x ein lokaler Minimierer, falls es eine Umgebung U X von x gibt,

sodass f (x ) f (x)

x U.

x ein strikter lokaler Minimierer, falls es eine Umgebung U X von x gibt,

sodass f (x ) < f (x)

x U {x }.

Bemerkung: Analog definiert man Maximierer.

Bezeichne:

f
x
(x)
1

f (x) =

f
x

(x)
n

x2 (x)
1

2 f (x) =

f
x x (x)
n
1

2f
x1 xn (x)

2f

(x)
x2

Definition 2. Sei X Rn offen, f C 1 (X, R).

Ein x X heit stationrer Punkt, falls f (x ) = 0.

2 Optimalittsbedingungen
Satz 1. Fr X Rn offen, f C 1 (X, R) gilt:
Ist x lokaler Minimierer von f , so gilt f (x ) = 0.
Beweis. text
Fr d Rn existiert t0 > 0, sodass x + td U fr 0 < t < t0 , wobei U X Umgebung von x ,
sodass f (x ) f (x)
x U.
1

Damit 0 < t [f (x + td) f (x )] fr 0 < t < t0

t0

Durch ersezten von d durch d folgt f (x ) d = 0

0 f (x ) d.
d Rn

f (x ) = 0
qed

45

text
Bemerkungen:
(i) Satz 1 liefert notwendige Bedingung.
(ii) Die Bedingung ist nicht hinreichend.
Fr X = R

f (x) = x2 gilt f (x) = 0, aber f besitzt kein Minimum.

Satz 2. Sei X Rn offen, f C 2 (X, R) und x ein lokaler Minimierer.

Dann gilt:

f (x ) = 0

und

2 f (x ) 0

Bemerkung:
2 f (x ) 0

2 f (x ) ist positiv semidefinit, d. h. 2 f (x ) y y 0

y Rn .

Beweis. Whle d Rn .
Fr t R in einer Umgebung von 0 gilt: g(t) = f (x + td) erfllt mit Taylorentwicklung und
Restglied in Integralform:
t

0 g(t) g(0) = g (0)t + g (s)(t s) ds

=0

g(t)g(0)
t2

1
t2

g (s)(t s) ds

t0

0 g (0)

Aber: g (0) = 2 f (x ) d d

2 f (x ) 0, da d Rn beliebig.
qed

text
Beispiel: f (x) = x21 x42
f (x) =

2x1
4x32

2 f (x) =

f (0) = 0

2
0
0 12x22

2 f (0) =

2 0
0
0 0

x = 0 ist jedoch kein Minimum. In Grafik x1 (1/2 , 1/2)

46

x2 (3/4 , 3/4).

Also auch wieder notwendige Bedingung.

Satz 3. Sei X Rn offen, f C 2 (X, R).

(a)
f (x ) = 0

x ist strikter lokaler Minimierer von f.

2

(b)
f (x ) > 0

Bemerkung:
2 f (x ) > 0

2 f (x ) ist positiv definit, d. h. 2 f (x ) y y > 0

y Rn {0}.

Beweis. text
min (2 f (x ) y y) = > 0

Sei S = {x Rn x = 1} kompakt in Rn

f (x ) y y = y ( f (x )
2

y
y

yS

y
y )

y2

y 0

Taylorentwicklung:
f (x + d) = f (x ) + f (x ) d + 12 2 f ((d)) d d

mit (d) = x + d fr (0, 1).

1
1
f (x + d) = f (x ) + 2 f (x ) d d + [2 f ((d)) 2 f (x )] d d
2
2
d2 1 2
f (x ) +
f ((d)) 2 f (x ) d2
2
2
x 2 f (x ) ist stetig
f (x + d) f (x ) +

d2 > f (x )

2 f ((d)) 2 f (x ) <

fr d 0 und d .

x ist strikter lokaler Minimierer.

qed
text
Definition 3 (Wiederholung Konvexitt). text
(i) X Rn ist konvex, falls x, y X

[0, 1]

x + (1 )y X

(ii) Sei f X R mit X konvex. Dann ist f strikt konvex, falls

f (x + (1 )y) f (x) + (1 ) f (y)
<

x, y X

[0, 1]

bzw.

x, y X x y

(0, 1)

(iii) f ist gleichmig konvex, falls > 0, sodass

f (x + (1 )y) + (1 ) x y2 f (x) + (1 ) f (y)
x, y X

[0, 1]

47

Bemerkung: Fr X = Rn

X R
f

f (x) = 12 Ax x + b x + c

A Rnn symmetrisch
ist konvex

b Rn

A0

cR

Auerdem: f strikt konvex

f gleichmig konvex

A>0

Satz 4. Sei X Rn offen, konvex und sei f C 1 (X, R). Dann gilt:
(i) f ist konvex

(ii) f ist strikt konvex

f (x) f (y) + f (y) (x y)

x, y X

f (x) > f (y) + f (y) (x y)

(iii) f ist gleichmig konvex

x, y X

xy

> 0 f (x) f (y)+f (y)(xy)+ x y2

x, y X

Beweis. text
(i) Siehe II Lemma 1
Es gelte die Ungleichung
Fr x, y X

[0, 1]

z = x + (1 )y

folgt:

zX
f (x) f (z) + f (z) (x z)
f (y) f (z) + f (z) (y z)
f (x) + (1 )f (y) f (z) + f (z) (x + (1 )y z) = f (z) = f (x + (1 )y)
=0

(ii) Analog zu (i)

(i)

f (y) (x y) f (x) f (y)

Ist x y, so setze z =

1
2 (x + y)

x, y X

x = 2z y

f (y) (x y) = 2f (y) (z y) 2[f (z) f (y)]

Da f strikt konvex f (z) < 12 [f (x) + f (y)] 2f (z) < f (x) + f (y)
f (y) (x y) 2f (z) 2f (y) < f (x) f (y)
(iii) Analog zu (i)
qed
text
Satz 5. Sei X Rn offen, konvex und f C 2 (X, R)
(i) f ist konvex

(ii) f ist strikt konvex

2 f (x) 0

f (x) > 0

(iii) f ist gleichmig konvex

Bemerkung: A B

x X

x X

> 0 2 f (x) I

AB 0

2 f (x) I

48

x X

2 f (x)y y y2

Beweis. text
(i) Taylorentwicklung
f (y) = f (x) + f (x) (y x) + 21 2 f (x)(y x) (y x) + r(y x)
Setze y = x + td

dR

t > 0 hinreichend klein

t2 2
2 f (x)d d + r(td)
t0
2

= f (y) f (x) + f (x) (y x) 0

f (x)d d 0

wobei

d Rn

Es gilt f (x) 0

x X

2 f (x)d d +

2 f (x) 0

r(yx) yx

yx2
2r(td)
t2

x X

x X. Dann gilt:

f (y) = f (x) + f (x) (y x)+

1

+ (1 ) 2 f (x + (y x))(y x) (y x) d f (x) + f (x) (y x)

0

Satz 4(i)

f konvex

(ii) Analog zu (i)

(iii) Analog zu (i)
2
t2 2
2
2 f (x)d d t d
t0
2

+ r(td) = f (y) f (x) (y x) y x2 0

f (x)d d 2 d2

unabhngig von x

Wieder analog zu (i)

1

2
2
(1 ) f (x + (x y))(y x) (y x) d (1 ) d y x =
0

Satz 4 liefert die Behauptung.

y x2

qed
text
Bemerkung: In (ii) gilt die Umkehrung nicht.
z. B. f R R
Zeige dazu

f (x) = x4

f (0) = 0 aber f ist strikt konvex.

y 4 > x4 + 4x3 (y x)

x, y R

xy

Fr diese x, y ist quivalent: y 4 x4 = (x2 y 2 )(y 2 + x2 ) = (y x)(y + x)(y 2 + x2 ) > 4x3 (y x)

o. B. d. A. y > x

d. h.y = x + r

r > 0. Damit sind quivalent:

(2x + r)(2x2 + 2xr + r2 ) > 4x3

6x2 r + 4xr2 + r3 > 0

4x3 + 4x2 r + 2xr2 + 2x2 r + 2xr2 + r3 > 4x3

6x2 + 4xr + r2 > 0

Da r > 0 ist Letztes immer erfllt f strikt konvex.

49

2x2 + (2x + r)2 > 0

Lemma 1. Sei f C 1 (Rn , R) und gleichmig konvex auf X konvex und nichtleer.
Fr x0 X bezeichne

L(x0 ) = {x X f (x) f (x0 )} Niveaumenge.

Dann gilt L(x0 ) ist beschrnkt.

Beweis. L(x0 ) . Sei x L(x0 ).
Da f gleichmig konvex ist, gilt fr

1
0
2 (x + x )

f ( 12 (x + x0 )) + 4 x x0 21 (f (x) + f (x0 ))

fr > 0 unabhngig von x und x0 .

1
1
2
x x0 (f (x) f (x0 )) [f ( (x x0 )) f (x0 )]
4
2
2
1
1
1
0
0
[f ( (x x )) f (x )] f (x0 ) (x x0 ) f (x0 ) x x0
2
2
2

x x0

f (x0 )

x L(x0 )

L(x0 ) beschrnkt
qed

text
Satz 6. Es sei f C 1 (Rn , R) , X Rn konvex und nichtleer.
Betrachte (1),

d. h. min f (x).
xX

Fr die Lsungsmenge L = {x X f (x ) f (x)

x X } gilt:

(i) Ist f konvex, so ist L konvex.

(ii) Ist f strikt konvex, so ist L einelementig oder leer.
(iii) Ist f gleichmig konvex auf X und X abgeschlossen, so besitzt L genau ein Element.
Beweis. text
(i) Es seien x, y L und [0, 1]. Dann f (x) f (y) f (y) f (x)
z=x+(1)y

f (z) f (x) + (1 )f (y) = f (x)

(ii) Angenommen x, y L und x y.

Dann f ( 21 (x + y)) < 21 f (x) + 21 f (y) = f (x)

f (x) = f (y)

zL

x / L

(iii) Sei x X, dann ist L(x ) X beschrnkt und L(x0 ) abgeschlossen

0

L(x0 ) X ist kompakt. f stetig auf L(x0 ) X

Nach (ii)

L .

L besitzt genau ein Element.

qed

text
Bemerkung:
1. (1) muss nicht notwendigerweise eine Lsung haben, auch wenn das Infimum existiert.

R R
inf f (x) = 0 aber es existiert kein Minimierer, obwohl f strikt
Bsp: f

x
xR

konvex ist.

50

2. Fr Satz 6(iii) ist X abgeschlossen essentiell.

X R
inf f (x) = 0 aber es gibt keinen Minimierer, obwohl
Bsp: X = (0, 1) f

2
xX

f gleichmig konvex ist.

Lemma 2. Sei f C 1 (Rn , R) , x0 Rn und f gleichmig konvex auf L(x0 ).

Sei x eindeutiges Minimum von f

> 0 x x f (x) f (x )

x L(x0 )

Beweis. text
Nach Satz 4(iii) gilt:
f gleichmig konvex
Hier y = x Minimum

> 0 f (x) f (y) + f (y))(x y) + x y2

f (x ) = 0

x, y

f (x) f (x ) + x x 2
qed

text
Satz 7. text
Sei f C 1 (Rn , R) konvex und sei f (x ) = 0

x ist globales Minimum von f auf Rn .

Beweis. text
Nach Satz 4(i) gilt: f konvex
f (y) f (x )

y Rn

f (y) f (x ) + f (x ) (y x )

x globales Minimum

y Rn

=0

qed

3 Abstiegsverfahren und Schrittweitensteuerung

Definition 1. Sei f Rn R

und x Rn .

d Rn heit Abstiegsrichtung von f in x, falls > 0 f (x + d) f (x)

(0, ]

Bemerkungen:
(1) Falls f differenzierbar in x und f (x) d < 0 , dann ist d Abstiegsrichtung.
() = f (x + d) = (0) + (0) + r()

wobei

r() 0

() = f (x) + f (x) d + r()

()(0)

>0

= f (x) d +

r()

<0

fr hinreichend kleine

<0

f (x + d) = f (x) + kleine negative Zahl fr hinreichend kleine

51

(2) f (x) d < 0

(f (x), d) > 90

(3) Wenn f (x) d = 0 , dann must d nicht unbedingt keine Abstiegsrichtung sein.
(4) Kandidaten fr Abstiegsrichtungen:
d = f (x)

f (x) d = f (x) 2 < 0

d = M f (x)

M = MT > 0

(gradientenhnliche Richtungen)

Algorithmus 1. text
Input: f Rn R

x0 Rn

begin k = 1
textwhile Konvergenzkriterium nicht erfllt
texttextbegin
bestimme Abstiegsrichtung dk in xk
texttexttext
bestimme Schrittweite , sodass f (xk + k dk ) < f (xk )
texttextSetze xk+1 = xk + k dk
texttextk = k + 1
textend

Bemerkung:

f (x) =

1
2

Landweber-Verfahren:

Ax y2
x0 = 0

f (x) = A (Ax y)
xk+1 = xk A (Ax y)

konvergiert, falls A2 < 1.

Satz 1. Sei f C 1 (Rn , R) {xk } durch Algorithmus 1 erzeugt.

Seien 1 , 2 > 0 so, dass:
(i) Winkelbedingung:

f (xk ) dk > 1 f (xk ) dk

(ii) Abstiegsbedingung:

f (xk + k dk ) <

f (x )d 2
f (xk ) 2 ( dkk )

Sei x ein Hufungspunkt von xk , dann ist x stationrer Punkt von f.

Beweis. text

f (x )d 2

f (xk+1 ) = f (xk + k dk ) < f (xk ) 2 ( dkk ) < f (xk ) 2 21 f (xk )2

{f (xk )} ist monoton fallend xkl x f (xkl ) f (x ) f (xk ) f (x )
f (xk+1 ) f (xk ) 0

f (xk ) 0

f (x ) = 0

qed
text

52

3.1 Schrittweitenstrategie
Am liebsten htte man k so, dass f (xk + dk ) = min f (xk + dk ) doch das geht (meistens)
>0

nicht.
Armijo-Regel
d = M f (x)

MT = M > 0
(A)

(0, 1)
f (x + d) < f (x) + f (x) d

Einschrnkung der Schrittweite. Schrittweite nicht zu lang!

> 0 ist gesichert, falls f Lipschit-stetig ist.
1

f (x + d) = f (x) + f (x) (d) + [f (x + sd) f (x)] (d) ds

0

Lsd

L
L
f (x) + f (x) d + d2 2 = f (x) + f (x) d (1 ) f (x) d + d2 2
2
2
0

Fr einen hinreichend kleinen Bereich ist abgesichert, dass Armijo gilt!

Algorithmus 2. text
Input: Abstiegsrichtung d
begin l = 0

0<<1

0 = 1

textwhile (A) nicht erfllt

texttextbegin
choose l+1 [l , l ]
texttexttexte.g. l+1 = l+1
==
l =l+1
texttextSetze k = l
textend

Lemma 1. Sei f C 1 (Rn , R) mit f Lipschitz-stetig mit Konstante L.

Weiters seien (0, 1) , x Rn , M T = M > 0 und min (M 1 )
Falls f (x) 0
mit (M 1 )) =

(A) erfllt fr alle mit:

0<<

max (M 1 ) gegeben.

2min (M 1 )(1)
L(M 1

max
min

Beweis. text
()

f (x + d) f (x) + f (x) d +
i
i
i
max z z M z min z

53

L 2
d2
2

i = 1, 2

d2 = M f (x)2 = f (x) [M 2 f (x)] 2

min f (x)

max
max
f (x) [M f (x)] = 2 f (x) d = (M 1 )1
min f (x) d
2
min
min

()

L
f (x + d) f (x) + (1 (M 1 )1
min 2 ) f (x)
!

Dies gilt genau dann, wenn:

L
1 (M 1 1
min ) 2

qed
text
Lemma 2. Sei f C 1 (Rn , R) mit f Lipschitz-stetig mit Konstante L.
Sei {xk } erzeugt durch Algorithmus 2 und Algorithmus 1 mit:
MkT = Mk > 0

0 < min (Mk1 ) max (Mk1 ) <

k =

2(1)
L

mit =

Bemerkung:
Armijo (mit 0 = 1 und mit 0 = k1 ) bricht nach einer endlichen Anzahl von Schritten ab.

Satz 2. Sei f C 1 (Rn , mR) , {Mk } wei in Lemma 2 und {xk } erzeugt durch Algorithmus 1
mit Schrittweiten aus Algorithmus 2.
{f (xk )} nach unten unbeschrnkt oder

lim f (xk ) = 0.

Somit ist jeder Hufungspunkt ein stationrer Punkt. Insbesondere {f (xk )} beschrnkt und
x = lim f (xkl )
l

f (x ) = 0.

Beweis. Nach Konstruktion ist {f (xk )} monoton fallend.

Falls {f (xk )} nach unten beschrnkt ist, so existiert f mit
lim [f (xk+1 ) f (xk )] = 0
k

f (xk+1 ) f (xk ) k f (xk ) [Mk f (xk )]

0

lim f (xk ) = f

f (xk )2 0

qed

text
Bemerkungen:
1.) Es wurde nicht gesagt xk x . Insbesondere ist nicht gesagt, dass der erwhnte Hufungspunkt eindeutig ist.
2.) Armijo kann zu konservativ sein.

54

Goldstein-Regel
(G)

f (x + d) f (x) + f (x) d

0<

1
<1
2

Armijo

Goldstein

nicht zu gro

nicht zu klein

aus Armijo

Intervallschachtelung:
10 = 0

20 =

Wir haben
l

[a01 ,

l=0
2l ]

Falls l Armijo erfllt

Falls

1l+1 = 1l

l Goldstein nicht erfllt

2l+1 = l

1l+1 = l

(Reduktion des Intervalls)

2l+1 = 2l

(Vergrerung des Inter-

valls)
Heuristik:
l+1 [1l+1 + l+1 , 2l+1 l+1 ]
Falls 2l+1 =

mit 0 < << 1 und l+1 = 2l+1 1l+1

mit > 1 und > 0

l+1 > max{1l , }

3.2 Armijo und polynomiale Modelle

f (x + d) als Funktion von lokal eine Parabel
() = f (x + d)
(0) = f (x)
(l ) = f (x + l d)
(0) = f (x) d < 0

Quadratisches Modell:

q() = a + b + c2

q(0) = (0)
q() = (0) + (0) +

q (0) = (0)

q(l ) = (l )

1
((l ) (0) (0)l ) 2
(l )2

wird nur erstellt falls (A) verletzt ist.

(l ) (0) (0)l > (l ) (0) (0)l > 0.

55

Der Trick ist, die Modellfunktion zu minimieren

(0) +

1
!
((l ) (0) (0)l ) 2 = 0
(l )2

text

Verfeinerung von Armijo: l+1 = min

min =

(0)(l )2
>0
((l ) (0) (0)l )2

f alls min < l

f alls l < min < l
f alls l < min

Kubische Modelle:
(0)

(l )

(0)

(l )

(0)

(l )

(0)

(l1 )

Wolfe-Powel-Regel
[, 1)
(0, 12 )

f (x) d < 0

f (x + d) f (x) + f (x) d
Bestimme > 0 so,dass (W P )

f (x + d) d > f (x) d

Satz 3. Sei f C 1 (Rn , R) , (0, 12 ) , [, 1) , x0 Rn , x L(x0 ) , f (x) d < 0.

SW P (x, d) = { > 0 erfllt (W P )} Dann gilt:
(a) f nach unten beschrnkt

SW P (x, d)

(b) f Lipschitz-stetig auf L(x0 )

> 0 f (x + d) f (x) (

SW P (x, d)

f (x)d 2
d )

Beweis. text
(a)

() ()
z. z. > 0

() > (0)

() = f (x) + f (x) d
() = f (x + d)

Wir wissen: (0) = (0) und (0) = f (x) d f (x) d = (0)

= min{ > 0 () = ()} > 0 existiert, da

zung nach unten beschrnkt. ( ) ( )

lim () = und nach Vorausset-

Fall 1: ( ) < 0
( ) ( ) = f (x)d (0) und ( ) = ( )
Fall 2: ( ) 0
(0) < 0

(0, ) ( ) = 0

56

SW P (x, d)

0 = ( ) (0)

( ) ( )

(b) Sei SW P (x, d)

a SW P (x, d)

f (x + d) f (x)

f (x + d) d f (x) d
( 1) f (x) d (f (x + d) f (x)) d
( 1) f (x) d f (x + d) f (x) d L d2
L > 0 Abschtzung an die Lipschitz-Konstante

(1)
Ld2

f (x) d

f (x)d
Ld2
(1)
f (x)
Ld2

(1 )

f (x + d) f (x) + f (x) d

(f (x) d)

(1)
= L >0

f (x + d) f (x) (

f (x)d 2
d )

qed
text
Folgendes Lemma ist hinreichend fr die Schrittweitenbestimmung.
Lemma 3. Sei < , f Rn R stetig differenzierbar.
Bezeichne fr d Rn Abstiegsrichtung () = f (x + d). Sei (0) < 0.

R R
und 0 a < b gelte: (a) 0
Fr

()
=
()

(0)

(0)

Dann gilt:
[a, b) () < 0

(b) 0

(a) < 0.

() = 0

I [a, b) I und () 0 und () (0)

Beweis. text
Aus (a) 0

(a) < 0

Denn falls () 0

(b) 0 folt: (a, b) und > 0 () .

[a, b]

(b) = (a) + ( ) d < 0

a

<0

Sei = min{ (a, b) () }

mit = min{ (a, )
() = 0} () < 0
(a, )

=0
Anderenfalls: () 0 und (a, ) () < 0 (a, ) ()
0 = () = () (0) = f (x+d)df (x)d = f (x+d)df (x)d+() (0)
f (x + d) d > f (x + d) d ( ) (0) = f (x) d

57

Sei o. B. d. A. (0 , 12 ( ) (0)). Dann existiert r > 0, sodass [ r , + r ] gilt:

() = f (x + d) d > f (x + d) d
1
3
1
( ( )) f (x) d = ( ) f (x) d f (x) d = (0)
2
2
2
Da () < 0

r (0, r ) () 0

Insgesmat: () 0

[ r , + r]

() (0)

[ r , + r] = I
qed

text

Algorithmus 3 (Wolfe-Powel Schrittweite). text

Gegeben: Abstiegsrichtung d Rn
Whle: (0) > 0 , > 0 beliebig
i0
while ((i) ) < 0
textif ((i) ) (0)
texttextreturn (i)
textelse
texttext(i+1) (i)

ii+1

end
a0

b (i)

Whle (0, 21 )
j0
(0)

1 a

(0)

(j)

2 b

(0)

(j)

(0)

(0) 2 1

(j) [1 + (j) , 2 (j) ]

while ((j) ) 0 ((j) ) < (0)

textif ((j) ) 0
(j+1)

texttext1

(j)

(j+1)

(j)

(j+1) 2

(j+1)

(j)

(j+1) 2

(j+1)

(j+1)

(j+1)

texttextj j + 1
textelse
(j+1)

texttext1

(j)

texttextj j + 1
textend
(j)

(j)

(j) [1 + (j) , 2 (j) ]

end
return (j)

58

(j+1)

 Ausgabe: SW P (x, d)

Bemerkung:
Fr k 2

(Iterationsindex) whle (0) = k1

Fr k = 1 Falls f nach unten beschrnkt durch f . Die Bedingung () 0 liefert:

0 () = () (0) f (x) d f (0) (0)

f (0)
(0)

= . Damit (0) (0, ].

Satz 4. Sei f C 1 (Rn , R) , f (x) f

x Rn und seien 0 < <

1
2

< < 1.

Dann bricht Algorithmus 3 nach endlich vielen Schritten ab und SW P (x, d).
Beweisskizze:. text
Klar: Falls Algorithmus 3 terminiert SW P (x, d)
1. whileSchleife
Nach i Schritten ((i) ) = ((i) ) (0) (i) (0) < 0
Da f f (x)
Da > 1

x Rn

f ((i) < (0) + i (0) (0)

i ist beschrnkt

2. whileSchleife
(j)

(j)

Intervalle [1 , 2 ] erfllen:

(0) ().

Falls Schleife unendlich:

(j+1)

0 2

(j+1)

(j)

i <

1. whileSchleife terminiert
(j)

(j)

f (0)
(0) (0)

(j)

(j)

(1 ) 0 , (2 ) und (1 ) < 0. (1 ) <

(j)

(0)

(0)

(j)

fr j und ein
Damit 1(j)

2
(j)
(j)
(j) (1 , 2 ) mit (
Nach Lemma 3 existiert
(j) ) 0 und (
(j) ) = 0
(j)

(1 )(2 1 ) (1 )j+1 (2 1 )

( ) 0 , ( ) = ( ) (0) = 0

Aber mit () (0) ( ) = (0) > (0)

Abbruch nach endlich vielen

Schritten.
qed
text

4 Konvergenzgeschwindigkeit
Durchgehende Voraussetzung:

lim xk = x

x Rn

59

4.1 Q- und R-Konvergenz

Definition 1 (Q-Konvergenz). text
(a) Sei p [1, ). Dann heit

x
x

lim sup xk+1

f alls xk x f r k k0

x
k

k
Qp ({xk }) =
0
f alls xk = x f r k k0

sonst

Quotientenfaktor oder Q-Faktor.

(b) Der Wert inf {p [1, ) Qp ({xk }) = 0} heit Q-Konvergenzordnung.

Bemerkung:
(1) QFaktor hngt von der Norm ab, die QOrdnung jedoch nicht.

f r p [1, p0 )
0
(2) Es existiert stets ein p0 [1, ) mit Qp ({xk }) =

f r p (p0 , )

(3) Bezeichnungen:
Q1 ({xk }) = 0

Qsuperlineare Konvergenz

Q1 ({xk }) < 1

Qlineare Konvergenz

Q2 ({xk }) = 0

Qsuperquadratische Konvergenz

0 < Q2 ({xk }) <

Qquadratische Konvergenz

Beispiel:
xk = ak

a (0, 1). Hier lim ak = 0.

xk+1 x
xk x

ak+1
ak

xk+1 x
xk x p

p>1

=a

lim sup
k

ak+1
apk

xk+1 x
xk x

= ak(1p)+1

=a

Qlineare Konvergenz

QOrdnung ist 1
k

xk = a2
p=2

a (0, 1)

xk+1 x
xk x 2

a2k+1
a2k 2

=1

Q2 ({xk }) = 1

QKonvergenzordnung

Fragestellung: Abbruckkriterium: Wann gilt xk x

direkte Abfrage unrealistisch

Ziel: Abschtzung von xk x durch gegebene Daten

Satz 1. text
(a) Es gilt: 1

xk+1 x
xk x

xk+1 xk
xk x

xk x

(b) Falls xk x Qsuperlinear und xk x fr k k0 , so gilt: lim

60

xk+1 xk
xk x

=1

Beweis. text
Es gilt: x xk x xk+1 xk xk+1 xk x + x xk+1
Falls xk x

xk+1 x
xk x

xk+1 xk
xk x

(a)

1+

xk+1 x
xk x

xk+1 x k

xk x

Falls xk x Qsuperlinear konvergent

lim

xk+1 xk
xk x

=1
qed

text
Bemerkung:
(b)

> 0 k0

k k0 (1 )

xk+1 xk
(1 + )
xk x

(1 ) xk x xk xk+1 (1 + ) xk x

Also Abbruchkriterium xk+1 xk sinnvoll, falls {xk } Qsuperliear konvergent und k gro
genug.

Definition 2 (R-Konvergenz). text

(a) Sei p [1, ). Dann heit
1

lim
sup
x

p=1
k

Rp ({xk }) = k
1

p>1
lim sup xk x pk

k
Wurzelfaktor oder RFaktor.
(b) Der Wert inf {p [1, ) Rp ({xk }) = 1} heit RKonvergenzordnung.

Bemerkung: Fr fixes p ist lim sup xk x pk < 1 nur, falls xk x 0 in hinreichender

k

Geschwindigkeit.
Beispiel:
xk = cak

a (0, 1) c R {0}
1

p=1

xk x k = c k a

p>1

xk x pk = c pk a pk

R1 ({xk }) = a

RKonvergenzordnung ist 1
k

xk = a2

1
k

p=2

xk x 2k = (a2 ) 2 = a

p>2

xk x pk = (a2 ) p = a

1
k

R2 ({xk }) = a < 1
k

( p2 )

61

 RKonvergenzordnung ist 2

Bemerkung:
(1) RFaktor ist unabhngig von der Norm.
Seien a , b Normen auf Rn . 0 < c1 < c2 c1 xb xa c2 xb

x Rn .

Sei {k } eine Nullfolge positiver Zahlen. Dann gilt:

lim sup xk x ak lim sup ck xk x b k = ( lim c2k ) lim sup xk x b k

k
=1

Analog gilt: lim sup xk x b k lim sup xk x ak

k

RFaktoren zu a und b stimmen berein.

(2)

f r p [1, p0 )
0
(3) Es existiert stets ein p0 [1, ) mit Rp ({xk }) =

f r p (p0 , )

1
(4) QOrdnung von {xk } ROrdnung von {xk } und R1 ({xk }) Q1 ({xk }).

Ziel im Folgenden: Charakterisiere Konvergenzordnung fr Folgen die f minimieren.

Vormbemerkung:
Falls xk+1 x = o( xk x )

{xk } Qsuperlinear konvergent

Falls xk+1 x = O( xk x 2 )

{xk } Qquadratisch oder Qsuperquadratisch

konvergent.

Lemma 1. text
(a) Falls f C 2 (Rn , R), so gilt:

f (xk ) f (x ) 2 f (xk )(xk x ) = o( xk x )

(b) Falls darberhinaus 2 f lokal Lipschitz-stetig mit Konstante L ist, so gilt:

f (xk ) f (x ) 2 f (xk )(xk x ) = O( xk x 2 )

62

Beweis. text
(a) Es gilt
f (xk ) f (x ) 2 f (xk )(xk x )
f (xk ) f (x ) 2 f (x )(xk x ) + 2 f (xk ) 2 f (x ) xk x
Wegen f C 2 (Rn , R)

f C 1 (Rn , R)

T aylorEntwicklung

f (xk ) f (x ) 2 f (x )(xk x ) = o( xk x )

Weiter 2 f (xk ) 2 f (x )

2 f (xk ) 2 f (x ) xk x = o( xk x )

(b) Wir haben f (xk ) f (x ) = 2 f (x + )(xk x ))(xk x ) d

0

f (xk ) f (x ) 2 f (xk )(xk x ) =

1

= [2 f (x + (xk x )) 2 f (xk )](xk x ) d

0
1

2 f (x + (xk x )) 2 f (xk ) d xk x
0

L(1 )xk x
1

(1 ) d L xk x =
2

L
2
2
xk x = O( xk x )
2
qed

text
Lemma 2. text
Fr A, B Rnn mit I BA < 1 gilt:

A und B sind regulr und B 1

A
1IBA .

Beweis. text
Ang. A ist singulr, d. h. x B1 (0) Ax = 0
A ist regulr. Analog folgt Regularitt von B.
Die Neumannreihe liefert nun I BA < 1

B 1 = A (I BA)k
k=0

(I BA)x = x

I BA 1
1

(I BA)k = (I (I BA))

k=0

B 1 A I BAk =
k=0

= A1 B 1

A
1IBA

text
Lemma 3. Sei f C 2 (Rn , R) und x Rn so, dass nablaf (x ) = 0 und 2 f (x ) regulr.
Dann gilt:

k0 N

> 0

k k0 f (xk ) xk x

63

qed

Beweis. Da f C 2 (Rn , R) folgt mit Taylorentwicklung:

> 0 k0 N f (xk ) f (x ) 2 f (x )(xk x ) xk x

k k0

Whle > 0 so, dass < 2 f (x )1 . Fr k k0 gilt:

f (xk ) = f (xk ) f (x ) 2 f (x )(xk x ) + 2 f (x )(xk x )
2 f (x )(xk x ) f (xk ) f (x ) 2 f (x )(xk x )
()

2 f (x )1

xk x xk x = xk x

mit = 2 f (x )1 > 0
() xk x = 2 f (x )1 2 f (x ) (xk x ) 2 f (x )1 2 f (x )(xk x )

qed

Interpretation:
Falls f (xk ) <

xk x

Satz 2. Sei f C 2 (Rn , R) , xk x

fr k gro genug sinnvolles Abbruchkriterium

k k0 und 2 f (x ) sei regulr.

Dann sind folgende Aussagen quivalent:

(a) xk x Qsuperlinear und f (x ) = 0
(b) f (xk ) + 2 f (x )(xk+1 xk ) = o( xk+1 xk )
(c) f (xk ) + 2 f (xk )(xk+1 xk ) = o( xk+1 xk )
Beweis. text
(b) (a)
f (xk+1 ) =
= f (xk+1 ) f (xk ) 2 (x )(xk+1 x ) + f (xk ) + 2 f (x )(xk+1 x ) =
1

= [2 f (xk + (xk+1 xk )) 2 f (x )] (xk+1 x k) d +

0

+f (xk ) + 2 f (x )(xk+1 xk )
1

2 f ( xk + (xk+1 xk ) ) 2 f (x ) d xk+1 xk +

[0,1]

+ f (xk ) 2 f (x )(xk+1 xk ) k xk+1 xk

mit k

64

 f (xk+1 ) k xk+1 xk

lim f (xk+1 ) = 0
k

f (x ) = 0

Nach Lemma 3 gilt: > 0 (xk+1 ) xk+1 x

fr k gro genug

xk+1 x (xk+1 ) k xk+1 xk k xk+1 x + k x xk

( k )

xk+1 x
xk x

(a) (b) f C 2 (Rn , R)

Da xk x

xk+1 x
xk x

k
k

Qsuperlineare Konvergenz

f lokal Lipschitz-stetig

L > 0 und k0 N, sodass: f (xk ) f (x ) L xk x

f (xk+1 ) = f (xk+1 ) f (x )

x
x xk x
L xk+1

k x xk+1 xk

k k0

xk+1 xk

Da xk x Qsuperlinear, existiert Nullfolge {k }, sodass f (xk+1 ) k xk+1 xk

f (xk ) 2 f (x )(xk+1 xk ) =
1

= f (xk+1 ) + [2 f (xk + (xk+1 xk )) 2 f (x )](xk+1 xk ) d

0
1

f (xk+1 ) + 2 f (xk + (xk+1 xk )) 2 f (x ) d xk+1 xk

0

(k + k ) xk+1 xk
mit k 0
(b) (c) bung
qed
text
Konsequenz von Satz 2
Gradientenhnliche Verfahren
Sei (H k ) Rnn eine Folge regulrer Matrizen. xk+1 = xk (H k )1 f (xk )
Falls xk x

kN

und f (x ) regulr, so sind quivalent

2

(a) xk x
Qsuperlinear und f (x ) = 0
(b) (2 f (x ) H k )(xk+1 xk ) = o( xk+1 xk )
(c) (2 f (xk ) H k )(xk+1 xk ) = o( xk+1 xk )
Also: xk x Qsuperlinear falls

lim H k 2 f (xk ) = 0 oder lim H k = 2 f (x )

Beweis. f (xk ) = H k (xk+1 xk ) und Satz 2

65

qed

text
Bemerkung: Satz 2 gilt auch wenn superlineare Konvergenz durch superquadratische Konvergenz und o( xk+1 xk ) durch O( xk+1 xk 2 ) ersetzt wird.

5 Gradientenverfahren
Das allgemeine Abstiegsverfahren (Seit 52 Algorithmus 1) lsst Freiheiten in der Wahl der
Abstiegsrichtung dk zu.
5.1 Verfahren des steilsten Abstiegs
Wahl von dk als Lsun von

min f (xk ) d

mit d = 1

(1)

f (x )

Es gilt: 0 f (xk ) d f (xk ) . Die Wahl dk = f (xkk ) liefert f (xk ) = f (xk )

und lst (1).

Es gilt: f (xk ) dk = f (xk ) = f (xk ) dk = 1 f (xk ) dk mit = 1 und erfllt

Bedingung.
Verwendet man die Wolfe-Powel-Regel, so folgt aus Satz 3 und Satz 1 aus Kapitel III.3, dass
jeder Hufungspunkt von {xk } ein stationrer Punkt ist. Da Armijo die Abstiegsbedingung nicht
notwendigerweise erfllt Beweis der Konvergenz.
Lemma 1. Sei f C 1 (Rn , R) , x , d Rn , tk 0 sodass:
Dann gilt:

f (xk +tk dk )f (xk )

lim
tk
k

xk x

dk d

tk 0.

= f (x ) d

Beweis. text

M ittelwertsatz

k [xk , xk + tk dk ] f (xk + tk dk ) f (xk ) = tk f (k ) dk

Da k

lim

f (xk +tk dk )f (xk )

tk

= lim f (k ) dk = f (x ) d
k

qed

text
f (x )

Satz 1. Jeder Hufungspunkt von Algorithmus 1 aus Kapitel III.3 mit dk = f (xkk ) und
Armijo-Schrittweitenstrategie ist ein stationrer Punkt von f.

Beweis. Sei x Rn Hufungspunkt von {xk } und xk x .

Angenommen f (x ) 0. Es gilt {f (xk )} ist monoton fallnd und f (xkl ) f (x )
f (xk ) f (x ) 0 und f (xk+1 ) f (xk ) 0
Armijo mit , . l N und mkl geeignet gilt:
()

f (xkl + mkl 1 dkl ) > f (xkl ) + mkl 1 f (xkl ) dkl

66

 f (xkl + mkl dkl ) f (xkl ) + mkl f (xkl )

f (x )

mkl 0

f (x )

und mit ()

f (x )

f (xkl +

mk 1
l
dk

mk

Lemma 1

f (x ) f (x )

> f (xkl ) dkl

zu f (x ) 0 und (0, 1)
qed

text
Das Verfahren des steilsten Abstiegs kann fr ungnstige Probleme sehr langsam sein.
Konvergenzgeschwindigkeit fr
()

minn f (x)

xR

1
mit f (x) = xT Qx + cT x +
2

Q spd , c Rn , R

Lemma 2 (Kantorovich-Ungleichung). text

Sei Q symmetrisch positiv definit, min und max kleinster und grter Eigenwert von Q.
4max min
xT x

Dann gilt x Rn
T
T
1
(x Qx)(x Q x) (min + max )2
Beweis. text
Geiger, Kanzow: Numerische Verfahren zur Lsung unrestringierter Optimierungsaufgaben,
Lemma 4.5

qed

text

Lemma 3. Mit f wie in (), xk erzeugt durch

dk = f (xk )

tk = arg min f (xk + tdk )

xk+1 = xk + tk dk gilt:

xk x die eindeutige Lsung

2

max min
(f (xk ) f (x) )
f (xk+1 ) f (x ) ( max
+min )

Mit =

max
min

gilt:

xk x

1 k
( +1 ) x0 x

Beweis. text
Es gilt: d= f (xk ) = (Qxk + c)
1
(t) = f (xk + tdk ) = (xk + tdk )T Q(xk + tdk ) + cT (xk + tdk ) + =
2
1
1
= t2 (dk QT dk ) + t(dTk Qxk + cT dk ) + xTk Qxk + cT xk +
2
2

67

tk = arg min (t)

(tk ) = 0

0 = tk (dTk Qdk ) + dTk Qxk + cT dk

tk =

dTk dk
(Qxk + c)T dk
=
dTk Qdk
dTk Qdk

f (xk+1 ) = f (xk + tk dk ) =
1
1
= t2k (dk QT dk ) + tk (dTk Qxk + cT dk ) + xTk Qxk + cT xk + =
2
2
1
T
= f (xk ) + tk (dk (Qxk + c) ) + t2k (dTk Qdk ) =
2
= f (xk )

f (xk+1 ) f (x ) = f (xk ) f (x )
= (1

dk
(dTk dk )2

dk Qdk

1 (dTk dk )2
1 (dTk dk )2
=
f
(x
)

k
2 dTk Qdk
2 dTk Qdk

1 (dTk dk )2
= ... =
2 dTk Qdk

(dTk dk )2
) (f (xk ) f (x ))
(dTk Qdk )(dTk Q1 dk )
(1

Kantorovich

4max min
max min 2

(f
)
(x
)

f
(x
))
=
(
) (f (xk ) f (x ))
k
2
(min + max )
max + min

text
y Rn gilt:
f (y) f (x ) = 21 y T Qy 12 (x )T Qx + cT y cT x = 12 (y x )T Q(y x ) + (y x )T (c + Qx )
=0

min y T y y T Qy max y T y

1
min
2
xk+1 x (xk+1 x )T Q(xk+1 x ) = f (xk+1 ) f (x )
2
2
max min 2
1 2
(
) (f (xk ) f (x ))
) (f (xk ) f (x) ) = (
max + min
+1
1 2(k+1)
1 2k+2 max
2
(f (x0 ) f (x )) (
(
)
)
x0 x
+1
+1
2
xk+1 x

1
)
( +1

k+1

x0 x

xk

x
qed

text
Abhngig von kann die Konvergenz sehr langsam sein.
Es gilt annhernd fr allgemeine Probleme (quadratische Approximation von f um x )

68

Bei Wahl von dk = H 1 f (xk ) sollte man H so whlen, dass (H 1 Q) << (Q) und H 1
leicht berechenbar.

5.2 Gradientenhnliche Verfahren

Definition 1. Sei f C 1 (Rn , R) und {xk } Rn .
Dann heit {dk } Rn gradientenhnlich bezglich f und xk , wenn fr jede gegen einen nicht
stationren Punkt konvergierende Teilfolge {xkl } Konstanten c > 0 , > 0 existieren, sodass
(a) dkl c

l N

(b) f (xkl ) dkl

l gro genug

Beispiel:
f (x )

dk = f (xkk )
c1 x2 xT Hk x c2 x2

Hk mit:
dk =

Hk1

f (xk )

c1 , c2 0

(bung)

Bemerkung:
(1) Fr gradientenhnliche Verfahren mit Armijo-Schrittweitensteuerung gilt: Jeder Hufungspunkt ist kritisch (Geiger, Kanzow: Satz 8.9)
(2) Hk = diag (

2 f (xk )
)
x2

liefer manchmal gute Ergebnisse

6 Verfahren der konjugierten Gradienten fr quadratische Probleme

Oft trifft man auf Problemstellungen der Form
(1)

minn f (x)

xR

1
mit f (x) = xT Ax bT x + c
2

mit A Rnn spd , b Rn , c R

wobei A sehr gro ist und hufig eine spezielle Struktur aufweist, sodass z. B. Ax einfach zu
berechnen ist.
Entwickle ein Verfahren speziell fr Typ (1).
Hier: Verfahren zu Lsung von (1), dass nur Ax bentigt und in endlich vielen Schritten abbricht
(lst zugleich Ax = b)

69

Motiation: Sukzessives minimieren ber Unterrume, sodass unabhngige Probleme entstehen.

Angenommen wir haben Vektoren d0 , . . . , dn1 0 so, dass
dTi Adj = 0

i, j = 0, . . . , n 1

ij

Akonjugiert oder Aorthogonal. Dann sind {dj }j linear unabhngig und die optimale Lsung
von (1) kann als Linearkombination der di dargestellt werden.
T

min

0 ,...,n1

n1
n1
1 n1
1 n1
T
T
( i di ) A ( i di ) bT ( i di ) + c = min
(i di Adi i b di ) + c
0 ,...,n1 2
2 i=0
i=0
i=0
i=0

n unabhngige Probleme i i =

bT di
dT
i Adi

Wir haben gezeigt: Seien d0 , . . . , dn1 Akonjugierte Vektoren. Dann konvergiert das Verfahren
x0 = t0 d0
xk+1 = xk + tk dk

mit tk =

bT dk
Adk
dT
k

in hchtens n Schritten gegen die optimale Lsung (1).

Problem:
Bentigt d0 , . . . , dn1 (Iterative Berechnung mit mglichst wenig Rechenschritten)
Falls n sehr gro

exakte Lsung nicht praktikabel definiere iteratives Verfahren mit

beliebigen Startpunkt

Lemma 4. Seien d0 , . . . , dn1 Akonjugiert und x Rn .

Definiere xk+1 = xk + tk dk mit tk = arg min f (xk + tk dk ). Dann gilt mit g k = f (xk ) = Axk b
(g k )T dk

tk = (dk )T Adk
(g k+1 )T dj = 0

j = 0, . . . , k und das Verfahren konvergiert in hchstens n Schritten.

Beweis. text

(g k )T dk

Es gilt: f (xk + tdk ) = 12 t2 (dk )T Adk + t(Axk b)T dk + const

tk = (dk )T Adk

gk

0 = tk (dk )T Adk + (g k )T dk = (tk (dk )T A + (xk )T A bT ) dk =

T

= (A(xk + tk dk ) b) dk = (Axk+1 b)T dk = (g k+1 )T dk

70

fr k = 0, . . . , n 1. Damit gilt fr j {0, . . . , k}

k

(g k+1 )T dj = (g j+1 )T dj + (g i+1 g i )T dj =

i=j+1

=0

i=j+1

i=j+1

= (xi+1 xi )T Adj = ti (di )T Adj = 0

xn ist optimal, da f (xn )T dj = (g n )T dj = 0

j = 0, . . . , n 1 und {dj } linear unabhngig

f (xn ) = 0
qed
text
Berechnung der di : Start d0 = f (x0 ) = g 0 ( 0)
Gegeben: d0 , . . . , dl . Da g l+1 linear unabhngig zu d0 , . . . , dl whle als Ansatz
l

dl+1 = g l+1 + il di
i=0

mit il so, dass (dl+1 )T Adj = 0

l

j = 0, . . . , l
T

0 = (dl+1 )T Adj = (g l+1 + il di ) Adj = (g l+1 )T Adj + jl (dj )T Adj

i=0

jl =

(g l+1 )T Adj
(dj )T Adj

Weiters gilt fr j = 0, . . . , l:
j1
j1
(g l+1 )T g j = (g l+1 )T ij1 di dj = ij1 (g l+1 )T dj (g l+1 )T dl = 0
i=0
i=0
text
g j+1 g j = A(xj+1 xj ) = tj Adj

j = 0, . . . , l 1
1
((g l+1 )T Adj ) = (g l+1 )T (g j+1 g j ) = 0
tj

jl = 0

j = 0, . . . , l 1
2

l = ll =
Also liefer

j = 0, . . . , l 1

g l+1
g l+1
g l+1
(g l+1 )T Adl 1 (g l+1 )T (g l+1 g l )
=
=
=
=
2
(dl )T Adl
tl
(dl )T Adl
(dl )T (g l+1 g l ) (dl )T g l
g l

dl+1 = g l+1 + l dl Akonjugierte Vektoren.

Momentan AMultiplikation fr tk =
Da g k+1 g k = Axk+1 Axk = tk Adk

(g k )T dk
(dk )T Adk
k+1

g k
(dk )T Adk
g k + tk Adk

71

und g k = Axk b

Algorithmus 4 (Konjugierte Gradienten). text

Input: A , x0 , > 0
Setze: g 0 = Ax0 b ; d0 = g 0 ; k = 0
while g k >
2

g k

texttk =
textx
textg

k+1

% Schritt

textk =
textd

= x + tk d
k

= g + tk Ad

k+1

k+1

% Schrittweite

(dk )T Adk

% Gradienten-Update

g k+1
2

g k
k+1

= g

+ k dk

textk = k + 1
end
Output: xk

text
Bemerkung:
(1) Fr l = 0, . . . , k 1 gilt:
f (xl ) dl = (g l ) (g l + l1 dl1 ) = (g l )2 < 0
(2) Hauptaufwand: Berechnung von Adk
(3) Es gilt: k =

(g k+1 g k )g k+1
2

g k

g l Abstiegsrichtung

zk = AdK abspeichern

Diese Wahl ist numerisch stabiler und daher besser geeignet als k =
numerischer Fehler Richtungen nicht mehr Akonjugiert sind

g k+1
2
g k

, da aufgrund

Abstiegseigenschaft kann

verloren gehen.
Auch tk kann klein werden, falls tk = 0
d

k+1

= g

k+1

xk+1 = xk

g k+1 = g k

k = 0

Restart

(4) (a) CGAlgorithmus findet in hchstens n Schritten die Lsung

(b) Besitzt A genau m n verschiedene Eigenwerte CG bricht nach m Schritten ab
(c) Falls b Linerakombination von m Eigenvektoren von A ist
Schritten ab, falls x = 0

Verfahren bricht nach m

(5) Man kann zeigen:

xk x A 2 ( 1
) x0 x A
+1

6.1 Prkonditionierung
Sei B Rnn symmetrisch positiv definit.
Ax = b

ABB 1 x = b

y = B 1 x

ABy = b

72

BABy = Bb mit BAB spd

Benute B mit (BAB) < (A)

CGVerfahren durchfhrbar. Ziel: Integriere B in CGVerfahren.
Neues inneres Produkt:

( , )B = B ,

bernimmt Rolle der euklidischen inneren Pro-

dukts. Energieprodukt:

( , )AB = ( AB , )B = BAB ,

CG zur Lsung von ABy = b:

g 0 = ABy 0 b

d0 = g 0

k =

g k B
, dk )AB

( dk

k0

g k , Bg k
ABdk , Bdk

y k+1 = y k + k dk
g k+1 = g k + k ABdk
k =

g k+1 , g k+1 B
g k , g k B

dk+1 = g k+1 + k dk
k k+1
Zurckziehen zur Lsung von Ax = b:
d0 = Bg 0

g 0 = Ay 0
k =

g k

Bd0 = d0

k0

, Bg k

Adk , dk

xk+1 = xk + k dk
g k+1 = g k + k Adk
2

k =

g k+1 B
2

g k B

dk+1 + Bg k+1 + k dk
k k+1
Prkonditioniertes CGVerfahren

73

7 Newton-Verfahren
Wir betrachten:

x lokales Minimum von f

(A) f C 2 (U (x ), R)
2 f (x) 2 f (y) x y

2 f (x ) > 0
f (x ) = 0

x, y U (x )

text
Notation:
xa aktuelle Iterierte
x+ neue Iterierte
Quadratisches Modell:
1
ma (x) = f (xa ) + f (xa ) (x xa ) + 2 f (xa )(x xa ) (x xa )
2
Angenommen: 2 f (xa ) > 0

0 = ma (x+ ) = f (xa ) + 2 f (xa )(x+ xa )

x+ = xa 2 f (xa )1 f (xa )

oder

2 f (xa )d = f (xa ) mit d = x+ xa .

Lemma 1.

(A)

> 0 x B (x )

2 f (x) 2 2 f (x )

2 f (x)1 2 2 f (x )1

xx
1
2 f (x )normxx

2 2 f (x )1 f (x) 2

Beweis. bung

qed

text
Satz 1. Es gelte (A). Dann existieren K > 0 und > 0 so, dass falls xa B und x+ =

xa 2 f (xa )1 f (xa ) folgt:

x+ x K xa x 2 .

74

Beweis. Fr klein genug gilt:

x+ x = xa x 2 f (xa )1 f (xa ) = 2 f (xa )1 [f (xa )(xa x ) f (xa )] =
1

2
1
2

= f (xa ) f (xa )(xa x ) f (x ) f (x + t(xa x ))(xa x ) dt =

0
1

= f (xa )
2

2
2

[ f (xa ) f (x + t(xa x ))](xa x ) dt

0

2 f (xa )1 2 2 f (x )1

x+ x+ 2 2 f (x )1 (1 t) xa x dt
2

0
1
1

2 f (x ) (1 t) dt xa x =
2

= 2 f (x )1 xa x = K xa x
2

qed
text
Satz 2. Es gelte (A). Dann existiert ein > 0 so, dass fr x0 B , das Newton Verfahren
Qquadratisch gegen x konvergiert.
Beweis. Sei > 0 derart, dass Satz 1 gilt (gibt Konstante K > 0). o. B. d. A. K = < 1.
Fr xk B gilt: xk+1 x K xk x 2 K xk x = xk x <
xk+1 B . Mit Satz 1

Qquadratische Konvergenz
qed

text
Abbruchkriterium: Relative und absolute Fehlerschranke r , a (0, 1).
STOP, sobald f (xk ) r f (x0 ) + a
7.1 Ungenauigkeiten in Funktions-, Gradiente- und Hessematrixauswertung
Annahme: f R R
Approximiere Gradient:

f = f + f

f ( ) f
f(x+h)f(x)
+
Dk f (xk ) =

75

f > 0

Schtze Fehler ab:

f(x + h) f(x)
f (x) =
h
f (x + h) f (x + h) f (x) f (x)
2f
f (x + h) f (x)
=
f (x)
f (x) +
=
h
h
h
2f
f
1
=
f ()h +
= O (h + )
T aylor
2
h
h

Dk+ f (x) f (x) =

[x,x+h]

Definiere:

err+ (h) = h +

f
h

!
err+ (h) = 1 hf2 = h = f

Einsetzen: err+ ( f ) = 2 f Fehler im Gradienten g = O( f )

Minimiere err+

Fr die Hessenbergmatrix, abermals Vorwrtsdifferenzieren H = O( g ) = O( 4 f )

Beispiel: f = 1016

H = 104

Besser: Zentrale Differenzen

Dk+ f (x) f (x) =

modulo Faktoren

Dk0 f (x) =

f(x+h)f(xh)
2h

1
(f (x + h) f(x h)) f (x) =
2h

1
(f (x + h) f (x h) + f (x + h) f (x h)) f (x)
2h

f
f (x + h) f (x h)
f (x) +
=
2h
h

1
1

2
+ f (x)h + 1 f

[
f (x)
(x)h
+ f (x)h3
f (x)+

2h
2
6

f
1
1
+f (x)h f
(x)h2 + f (x)h3 ] f (x) +

2
6
h

Minimalstelle von h2 +
2

g = O (f3 )

f
h

h =
2

f
2
4

H = O (g3 ) = O (f3 )

f
f
1 2
h [ f (x)1 ) + f (2 ) ] +
= O (h2 + )
12
h
h
err0 (h ) = (

f 23
)
2

+ f

besser Abschtzung

76

3
2

3 f

= O (f3 )

Satz 3. Es gelte (A). Dann existierern K > 0 , > 0 und > 0 so, dass fr xa B und
H (xa ) < gilt:
1

x+ = xa (2 f (xa ) + H (xa ))

(f (xa ) + g (xa ))

x+ x K (xa x 2 + H (xa ) xa x + g (xa ))

ist wohldefiniert und:

Beweis. Angenommen (2 f (xa ) + H (xa ))

1

x+ x = (2 f (xa ) + H (xa ))

existiert, dann gilt:

[2 f (xa )(xa x ) f (xa ) + H (xa )(xa x ) g (xa )]

Analog zu Satz 2 folgt:

1

x+ x (2 f (xa ) + H (xa )) [ xa x + H (xa ) xa x + g (xa )]

2

text
Nun gilt: A, B Matrizen, A regulr und A1 B < 1
(A + B)1 existiert und (A + B)1
Ist <

42 f (x )1

2 f (xa )1 H (xa )
1

( f (xa ) + H (xa ))
2

A1
1A1 B

22 f (x )1
42 f (x )1

1
2

<1

existiert, falls H (xa ) < und

(2 f (xa ) + H (xa )) K0 unabhngig von xa

x+ x K (xa x 2 + H (xa ) xa x + g (xa ))

fr ein K > 0
qed

text
Interpretation:
Falls H (xa ) H , dann folgt mit Satz 3 hchstens lineare Konvergenz.
Falls g (xa ) g

Iteration kann stagnieren in Umgebung von x .

7.2 Varianten des Newton-Verfahrens

Keine Updates fr 2 f (xa ), d. h.

xk+1 = xk 2 f (x0 )1 f (xk ) k = 0, 1, 2, . . .

Entspricht:
g (xa ) = 0
H (xk ) = 2 f (xk ) 2 f (x0 ) x0 xk ( x0 x xk x )

77

Satz 4. Sei (A) erfllt. Dann existieren K > 0 und > 0 so, dass fr
xk+1 = xk f (x0 )1 f (xk )

und

x 0 B

folgt: {xk } konvergiert Qlinear gegen x und xk+1 x K x0 x xk x .

Beweis. text
xk+1 x K [ xk x + xk x 2 + x0 x xk x

Auswerten von Satz 2:

Fr klein genug und mit Hilfe von Induktion nach k folgt:

xk+1 x c xk x

k N mit c < 1

{xk } konvergiert Qlinear gegen x .

Damit insbesondere: xk x x0 x

xk+1 x K(1 + 2) x0 x xk x
K

qed

text
Skamarski-Verfahren:

xk+1 = xk Hk f (xk )
f wird nach m 1 Schritten aktualisiert

fr ml k m(l + 1)

Hk = f (xml )
2

Satz 5. Es sei (A) erfllt. DAnn existiert > 0 so, dass fr x0 B das Skamarski-Verfahren
Qsuperlinear gegen x konvergiert.
Beweis. bung

qed

text
7.3 Nichtlineare Ausgleichsprobleme
Ziel: Lse fr r Rn Rm die Gleichung r(x) = 0.
Flle:
m=n

Newton

m>n

berbestimmte Probleme

m<n

unterbestimmte Probleme

78

In jedem Fall lsst sich betrachten:

min 1
xRn 2

r(x)2

Nullresiduenproblem bzw. Problem des kleinsten Resduums.

r1 (x)

2
1
Mit f (x) = 2 r(x) und r differenzierbar folgt mit r(x) = :

rm (x)
m

f (x) h = r(x) r(x) h = r(x)T r(x) h

f (x) = r(x)T r(x) = ri (x) rj (x)

i=1

Notwendige Optimalittsbedingung fr Minimierer von f 0 = f (x ) = r(x )T r(x )

Falls m n und rang (r(x )) = m r(x )T injektiv
r(x ) = 0

Gleichung wird gelst.

Bemerkung: Hessematrix von f

2 f (x) = r(x)T r(x) + ri (x) 2 ri (x)

i=1

Gau-Newton-Verfahren:
Betrachte:

(H1)

Falls r(x ) = 0

minn 12 r(x)2

fr

xR

r Rn Rm
mn

Nullresiduenproblem

2 f (x ) = r(x )T r(x )

Also verwende dieses Produkt als Appoximation an 2 f (x) fr x Rn .

Damit ergibt sich folgendes quadratisches Modell:
1
ma (x) = f (xa ) + r(xa )T r(xa ) (x xa ) + r(xa )T r(xa ) (x xa ) (x xa )
2
ma (x) = r(xa )T r(xa ) + r(xa )T r(xa ) (x xa )
text
Beobachtungen:

r(xa ) r(xa ) R
T

nn

hat vollen Rang

r(xa ) ist regulr

r(xa ) hat vollen Spaltenrang

r(xa ) hat vollen Zeilenrang

r(xa )T r(xa ) ist regulr,falls m n und ker (r(xa )) = {0}

r(xa )T r(xa )y y = r(xa )2 > 0

falls y 0

r(xa ) r(xa ) ist positiv definit regulr

T

r(xa ) ist injektiv

r(xa )T r(xa ) Rnn ist auf range (r(xa )T ) invertierbar

range (r(xa )T ) = ker (r(xa ))

bildr(xa ) = ker (r(xa )T )

79

m=n
m>n
m<n

y range (r(xa )T ) und r(xa )T r(xa ) y = 0

r(xa )y ker (r(xa )T ) und r(xa )y range (r(xa )) = ker (r(xa )T )

r(xa )y = 0
Analog: y ker (r(xa )) und y range (r(xa )T ) = ker (r(xa ))
y = 0 r(xa )T r(xa ) ist injektiv auf range (r(xa )T )

Folglich: x+ = xa (r(xa )T r(xa )) r(xa )T r(xa ) ergibt Sinn.

1
(r(xa )T r(xa )) r(xa )T r(xa ) als Lsung von r(xa )T r(xa ) x = r(xa )T r(xa )
range(r(xa )T )

Annahme: (H2)
Fr x lokales Minimum von

x r(x)2

sei r Lipstitz-stetig in Umgebung von x und

r(x )T r(x ) habe vollen Rang.

berbestimmte Probleme:
Satz 6. Es sei m n un des gelte (H2).
Dann existieren K > 0 und > 0 so, dass fr xa B (x ) und
x+ = xa (r(xa )T r(xa ))

r(xa )T r(xa )

folgt: x+ B (x ) und x+ x K [ xa x 2 + r(x ) xa x ]

Beweis. text
Es sei zunchst > 0 so, dass xa x <

rang (r(xa )T r(xa )) = n.

Dies ist mgich, denn r stetig und r(x )T r(x ) regulr.

Bezeichne die Lipschitz-Konstante von r in Umgebung von x .
x+ x = xa x (r(xa )T r(xa ))

r(xa )T r(xa ) =

= (r(xa )T r(xa ))

r(xa )T [r(xa )(xa x ) r(xa )]

r(x ) r(xa ) r(xa )(x xa ) = [r(xa + (x xa )) r(xa )](x xa ) d

0

Notwendige Optimalittsbedingung: r(x )T r(x ) = 0

80

x xa 2

r(xa )T r(x ) = (r(x ) r(xa )) r(x )

1

x+ x (r(xa )T r(xa )) r(xa )T [r(x ) r(x ) r(xa ) r(xa )(x xa )]

2
x xa ]
2
T

r(x

)
a
1

(r(xa )T r(xa )) xa x r(x ) +

xa x

r(xa )
1
) [ r(x ) + xa x ] xa x
(r(xa )T r(xa )) max (1,
2
1

(r(xa )T r(xa )) [(r(x ) r(xa )) r(x ) + r(xa )T

Whle K =

sup

xa B (x )

{(r(xa )T r(xa )) max (1,

r(xa )
)}
2

<

Abschtzung

Eventuell > 0 reduzieren x+ B (x )

qed

81

Literaturempfehlungen
[1] Luenberger, David G.; Ye, Yinyu: Linear and Nonlinear Programming, 3. Auflage, New
York, Springer Science+Business Media, 2008.
[2] Nocedal, Jorge; Wright, Stephen J: Numerical Optimization, 2. Auflage, New York, Springer
Science+Business Media, 2006.
[3] Geiger, Carl; Kanzow, Christian: Numerische Verfahren zur Lsung unrestringierter Optimierungsaufgaben, Springer Berlin Heidelberg, 1999.

82