DeutschesFachbuch.de : Optimierungsmethoden Eine Einführung Von Dieter Jungnickel

INHALTSVERZEICHNIS | öffnen

Inhaltsverzeichnis
Vorwort zur zweiten AuflageV
Vorwort zur ersten AuflageIX
1 Einführung 1
1.1 Ein erstes Beispiel 1
1.2 Nichtlineare Optimierungsprobleme 9
1.3 Einige Spezialfälle 12
1.4 Optimalitätskriterien im klassischen Fall 16
2 Konvexe Mengen 23
2.1 Grundlagen 23
2.2 Topologische Eigenschaften konvexer Mengen 28
2.3 Projektionen und Trennungssätze 33
2.4 Alternativsätze 38
2.5 Extremalpunkte und Seitenflächen 46
2.6 Rezessions- und Polarkegel 49
2.7 Tangential- und Normalkegel 53
2.8 Seitenflächen von Polyedern 61
2.9 Darstellungssätze für Polyeder 69
2.10 Spitze Polyeder 75
2.11 Exkurs: Der Satz von Helly 77
3 Konvexe Funktionen 81
3.1 Grundlagen 81
3.2 Konvexe Funktionen und Differenzierbarkeit 88
3.3 Optima konvexer Funktionen 92
3.4 Verallgemeinerte Konvexitätsbegriffe 100
4 Optimalitätskriterien 107
4.1 Ungleichungsrestriktionen 108
4.2 Constraint qualifications 115
4.3 Gleichungsrestriktionen 123
4.4 Der allgemeine Fall 130
4.5 Kriterien zweiter Ordnung 135
4.6 Lagrange-Dualität 142
5 Lineare Programme 153
5.1 Dualität und Komplementarität 153
5.2 Das Simplexverfahren: Geometrische Grundlagen 161
5.3 Das Simplexverfahren: Grundform 170
5.4 Das Simplexverfahren: Initialisierung 183
5.5 Das Simplexverfahren: Kreiseln 195
5.6 Das Simplexverfahren: Stalling 203
5.7 Das duale Simplexverfahren 209
5.8 Das Simplexverfahren: Postoptimierung 218
5.9 Parametrische lineare Programme 225
5.10 Ein polynomialer Algorithmus 235
5.11 Ausblick 247
6 Eine allgemeine Konvergenztheorie 249
6.1 Der globale Konvergenzsatz 249
6.2 Zusammengesetzte algorithmische Abbildungen 254
6.3 Ausblick 260
AAnhang: Affine Geometrie 261
1.1 Die affine Hülle 261
1.2 Der affine Rang 264
1.3 Die affine Geometrie AG(V)265
Literaturverzeichnis 271
Sachverzeichnis 273
[weiter lesen]

REGISTER | öffnen

Sachverzeichnis
AAbbildung
affine, 27
algorithmische, 249
- differenzierbare, 16
- konkave, 81
- konvexe, 81
- pseudokonvexe, 105
- quasikonvave, 100
- quasikonvexe, 100
- stark quasikonkave, 104
- stark quasikonvexe, 104
- strikt konkave, 81
- strikt konvexe, 81
- strikt quasikonkave, 103
- strikt quasikonvexe, 103
- zweimal differenzierbare, 19
Abbruchkriterien, 251
Abschluß, 28
Abstiegsfunktion, 249
Abstiegsrichtung, 16
- steilste, 18
Abstiegsverfahren, 94
ACQ, 117
Adler-Monteiro-Folge, 240
affin abgeschlossen, 261
affin abhängig, 264
affin unabhängig, 264
affine Dimension, 264
affine Ebene, 268
affine Geometrie, 266
affine Hülle, 261
affiner Rang, 264
affiner Unterraum, 261
- zugehöriger linearer Unterraum, 262
Affinkombination, 261
algorithmische Abbildung, 249
abgeschlossene, 252
- zusammengesetzte, 254
Algorithmus, 250
Alternativsätze, 38
Alternativsatz
- für lineare Gleichungssysteme, 38
- konvexer, 145
Anstiegsrichtung, 16
Auswahlregeln, 202
BBarriere-Problem, 236
Barriereterm, 236
Basis, 163
- dual zulässige, 209
- optimale, 210
- primal zulässige, 209
- zulässige, 164
Basislösung, 163
- degenerierte, 164
- dual zulässige, 209
- duale, 209
- entartete, 164
- nichtdegenerierte, 164
- nichtentartete, 164
- primal zulässige, 209
- zulässige, 164
Basismatrix, 163
- zulässige, 164
Basisvariable, 163
Bedingungen des komplementären Schlupfes, 109
Big-M-Methode, 192
Bland-Regel, 197, 202
Cconstraint qualification, 114
- Abadie- 117
Cottle- 122
- LICQ, 61, 114
- Slater- 122
- Zangwill- 122
DDantzig-Regel, 202
Darstellung
- irredundante, 63
Darstellungssatz für Polyeder, 72
Dimension, 26, 265
- affine, 264
Dreieck, 24, 268
Duales Simplex ver fahr en, 211
Dualitätslücke, 144
Dualitätssatz
- allgemeiner, 159
- schwacher, 8, 119, 143, 154
- starker, 119, 146, 154
EEbene, 266
Ecke, 47
- adjazente, 169
Eingabegröße, 243
Einheitskugel, 24
Einheitssimplex, 24
Einheitssphäre, 24
Epigraph, 83
Erste lexikographische Zeilenauswahlregel, 201, 203
Erzeugendensystem
endliches, 69
Erzeugermenge
endliche, 69
Erzeugnis von zwei affinen Unterräumen, 266
Extremalpunkt, 46
FFacette, 47
Farkas-Lemma, 39, 40
- allgemeines, 41
- Varianten, 40
Fritz-John-Bedingung, 109
Funktion
- duale, 143
GGerade, 266
Gleichungsrestriktion, 10
Gleichungssystem
- erweitertes, 176
Globale Minima
- für dif-Ferenzierbare konvexe Funktionen, 94
- für konvexe Funktionen, 93, 97
- im affinen Fall, 118, 121
Globaler Konvergenzsatz, 253
Größter-Fortschritt-Regel, 202
Gradient, 16
Grundtableau, 180
HHalbgerade, 65
- affine, 65
Halbraum, 24
- affiner, 65
Häufungspunkt, 28
Hesse-Matrix, 19
Hilfsprogramm, 183
Hinreichende Bedingungen zweiter Ordnung
- im allgemeinen Fall, 138
- im klassischen Fall, 20
Hinreichende KKT-Bedingungen für Ungleichungsrestriktionen Globale Version, 114
Lokale Version, 115
- im allgemeinen Fall, 134
Höhenlinien, 11
Hülle
- abgeschlossene konvexe, 28
- affine, 261
- konische, 25
- konvexe, 25
Hyperebene, 266
- affine, 24
- redundante, 77
- Restriktions- 61
- Stütz- 35
- strikt trennende, 35
- trennende, 35
- uneigentlich trennende, 35
Hyperfläche
- glatte, 123
Hypograph, 83
IIndexmenge der straffen Restriktionen, 57
innere-Punkte-Verfahren, 237
Inneres, 28
- relatives, 28
inzident, 266
JJacobi-Matrix, 110, 125
Kkanonische Form, 46
Kante, 47
Kegel, 24
- der Abstiegsrichtungen, 108
- der normalen Richtungen, 54
- der Tangentialrichtungen, 53
- der zulässigen Richtungen, 53
konvexer, 24
- Normal- 54
- Polar- 50
- polyedrischer, 50
- Rezessions- 49
- Tangential- 53
KKT-Bedingungen
- für lineare Programme, 118
- für quadratische Programme, 120
Klee-Minty-Würfel, 204
Kleinster-Index-Regel, 202
Kleinster-Variablenindex-Regel, 197, 202
Kodierungslänge, 243
Kombination
- Affin- 261
konische, 25
Konvex- 25
Komposition, 254
Konvergenzsatz
- für mehrdimensionale Suche, 258
- für zusammengesetzte Abbildungen, 256
- globaler, 253
- Spacer-step-Theorem, 257
Konvexer Alternativsatz, 145
Konvexkombination, 25
Kosten
- reduzierte, 171
Kostenkoeffizient
- reduzierter, 171
Kreiseln, 170, 195
Kugel, 28
Kurve
- glatte, 124
LLagrange-Dualität, 142
Lagrange-Funkt ion, 142, 143
Lagrange-Multiplikatoren, 109, 129
[weiter lesen]