1

VorlesungEinfuhrung

in dieMathematische Optimierung

(Wintersemester 2016/17)Einleitung

Volker Kaibel

Otto-von-Guericke Universitat Magdeburg

(Version vom 17. Oktober 2016)

2

Kommunikationsnetzwerke. . .

DatenI uij : Maximale Bitrate uber Link (i , j)

I cij : Kosten Ubertragung ein Bit uber (i , j)

I bk`: (Konstante) Bitrate von k nach `

3

. . . Kommunikationsnetzwerke

Ziel

Route Daten unter minimalen Kosten.

Modellierung: Variablen

xk`ij : Datenrate fur die Verbindung von k nach ` auf Link (i , j)

Konnen zulassen (weil Bitraten groß sind): xk`ij ∈ R

4

Lineares Optimierungsmodell

Minimiere ∑(i ,j) Link

∑k

∑`

cijxk`ij

unter den Nebenbedingungen

∑j :(j ,i) Link

xk`ji −∑

j :(i ,j) Link

xk`ij =

−bk` (i = k)

bk` (i = `)

0 sonst

∀i , k , `

∑k

∑`

xk`ij ≤ uij ∀(i , j)

xk`ij ≥ 0 ∀(i , j), k , `

5

(Kontinuierliche) Lineare Optimierung

Optimierung von

I linearen Zielfunktionen

unter (endlich vielen)

I linearen Nebenbedingungen (=, ≤, ≥)

in (endlich vielen)

I kontinuierlichen Variablen.

6

Variante

Zusatzliche Daten

fij : Fixkosten fur Verwendung von Link (i , j)

Zusatzliche Variablen

yij ∈ {0, 1}: 1, falls Link (i , j) verwendet, sonst 0

7

Gemischt ganzzahliges Modell

Minimiere ∑(i ,j) Link

∑k

∑`

cijxk`ij +

∑(i ,j) Link

fijyij

unter den Nebenbedingungen

∑j :(j ,i) Link

xk`ji −∑

j :(i ,j) Link

xk`ij =

−bk` (i = k)

bk` (i = `)

0 sonst

∀i , k , `

∑k

∑`

xk`ij ≤ uijyij ∀(i , j)

xk`ij ≥ 0 ∀(i , j), k , `

yij ∈ {0, 1} ∀(i , j)

8

(Gemischt) Ganzzahlige Lineare Optimierung

Optimierung von

I linearen Zielfunktionen

unter (endlich vielen)

I linearen Nebenbedingungen (=, ≤, ≥)

in (endlich vielen)

I Variablen, von denen einige nur ganzzahlige Werte annehmendurfen.

9

(Kontinuierliche) Lineare Optimierung

10

Ganzzahlige Lineare Optimierung. . .

11

. . . Ganzzahlige Lineare Optimierung

I Machtig (z.B. 0/1-Entscheidungsvariablen)

I Baut auf (kontinuierlicher) LP auf

I Einblick am Ende dieser VLI Vertiefung:

I WiSem 17/18: VL Kombinatorische OptimierungI SoSem 18: VL Ganzzahlige Optimierung

12

(Kontinuierliche) Lineare Optimierung

I Sehr gutes strukturelles Verstandnis (Zertifikate, Dualitat)

I Theoretisch effizient losbar (polynomial)

I Praktisch effizient losbar

I Hintergrund: Konvexitat

13

Konvexe Optimierung

14

Portfolio-Optimierung

DatenI n Anlagemoglichkeiten (Anlage)

I Zu investierendes Kapital: K = 1

I Ri : Rendite Anlage i (Zufallsvariable)

Variablen

xi : Anteil des in Anlage i investierten Kapitals

Gesamtrendite (Zufallsvariable)

G (x ,R) =∑n

i=1 Rixi

15

Optimierungsmodell

I Ziel: Maximale erwartete Rendite unter der Nebenbedingung,dass die Wahrscheinlichkeit, einen Anteil von b zu verlieren,hochstens α ist.

I MaximiereE[G (x ,R)]

unter den Nebenbedingungen

n∑i=1

xi = 1

P[G (x ,R) ≥ −b] ≥ 1− αx ≥ O

16

Optimierungsmodell (umformuliert)

Maximiere〈r , x〉

unter den Nebenbedingungen

〈1, x〉 = 1

zα√xTCx − 〈r , x〉 − b ≤ 0

x ≥ O

I zα: (1− α)-Quantil Standardnormalverteilung

I C : Kovarianzmatrix (positiv definit) der normalverteilten Ri

I r i : Erwartungswerte der Ri

17

Konvexe Optimierung

Minimierung von

I konvexen Zielfunktionen

uber

I konvexen (abgeschlossenen) Mengen X ⊆ Rn

I Hier: Differenzierbare Zielfunktionen

I Oft: X = {x ∈ X0 | gi (x) ≤ 0 fur i = 1, . . . ,m} mit einfacherkonvexer Menge X0, gi konvex

18

Inhalt

I Optimierung ohne Nebenbedingungen

I Konvexe Mengen und Kegel

I Optimalitatsbedingungen fur konvexe Optimierungsprobleme

I Dualitat und Konische Optimierung

I Polynomiale Verfahren fur konvexe Optimierung

I Die Geometrie der Linearen Optimierung

I Der Simplex-Algorithmus

I Ganzzahlige und Kombinatorische Optimierung

19

Literatur. . .

I R. J. VanderbeiLinear ProgrammingSpringer, 2001.

I J. Matousek und B. GartnerUsing and Understanding Linear ProgrammingSpringer, 2006.

I V. ChvatalLinear ProgrammingFreeman, 1983.

I D. Bertsimas and J. N. TsitsiklisIntroduction to Linear OptimizationAthena, 1997

20

. . . Literatur

I G. B. DantzigLinear Programming and ExtensionsPrinceton University Press, 1998 (1963).

I A. RuszcynskiNonlinear OptimizationPrinceton University Press, 2006

I A. SchrijverTheory of Linear and Integer ProgrammingWiley, 1986.

I M. Grotschel, L. Lovasz, A. SchrijverGeometric Algorithms and Combinatorial Optimization.Springer, 1988.

21

Materialien

I www.math.uni-magdeburg.de/~kaibel/

I LATEX-Folien: Vor VL im Netz

I Empfehlung: Zur VL mitbringen (Notizen)

I Handschriftliche Folien: Nach VL im Netz

22

Organisatorisches

I VorlesungI Montag 15:15-16:45 G05-307I Dienstag 15:15-16:45 G05-307

I UbungenI Verantwortlich: Tobias WeberI Dienstag, 7:30-9:00 (G22A-211)

I LeistungsnachweisI Klausur (Ubung letzte VL-Woche, 24.1.2017)I Teilnahmenvoraussetzungen

I Ubungspunkte, VorrechnenI Details in Ubungen

I ModulprufungI September 2017 (Februar/Marz 2017)I In der Regel: Gemeinsam mit Numerik