Duale Optimierungsaufgaben und Sattelpunkts/itze Von W. VOGEL,Bonn

1)

Eingegangen am 29. November 1968

Zusammenfassung: Es wird der formale Zusammenhang zwischen der Existenz eines Sattelpunktes und einem Paar dualer Optimierungsaufgaben angegeben. Dabei werden Voraussetzungen wie konvex oder konkav nicht ben6tigt. Die Theorie ist so aufgezogen, dab die FENCHELsche Theorie der konjugierten Funktionen gut in diesen Rahmen eingebaut werden kann. An vieten Beispielen wird der Zusammenhang mit bekannten Dualit/itss~itzen dargestellt.

Summary: We treat the formal relations between the existence of a saddle-point and a pair of dual programming problems without using assumptions like convex or concave. The theory is built in such a way, that FENCHELS theory of conjugate functions fits very well in its frame. The relationship between the theory and other well known duality theorems are explained by many examples.

°

Die M engen 99lx C 9t" und 9J/z C ~R" mit x E 9311und y ~ ~J2R2 sollen durch die Funktionen zc(x) und a (y) in die reelle Zahlengerade abgebildet werden. Wir betrachten die beiden Aufgaben suche

max {~(x) lxEgJ~l}

suche

rain {a(y) lyegJ~2}.

und Die Struktur dieser beiden Aufgaben sei derart, dab aus x ~ ~lJt1 und y ~ gJt2 stets die Ungleichung rc (x) _< a (y) folgt. Es ist dann jedenfalls sup {re (x)[ x e 92R~} _< inf {a (y)[ y ~ ~J~2}, Ein Satz, welcher hinreichende (oder notwendige und hinreichende) Bedingungen ftir das Bestehen der Gleichung max {re(x) ] x ~ 9)t~} = min {a(y) [ y s g)12} oder auch der Gleichung sup {~ (x) I x ~ ~11} = inf {a (Y) I Y ~ 9Jr2} angibt, soll ein Dualitiitssatz genannt werden. 1) Prof. Dr. W. VOGEL,Institut fiir angewandte Mathematik, 53 Bonn, Bonner Talweg 8.

(1.1)

2

W. VOGEL

Wir gehen von den Mengen .,~C~" und R2C~" aus. Die Funktion 4'(x,y) bilde RI x Rz in die reelle Zahlengerade ab. Ein Satz, welcher hinreichende (oder notwendig und hinreichende) Bedingungen t'fir das Bestehen der Gleichung min

max 4'(x,y) = max

min ~,(x,y)

y~

x~

y~R 2

1

X~R~

(1.2)

angibt, wird als ein Minimax-Theorem bezeichnet. Aus der Gleichung (1.2) folgt bekanntlich die Aussage: Es gibt xo ~ R1 und Yo e R2, so dab fiir alle x s R1 und ftir alley ~ R2 die Ungleichungskette 4'(x, Yo) -< 4' (Xo,Yo) -< 4' (Xo,Y) (1.3) gilt. Man sagt dann auch: Die Funktion ~9(x,y) mit dem Definitionsbereich x e R1 und y ~ R2 hat einen Sattelpunkt. Wir benutzen hier den Ausdruck Sattelpunkt stets im Sinne der Beziehung (1.3). Ein Satz, welcher hinreichende (oder notwendige und hinreichende) Bedingungen f'fir die Aussage (1.3) angibt, soll ein Sattelpunkt- Theorem heiBen. Man kann im allgemeinen nicht v0n (1.3) auf (1.2) zurtickschliel3en. Sei a(y): =max {O(x,y)[x e R1} (1.4) und z (x): = min {4' (x, Y) IY e R2 }. (1.5) Das Maximum o"(y) braucht natiirlich nicht fiir alle Punkte y von R2 zu existieren. Wir bezeichnen mit 931.2 diejenige Teilmenge von •z, fiir welche a(y) existiert. Entsprechend sei 93l1 diejenige Teilmenge von R1, fiir welche z (x) existiert. Dann kann man zeigen: Wenn die Sattelpunktaussage (t.3) gilt, so ist J/g1 ~= 0 und ~ 2 + 0 und es gilt rain

max 4'(x,y)=

max

rain 4'(x,y).

y~Jl 2

x~!~ 1

x~r/~

y~/2

(1.6)

Jetzt ist auch der umgekehrte Schlug m6glich. Wenn die Gleichung (1.6) gilt (wobei 9921und g)lz die oben angegebene Bedeutung haben), so gilt auch die Sattelpunktaussage (1.3). Die Gleichung (1.6) ist gerade die Dualitgtsaussage min {a(y)[y ~ 9)12} = max {z(x) I x ~ 9J/1}.

(1.1)

Wir haben also hier die )kquival~nz einer Sattelpunktaussage mit einer Dualit~itsaussage. Der Zusammenhang zwischen (1.1) und (1.3) ist in einer Reihe von Arbeiten behandelt worden. [KARAMARDIAN; MANGASARIAN; MANGASARIAN-PONSTEIN; STOZR, 1963, 1964]. Der Hauptsatz 1 dieser Arbeit sagt im wesentlichen nur aus, dab (1.1) und (1.3) ~iquivalent sind, doch geben wir dabei der Funktion 4' eine bestimmte Struktur.

Duale Optimierungsaufgabenund Sattelpunktsgtze

3

Wir setzen ~ (x, y) = q) (x, y) - e (x)-/3 (y). In anschlieBenden Beispielen zeigen wir, dab diese Struktur fiir die Anwendung des Satzes besonders vorteilhaft ist. Dies ist der Inhalt yon Abschnitt 2. In Abschnitt 3 wird vorausgesetzt, dab q~symmetrisch ist (d. h. q~(x, y) = (p 0', x)). Dies ftihrt zum Hauptsatz 2. Der Abschnitt 4 zeigt, wie sich die monotone Optimierung in die hier vorgetragene Theorie einordnet. Abschnitt 5 behandelt die ANinderungen, wetche niStig sind, wenn man max und min durch sup und inf ersetzen mul3. Im Abschnitt 6 werden einige Sattelpunkt-Theoreme aufgeftihrt, welche im Zusammenhang mit der obigen Theorie yon Nutzen sind. Wir wollen diesen Abschnitt mit der folgenden Bemerkung schliegen: Wenn die Funktion ~ (x, y) aufR1 x R2 einen Sattelpunkt hat, so liefern die Formeln (1.4) und (1.5) zwei Funktionen 7c und o-, fiir welche die Dualit~itsaussage (1.1) gilt. Seien nun umgekehrt zwei Funktionen ff und ~ mit den Definitionsbereichen 9J~1 und ~f~2 gegeben und sei max {~(x) t x ~ 9Jtl} = rain {6(y) I y ~ g)12} = :c< Wir wollen zeigen: Es gibt stets eine Funktion q)(x, y), ftir welche die Formeln (t.4) und (t.5) gerade ~ und ff liefern. Wir w~ihlen fi derart, dab c~ + fi > 0 ist (gilt e > 0, so setze man/3 = 0). Sei

4, (x, y) = (~ (x) +/~) (~ (y) +/~) und sei R1 = 9J~ und R2 = ~ 2 . Setzt man dies in (1.4) und (1.5) ein, so erhiilt man rc (x) = zc(x) und ~r(y) = 8 (y). Man kann also zu jedem Dualit~its-Satz eine Funktion ~ finden, fiir welche der Sattelpunkt-Satz gilt.

.

Wir gehen aus von zwei Mengen R~Cg~" und ReCW", Im folgenden sei x (bzw. y) stets ein Punkt aus R 1 (bzw. aus Rz). Gegeben seien die Funktionen q~(x, y), e (x) und fi (y). Wir bilden damit rain {~0(x, y ) - fl (y) l Y ~ R2} =/~(x) und max {~o(x, y ) - e (x) l x e R1} = 02(y). Nattirlich braucht/~(x) (bzw. 02(y)) nicht ftir alle Punkte von !~11 (bzw. von R2) zu existieren. Wir bezeichnen mit gJ~aCR1 (bzw. ~2C}12) den Definitionsbereich der Funktionen/~(x) (bzw. 02(y)). Wenn 99l2 = 0 oder 9Jt2 = 0, so werden die folgenden Aussagen inhaltlos. Zur Abkiirzung setzen wir

~,(x,y) = q~(x,y)-~(x)-/~(y).

4

W. VOGEL

Hauptsatz l: Die folgenden drei Aussagen sind ~iquivalent. (i) Es gibt x o e R1 und Yo ~ R2, so dab fiir alle x E R1 und ftir alley e ~t 2 die Ungleichungskette

4' (x, yo) - 4` (xo, yo) -- 4` (Xo, y) gilt. (ii) max {fl(x)- e (x) I x e g-~l} = min {~ ( y ) - fl (y) I Y ~ ~f~2} und ~1~1 + 0

240. (iii) Es gibt x o e 9)11 und Yo ~ gR2, so dab die Gleichungen p(xo, Yo) = c~(Xo) + o2(yo) q (xo, yo) = f l ( y o ) + (Xo)

(2.1)

gelten. Beweis : (i) ~ (iii): Aus

4`'(x,yo) < 4`(xo,Yo)

folgt

~o(x, Yo) - "(x) < ,p(xo, Yo) - "(Xo). Dies zeigt, dab

,p(x,yo) - ~(x) <_ ,p(xo,yo)- ,(Xo). ist. Wit haben gefunden: 5Y/2 + 0 (denn Yo ~ 93t2), und es gilt die erste tier Gleichungen (2.1). Genauso kann man aus 4`(xo,Yo) < 4`(xo,y) folgern: Xo ~ 93/I und es gilt die zweite der Gleichungen (2.1). Damit ist (iii) hergeleitet. (iii) ~ (ii): Wegen (iii) ist 9~1 ~ 0 und 9A2 =~0. Fiir x ~ 9J/1 und y ~ R2 gilt auf Grund der Definition yon fl (x):

~o(x, y) _> fl (y) +/~(x). Far x e R1 und y e ~ 2 gilt entsprechend

,p (x, y) _ ~ (x) + ~ (y). Aus den beiden Ungleichungen folgt sofort

f l ( x ) - . ( x ) <_ ~(y)-fl(y) ftir alle x E 9911 und ftir alle y ~ 93l2. Aus den Gleichungen (2.1) folgt:

fl (Xo)- ~ (Xo) = ~ (yo)- fl (Yo)Mso ist max { f l ( x ) - ~ ( x ) [ x

~ g.ll~} = min {&(y)-fl (y)]y ~ 9)12}.

(ii) ~ (i): Auf Grund yon (ii) gibt es xo s ~ t

und Yo egJ~2 mit

fl (Xo)- ~(Xo) = ~ (yo)- fl (yo).

Duale Optimierungsaufgaben und Sattelpunkts/itze

5

Setzt man hierin die Ungleichungen ~(Xo) <_ q)(xo, y ) - f i ( y ) ffiralle y ~ R 2 und o2(yo) _> q~(x, yo)-Ce(x ) ffir alle x e f t 1 ein, so folgt q~(x, y o ) - ~ (x)-/~ (yo) -< ~ (yo) -/~ (yo) =/~ (Xo)- ~ (Xo) <_ q, (Xo, y)-/~ (y) - ~ (Xo) flit alle x e R1 und alley s R2. Dies ist aber gerade die Sattelpunktsungleichung (i). Wir bezeichnen (i) als die Sattelpunktsaussage und (ii) als die Dualit~itsaussage. Ist (i) bewiesen, so gilt ein Sattelpunkt-Theorem; ist (ii) bewiesen, so gilt ein Dualit~itstheorem. Wit wollen die Aussage (iii) noch etwas umformulieren. Sei 921 = {(x, y) [ ~o (x, y) = ~ (x) + ~(y), x ~ st1, y ~ ~ 2 } .

Entsprechend bilden wir 9/2 = {(x, Y) l q~(x, y) = fl (x) + fl (y), x ~ ~ l, y e Sl2 } . Die Aussage (iii) erhglt dann die Form (iii)'Es gibt x o ~ ) l 1 und yoeg)l 2 mit (xo, yo)eg/1 und (xo, Yo)eg/2. Aus (Xo,Yo) ~ 9.11folgt aber schon Yo e ~J~2 und aus (Xo,Yo) ~ 9/2 folgt schon Xo e 9)ll. Daher l~iBt sich die Bedingung auch folgendermagen ausdriicken: (iii)"

9.11 O 9/2 + 0"

Satz 2.1: Sei ~o(x, y) konkav in x und konvex in y, sei ~ (x) konvex in x und sei fi (y) konkav in y. Alle Funktionen seien differenzierbar nach x und nach y und es sei R1 = {x [x > 0} und R2 = {YlY > 0}. Dann sind die Bedingungen Dxq)(xo, Yo) <_ Dxc~(Xo), D,~o(Xo, Yo) _> Dy/~(yo),

Dxq~(xo, Yo)Xo = Dxo~(Xo)Xo, Dy~o(Xo,Yo)Yo = D,/~(Yo)Yo,

und x o_>0, Yo > 0 notwendig und hinreichend fiir die Gtiltigkeit von (i), (ii) und (iii). Beweis : Die angegebenen Bedingungen sind gerade die zu (i) geh/Srenden KVnN-TVCICERBedingungen. Man sehe dazu KUHN-TUCKER oder VOGEL [1967 b, Satz 2.6]. Setzt man ~ = fl = 0, so liefert der Hauptsatz 1 die folgende Aussage: Korollar 2.2: Sei 9~1 ~ 0 (bzw. 9)l2 @ 0) die Menge der x s ~1 (bzw. der y ~ St2), ftir welche rain {~p(x, Y) IY s ~2} (bzw. max {q~ (x, y) lx ~ R1}) existiert. Die Gleichung rain max ~o(x, y) = max min qo(x, y) y~!lJl2 x a R a xeKIll y a ~ 2

(1.2)

ist notwendig und hinreichend ffir das Bestehen der Sattelpunkt-Aussage (1.3).

6

W. VOGEL

Setzt man 9.I1 = {(x, Y) I ~o(x, y) = max {q) (x, y) lx ~ 5tl, y ~ 2 } } und 9I 2 = {(x, Y) I qo(x, y) = min {cp (x, Y) I Y E Sty, x ~ ~1}}, so ist die Bedingung

911 c~ 912 + 0 ~iquivalent zu (1.3) und (1.2). Beispiet 1: Sei ~0(x,y) = x'Ay, ~(x) = b'x, B(Y) = c'y, 5tl = {x]x >_ 0} und 5t2 = {YlY > 0}. M a n erh~ilt:

]{(x) - min {x'A y - c ' yl y >_ O} = 0 und ~1

=

{ x l A ' x - c >- O,x > 0}.

W e n n n~imlich die i-te K o m p o n e n t e des Vektors A ' x - c kleiner als Null ist, so ist die Linearform y' ( A ' x - c ) auf der Menge y > 0 nach unten nicht beschr~inkt. Entsprechend findet man: ~(y) = max { x ' A y - b ' x I x

> 0} = 0

und

90l2 = { y [ A y - b

< O,y >_ 0}.

Die drei Aussagen yon Hauptsatz 1 lauten jetzt:

O)

O(x,y) = x ' A y - b ' x - c ' y

= -b'x + y'(A'x-c) = -c'y + x'(Ay-b)

mit dem Definitionsbereich x > 0, y > 0 hat einen Sattelpunkt. (ii) oder (iii)

max{-b'xiA'x>c,x>_O}=min{-c'YlAy_O max { c ' y l A y <_ b,y >_ O} = min { b ' x t A ' x > O,x > O}.

}

Es gibt x, y mit A' x >_ c, x > O, A y <_ b, y >_ 0, und y ' ( A ' x - c ) = O,x'(A y - b ) = O.

Hier kann man das Sattelpunkt-Theorem 1 aus Abschnitt 6 anwenden und findet: (i), (ii) und (iii) gelten genau dann, wenn es x und y mit A' x > c, x > 0 und A y _< b, y >_ 0 gibt. BeispieI 2: Sei ~o(x, y) = x' A y und fl (y) = c' y. Wir teilen die K o m p o n e n t e n yon y in zwei G r u p p e n und setzen Y= Entsprechend sei A = (A 1, A2) u n d c = Einschriinkungen}. D a n n wird

Y2

(-) C2

. Sei ferner 512 =

{ylyl -> 0, y2 ohne

Duale Optimierungsaufgaben und Sattelpunkts~itze

7

]~(x) = min { x ' A y - c ' y l y ~ R2} = min { x ' A t y l - c l ' y 1 + x ' A 2 y a - c 2 ' y z l y 1 > 0} = 0 mit 9~l 1 = {xlA'~x > c 1, A'zx = c2, x ~ R ~ } . Zun~ichst sollen a(x) und R1 noch nicht'spezialisiert werden. Die Aussagen von H a u p t s a t z 1 lauten dann: (i) tp(x,y) = x ' A y - c ' y - c ~ ( x ) hat einen Sattel fiir x ~ R~ u n d yt _> 0, (ii) m a x { - ~(x) ] A'~ x > c 1, A~ x = c2, x ~ R1} = min {&(y)- c'y]y ~ ?012}, (iii) wollen wir nicht extra anschreiben. W i r werden jetzt die Aufgabe weiter spezialisieren. Sei e ( x ) = b'x + ½x'Cx u n d R~ = 9t". Hierbei sei C = C' u n d positiv definit. In c~(y) = m a x { x ' A y - b ' x - ½ x' Cx[ x ~ 9t"} k a n n m a n das M a x i m u m berechnen, i n d e m m a n die Ableitung der zu maximierenden F u n k t i o n gleich Null setzt. Dies liefert

Ay-b-Cx

= O.

Also wird

~(y) = ½ ( A y - b ) ' C - t ( A y - b )

und

~ 2 = R2'

Die Dualit~itsaussage (ii) lautet jetzt

max { - b ' x - ½ x' Cx i Ai x > Cl, A ' 2 x = C2) = min {½ ( A y - b)' C -1 ( A y - b ) - c'yly 1 > 0} = min {3 z' C - i z - c ' y l A y - b = z, y~ > O, Y2 ohne Einschr~inkungen}. Schreibt m a n hierfiir die Bedingung (iii) an, so erhiilt m a n : Es gibt x mit A'~x > Cl, A'2x = c2 und y mit yt > 0 , ftir welche die Gleichungen x'Ay = c'y und

x'Ay = ½ ( A y - b ) ' C - ~ ( A y - b ) + ½ x ' C x - b ' x gelten. N a t i M i c h wird m a n bier statt (iii) lieber die KuHN-TUcKER-Bedingungen benutzen. Sie lauten: A y - b - C x = O, A'2x-c2 = O, A i x - c l > 0 u n d y'~( A i x - q ) = O.

Beispiel 3: Wir wollen n u n eine Dualit~itsaussage ftir quadratisches O p t i m i e r e n herleiten, bei der die M a t r i x C d e r quadratischen F o r m keine Inverse zu besitzen braucht. I m 9t" = Nm sei x = Wir setzen

(') x2

und y =

('9 Y2

und es sei C =

q)(x,y) = x'ly 1 + y'2(A'x 1 + C x 2 - c ) a(x) = b'xl + ~1 x2, CX2, fl(Y) = O.

positiv semidefinit.

8

W. VOGEL

Ferner sei h i = 9l" und ~2 = {Y [ Yl ~ 0, Y2 ohne Einschr.}. Dann wird ]~(x) = rain {x'~yl + y'2(A'xl + Cx2-c)[y~ >_ 0} = 0 mit

?9lI = { x l x 1 >_ O, A'x 1 + Cx 2 = c}. Ferner ist 02(y)

max {x'~yl + y'2(A'xl + C x 2 - c ) - b ' x l - ½

X 2'

Cx21xe91 n} •

Das Maximum kann man bestimmen, indem man die Ableitung der zu maximierenden Funktion gleich Null setzt. Man erh~ilt:

Yl + A y 2 - b = O, C y 2 - C x 2 = O. Dies liefert

~(Y) = - c ' y 2 + ½Y'2Cy2

und

9Jl2 = {y[Ay2 + Yl = b, Yl >- 0}.

Damit hat man die Dualitiitsaussage

max { - b ' x ~ - ½ x'2Cxz[x~ > O, A' xx + Cx2 = c} ' _ b} = rain { - c ' y 2 + yy2Cy2]Ay2 < oder, in anderer Bezeichnung, max { c ' y - ½ y ' C y l A y _< b} = rain {b'x + ½z'Cz]x > O, A ' x + Cz = c}. Zu dieser Aufgabe gehSrt die Funktion ~p(x,y) = x'lyl + y'z(A' xl +

Cx2--c)-b'Xl

_

~1X2,C x

2

mit xl, x2 ohne Einschr~inkungen, Yl > 0 und Y2 ohne Einschr~inkungen. Auf Grund yon Sattelpunkt-Theorem 4 aus Abschnitt 6 hat diese Funktion einen Sattelpunkt, wenn max { - b ' x a - T x12 C x 2 l x i

>- O, A ' x l + Cx2 = c}

existiert, wenn die Zeilen von (A', C) linear unabh~ingig sind und wenn es ein Xl > 0 mit A'xa + Cx2 = c gibt. Statt das Sattelpunkt-Theorem 4 zu benutzen, ist es hier naheliegend, die KUHN-TUCKZR-Bedingungen anzuschreiben. Sie lauten:

Yl +

Ay2 =

b,

Cy 2 = Cx2,

A'x a + Cx 2 = c, xl > O, x'~y 1 = O.

Man sehe hierzu auch VOGEL [1967b, S. 96]. Beispiet 4:

x) undcp(x,y)=y~h(x)+y'2(Ax-a). Seiy = ( YY2 Ferner sei R2 = {YlY~ > 0} und fi(y) = 0. !;l1 und c~(x) spezialisieren wir nicht, doch sei R1 konvex und e(x) konvex. Man erhNt:

und

fl(x) = min {y',h(x) + y 2 ( A x - a ) I y 1 >>_0} = 0 9)l 1 = {xlh(x) >_ O, Ax = a, X e R x } .

Duale Optimierungsaufgaben und Sattelpunkts/itze

9

Die Aussagen (i) und (iii) yon Hauptsatz 1 lauten jetzt:

0 (x, y) = Yl h (x) + Y'2(Ax - a) - c~(x)

(i)

hat einen Sattelpunkt ffir x e R 1 und Yl >- 0. (ii)

max {-c~(x)tAx = a, h(x) > 0, x s R 1 } = min {~(y)[ysgJ~ 2 und yl _> 0}.

Dabei ist 9J~2 C R2 der Definitionsbereich yon :i(y) = max {Y'I h (x) + Y l ( A x - a ) -

~ (x) lx e R t }.

Das Sattelpunkt-Theorem 4 liefert: Sei e(x) konvex, h(x) konvex und !;11'konvex. Wenn min{c~(x)lAx = a, h ( x ) > O, x e $ t l } existiert, wenn es ein x ~ R 1 mit Ax = a und h(x) > 0 gibt, wenn es einen inneren Punkt x ~ !;11 und Ax = a gibt und wenn die Zeilen yon A linear unabh~ingig sind, so gilt (ii). Dies ist eine Dualit~itsaussage ftir die nichtlineare konvexe Optimierung.

Beispiel 5: Gegeben seien die Funktionen cr(x) und a*(y) und die Mengen ~31 und ~32. Es gelte: a*(y) = max { x ' y - ~ r ( x ) l x ~ ~1} und a(x) = max { x ' y - ~ * ( y ) l y e ~z}. Dabei sei ~ z der genaue Definitionsbereich yon o-*(y) (d. h. ftir y ~ ~32 soll das Maximum nicht existieren), entsprechend sei ~1 der genaue Definitionsbereich von a(x). Ferner seien die Funktionen r (x) und z* (y) mit den genauen Definitionsbereichen ~ und ~2 gegeben und es gelte ~*(y) = min {x' y - z ( x ) [ x ~ ~1} und

z(x) = min { x ' y - z * ( y ) I y E ~ z } . Wir schreiben nun die Dualitiitsaussage yon Hauptsatz 1 ftir

(p(x,y) = x'Ay, ~(x) = ~r(x), fi(y) = "c*(y), •1 = ~31 und

!;/2 = ~ 2

an. Man erh~ilt ~2(y) = max {x'Ay-c~(x)[x e R1} = max {x' A y - o-(x) [ x ~ ~31} = ~r*(Ay). Hierbei muB Ay e ~2 gelten, denn fiir A y ¢ ~2 sollte das Maximum auf G r u n d der Definition von ~2 nicht mehr existieren. Aul3erdem muB natiirlich y s~/2 = ~2 gelten. Daher ist

10

W. VOGEL

Entsprechend erh~ilt man fl(x) = min {x'Ay-fl(y)[y ~ R~} = min {x'Ay-z*(y) ty ~ ~2} = z(A;x) mit

Damit lautet die D.ualifiitsaussage

max{z(A'x)-a(x)[A'X~l und x ~ 3 1 } = min {cr*(Ay)-z*(y)[Ay~9~2 und Y ~ 2 } .

(2.2)

Sie gilt genau dann, wenn die Funktion

O(x,y) = x ' A y - a ( x ) - ' c * ( y ) mit dem Definitionsbereich x s ~31 und y e ~2 einen Sattelpunkt hat. Funktionen ~ und ~r* (bzw. r u n d r*) mit den hier geforderten Eigenschaften werden in der Theorie von FENC~tEL behandelt. Man sehe dazu DIETER [1965, 1966]. Die Formulierung der Dualit~itsaussage (2.2) findet man in ROC~:AFELLAR [1967b]; dort stehen auch weitere Bedingungen, unter denen (2.2) giiltig ist.

,

Wir wollen den Sonderfall betrachten, dab die Funktion 0(x,y) symmetrisch ist. Sei jetzt 9t" = 91m, also !;tl C 91" und R 2 Q 91n. Ferner seien die Funktionen ~o(x,y), e(x) und fl(y) gegeben. Es gelte: (p(x,y) = ~o(y,x). Der Definitionsbereich yon c~(x) ist RI, der Definitionsbereich yon fl(y) ist "~2 und der Definitionsbereich yon ~o(x,y) ist jetzt (R1 u !R2) x (R1 w !;/2). Wir bilden wieder /~(x) = min {(o(x,y)-fi(y)[y ~ R2} und c~(y) = max {q~(x, y ) - c~(x) lx e ~1} mit den Definitionsbereichen 9~R~und 0Jr2. Dann gelten die Ungleichungen

fl(x)+fl(y)<_q)(x,y)

fur

xe9311

und

yeg2

und

e(x) + ~(y) > q~(x,y) fiir x ~

1 und

Y~J~2-

Wegen q~(x,y) = ~o(y,x) kann man ftir die letzte Ungleichung auch

d(x) + e(y) >_ q~(x,y)

fi.ir

X~fJ~2 und Y ~ I

schreiben. Zusammen mit der ersten Ungleichung folgt daraus fl(y)-~(y)_<~(x)-fl(x)

fiir

x ~ f f R l n g ) l 2 und

y~Rlc~!;12.

(3.1)

Duale Optimierungsaufgabenund Sattelpunkts~itze

11

Dies legt es nahe, nach einer Dualifiitsaussage der Form max {fl(y)-c~(y)ly e R~ ~ R2} = min {~(x)-fl(x)lx E 921tI c~ ~J~2}

(3.2)

zu ffagen. Wir suchen also jetzt Be(tingungen fiir die Gtiltigkeit von (3.2). Sei Oi(x,y)=(p(x,y)-fl(x)-a(y) mit xegJtl und y e ~ / i und sei ~2(x,y)=(p(x,y)--fl(y)-G:(x). mit xe~)t 2 und y E ~ 2 .

Satz 3.1 : Die Beziehung (3.2) gilt dann und nur dann, wenn es Xo e gill c~ 9912 und Yo e h i c~ R2 gibt, so daB

Ol(xo,y) <- Ol(xo,Yo) < tPl(x,yo)

fiir alle

x~gJ~i

und

yegll

und ~2(x, y0) < 1//2(x0,Yo) N O2(x0,y)

f'tiralle

xe9312

und

ye~2

gilt.

Beweis : Wir leiten zuerst aus (3.2) die Sattelpunktsungleichungen her. Nach Voraussetzung gibt es xo ~93ti c~ 93l2 und Yo e !~1i c~ ~/2 mit

fl(Yo)- e(Yo) = c2(Xo)-fl(Xo) •

(3.3)

Nach Definition gilt

~(Xo) >- (p(xo,y)-o:(y)

fiir alle

ysS/i

fl(Yo) < (p(x,yo)-fl(x)

fiir alle

xeg]l 1.

und Setzt man dies in (3.3) ein, so erh/ilt man

~kl(Xo,Y) < o2(Xo)-~(Xo) = fl(Yo)-~(Yo) <- ~l(X,yo). Damit ist die erste Sattelpunktsungleichung bewiesen. Entsprechend findet man die zweite Sattelpunktsungleichung, indem man

~(Yo) > q~(x,yo)-~(x) fl(Xo) <- q~(xo,y)-fi(y)

fiir alle

xegJ/2

flit atle

y~R2

in die Beziehung (3.3) einsetzt. Wir setzen jetzt die Sattelpunktsungleichungen voraus und leiten die Beziehung (3.2) her. Aus Ol(Xo,y) <_ Ol(xo,Yo) folgt

q)(xo,y)-c((y ) <_ q)(xo,Yo)-a(yo)

fiir alle

ye!;l i.

Daher ist o2(Xo) = max { q~(xo, y)-a(y) [y e St1} = qg(Xo,Yo)-c~(yo) . Entsprechend folgt aus O2(xo,Yo) _< O2(xo,y ) die Beziehung

(P(xo,Yo)-fl(Yo) <- (Pxo,Y)-fl(Y)

fiir alle

ye.~

2 .

12

W. VOGEL

Daher ist

~(Xo) = q~(xo,yo)-fl(yo). Au~ den beiden eben hergeleiteten GMchungen folgt c~(Xo) + c¢(Yo) = (p(xo,Yo) = ~(Xo) + ]?(Yo)Zusammen mit der Ungleichung (3.!) beweist dies die Beziehung (3.2). Bei einer symmetrischen Funktion ~o(x, y) liegt es nahe, die Beziehung /7(x) = min {q) (x, y)-/~ (y) ly ~ 5/2} zu iterieren. Wir setzen: /~(y) = rain {~o( x , y ) - ~ ( x ) l x e 9Jt~}. Dabei ist 9)l 1 der Definitionsbereich yon/7(x); den Definitionsbereich von/~(y) nennen wir 93l3. Wir setzen jetzt voraus: (3.4) ~JJl3 = 512 und if(y) = fi(y). Dann gilt: Hauptsatz 2: Sei (3.4) vorausgesetzt. Die Aussage: Es gibt xo ~ 921/1~ ~J~2 und Yo ~ 511 m $t2, sodaB fiir alle x ~ 9Jl 1 und alley E 511 die Ungleichungskette O1(xo, y) < q~l(xo, Yo) -< Ol(x, yo) gilt, ist notwendig und hinreichend ftir das Bestehen der Gleichung (3.2). Beweis : Es gelte (3.2). Im vorhergehenden Satz wurde bewiesen, dab dann die Sattelpunktungleichung gilt. Wir setzen jetzt die Sattelpunktsungleichung voraus. Aus ~1 (xo, y) -< ~Pl (xo, Yo) folgt (genau wie beim Beweis des vorhergehenden Satzes) die Gleichung (xo) + ~ (yo) = 'P (Xo, yo).

(3.5)

Aus ~, 1 (Xo,Yo) < @1 (x, Yo) folgt ~o(Xo, Yo)-/7 (Xo) < ~o(x, Yo)-/7 (x) Kir alle x ~ 93ll. Daher ist ¢ (Xo,Yo)-/7 (Xo) = min {~o(x, Yo)-/7 (x) ] x ~ 93ll} = / ~ (Yo) =/3 (Yo). Also ist

/7(Xo) +/~(yo) = ~O(xo, yo). Zusammen mit (3.5) erh~ilt man

(Xo)- ~ (Xo) = fi (yo)- ~ (yo) und dies beweist die Beziehung (3.2). Unter der Voraussetzung (3.4) ist also (3.2) iiquivalent mit einer Sattelpunktsungleichung und, wie wir jetzt nicht mehr extra beweisen, auch ~iquivalent mit der Aussage:

Duale Optimierungsaufgabenund Sattelpunkts~itze

13

Es gibt x 0 e gJl t c~ ~fJ~2und Yo ~ 5/1 m R2,fiir welche die Gleichungen

~:(Xo) + ~(yo) = q,(Xo, yo) = fl(Xo) + fi(yo) getten. Fiihrt man wieder 9.I1 = {(x,y)] q)(x,y) = c~(x) + ~(y), x e !~li, yeTJ~z}

= {(x,y)] ~o(x,y)= ~(y) + a ( ~ ) , y ~ S ~ l , x ~ 2 } und 9I 2 = {(x,y)I ~o(x,y) = fl(x) + fl(y),xefOll, y e £ 2 } ein, so folgt: Unter der Voraussetzung (3.4) ist die Bedingung

~1 c~ 9.I2 + 0 notwendig und hinreichend f0r die Gtiltigkeit der Gleichung (32). Wit suchen nun nach Bedingungen daftir, dab die Beziehung (3.4) gilt. Wit ftihren die Schnitte der Menge

~ 2 = {(x,y)l q,(x,y)= fl(x) + ~ ( y ) , x ~ l ,

yeS~2}

an den Stellen x und y ein. Dazu w~ihlen wir die folgenden Bezeichnungen:

S (x) = {y I (P (x, y) = j~(x) Jr- fl (y), y e ~2} und T(y) = {x [ (#(x,y) = fl(x) + fi(y),xegJRt}. Auf Grund der Definition yon

fl(x) mug S(x) =~0

tar alle x e ~J~i gelten.

Satz 3.2: Dann und nur dann, wenn T(y) + 0 ftir alley e £2 ist, gilt auch die Gleichung fl(y) = min {q~(x,y)-~(x)lx e ~ l } und das Minimum existiert ftir alley e £2.

Beweis : Sei

fl (y) = min { (p (x, y ) - fl (x) ]x e ?iR~} . Daraus folgt ~o(x,y) > fl(x) + fl(y) ftir alle xe!lR 1 und alle y e £ 2 . Zu jedem y e Rz gibt es hier wenigstens ein x e ~ , , so dab in dieser Ungleichung das Gteichheitszeichen steht. Daher ist T(y) ~=0Sei jetzt T(y) ~= 0 fiir alley e R2. Dann g i n es zu jedem y E £2 wenigstens ein x e ~ R i, so dab

~o (~, y) = fl00 + fl (y) gilt. Zusammen mit der Ungleichung

q)(x,y) > fl(x) + fl(y) fiir alle x e g ) l , und alle y e £ 2 (welche auf Grund der Definition yon fl(x) gilt) erNilt man dann: Ftir y e !;12 ist rain {(p (x,y)-fl(x)]x e ?i2~t} = fl(y).

14

W. VOGEL

BeispieI 6: Sei C = C' eine negativ semidefinite Matrix. Dann gilt 0 > (x-y)'C(x-y)

= x'Cx + y'Cy-2x'Cy.

Daraus folgt: Fiir ¢p(x,y) = 2x'Cy, fl(y) = y'Cy und R2 = 8~" wird /~(x) = rain { 2 x ' C y - y ' C y l y

~ 9~"} = x ' C x

mit x e ~" und weiter /~(y) = min { 2 x ' C y - x ' C x

[ x e ~l"} = y'Cy = fl(y)

mit y e ~R". Hier ist

= {(x,y) lx

= y}.

Beispiel 7: Im folgenden ist die Bedingung T(y) ~- 0 nicht erRillt. Da die Vektoren x und y jetzt nur eine Komponente haben sollen, schreiben wit ~ start x und r/statt y. Sei 9(~,r/) = -~Zr/2, fl(r/)= +r/ und R2 ={r/I 1,71-< 1}. Dann wird /~(~) = rain { - ~ 2 r / g - r / l iql < 1} = _ ~ Z _ l mit ~ 1 = 9tl, und man erh~lt 9a 2 = {(~,r/)[ _~2r/2 = ~ _ ~ e _ a , lr/[ <_ 1} -- { ( ¢ , l ) l ~ f f P }. Ferner wird /~(r/) = m i n { _ { 2 q 2 + {2 + l [ { e ~ R 1} = 1 + min{¢2(1-t/2)14e~Rx } = 1; fi(r/) existiert fiir l-r/e _> 0; zusammen mit r/e Re bleiben also fiir ~R3 nut noch die W e r t e ~ = +_1. Ist die Bedingung (3.4) erftillt, so kann man zwei Dualit~itsaussagen anschreiben: die alte Aussage (ii) aus dem Hauptsatz 1 und die neue Aussage (3.2). Wir geben hierzu ein (eindirnensionales) Beispiel.

Beispiel 8: Sei!~tl = { ¢ 1 4 > 0 }

und !;12 = {r/It/> 1}.

Sei ferner (P (4, t/) ~--- ¢2 y/2, • (¢) = ¢2 u n d

fi (r/) = r/.

Dann folgt:

1 min {42tl~-r/] r/ > 1} = Dies liefert die Funktion ~({).

--~fiir ¢2-1

0 < ¢ < - , ~1 1 x/~ < {

Duale Optimierungsaufgaben und Sattelpunkts~itze

15

Es ist ~ 1 = RI und es wird T(t/) = {~ l ~2t/2 = t/ + ~(~), ~ > 0} = {~I~ z _-

1 und ~ 2 <_-~-} 1 fiir ~7 > I 2t/ 1

=

>5_ }

t / = 1.

Also ist T (t/) :~ 0 ffir alle t/~ R2 u n d e s gilt (3.4). Als ngchstes berechnen wir ( t / ) = m a x {4 2 t / 2 - ~ 2 [ ~ > 0 }

=0.

Diese Beziehung gilt wegen t/z > 1; m a n erh~ilt noch ~3l2 = {t/= 1}. Damit wird die Dualit~itsaussage (ii) max { i f ( i ) - ~ 2 1 ~ > 0} = min{t/tt/ = 1}. Diese Aussage ist offensichtlich richtig. Das M a x i m u m wird fiir { ___1 und das 2 M i n i m u m fiir t / = 1 angenommen. = {2t/i-U-t/

1 hat einen Sattel fiir 4o > ~--, t/o = 1. Die Dualitiitsaussage (3.2) lautet: max {t/-t/2[t/ > 1} = min {-/7(~)[~ = 1}. Hier wird das M a x i m u m ftir ~ = 1 und das M i n i m u m ftir t / = 1 angenommen und beide Extremwaerte sind gleich. Daher hat ~//l(~'t/) = ~2t/2__~(~)__t/2 einen Sattel ftir { = t / = t. 4.

Sei jetzt 9t" = ~R" und ¢ (x, y) = x' y. Fiir das folgende brauchen wir die beiden zueinander orthogonalen linearen Mannigfaltigkeiten 911 = {x l A x = a} = {x l x = B' z + c}

und 91 z = { y l B y

= b} = { y l y = A ' w + d}

mit A c = a und B d = b. Ferner sei A B ' = 0 und die Matrix (A',B') habe Rang n. M a n vergleiche dazu Vo6Erc [1967a]. Wir setzen: R z = T/z, qo(x, y) = x' y und fl (y) = c' y.

16

W. VOGEL

Man erh/ilt dann/~ (y) wie folgt: Fiir x ~ 911 und y ~ 912 ist

q)(x,y)-[3(y) = x' y - c ' y = ( x - c ) ' ( A ' w + d) = d' x - c ' d , denn ( x - c ) ' A ' = x ' A ' - c ' A ' = a ' - a ' = O. Fiir xe912 ist A ( x - c ) = A x - A c = A x - a

~- 0; also nimmt

(p(x,y)-t~(y) = ( x - c ) ' ( A ' w + d) = w ' A ( x - c ) + d ' ( x - c ) fiir passendes w jeden beliebigen Wert an. Daher ist 9J{1 = 9l 1 n R1 und fl(x) = d ' x - c ' d . Die Dualit~itsaussage (ii)yon Hauptsatz 1 lautet jetzt:

max{d'x-~(x)lx~91

~ c~R~} = m i n { ~ ( y ) - c ' y l y ~ 9 1 2

c~gJl2} + c'd.

(4.1)

Statt ~Rz haben wir hier 9t2 c~ 93~z geschrieben; das ist wegen 93¢z < 912 natfirtich zul~tssig und erweist sich im folgenden als zweckm~iBig. Fiir die Menge 9Iz gilt:

9.12 = {(x, y) Jx' y = c'y + d ' x - c ' d , x ~ 911 r~ 9¢1, y ~ 912 c~ 9Jl2}. Aus der Orthogonalit~t yon 911 und 912 folgt aber ( x - c)' ( y - d) = 0 oder x'y = c'y + d' x - c' d. Daher ist Die eine H/ilfte der Bedingung (iii), n~imlich es gibt Xo ~ 911 ~ R1 und Yo ~ 912 ('3 ~J~2 mit (xo, Yo) ~ ~2 ist daher immer erfiillt (falls 911 c~ R1 + 0 und 912 ~ ~(J~2+ 0 gilt). Folglich reduziert sich die Bedingung (iii) in diesem Fall auf: Es gibt Xo~91~ c~ RI und y 0 E 9 1 2 ~ 9~ 2 mit (xo, Yo)~gJ1,

Beispiel 9: 1

,

1

,

Aus ( x - y ) ' ( x - y) _> 0 folgt x ' y <_ --f x x + -~ y y, und das Gleichheitszeichen 1 , gilt genau dann, wenn x = y ist. Setzt man c~(x) = -~-x x und R1 = 9t", so wird 1 , y, 9)l z daher c2~) = -~-y

{

=

91, und

Damit haben wir erhalten: Es gilt

{

max d'x

.x'x[x~911

1

1}

}

=min

--~yy-c'ytye912

}

+c'd

genau dann, wenn es x o ~ 911 und Yo e ~l 2 n/it x o = Yo gibt. So ein xo = Yo gibt

esaberstets;(A)x=(~)istl6sbar,

d a ( A ' , B ' ) d e n R a n g nhabens°llte.

Duale Optimierungsaufgaben und Sattelpunkts~itze

17

Sei nun

~(x) = ~ ~,(~i) i=1

d. h. ~ ,st eine Summe yon n Funktionen, und die i-te Funktion h~ingt nur vonder /-ten Koordinate von x ab. Die Menge 1;t1 sei ein Rechteck: R1 = ,31 x `32 x ... x ,3, = `3. Es gilt also x e !;t I genau dann, wenn fiir jedes i die Beziehung 4i • `3i gilt. Dann wird rl

~2(y) = max { x ' y - a ( x ) [ x • •1}

~-

E max {4~t/i- cq(4i) [ 4, • ,3~} = 2 i(rh), /=1

und 93l2 = ,~1 x 3a x... x,~, = ,~ wird ebenfalls ein Rechteck sein. Ffir die Menge 9,I1 gilt jetzt:

~l={(x,y)l x'y = ~(x) + ~(y),x •s~l, y •9~2} = ¢1 ×¢2 x ... × ¢ , mit

• , = {(~,, ~,)14,,I, = ~,(¢,) + a,(n), ~ •-~,, ,1 •.3,}.

Aus den vorhergehenden Oberlegungen folgt: Die Dualit~itsaussage (4.1) gilt genau dann, wenn es x e g l 1 ~ 3 und y • g t 2 c', 9J~2 mit (4,,th) • E, ftir alle i gibt. Es gibt nun die M6glichkeit, die Mengen E~ so vorzugeben, dab diese Bed,ngungen erfiillt werden kOnnen. Dazu gehen wir (ftir jedes i) yon zwei monoton steigenden Funktionen n(4) und a(~) aus. Die Funktionen und die Intervalle 3~ und 3~ seien der Art, dab

{(¢,~) ] ~ ( ~ - 0 ) _< ~ ---~(4 + 0), 4 •`3,} = {(4,~)1~(~-0) - 4 - ~(~ + 0),~ •3,} ,st. Die Intervalle -~i und .3i seien abgeschlossen; es diirfen auch abgeschlossene Halbgeraden oder die ganze Zahlengerade sein. Be, im Endlichen liegenden linken Eckpunkten setzen wir r e ( 4 - 0 ) = - o 0 bzw. a ( t / - 0 ) - -oQ, be, rechten Endpunkten re(4 + 0) = + oo bzw. a ( t / + 0) = + co. Von einem beliebigen Punkte (4o,~/o) ausgehend, bilden wir cti(~) = ~ 7z(~)d~ ~o

und

"h(t/) = f a ( 0 d ~ . #o

Es wird vorausgesetzt, dab diese Funktionen endlich sind. Wegen der Monotonie von rci und a, sind e, und 7~ konvexe Funktionen. Wir werden zeigen, dab die oben angegebene Menge gerade die Menge ~ ,st, welche zu ch(~) geh6rt. Wir bezeichnen sie jetzt schon mit ~i, um keine unn6tigen Buchstaben einfiihren zu miissen. Hitfssatz 4.!: Fiir r/• 3~ ,st max {~r/- ~(~) [ ~ • ,~} = ~ t / - cq(41) mit (41 ,t]) • ~i" Fiir ~/~ 3~ wird i t / - ~ , ( ¢ ) auf 3g beliebig grog.

18

W. VOGEL

Beweis : Wir bilden die rechten und linken Ableitungen der Funktion ~t/-~i(~) (ats Funktion von ~). Sei t/~,~i und sei (~1,q)e ~ . Dann ist

D~,z(~t/-a~(~))=r/-n(~_+0)>0

fiir

~<~1

und

Dr, l - < 0

fi.ir ~ > ~ 1 ;

dies beweist die erste Behauptung. Wenn t/+ ,~ ist, so gibt es zwei MiSglichkeiten: ,~i hat einen oberen Endpunkt ~ und es ist ~/> a; -~i ist dann nach oben unbeschr~inkt (wegen a(~ + 0) = oo).

(4.2)

,~ hat einen unteren Endpunkt fl und es ist r / < fl; (4.3) 5i ist dann nach unten unbeschr~inkt (wegen a ( f l - 0 ) = - co). FiJr den Fall (4.2) gilt Dr, l (~r/--O~i(~)) = r/--7~(~ ___O) ~ t]--0~ > 0.

Also wird ~ t / - % ( ~ ) flit ~ ~ co beliebig grog. Ftir den Fall (4.3) gilt Dr, z ( ~ - ~ ( ~ ) )

+ 0) _< ~-/~ < 0 .

= n-~(~

Also geht ~tl-~,(~) fiir ~ ~ - c o nach + Go. Damit ist der Hilfssatz bewiesen. Aus dem Hilfssatz folgt unmittelbar: Es ist ~ 2 = 3 und ~i(t/) = max { i t / - ~i(~)l ~ ~ 3i} = ~ t / - a~(~) wobei (~, ~/) ~ ~ gilt. Auf Grund der Definition von ai und ?~ folgt nun: Fiir (~,~/) ~ ~i ist ~i(~) + ~(~) = ~ n - ~ o q o . Man sehe hierzu Vo6H. [1967a]. Damit wird ~(~) = 7~(~) + ~o~o, und man erh~ilt ~(y) = X'oYo + ~_, 7~(rh) mit dem Definitionsbereich

9Jl2 = 3 .

Die Dualit~itsaussage hat dann die folgende Form: max { d ' x - ~ ~ ( ~ ) l x ~ 9~ c~ 3} + max { c ' y - Z 7,(~h) lY ~ ~2 c~ 3} = c ' d + XoYo ' . Dazu geh/Srt die Funktion (j(x,y)=x'y-e'y-~oh(~i)

mit

xe~

und

y~9~ 2.

Setzt man hier y = A ' w + d ein, so erh~lt man aus d'x-Y',~i(~)+d'c+w'(Ax-a)

und w ohne Einschr~inkungen.

mit

x~5

(4.4)

Duale Optimierungsaufgabenund Sattelpunkts/itze

19

Diese Funktion hat nach dem Sattelpunkt-Theorem 4 aus Abschnitt 6 einen Sattelpunkt, falls max { d ' x - ~ , ~ i ( ~ ) i A x = a, x~`3} existiert und falls die Gleichung A x = a fiir einen inneren Punkt yon .3 erffillt ist. Damit haben wir erhalten: Genaudann, wennes Xoe911c~.3 und YoE912c~,3 mit (Xo, Yo) E ¢g gibt, gilt die Beziehung (4.4). (4.5) Wenn max {d'x - ~ 0~i(~i)[ x ~ 911 c~ .3} existiert, und die Menge (4.6) 911 n .3 innere Punkte hat, so gilt (4.4). In VOGEL [1967a] wurde gezeigt: Auch wenn man die Voraussetzung .3, .3 abgeschlossen nicht macht, gelten (4.5) und (4.6). (Siehe Satz 1 und Satz 4.) Wenn `3 und ,3 abgeschlossen sind, so gilt: Genau dann, wenn 911 c~ .3 ~ 0 und 912 n ,3 ~= 0 ist, gilt die Beziehung (4.4). (Siehe Satz 3 bei VOGEL [1967a].) Die Menge der miSglichen Funktionen c~-ist nicht gleich der Menge aller stetigen konvexen Funktionen (bis auf eine Konstante). Eine genaue Charakterisierung der m6glichen ei findet man in ROCKAFELLAR[1967 a]. Diese Arbeit enth~ilt auch eine Verallgemeinerung der Formel (4.4) und weitere Literatur zur monotonen Optimierung. 5. Gegeben seien die Funktionen q~(x,y), a(x) und fl(y), sowie die Mengen !;tl C 91" und !t 2 C Ol'. Wir bilden damit inf { ( p ( x , y ) - f l ( y ) [ y ~ 112} -- fi(x) und sup { e ( x , y ) - ~(x) l x E 111} = ~(Y)-

Natiirlich brauchen fl(x) bzw. c~(y) nicht fiir alle Punkte yon R1 bzw. yon 112 zu existieren. Wir bezeichnen den Definitionsbereich der Funktionen /~(x) (bzw. c~(y)) mit ~ 1 (bzw. mit g)12). Es ist also ~1 = {xlinf{cp(x,Y)-fi(Y)lY~112} > -or}

und ?Ol2 = { Y l s u p { c p ( x , y ) - c ~ ( x ) l x e R 1 }

< + oo}.

Zur Abkiirzung setzen wir wieder q, (x,y) = ~ o ( x , y ) - ~(x) - fl(y). Hauptsatz 3: Die folgenden drei Aussagen sind ~iquivalent. (i): Zu jedem e > 0 gibt es x~ e 111 und y~ s 112, so dab ftir alle x e 111 und fiir alle Y ~ 112 die Ungleichungskette

gilt.

O ( x , y 3 - e <_ 4,(x~,y3 <_ O(~,y) +

20

W. VOGEL

(ii): sup{fl(x)-oc(x)txe~iJ~l} = inf{6(y)-fl(y)]y~9)12} und ~111 =~ 0, 92~2 + 0. (iii): Zu jedem ~ > 0 gibt es xe e ~Ji i und y~ a 93l2, so dab die Ungleichungen

~o(x~,y~) _< ~(x~) + fl(y~) + ~o(x~,y~) >_. (x~) + 6 0'3 -

(5.1)

gelten. Beweis : (i) => (iii): Aus O(x~,y~) <_ O(x~,y) + e folgt

,p (x~, y) - fl (y) >_ ¢ (x~, y~)- fl (y3 - ~Daher gilt: (xe) = inf {qo (x~, y) - fi (y) ] y a ~2} ~---~0(Xe,y~)-- fl (y~)-- 8. Dies zeigt: 9J~l :~ 0, denn x, e 9Jll und es gilt die erste der Ungleichungen (5.1). Genauso kann man aus O(x,y,) < O(x~,y~) + e folgern: y~ a 9J~2 + 0 und es gilt die zweite der Ungleichungen (5.1). Damit ist (iii) hergeleitet. (iii) =~ (ii): Wegen (iii) ist ~Jl~ ~= 0 und ~f~2 + (~' Ftir x e R 1 und Y~f~2 gilt auf Grund der Definition yon fl (x):

~o(x, y) >__fl(x) + fl (y). Ftir x ~ ~Jla und y ~ R2 gilt entsprechend

,p (x, y) _<. (x) + 6 (y). Aus beiden Ungleichungen fotgt sofort: Fiir alle x s ~J~a und fiir alle y ~ ~ z gilt

/ ~ ( x ) - . (x) _< ~ (y)- fl (y). Aus den Ungleichungen (5.1) folgt fl(x,)-o~(x~) > 6(y~)-fl(y~)--Ze. Die beiden letzten Ungleiehungen zusammen ergeben dann sup {/~ (x) - ~ (x)] x ~ ~

} = inf {6 (y) - fl (y)] y E ~A2}.

(ii) =~ (i): Fiir jedes e > 0 g i n es x~ ~ ffJ~ und y~ ~ 9)l 2 mit

sup {/~(x)- ~ (x) [ x ~ ~ }

_< fl % ) + . (~) +

und inf {6 (y) - fl (y) I Y ~ 9J~z} _> 6 (y~) + fl (y~) - e, Zusammen mit (ii) erh~ilt man daraus

6 (y~)- fl ( y 3 - ~ -< fl(x~)- ~ (x~) + ~. Setzt man hierin die Ungleiehungen fl (x,) < ~p(x~,y)- fl (y) fiir alle y e Rz und c~(y~) > q~(x, y~)- e (x) ftir alle x s R~

Duale Optimierungsaufgaben und Sattelpunkts/itze

21

ein, so folgt (p(x,y~)-e(x)-fl(y3-e

N (p(x~,y)--e(x~)--fi(y) + e,

und daraus erh~ilt man unmittelbar die Aussage (i). Wir wollen wieder den Sonderfall betrachten, dab die Funktion ~0(x, y) symmetrisch ist. Gegeben seien die Mengen R1 C ~R"und R2 C ~R"und die Funktionen (x), fi (y) und (p (x, y). ~ (x) habe den Definitionsbereich R1, fl (y) habe den Deftnitionsbereich R2 und q~(x, y) habe den Definitionsbereich (R1 w R2) x (R1 w R2). Ferner sei (p (x, y) = cp(y, x). Wit bilden fl (x) = inf {(p (x, y ) - fl (y) [ y e R2} und ~(y) = sup { ~ o ( x , y ) - e ( x ) [ x e R 1 } mit den Definitionsbereichen g)11 und 93l2. Wir wollen ferner voraussetzen, dab fl = fl ist. Es sei also fl (y) = inf {(p (x, y)-/~ (x) I x s 92~ }

(5.2)

und zwar Rir alley e !;l2. Sei q)1(x, y) = q~(x, y ) - fl (x) - c~(y). Wir betrachten die beiden folgenden Aussagen: (i): Zu j edem e > 0 gibt es x~ e R.R1 und y~ e R2, so dab far alle x e ~J~l und atle y e R2 die Ungleichungskette _< O

(x ,yO <- O (x, y3 +

gilt. (ii) sup {fl(y)-e(y) ] y s R~ c~ R2} = inf {~(x)-fl(x)lx e ~ c~ ~2} und R i c e R 2 + 0 , 9Jllc~J~2 + 0 . Dann gilt: Hauptsatz 4: Wenn (5.2) gilt, so sind (i) und (ii) ~iquivalent. Beweis : Es gelte (i). Aus tfi~(x~,y)-e < ~(x~,y~) folgt _<

Dahcr ist x~ ~ TJ~2 und es gilt ~(x~)-e <_ q~(x~,y,)-e(y~).

(5.3)

Aus Ol(x~,y~) -< 01(x,Y~) + e folgt Also gilt y~ e R2 und q)(x~,y~)-~(x,) < fl(y~) + e.

Hierbei wurde (5.2) gebraucht.

(5.4)

22

W, VOGEL

Aus (5.3) und (5.4) folgt oder

~(xO-fl(xO-~ <_fi(y0-c~(y0 + s.

(5.5)

Nun liefern die Ungleichungen fl(y) +/~(x) < q)(x,y) _< c~(y) + c~(x) far x~92R~ c~ 9312 und y e ! ~ l m R 2 , welche auf Grund der Definitionen yon c~ und fl und der Symmetrie yon q) (x, y) gelten, die Beziehung fl (y) -- c~(y) < ~ (x)-- fi (x).

Zusammen mit (5.5) beweist dies (ii). Wir setzen jetzt (ii) voraus. Dann gibt es zujedem e > 0 die Punkte x~ E 9J~ c~ ~R2 und y~ e R~ ~ R 2 mit

fl(y~)-~(y~) + e > a ( x ~ ) - f l ( x O - e .

(5.6)

Nach Definition gilt c~(x~) _> q~(x~, y ) - ~ (y) ftir alle y ~ ftl und

t3(y~) <_ ~o(x, y O - f l ( x ) fiir alle x~00l 1. Setzt man dies in (5.6) ein, so erh~lt man: ~, (x~, y ) - ~ _< ~ ( x 0 - fl ( x 3 - ~ _
abgeschlossen ist. Fiir konvex-abgeschlossene Funktionen e gilt dann c~ = c} und der Definitionsbereich yon c~ ist wieder R1.

Duale Optimierungsaufgabenund'Sattelpunkts~itze

23

Sei nun q~(x,y)= x'y, sei c~(x) mit X E ~ 1 konvex-abgeschlossen und sei /~(y) mit y ~ R2 konkav-abgeschlossen. Dann gilt: Aus R i ~ R 2 ~: ~ und 9J~1 c~ 93~2 Jf ~ folgt sup { f l ( x ) - e ( x ) l x E R 1 c~ R2} = inf{g~(y)-~(y)lye?Oll ~ 9Jl2}. Sind R 1 r~ R2 und gJ{1 c~ 9J~2 kompakt oder haben die Mengen R1, R2 und 9321,9J~2 relativ innere Punkte gemeinsam, so gilt max

{fl (X)--(Z(X) [ X e R 1 ~ R2) =min {G:(x)-~ (y) l y e ~l I c~ ~fJ~2} .

Ffir Beweise, weitere Einzelheiten und Folgerungen verweisen wir auf DIETER [1965; 1966]. In ROCKAEELLAR[-1967b; 1968] findet man Verallgemeinerungen der Theorie, wobei aber immer q~(x, y) = x'y und alle Funktionen entweder konkav oder konvex sind. .

Minimax- (bzw. Infsup-) und Sattelpunkt-Theoreme stammen aus der Theorie der Zweipersonen-Nullsummenspiele. Ftir solche Spiele wurde 1922 das erste Minimax-Theorem yon E. BOREL hergeleitet. Es lautet: Sei s~l = {(~1, ~2) 1~1 + ~ = 1, ~1 ~2 -> o}, a2 = {(~l, ~ ) l ~1 + ~ = 1, ~1,~ -- o) und ~/(~1,~2,~11~2) = a11~i/~1 -~ al2~iq 2 + a21 ~2/~1 --~ a22~2q2, so gilt die Gleichung (1.2). Im Jahre 1928 gelang es J. YONNEUMANN,diesen Satz wie folgt zu verallgemeinern: Sei R I = { x ] e , ' x = 1, x_> 0} und R2 = {ylem'y = 1, y > 0}, wobei e, (bzw. e,,) ein Vektor mit n (bzw. m) Einsen ist. Sei ferner ~ (x, y) = y' A x. Dann gilt die Gleichung (1.2). In der Folgezeit wurden viele Verallgemeinerungen gefunden; auBerdem wurden die Beweishilfsmittel stark vereinfacht. Wir erw~ihnen in diesem Zusammenhang das Infsup-Theorem yon KNESER. Seien R1 und $t 2 konvexe Mengen und sei ~(x,y) konkav in x und konvex in y. Sei ferner R1 kompakt u n d ~ (x, y) ftir jedes feste y halbstetig nach oben in x. Dann gilt die Gteichung (1.2). Wir mSchten hier keine Ubersicht fiber alle mSglichen Arten yon Minimaxund Infsup-Theoremen geben. Im folgenden fiihren wir einige S~itze dieser Art an, welche einen direkten Bezug zu der vorliegenden Arbeit haben. Der folgende Satz wurde 1959 yon StON bewiesen:

Sup-Inf-Theorem 1: Die Funktion ~ (x, y) mit x e !;t1 und y e R2 sei ffir jedes feste y als Funktion yon

24

W. VOOEL

x quasikonkav und halbstetig nach oben; fiir jedes feste x sei sie quasikonvex und halbstetig'nach unten. R1 und R2 seien konvex und ~/1 sei kompakt. Dann gilt: sup

inf O(x,y)= inf sup O(x,y).

x~Ri

Y~-q2

Y~~'/z x~-~l

Bemerkung 1:

Ist zusiitzlich zu den Voraussetzungen des Sup-Inf-Theorems 1 auch noch R2 kompakt, so gilt max

min ~ ( x , y ) = m i n

max tp(x,y).

xsR~

y~R2

x ~,~t~

yeR~

Es ist nun (insbesondere im Hinblick auf die Anwendungen) wichtig, dab man Sattelpunkt-Theoreme herleiten kann, bei denen man nicht voraussetzen mug, dab R 1 bzw. R2 kompakt sind. Es zeigt sich, dab man die Forderung R sei kompakt, durch die Forderung R sei ein konvexer polyedrischer Kegel ersetzen kann, wenn nur die Funktion 0 in der betreffenden Variablen linear ist. Der bekannteste Satz dieser Art ist der folgende: Sattelpunkt-Theorem 1: Sei O ( x , y ) = c'x + b ' y - y ' A x

und x _> 0, y >_ 0.

Die Ungleichungskette O(X, yo) <- O(xo,Yo) <- O(xo,y) fiir x _> 0, y _> 0

mit x o > 0, Yo > 0 gilt dann und nur dann, wenn die Ungleichungs-Systeme A x <_ b, x >>_O und A ' y >>.c, y > O

beide 16sbar sind. Dieses Sattelpunkt-Theorem ist 1956 yon GOLDMAN und TUCKER bewiesen worden. Die polyedrischen Kegel R1 = {x[x_>0} und R2 = { y l Y > O } lassen sich leicht verallgemeinern. So ist z. B. in VOGEL[1967b] der folgende Satz bewiesen: Sattelpunkt- Theorem 2:

Sei 0 (x, y) = y' A x + a' x + d' y mit Xe~l=

{xlBx=b,x>_O}

und y ~ R ; =

{ylCy=c,y>_O}.

Die Funktion 0 (x, y) hat genau dann einen Sattelpunkt, wenn die Systeme und

B x = b, x >_ O, A x + d >_ C' u, u beliebig C y = c, y >_ O, A' y + a <<_B' v, v beliebig

beide 1/Ssbar sind. Es ist leicht, weitere S~itzedieser Art aufzustellen, wobei R 1und R2 durch Systeme linearer Gleichungen und Ungleichungen bestimmt werden. Das bekannteste Sattelpunkt-Theorem, bei welchem die Funktion in einer Variablen linear ist, ist der folgende Satz:

Duale Optimierungsaufgabenund Sattelpunktsgtze

25

SatteIpunkt-Theorem 3: Sei 0 (x, y) = c~(x) + y'f(x) mit x ~ !;1 und y >_ 0. Die Funktionen ~ undfseien konkav und ~t sei konvex. Ferner existiere max {e(x) ] f ( x ) _> 0, x s ~} u n d e s gebe ein x ~ ~ mitf(x) > 0. Dann hat tp einen Sattelpunkt, Einen Beweis dieses Satzes findet man in UZAWA oder in VOGEL [1967b]. Die Bedingungf(x) > 0 stammt yon SEATER. Fiir lineare Komponenten v o n f b r a u c h t sie nicht zu gelten. Man hat vielmehr den folgenden allgemeineren Satz: Sattelpunkt- Theorem 4: Sei y' = (Y'I,Y~) und sei O(x,y) = ~(x) + y'lf(x) + y ' z ( A x - a ) mit x e R, Yl > 0 und Y2 ohne Einschr~inkungen. Seien e(x) und f ( x ) konkave Funktionen und R eine konvexe Menge. Die Zeilen der Matrix A seien linear unabh~ingig; ftir einen inneren Punkt xl ~ St gelte Axi = a u n d e s gebe ein x2 sgt mit A x2 = a und f(x2) > O. Ferner existiere max{~ (x) If(x) _> 0, x ~ $1, A x = a}. Dann hat 4' (x, y) einen Sattelpunkt. Hier ist y auf den besonders einfachen konvexen polyedrischen Kegel {y ] yl _> 0, Y2 ohne Einschr/inkungen} beschriinkt. U m den allgemeinen Fall behandeln zu kSnnen, schicken wir folgenden Hilfssatz voraus: Hilfssatz 6.1: Gegeben seien die Funktion 4' (x, y) mit y ~ R1 und y e R 2, Wir bilden

z(x,u,y) = O(x,y) + u ' ( B y - b ) . Wenn es Xo E R1, Uo >_ 0 und Yo ~ Rz gibt, so dab die Ungleichungskette Z(x,u, yo) -< X(Xo, Uo,Yo) <- )~(Xo,Uo,y) fiir alle x E R1, ftir alle u >_ 0 und ftir a l l e y e R2 gilt, so gilt auch

4' (x, yo) < 4' (Xo, yo) -< 4' (Xo, y) fiir alle xER~ und fiir alle Y ~ 2 mit B y < b und es ist Byo < b. Beweis : Die vorausgesetzte Ungleichungskette lautet ausftihrlich

4'(x, Yo) + u ' ( B y o - b ) <_ 4'(Xo, Yo) + U'o(Byo-b) <- 4'(xo,y) + U'o(By-b). Die erste Ungleichung liefert ffir x = xo die Beziehung

(U-Uo)'(Byo-b) <_ 0 ftir alle u >_ 0.

(6.1)

Setzt man hier u = uo + ei (e~ = i-ter Einheitsvektor), so erhglt man B y o - b < 0. Daraus folgt (wegen uo >-0) die Ungleichung u'o(Byo-b)<_ O. Anderseits liefert (6.1) mit u = 0 die Ungleichung U'o(Byo-b) >_ O. Daher ist u'o(Byo-b) = 0. Dies setzen wir in die Ungleichungskette ein. Die erste Ungleichung mit u = 0 liefert dann

0 (x, Yo) <- 4' (xo, Yo) fltir alle x e RI.

26

W. VOGEL

Die zweite Ungleichung liefert: fiir alle y e !R2 mit B y <_ b ist

~,(Xo,yo) - 0(Xo, y) + u;(By-b) _< O(Xo,y). Damit ist der Hilfssatz bewiesen. Bemerkun 9: Natiirlich gilt dieser Hilfssatz auch mit der Nebenbedingung 9 (Y) -> 0 an Stelle yon b - B y >_ 0; wir brauchen ihn aber nur in der hier angeschriebenen Form. Die Anwendung des Hilfssatzes auf das Sattelpunkt-Theorem 4 liefert nun:

Sattelpunkt- Theorem 5: Sei y ' = (Y'I,Y2) und sei 0 (x, y) = ~ (x) + Y'I f ( x ) + Yl (A x - a) mit x e R 1 und y e {y[B1y 1 + B2y2 <- b, Yl >- 0} = Rz. Hinreichend daftir, dab O (x,y) einen Sattelpunkt hat, sind die folgenden Bedingungen: c~(x) und f (x) seien konkave Funktionen, R1 sei eine konvexe Menge. Der Ausdruck max { ~ ( x ) - b ' u l f ( x ) + B'lu >_ O, A x + B i u = a, x e h l } soll existieren. Fiir einen inneren Punkt x e h i gelte A x + B~ u = a und die Zeilen der Matrix (A,B'z) seien linear unabh~ingig. Ferner gebe es ein x e h i und ein u mit Ax + B~u = a u n d f ( x ) + B'lu > O. Als n~ichstes zeigen wir eine andere MSglichkeit, Sattelpunkt-Theoreme zu beweisen, ohne dab man Kompaktheit bei St1 oder h2 voraussetzen mul3. Diesmal braucht 0 (x,y) nicht linear in wenigstens einer Variablen zu sein. Gegeben sei die Funktion tp(x,y) mit dem Definitionsbereich h i x ha. ~ habe folgende Eigenschaft: Bei festem x ist jedes lokale Minimum von qJ(x, y) als Funktion (6.2) yon y auch ein globales Minimum. (6.2) ist z. B. dann erfiillt, wenn ~(x,y) fiir jedes feste x eine konvexe Funktion in y ist. Der folgende Ausdruck soll existieren min

max ~(x,y) = O(xo,Yo) = : ~

ye~0~ 2

X~R I

(6.3)

wobei 97~2 ~ @ der Definitionsbereich yon max #(x,y) sei. x~IR 1

Satz 6.2: Sei (6.2) und (6.3) vorausgesetzt. Wenn man ~1C h 1 und ~2 C !;12 mit xo e ~1 und ll(yo) c~ h2 C ~z (tI(Yo) ist eine Umgebung yon Yo) so finden kann, dab max min ~ (x,y) >_ ~ x~

ye~2

ist, so gilt far O(x,y) mit x e ~/t und y e h2 die Sattelpunktaussage.

(6.4)

Duale Optimierungsaufgaben und Sattelpunkts~itze

27

Beweis : Aus (6.3) folgt ~b(X, yo)< O(xo,Yo) = e

fiiralle

xsY{ 1.

<- 0(xl,yl) -< ~b(xl,y)

ftkalle

ys332.

Aus (6.4) fotgt Beides zusammen liefert O(x,yo) < ~ <- ~b(xt,y)

fur x~R1

und

ye~2.

Also gilt ~b(x,yo) -< O(xl,yo)

ftiralle

x~{ 1

(6.5)

und ~b(xt,y) hat ein lokales Minimum fiir y = Yo- Wegen der Voraussetzung (6.2) folgt daraus O(xl,yo) <_ ~(xl,y) fiiralle YeY{2. (6.6) Die Ungleichungen (6.5) und (6.6) zusammengenommen liefern dann die Sattelpunktaussage. Die folgende ANinderung der Bedingungen des Satzes 6.2 findet sich bei S:rOER [1963]. Statt (6.4) setzen wir voraus: Zujedem ye331 gibtesein xe332 mit ~ ( x , y ) > und ffir O(x,y) gelte auf 331 x 332 ein Minimax-Theorem.

(6.5)

Aus (6.5) folgt max ~,(x,y) > c~ ftiralle

Y~2-

XE~) 1

Wegen des Minimax-Theorems erh~itt man daraus max

min 0 ( x , y ) = m i n

max ~b(x,y)_>~,

xe~t

y~32

x~'~l

ye~)2

und das ist gerade (6.4).

Literaturverzeichnis DIETER, U.: Dualit~it bei konvexen Optimierungs- (Programmierungs-)Aufgaben. Unternehmensforschung 9, 1965, S. 91--111. - - : Optimierungsaufgaben in topologischen Vektorfiiumen I. Dualit{itstheorie. Z. Wahrscheinlichkeitstheorie 5, 1966, S. 89--117. GOLDMAN, A. J., and TUCKER, A. W.: Theory of linear programming. Ann. of Math. Studies 38, 1956, S. 53--97. KARAMARDIAN, S. : Strictly Quasi-Convex (Concave) Functions and Duality in Mathematical Programming. J. Math. Anal. Appl. 20, 1967, S. 344--358. KNESER, H. : Sur un th6or+me fondamental de la th6orie des jeux. Comptes Rendus t. 234, 1952, S. 2418--2420. KUItN, H. W., and TUCKER, A. W.: Nonlinear Programming. Proceedings of the Second Berkeley Symposium. Herausgeber: J. Neyman, 1951, S. 481--492. MANGASARIAN,O. L. : Duality in Nonlinear Programming, Quart. Appl. Math, 20, 1962, S. 300~ -.-302.

28

W. VOGEL

MANGASARIAN,O. L., and PONSTEIN,J. : Minimax and Duality in Nonlinear Programming. J. Math. Anal. Appl. 11, 1965, S. 504--518. ROCKAFELLAR, R . T . : Convex Programming and Systems of Elementary Monotonic Relations. J. Math. Anal. Appl. 19, 1967a~ S. 543--564. - - : Duality and Stability in Extremum Problems Involving Convex Functions. Pacific J. Math. 21, 1967b, S. 167--187. - - : A General Correspondence between Dual Minimax Problems and Convex Programs. Pacific J. Math. 25, 1968, S. 597--611. SION, M.: On General Minimax Theorems. Pacific J. Math. 8, 1958, S. t71--176. STOER, J.: Duality in Nonlinear Programming and the Minimax Theorem. Num. Math. 5, 1963, S. 371--379. - - : l~ber einen Dualitgtssatz der nichtlinearen Programmierung. Num. Math. 5, 1964, S. 55--58. UZAWA, H. : The Kuhn-Tucker Theorem in Concave Programming. Studies in linear and nonlinear programming. (Herausgeber: Arrow-Hurwicz-Uzawa). 1958, S. 32--37. VOGEL,W. : Monotone Optimierungsaufgaben. Unternehmensforschung 11, 1967 a, S. 65--94. - - : Lineares Optimieren. Leipzig, 1967b.

Vorgel.v. : W, KRELLE.