Operations Research Konvexe Funktionen · Operations Research Rainer Schrader Zentrum für Angewandte Informatik Köln 4. Juni 2007 1/84 Konvexe Funktionen 2/84 konvexe Funktionen

Operations Research

Rainer Schrader

Zentrum für Angewandte Informatik Köln

4. Juni 2007

1 / 84

Konvexe Funktionen

2 / 84

konvexe Funktionen

• wir haben uns bereits mit linearen Optimierungsproblemen beschäftigt

• wir werden im nächsten Kapitel Verfahren zu ihrer Lösung untersuchen

• die Ideen und Aussagen dazu beruhen zum Teil auf einer allgemeinerenTheorie

• diese Theorie beschäftigt sich mit konvexen Funktionen

3 / 84

konvexe Funktionen

Gliederung

• konvexe Funktionen

• Grundlagen• differenzierbare konvexe Funktionen

• quadratische Funktionen

• Minimierung konvexer Funktionen

• Dualität

• Optimaliätsbedingungen

• Lösungsverfahren

4 / 84

konvexe Funktionen• sei F ⊆ Rn ein Definitionsbereich und f : F → R eine Funktion

• der Epigraph von f ist die Menge

epi f = {(x, z) ∈ Rn+1 | x ∈ F , z ∈ R, z ≥ f (x)}.

• f heißt konvex, wenn der Epigraph epi f eine konvexe Menge inRn+1 darstellt

Lemma 1f : F → R ist genau dann konvex, wenn gilt

(i) F ist konvex;

(ii) für alle x, y ∈ F und 0 < λ < 1:

f [λx + (1− λ)y] ≤ λf (x) + (1− λ)f (y).

5 / 84

konvexe FunktionenLemma 1f : F → R ist konvex genau dann, wenn gilt

(i) F ist konvex;

(ii) für alle x, y ∈ F und 0 < λ < 1:

f [λx + (1− λ)y] ≤ λf (x) + (1− λ)f (y).

x x yy

f(x)

λ (1−λ)+

6 / 84

konvexe Funktionen

Beweis:

• seien (x, z) und (y, w ) Punkte im Epigraphen von f

• ist f konvex, so gilt:

(λx, λz) +`(1− λ)y, (1− λ)w

´∈ epi f (0 < λ < 1).

• nach Komponenten aufgeschlüsselt bedeutet dies: λx + (1− λ)y ∈ F

• somit muss (i) erfüllt sein

• außerdem muss gelten:

f [λx + (1− λ)y] ≤ λz + (1− λ)w

• mit z = f (x) und w = f (y) folgt die Notwendigkeit von (ii).

• offensichtlich ist (ii) zusammen mit (i) aber auch hinreichend.

7 / 84

konvexe Funktionen

Lemma 2Die konvexen Funktionen f : F → R bilden einen Kegel.

Beweis:

• mit f ist auch λf konvex, für λ ≥ 0

• mit f1 und f2 ist auch f1 + f2 konvex

8 / 84

konvexe Funktionen

Gliederung





• Dualität



9 / 84

konvexe Funktionen• Lemma 1 zeigt, dass Konvexität von Funktionen eine

„eindimensionale“ Eigenschaft ist

• das Lemma lässt sich auch wie folgt formulieren:

Lemma 3Sei F konvex und f : F → R. Dann ist f genau dann konvex, wenn für allex ∈ F und alle h ∈ Rn die Funktion

fh(t ) = f (x + th)

konvex ist auf dem Intervall {t | x + th ∈ F}.

• es reicht also, sich auf Richtungen zu beschränken

• dies führt zur Untersuchung von differenzierbaren Funktionen

10 / 84

konvexe Funktionen

Lemma 4Sei F konvex und f : F → R differenzierbar. f ist genau dann konvex,wenn gilt:

f (y) ≥ f (x) +∇f (x)(y − x) für alle x, y ∈ F . (1)

Beweis:

• sei f konvex und seien x, y ∈ F

• dann gilt für alle λ mit 0 ≤ λ ≤ 1

f (λy + (1− λ)x) ≤ λf (y) + (1− λ)f (x)

• damit ergibt sich für 0 < λ ≤ 1:

f`x + λ(y − x)

´− f (x)

λ≤ f (y)− f (x)

• mit λ→ 0 folgt:∇f (x)(y − x) ≤ f (y)− f (x)

• die Bedingung ist also notwendig. 11 / 84

konvexe Funktionen• umgekehrt gelte für alle a, b ∈ F

f (b) ≥ f (a) +∇f (a)(b− a) (1)

• wähle x, y ∈ F und ein λ ∈ [0, 1]

• sei a = λx + (1− λ)y

• indem wir in (1) einmal b = x setzen und einmal b = y, folgt

f (x) ≥ f (a) +∇f (a)(x − a) (2)

f (y) ≥ f (a) +∇f (a)(y − a) (3)

• Multiplikation von (2) mit λ und von (3) mit 1− λ und Addition ergibt

λf (x) + (1− λ)f (y) ≥ f (a) +∇f (a)`λx + (1− λ)y − a

´• Rücksubstitution von a = λx + (1− λ)y liefert

λf (x) + (1− λ)f (y) ≥ f (λx + (1− λ)y).

12 / 84

konvexe Funktionenf (y) ≥ f (x) +∇f (x)(y − x) für alle x, y ∈ F . (1)

xy

f(x)

13 / 84

konvexe Funktionen

Für den eindimensionalen Fall ergibt sich daraus:

Korollar 5Sei f : (a, b)→ R differenzierbar. f ist genau dann konvex, wenn dieAbleitung f ′(x ) auf (a, b) monoton wächst.

Beweis:

• sei x < y

• nach (1) gilt f (y ) ≥ f (x ) + f ′(x )(y − x )

• somit:f (y )− f (x )

y − x≥ f ′(x )

• mit y → x folgt f ′(y ) ≥ f ′(x )

14 / 84

konvexe Funktionen

• zum Beweis der Rückrichtung zeigen wir nach Lemma 4:

f (y ) ≥ f (x ) + f ′(x )(y − x ) für alle x , y ∈ (a, b)

• wir nehmen wieder x < y an (y < x geht analog)

• nach dem Mittelwertsatz existiert ein x < ξ < y mit

f ′(ξ) =f (y )− f (x )

y − x

• wegen der Monotonie ist f ′(x ) ≤ f ′(ξ) und somit

f (y ) ≥ f (x ) + f ′(x )(x − y )

15 / 84

konvexe Funktionen

Gliederung





• Dualität



16 / 84

konvexe Funktionen

• sei Q = [qij ] ∈ Rn×n eine symmetrische Matrix und c ∈ Rn

• eine Funktion f : Rn → R heißt quadratisch, wenn f von der Formist:

f (x) =12

xT Qx − cT x =12

nXi=1

nXj=1

qij xi xj −nX

j=1

cj xj .

• f (x) hat den Gradienten

∇f (x) = xT Q − cT

• nach Lemma 4 ist f genau dann konvex, wenn gilt:

12

yT Qy − cT y = f (y)

≥ f (x) +∇f (x)(y − x)

=12

xT Qx − cT x + xT Q(y − x)− cT (y − x)

17 / 84

konvexe Funktionen• somit ist f genau dann konvex, wenn für alle x, y ∈ Rn gilt:

(y − x)T Q(y − x) ≥ 0.

• eine Matrix Q heißt positiv semidefinit, wenn für alle x ∈ Rn gilt:

xT Qx =nX

i=1

nXj=1

qij xi xj ≥ 0.

• also erhalten wir mit dieser Terminologie:

Proposition 6

Die quadratische Funktion f (x) = 12 xT Qx − cT x ist genau dann konvex,

wenn Q positiv semidefinit ist.

18 / 84

konvexe Funktionen

Da die Nullmatrix Q = 0 trivialerweise positiv semidefinit ist, folgt:

Korollar 7Jede lineare Funktion ist konvex.

Die Konvexität linearer Funktionen lässt sich natürlich viel einfacher direkt be-weisen . . .

19 / 84

konvexe Funktionen

Gliederung



• freie Minimierung• Minimierung über Teilräumen

• Beispiele

• Dualität



20 / 84

Minimierung konvexer Funktionen

• sei f : F → R eine differenzierbare konvexe Funktion und x ∈ F

• x heißt lokales Minimum von f , wenn es ein ε > 0 gibt mit:

f (x) ≤ f (y) für alle y ∈ F mit ‖x − y‖ ≤ ε. (4)

• x heißt globales Minimum von f über F , wenn

f (x) ≤ f (y) für alle y ∈ F . (5)

x x x1 2 3

21 / 84


• sei f : F → R eine differenzierbare konvexe Funktion

• wir betrachten das Problem

minx∈F

f (x).

• wir beschränken uns auf das Minimierungsproblem

• das Maximierungsproblem ist für allgemeine konvexe Funktionen sehrviel schwerer zu lösen

22 / 84


• im Allgemeinen sind wir nur in der Lage, Aussagen über lokale Minimazu machen

• für konvexe Funktionen jedoch gilt:

Lemma 8Sei f : F → R eine konvexe Funktion. Dann gilt:

(i) jedes lokale Minimum ist auch ein globales Minimum,

(ii) die Menge der globalen Minima ist konvex.

23 / 84

Minimierung konvexer Funktionen(i) jedes lokale Minimum ist auch ein globales Minimum,

(ii) die Menge der globalen Minima ist konvex.

Beweis:

(i) sei x ∈ F ein lokales Minimum

• angenommen es existiert ein y ∈ F mit f (y) < f (x)

• dann gilt für alle 0 < λ ≤ 1:

f (λy + (1− λ)x) ≤ λf (y) + (1− λ)f (x) < f (x),

• im Widerspruch zur lokalen Minimalität von x

(ii) sei x, y ∈ F globale Minima

• dann folgt aus der Konvexität von f :

f (λy + (1− λ)x) ≤ λf (y) + (1− λ)f (x) = f (x),

• damit ist die Menge der Minima konvex24 / 84


• welche Bedingungen muss der Punkt x ∈ F erfüllen, damit er alsMinimum in Frage kommt?

• wir betrachten zuerst den Fall allgemeiner Funktionen f

• sei x ∈ F und sei h ∈ Rn

• h heißt zulässige Richtung (in x), falls

x + h ∈ F

Lemma 9 (notwendige Bedingung 1. Ordnung)

Sei f : F → R stetig differenzierbar und x ∈ F ein lokales Minimum. Danngilt für jede zulässige Richtung h:

∇f (x)h ≥ 0.

25 / 84


• sei h eine zulässige Richtung

• dann ist x + th ∈ F für alle 0 ≤ t ≤ 1

• für 0 ≤ t ≤ 1 sei p(t) = f (x + th)

• dann hat p ein lokales Minimum in 0

• es ist

p(t)− p(0) = p′(0)t + o(t) (6)

• wäre p′(0) < 0, so wäre (6) negativ für kleine t

• im Widerspruch zur Minimalität von x

• somitp′(0) = ∇f (x)h ≥ 0

26 / 84


• der Beweis beruht auf einer lokalen Approximation 1. Ordnung(Linearisierung)

• entsprechend lassen sich auch Bedingungen 2. Ordnung formulieren

• sie basieren auf lokaler quadratischer Approximation

• bei der notwendigen Bedingung 1. Ordnung gilt weiter:

• liegt das lokale Minimum im Innern von F , so folgt

∇f (x) = 0.

• für konvexe Funktionen ist die Bedingung auch hinreichend:

27 / 84


Satz 10x ∈ F minimiert die differenzierbare konvexe Funktion f : F → R genaudann, wenn für alle h mit x + h ∈ F gilt:

∇f (x)h ≥ 0 (7)

Beweis:

• sei x ∈ F ein Punkt, der die Bedingung erfüllt

• für jedes andere y ∈ F gilt dann (mit h = y− x) wegen der Konvexitätvon f :

f (y) ≥ f (x) +∇f (x)h ≥ f (x).

28 / 84

konvexe Funktionen

Gliederung



• Beispiele

• Dualität



29 / 84


• sei f : F → R konvex und differenzierbar

• wir betrachten den Fall, dass F ein affiner Teilraum von Rn ist:

F = {x ∈ Rn | Ax = b} (A ∈ Rm×n , b ∈ Rm)

• dann gilt für jedes x ∈ F und jede zulässige Richtung h ∈ Rn :

x + h ∈ F ⇐⇒ x − h ∈ F ⇐⇒ h ∈ ker A.

• nach Satz 10 minimiert der Punkt x ∈ F f genau dann, wenn

∇f (x)h =nX

j=1

∂f (x)

∂xjhj = 0 für alle h ∈ ker A. (8)

30 / 84


∇f (x)h =nX

j=1

∂f (x)

∂xjhj = 0 für alle h ∈ ker A (8)

• die Bedingung (8) besagt:

∇f (x) ist orthogonal zu ker A

⇐⇒ ∇f (x) liegt im Zeilenraum von A

⇐⇒ ∇f (x) ist eine Linearkombination der Zeilen aTi von A

• damit erhalten wir die zu (8) äquivalente Optimalitätsbedingung:

∇f (x) = yT A =mX

i=1

yi aTi (9)

für einen geeigneten Vektor yT = [y1, . . . , ym].

31 / 84


Korollar 11Sei F = {x ∈ Rn | Ax = b} ein affiner Raum. x ∈ F minimiert diedifferenzierbare konvexe Funktion f : F → R genau dann, wenn für einy ∈ Rm gilt:

∇f (x) = yT A =mX

i=1

yi aTi (9)

32 / 84


Spezialfall:

• wir betrachten wiederum das Problem

minx∈F

f (x)

mit F = {x ∈ Rn | Ax = b} und f : F → R konvex

• sei f (x) = 12 xT Qx − cT x eine quadratische konvexe Funktion

• dann ist ∇f (x) = xT Q − cT

• nach (9) ist x ein Minimum, wenn es ein y gibt mit ∇f (x) = yT A

• damit muss nur das folgende (lineare) Gleichungssystem gelöst werden:

Qx − AT y = cAx = b

33 / 84

konvexe Funktionen

Gliederung




• Beispiele

• Dualität



34 / 84


1. Projektionen auf (affine) Teilräume

• sei p ∈ Rn ein Vektor und F = {x ∈ Rn | Ax = b} ein Teilraum

• die Projektion von p auf F ist ein Vektor p̂, der den (euklidischen)Abstand zu F minimiert:

‖p− p̂‖2 = minx∈F‖p− x‖2.

• es ist‖p− x‖2 = (p− x)T (p− x) = pT p− 2pT x + xT x

• somit reduziert sich die Berechnung von p̂ auf das konvexeMinimierungsproblem:

min f (x) =12

xT x − pT x

s.d. Ax = b.

35 / 84


min f (x) =12

xT x − pT x s.d. Ax = b.

• damit ergibt sich p̂ als Lösung von

x − AT y = pAx = b

• einsetzen von x = p + AT y führt auf das Gleichungssystem

Ap + AAT y = b

• bzw. mit A = AAT und b = b− Ap:

Ay = b

36 / 84


2. Regressionsprobleme

• wir betrachten folgende Aufgabenstellung:

• bestimme eine „beste“ Lösung des linearen Gleichungssystems

Ax = b

• d.h. wir suchen ein x ∈ Rn derart, dass der Abstand ‖b− Ax‖ soklein wie möglich ist:

minx∈Rn‖b− Ax‖2 = bT b− 2bT Ax + xT AT Ax.

• setzen wir cT = bT A und Q = AT A, dann ist das Problem äquivalentzu

minx∈Rn

f (x) =12

xT Qx − cT x.

37 / 84


• per Definition gilt xT Qx = xT AT Ax = ‖Ax‖2 ≥ 0

• damit ist Q positiv semidefinit und folglich f konvex

• also folgt:

• x ∈ Rn löst das Regressionsproblem genau dann, wenn gilt:

Qx = c bzw. AT Ax = AT b.

• das Regressionsproblem reduziert sich also auf das Lösen des linearenGleichungssystems Qx = c.

38 / 84


Beispiel (Interpolation)

• wir gehen von einer (unbekannten) Funktion f : R→ R aus,

• f ist an m Stützstellen t1, . . . , tm ausgewertet worden

• seien yi = f (ti )

• ferner seien n Funktionen f1(t), . . . , fn(t) gegeben

• gesucht ist eine Linearkombination

f̂ (t) =nX

j=1

aj fj (t)

• die f an den Stützstellen bestmöglich interpoliert

39 / 84


• also suchen wir die beste Lösung (in den Unbekannten a1, . . . , an) deslinearen Gleichungssystems

a1f1(t1) + a2f2(t1) + . . . + an fn(t1) = y1

a1f1(t2) + a2f2(t2) + . . . + an fn(t2) = y2...

......

...a1f1(tm) + a2f2(tm) + . . . + an fn(tm) = ym

• bezeichne F die Matrix, y die rechte Seite und a den Vektor derUnbekannten

• dann haben wir das folgende lineare Gleichungssystem zu lösen:

F T F a = F T y.

40 / 84


als Spezialfälle ergeben sich:

lineare Regression

• n = 2 und {f1(t), f2(t)} = {1, t}

• konstruiere die Regressionsgerade:

f̂ (t) = a1 + a2t

quadratische Regression

• n = 3 und {f1(t), f1(t), f2(t)} = {1, t , t 2}

• konstruiere das quadratische Regressionspolynom

f̂ (t) = a1 + a2t + a3t 2.

41 / 84

konvexe Funktionen

Gliederung



• Dualität

• Lagrange-Dualität

• lineare Programme



42 / 84

Dualität

• seien f , g1, . . . , gm : Rn → R konvexe und differenzierbare Funktionen

• sei g(x) = (g1(x), . . . , gm(x))

• wir betrachten das folgende allgemeine mathematischeOptimierungsproblem:

min f (x)g(x) ≤ 0 (10)

• damit betrachten wir ein konvexes Minimierungsproblem über demZulässigkeitsbereich

F = {x ∈ Rn | gi (x) ≤ 0, 1 ≤ i ≤ m}

• korrekterweise sollte man „inf “ und „sup “ verwenden

• die Verwendung von „min “ und „max “ hat sich in der Literatureingebürgert

43 / 84

Dualität

• wir wollen versuchen, untere Schranken für das Minimum in (10) zubestimmen

• seien dazu x ∈ F und y ≥ 0

• dann gilt sicherlichmX

i=1

yi gi (x) = yT g(x) ≤ 0

• damit liefert jedes y ≥ 0 eine untere Schranke L(y):

minx∈F

f (x) ≥ minx∈F

f (x) + yT g(x)

≥ minx∈Rn

f (x) + yT g(x)

=: L(y)

44 / 84

Dualität

• mit f und den gi , i = 1, m, ist auch f (x) + yT g(x) konvex

• für y ≥ 0 ist somit die Berechnung von

L(y) = minx∈Rn

f (x) + yT g(x)

ein freies konvexes Minimierungsproblem

• für jedes y ≥ 0 liefert L(y) eine untere Schranke

• eine beste untere Schranke erhalten wir durch das duale Problem:

maxy≥0

L(y) = maxy≥0

minx∈Rn

f (x) +mX

i=1

yi gi (x) (11)

• das ursprüngliche Problem (10) wird dann als das primale Problembezeichnet

45 / 84

Dualität

maxy≥0

L(y) = maxy≥0

minx∈Rn

f (x) +mX

i=1

yi gi (x) (11)

Bemerkung:

• das duale Problem ist wiederum ein konvexes Optimierungsproblem(über dem nichtnegativen Orthanten)

• dazu heiße eine Funktion f konkav, wenn −f konvex ist

• die Maximierung einer konkaven Funktion ist damit äquivalent zurMinimerung einer konvexen Funktion

46 / 84

Dualität

Lemma 12L(y) = minx∈Rn f (x) + yg(x) ist konkav.

Beweis:

• seien y1, y2 ∈ Rm+ und λ ∈ (0, 1)

• angenommen für y = λy1 + (1− λ)y2 gilt:

L(y) = L(λy1 + (1− λ)y2) < λL(y1) + (1− λ)L(y2)

• per Definition istL(y) = min

x∈Rnf (x) + yT g(x)

• damit existiert ein x so, dass

f (x) + yT g(x) < λL(y1) + (1− λ)L2(y2)

47 / 84

Dualitäty = λy1 + (1− λ)y2

f (x) + yT g(x) < λL(y1) + (1− λ)L(y2)

• ebenfalls per Definition gilt:

f (x) + yT1 g(x) ≥ min

xf (x) + yT

1 g(x) = L(y1)

f (x) + yT2 g(x) ≥ min

xf (x) + yT

2 g(x) = L(y2)

• Multiplikation mit λ und 1− λ führt zum Widerspruch.

• x heißt primal zulässig, falls g(x) ≤ 0

• y heißt dual zulässig, falls y ≥ 0

• zwischen primalem und dualem Problem besteht die folgendeBeziehung

48 / 84

Dualität

Satz 13 (schwache Dualität)

Seien x ∈ F und y ≥ 0 primal bzw. dual zulässig. Dann gilt:

(i) L(y) ≤ f (x)

(ii) gilt L(y) = f (x), so sind x und y primal bzw. dual optimal mityT g(x) = 0.

Beweis: Jedes y ≥ 0 liefert eine untere Schranke:

L(y) = minz∈Rn

f (z) + yT g(z)

≤ minz∈F

f (z) + yT g(z)

≤ f (x) + yT g(x)

Daraus folgen die Behauptungen.

Die Bedingung yT g(x) = 0 wird auch als Komplementarität bezeichnet.

49 / 84

Dualität• für festes y ≥ 0 ist die Berechnung von

L(y) = minx∈Rn

f (x) + yT g(x)

eine konvexes Minimierungsproblem

• daher gilt die Gleichheit L(y) = f (x) + yT g(x) genau dann, wennx ∈ Rn die Optimalitätsbedingung erfüllt:

∇f (x) +mX

i=1

yi∇gi (x) = 0T . (12)

• damit können wir das duale Problem umformulieren zu:

maxy≥0

f (x) +mX

i=1

yi gi (x) (13)

s.d. ∇f (x) +mX

i=1

yi∇gi (x) = 0T

50 / 84

konvexe Funktionen

Gliederung



• Dualität

• Lagrange-Dualität




51 / 84

Dualität• wir betrachten zur Veranschaulichung ein lineares Optimierungsproblem

max cT xAx ≤ b

(14)

• sei f (x) = −cT x und gi (x) = aTi x − bi

• das daraus abgeleitete allgemeine duale Probgramm lautet:

maxy≥0

f (x) +mX

i=1

yi gi (x) s.d. ∇f (x) +mX

i=1

yi∇gi (x) = 0T . (11)

• in unserem Spezialfall führt dies zu

maxy≥0

− cT x + yT (Ax − b) s.d. − cT + yT A = 0T .

• einsetzen von yT A = cT in die duale Zielfunktion ergibt die folgendeForm des dualen Problems:

min bT y s.d. AT y = c, y ≥ 0

52 / 84

Dualität• damit führt das primale lineare Problem

max cT xAx ≤ b

(15)

• zu dem dualen linearen Programm

min bT yyT A = c

y ≥ 0

• wegen cT = yT A ergibt die schwache Dualität:

f (x) = −cT x ≥ −cT x + yT (Ax − b) = −yT b

• bzw. cT x ≤ bT y

53 / 84

Dualität

Lemma 14 (Komplementarität für lineare Programme)

Seien x und y primal bzw. dual zulässig. Dann sind x und y genau dannprimal bzw. dual optimal, wenn die Komplementarität gilt

yT (Ax − b) = 0.

Beweis:

• aus der Komplementarität folgt die Optimalität:

cT x − yT b = (AT y)T x − yT b = yT (Ax − b) = 0

• umgekehrt folgt aus der Optimalität:

0 = cT x − yT b = (AT y)T x − yT b = yT (Ax − b).

54 / 84

konvexe Funktionen

Gliederung



• Dualität


• KKT-Bedingungen• Programme mit linearen Nebenbedingungen



55 / 84

Optimalitätsbedingungen

• im linearen Fall haben wir gerade gesehen:

• primale und duale Zulässigkeit und Komplementarität implizierenOptimalität

• wir wollen diesen Ansatz auf allgemeine konvexeOptimierungsprobleme übertragen

• wir suchen x, y so, dass

• x primal zulässig ist

• y dual zulässig ist

• beide die Komplementaritätsbedingung erfüllen

• d.h. es muss gelten:

56 / 84


Karush-Kuhn-Tucker-Bedingungen (KKT-Bedingungen)

∇f (x) +mX

i=1

yi∇gi (x) = 0T

yT g(x) = 0 (16)

g(x) ≤ 0y ≥ 0

• seien x, y so, dass sie die KKT-Bedingungen erfüllen

• dann heißt x KKT-Punkt des Optimierungsproblems

minx∈Rn

f (x) s.d. g(x) ≤ 0 (10)

57 / 84


Proposition 15

Sei x∗ ein KKT-Punkt mit zugehörigem y∗ ≥ 0. Dann ist x∗ eineOptimallösung des konvexen Minimierungsproblems (10).

Beweis:

• x∗ erfüllt alle Restriktionen gi (x∗) ≤ 0 für i = 1, . . . , m

• x∗ minimiert die konvexe Funktion f (x) + y∗T g(x)

• wegen der Komplementarität folgt:

f (x∗) = f (x∗) + y∗T g(x∗) = L(y∗)

• mit der schwachen Dualität folgt daraus die Minimalität von f (x∗).

58 / 84


Zwischenfazit

Für die KKT-Bedingungen gilt: sie sind

• im konvexen Fall hinreichend

• im linearen Fall hinreichend und notwendig

• in allgemeinen (nicht-konvexen) Fall weder hinreichend noch notwendig

Wir zeigen als nächstes, dass sie im konvexen Fall unter linearen Nebenbe-dingungen auch notwendig sind.

59 / 84

konvexe Funktionen

Gliederung



• Dualität





60 / 84


• seien jetzt speziell gi (x) = aTi x − bi , 1 ≤ i ≤ m

• in kompakter Schreibweise g(x) = Ax − b ≤ 0

• der Zulässigkeitsbereich ist das Polyeder

F = P(A, b) = {x ∈ Rn | Ax ≤ b}

• ist x ∈ F Optimallösung, so muss gelten:

x + h ∈ F =⇒ ∇f (x)h ≥ 0 bzw.

A(x + h) ≤ b =⇒ ∇f (x)h ≥ 0 bzw.

Ah ≤ b− Ax =⇒ ∇f (x)h ≥ 0

• maW: die Ungleichung −∇f (x)h ≤ 0 wird von Ah ≤ b− Ax impliziert

61 / 84


• maW: die Ungleichung −∇f (x)h ≤ 0 wird von Ah ≤ b− Ax impliziert

• nach dem Farkas-Lemma existiert dann ein y ≥ 0 so, dass

yT A = −∇f (x)

yT (b− Ax) ≤ 0

• da y ≥ 0 und b− Ax ≥ 0 ist die letzte Ungleichung äquivalent zu

yT (b− Ax) = 0

62 / 84


• damit erfüllen x und y notwendigerweise die folgenden Bedingungen:

∇f (x) + yT A = 0yT (Ax − b) = 0

Ax ≤ by ≥ 0

• dies sind genau die KKT-Bedingungen für Ungleichungsrestriktionen

• somit:

Satz 16Die KKT-Bedingungen sind hinreichend und notwendig dafür, dass x∗ eineOptimallösung eines konvexen Optimierungsproblems folgender Form ist:

minx∈Rn

f (x) s.d. Ax ≤ b.

63 / 84


Gliederung



• Dualität





64 / 84


Bemerkung:

• ist f (x) nichtlinear, dann ergeben die KKT-Bedingungen (selbst beilinearen Restriktionen) ein nichtlineares Ungleichungssystem.

• betrachten wir jedoch ein lineares Programm

max cT xAx ≤ b

(17)

• dann ergeben die KKT-Bedingungen das lineare Ungleichungssystem

AT y = ccT x − bT y = 0Ax ≤ b

y ≥ 0

65 / 84

LP-Dualität

• die KKT-Bedingungen reduzieren das Lösen eines linearen Programmsauf das Lösen eines linearen Ungleichungssystems

• damit kann man also im Prinzip lineare Programme mit demFM-Verfahren lösen

• umgekehrt kann natürlich jeder LP-Algorithmus dazu benutzt werden,ein lineares Ungleichungssystem zu lösen

• man braucht ja nur eine künstliche Zielfunktion einführen, z.B.

Ax ≤ b ←→ max 0T x s.d. Ax ≤ b.

• also folgt:

• das Lösen von linearen Programmen und das Lösen von (endlichen)linearen Ungleichungssystemen sind algorithmisch äquivalent

66 / 84

konvexe Funktionen

Gliederung



• Dualität



67 / 84

LösungsverfahrenZur Erinnerung:

• zur Lösung eines konvexen Optimierungsproblems reicht es, einenKKT-Punkt zu berechnen

• dazu müssen nichtnegative Lösungen eines nichtlinearenGleichungssystems bestimmt werden

• ein solches Gleichungssystem hat die allgemeine Form:

F (x) = 0, x ≥ 0

• hierbei ist F : Rn → Rm eine Funktion, die aus mKoordinatenfunktionen fi : Rn → R zusammengesetzt ist:

F (x) =

264 f1(x)...

fm(x)

375 ∈ Rm .

68 / 84

Lösungsverfahren

• die exakte Lösung eines nichtlinearen Gleichungssystems ist imallgemeinen sehr schwierig

• oft genügt aber schon eine „hinreichend gute“ approximative Lösung

• wir betrachten im folgenden zwei Spezialfälle:

• nichtlineare Gleichungssysteme ohne Vorzeichenbeschänkung

• KKT-Bedingungen von linearen Programmen

69 / 84

konvexe Funktionen

Gliederung



• Dualität



• das Newton-Verfahren

• die Methode der inneren Punkte

70 / 84

Lösungsverfahren• wir suchen eine approximative Lösung des Systems

F (x) = 0

• wir verwenden dazu den Ansatz des Newton-Verfahrens

• zur Erinnerung der eindimensionale Fall:

xxx012

71 / 84

Lösungsverfahren

Vorgehensweise des Newton-Verfahrens

• in jedem Punkt xi konstruiere eine lineare Approximation vonF bei xi

• d.h. eine Matrix Ai derart, dass

F (xi + h) ≈ F (xi ) + Ai h (für ‖h‖ hinreichend klein),

• berechne eine Lösung hi des linearen Gleichungssystems

Ai h = −F (xi )

• setze anschließend xi+1 = xi + hi

72 / 84

Lösungsverfahren

Newton-Verfahren

(1) starte mit einem Punkt x0 und i = 0

(2) while F (xi ) 6≈ 0 do

(3) wähle eine lineare Approximation von F im Punkt xi ,

(4) sei hi eine Lösung des Gleichungssystems Ai h = −F (xi )

(5) setze xi+1 = xi + hi

(6) end while

73 / 84

Lösungsverfahren

Beispiel

• wir suchen eine Lösung der Gleichung

f (x ) = x 2 − 2 = 0.

• beginne mit einem x0

• sei xk schon berechnet

• wähle z.B. Ak = f ′(xk )

• dann folgt

f ′(xk )h = −f (xk ) d.h. hk =−f (xk )

f ′(xk )=−x 2

k + 22xk

• und somitxk+1 = xk + hk =

xk

2+

1xk

.

74 / 84

Lösungsverfahrenf (x ) = x 2 − 2 = 0.

Schritt k f (xk )

0 1000, 00000000002 500, 00100000003 250, 00249999604 125, 00524995805 62, 51062464306 31, 27130960217 15, 66763299498 7, 89764234799 4, 075441240510 2, 283092824411 1, 579548752412 1, 422866579613 1, 414239873614 1, 414213562615 1, 414213562416 1, 4142135624

75 / 84

Lösungsverfahren

Bemerkung

• sei F differenzierbar,

• dann wird oft die Jacobimatrix gewählt,

• sie hat als Zeilen gerade die m Gradienten ∇fi (xk ):

Ak = ∇fi (xk ) =

»∂fi (xk )

∂xj

–∈ Rm×n

• im allgemeinen hat man keine Garantie, dass das Newtonverfahrentatsächlich zu einer zulässigen Lösung der Ausgangsgleichungkonvergiert

76 / 84

konvexe Funktionen

Gliederung



• Dualität



• das Newton-Verfahren

• die Methode der inneren Punkte

77 / 84

Lösungsverfahren• wir wollen einen KKT-Punkt für das folgende lineare Programm

bestimmen:max cT xAx ≤ b

(18)

• die KKT-Bedingungen lauten:

AT y = ccT x − bT y = 0Ax ≤ b

y ≥ 0

• mit s = b− Ax und µ = 0 ist dies äquivalent zu:

si yi = µ (i = 1, . . . , m)Ax + s = b

AT y = cs, y ≥ 0

(19)

78 / 84

Lösungsverfahrensi yi = µ (i = 1, . . . , m)

Ax + s = bAT y = cs, y ≥ 0

(19)

• wir relaxieren nun, indem wir

• einen Parameter µ > 0 wählen und

• das resultierende System mit einem Newtonverfahren zu lösenversuchen

• wir müssen in diesem Fall immer si > 0 und yi > 0 (d.h. s, y > 0)sicherstellen

• deshalb spricht man von „inneren Punkten“ (des positiven Quadrantenvon Rm).

79 / 84

Lösungsverfahren

Lemma 17Sei (xµ, yµ, sµ) eine Lösung des Systems (19) zu µ > 0. Dann ist xµ einezulässige Lösung des linearen Programms. Für jede andere zulässigeLösung x gilt

cT xµ ≥ cT x − ε (mit ε ≤ mµ).

Beweis:

• die Zulässigkeit folgt aus der Definition

• aus der schwachen Dualität folgt

cT x ≤ bT yµ = (Axµ+sµ)T yµ = (xµ)T AT yµ+(sµ)T yµ = cT xµ+mµ.

Im Fall µ→ 0 sind die xµ also annähernd optimale Lösungen des ursprüng-lichen linearen Programms.

80 / 84

Lösungsverfahren• wir wollen (19) mit einem Newtonansatz lösen

• wir gehen davon aus, dass wir bereits Vektoren y > 0 und x zurVerfügung haben mit der Eigenschaft

c = AT y und s = b− Ax > 0.

• wir suchen dann ∆x, ∆y, ∆s so, dass

(si + ∆si )(yi + ∆yi ) = µ (i = 1, . . . , m)A(x + ∆x) + (s + ∆s) = b

AT (y + ∆y) = cs + ∆s, y + ∆y ≥ 0

(20)

81 / 84

Lösungsverfahren(si + ∆si )(yi + ∆yi ) = µ (i = 1, . . . , m)

A(x + ∆x) + (s + ∆s) = bAT (y + ∆y) = c

s + ∆s, y + ∆y ≥ 0

(20)

• nach Annahme gilt Ax + s = b und AT y = c

• damit reduziert sich dieses System auf:

si ∆yi + yi ∆si + ∆si ∆yi = µ− si yi (i = 1, . . . , m)A∆x + ∆s = 0

AT ∆y = 0s + ∆s, y + ∆y ≥ 0

(21)

82 / 84

Lösungsverfahren• damit reduziert sich dieses System auf:

si ∆yi + yi ∆si + ∆si ∆yi = µ− si yi (i = 1, . . . , m)A∆x + ∆s = 0

AT ∆y = 0s + ∆s, y + ∆y ≥ 0

(21)

• das letztere System relaxieren wir nun zu dem linearenGleichungssystem

si ∆yi + yi ∆si = µ− si yi (i = 1, . . . , m)A∆x + ∆s = 0

AT ∆y = 0(22)

83 / 84

Lösungsverfahren

• mit dessen Lösung schreiben wir fort:

x+ = x + ∆x, y+ = y + ∆y, s+ = ∆s

• und verfährt nun wie zuvor mit x+ und y+ anstelle von x und y

• wobei man in jeder Iteration auch den Parameter µ reduziert, bis maneine hinreichend gute Lösung x des Ausgangsproblems gefunden hat

• liegt si yi nahe an µ, so kann man zeigen:

• s+i y +

i liegt noch näher an µ

• y+ > 0, s+ > 0

• das Verfahren konvergiert sehr schnell gegen eine optimaleLösung des Ausgangsproblems

84 / 84

Documents

Operations Research Konvexe Funktionen · Operations Research Rainer Schrader Zentrum für Angewandte Informatik Köln 4. Juni 2007 1/84 Konvexe Funktionen 2/84 konvexe Funktionen