Math. Nachr. 83,191-105 (1978)

Starke Losbarkeit von Optimiernngsaufgaben

Von PETER KOSMOL und MICHAEL F ~ R I E D T aus Kiel

(Eingegangen sm 9.2. 1976)

Ziel dieser Arbeit ist, diejenigen konvexen Funktionen f zu charakterisieren, die auf jeder abgeschlossenen konvexen Menge K ein starkes Minimum besitzen hzw. fur die alle konvexen Optimierungsaufgaben ( K , f ) korrekt ini Sinne von TYCHOXOFF sind. Fur beschriinkte Funktionen auf reflexiven Raumen werden die Funktionen einerseits durch die FR6cHET-Differenzierbarkeit der konju- gierten Funktion und andererseits durch die lokal uniforme Konvexitat charakte- risiert. Die Reflexivitkt ist dabei keine zusiitzliche Einschrlnkung, da beschriinkte Funktionen, die ein starkes Minimum auf allen abgeschlossenen konvexen Mengen besitzen, nur auf reflexiven Rlunien existieren [4].

Die minimalen Elemente einer Funktion f auf einer Menge K bezeichnen wir mit M ( f , K ) , d. h.

M(f, K ) : = (kocK 1 f ( k o ) = inf f ( k ) } .

Wr sagen, daB ko€K das starke Ninimuin von f auf K ist, wenn ( k o ) = N ( f , K ) und fur jede Folge ( k , J c K mit f (k , ) - f (k , ) gilt k,-k,. Anders gesagt: Jede ininiinierende Folge konvergiert gegen die Xinimallosung.

Lemma 1. h'ei S e i n r d e r reflexiver BANAPHraUm und f : 9 - R konvex und

a) f hat auf jeder abgeschlo.swnen Hyperebene und nuf X ein starkes Minimurn. 1) ) f h d auf jedem nbgeschlossenen Halbraum ein starkes Minimum. c ) f hat auf jeder abgeschlossenen konvexrn Menge ein starkes Minimum,

Be w eis. Ohne Beschrankung der Allgemeinheit kann inan annehmen, da13 f ( O ) = O und f ( x ) > O fur x+O. Anderenfalls betrachten wir g ( x ) = f ( q , - x ) - f ( ~ ~ ) , wobei f(xo) =min f ( x ) .

stetig. Es sind tiquimlent

X < S

a)=>b): Sei C=(x I (x;. x)%cr} und

Falls OEG, so ist g o = O sogar das starke Minimum von f auf X . 1st OqG, dann folgt a*O, und es gilt (x:, go)=a. dz, go kein globales Minimum von f ist.

192 Kosmol/Wriedt, Starke Losbarkeit yon Optimierungsaufgaben

Ferner

,denn fur jedes E =- 0 ist (x,*, sJ-. 9

inin { f ( x ) 1 (x:, x)zu+E}=-f(gO) I

U Weil --* - - ~- s 1, gilt.

(xo 7 sn>

-ferner ist.

folglich gn + g,,.

mit

1st OEK und f (kn) -0, so kann man annehmen, daB die k, in einem Halbraum liegen. Nach b) ist 0 starkes Minimum von f auf K, q. e. d.

Mit f* bzw. 2f bezoichnen wir die zu f konjugierte Funktion X * -RU {-} bzw. das Subdifferential von f (8. [2]).

Lemma 2. Sei X ein reeller reflexiver BANAcHra?l?m, f : X -+ R stetig konvex m d f* erullich. Dann gilt .

a) Fair jedes r e R ist die Henge Sf(r) : = (x I f ( x ) s r } beschrankt. b) Far jede abgeschlossene konvexe Menge K ist M ( f , K ) =I= 0.

Beweis. a) Sei x * € X * . Es gilt

b) D C ) : Sei K konvex, abgeschlossen und 0 4 K . Dann existiert ein Halbraum C

KcG, N ( f , K ) = M ( f , G ) .

a=-f*(x*)s sup ( ( x * , x ) - ~ ( x ) ) z sup(x* , x ) - r , X € Sf (99 z € S j ( r )

daher s u p ( x * , x ) ~ f * ( x * ) + r - = ~

x € S f ( r ) und analog

Dies bedeutet, da13 Xf(r) schwach beschrankt und damit beschrankt ist. b) Da X reflexiv ist, sind die Mengen S,(r) sogar schwach kompakt und damit

B(f, K ) 4 8 fur jede abgeschlossene konvexe Menge K , g . e . d. Eine konvexe Funktion f : X - R heiBt beschrankt, wenn das Bild jedcr

beschrankten Menge beschrankt ist. Es ist leicht zu zeigen, daB eine konvexe Punktion genau dann beschrankt ist, wenn sie LIPscHITz-stetig auf beschrankten Mengen ist ( [ 5 ] , Beweis zu Theorem 10.4.).

Sstz 1. Sei X e in reeller reflexiver BANAcHraum und f : X-R eine konvexe beschrankte Funktion, deren Konjuqierte f * GKTEAux-differenzierbccr ist. Dann

Kosmol/\Vriedt, 8tarke Losbarkeit von Optimierungsaufgaben 193

besitzt f m i f j e d e r abgeschlossenen konvexen Menge ein starkes Minimum yenazn &inn, t o e m f * PRECHET-differenxierbar ist.

Beweis. Sei f* FR6cHEFdifferenzierbar. Nach Lemma 1 geniigt es zu zeigen, daB f auf jeder abgeschlossenen Hyperebene und auf X starkes Minimum besitzt. Nach El], 3. Cor. 5 ist f* in x,* genau dann differenzierbar, wenn die Funktion f ( . ) - (rt , .) auf X starkes Minimum besitzt. Da f* in 0 differenzierbar ist, besitzt f auf X starkes Minimum. Sei H = ( x 1 (x;, x)=r}, x,* 1 0 . Each Lemma 2 ist M ( f , H ) + O . Sei h,EM(f, H ) . Nach [2], S. 31 gibt es zTEbf(h,,) mit (r:, h-ho)=O fiir alle h e H . Folglich existiert 1 C R mit Ax:=$, d. h.

f i ( x ) : =f (x ) -(I?..,*, X ) Z f (h0) -{h,*, ho) fur alle ~ € 9 .

Inshesondere ist h,, das starke Minimum yon f auf H , denn Da f* in Ax: differenzierbar ist, ist h,, das starke Minimum von f i auf X .

f I H = ( f l +(G, h")) I H Zuni Beweis der Umkehrung sei x,*EX*. Nach [l], 3. Cor. 5 ist zu zeigen, daB die Funktion f l(r) =f (x ) -(x,*, r) auf X starkes Minimum besitzt. Da fy(r*) =f* (x,* + +x*) besitzt nach Lemma 2 fi auf X ein Minimum xg-

Sei ft(x,)-+fl(xg). Es gilt (x:, xp2)-+(x:, xO), denn fur e=-0 ist nach Lemma 2

min { I&) 1 /(XR' r) - (4, r o ) l =-&I =-/I (2") . Palls x,T = 0. so ist f i = f und xu das starke Minimum von f t auf 9. 1st x,* =t= 0, so gilt fur H=(h i {x:, x o ) = ( x ~ , h)) nach [Sj, Lemma 1.2

folglich fur h,cM(jj*ll, H ) gilt x,-h,-0. Die Funktion f und damit auch f , hat auf H starkes Minimum. Nach Lemma 2 ist die Folge (x,) besohrankt und damit auch die Folge (h,). Da f LrPscHITz-stetig auf beschrgnkten Mengen ist, gibt es eine Tionstante L mit

lf(rp2)-f(hp2)l S L Ilx,-hxI!+O.

Hieraus fdgt

f l (h , ) - f l (~rl) >

also h,-:ro und somit x ,+xo . q. e. d.

Folgerung. Sei X ein reeller reflexiver BANACH~UUm und f : X -R eine nicht negative beschrankte konvexe Funktion. DafW, dap f auf jeder abgeschlossenen konvexen Menge ein starkes Minimum besitzt, ist notwendig und hinreichend, dub (f ' )* FRbcHET-differenzierbar id.

Hinliinglichkeit. Beweis. f und f 2 haben dieselben starken Minimallosungen. Daraus folgt die

13 Jlath. Nachr. Bd. 83

194 Kosmol/Wriedt, Starke Losbarkeit von 0pt.imierungsaufgaben

Wir zeigen: f' ist strikt konvex und (f')* ist endlich. Anders gesagt: (f?)* ist, GATEA'LIx-differenzierbar. Sei x , yE X und

f' (Y.+?)=pf'(x)+ 1 1 . . . f y Y ) , 2 2 2

dann folgt f ( x ) =f(y). f l hat auf dein Interval1 [ .r , y] ein eindeutiges Mininiutn. folglich x = y.

Sei inf {f(x) I l\xll= I } = r =- 0. Wir konnen voraussetzen, dal3 f ( 0 ) = 0.

(p)* (x*) =sup ((x", x)-j ' (x)) X € X

ist

und damit

(x*, x)-ff2(x)sIIx*ll - 1Ix11-11xlla - r , also ist (f2)* (x*) -= m, q. c. d.

Bemerkungen. 1. Aus der Differenzierbarkeit von f* folgt nach [l], 8. 461 &e stetige Differenzierbarkeit von f *. 2. Fur Normen ist die Folgerung wohlbekannt [2], S. 149.

Eine andere Charakterisierung von konvexen Funktionen, die auf jeder ab- geschlossenen konvexen Menge starkes Minimum besitzen, laat sich rnit dern Begriff der lokal uniformen Konvexitiit angeben.

Defition. Eine stetige konvexe Funktion f : X + R heipt lokal uniform konvex, wenn gilt

rnit V X E X V x * ~ a f ( ~ ) 3t.: R++Rf monoton

Z ( T ) t ( O ) = O , z(r)=-O far r+O und lim--=-, r+- r

so dap f ( X + Y ) Z f ( X ) + ( X * , Y)+T(llYIl) fGr a& yEX -

Satz 2. Sei X ein reeller reflexiver BANAcHraum und f : X - R eine nicht negative beschrankte konvexe Funktion. DafW, dap f auf jeder abgeschlossenen konvexen Menge starkes Minimum besitzt, ist notwendig und hinreichend, dap f' lokal uniform konvex ist.

Beweis. Sei f 2 lokal uniform konvex. Es gilt f u r x*Eaf(O)

KosnioliW'riedt, Starke Losbarkeit 77011 Optiniierungsaiifgaben f 9.5

foiglich bind alle Mengen S,L(r) heschrinkt und daiiiit i8t fur alle abgesrlilo,zsenen konvexen Jletigen K X(f . K ) * 0.

Sei k o c M ( f , K ) , cl. h. es existiert . ~ : E i f ( k ~ ) ) mit (x:? k - k l , ) s O fur alle k f l i ( [ ? I , s. 31). Zu k(, und ,r,* wahlen nir geintilj der Definition eine Funktion t. Fiir eiiie mini- mierende Folge ( k , ) gilt

also k,, + k,,. auf jecler ahgeschlossenen konvexen Jlenge ein starkes ~ l i n i ~ t i u i i i ,

so ist nach Folgerung 1 (I?)* FREcHET-differenzierbar. 6ei $€ Zf(x,,). Dann hat / ? ( a ) -(.r:, -) in xo das glohale starke Minimum. Fiir die nionotone Funktion

f ( k, ) - f (k , , ) z :.c". k,, - k,,) + t ( - ko!') ,

Besitzt

z ( ~ ) = inf (/! (-cO+y) - {xo, * .q,+y)-f2(.rO) + { J $ ~ -I.,,)>

' I / i = S

gilt soinit t ( O ) = O und z(S')>O fur S>O. \\'w kijntien annehmen, tlalj f(0) = 0. Sei S derart, daf3 fur Ily I z 8 gilt Ilxo+yi\ 2 1 . Dann folgt

(1. e. d.

Folgerung. Sei X e h reeller refleziver BANAcHraum und f : x'- R eine nicht negative beschrliwkte konvpre Funktion. f ? i s t gennzi dann lokal iiiiiform knnvex, w e m (ti)* FR&cHET-differe nz ierbar id.

Bemerkung. Lokal uniform konvexe Normen wurden von LOVAGLIA [3 J eingefiihrt. I n reflexiven Raumen hesitzen diese Normen auf jeder abgeschlossenen konvexen Menge ein starkes Minimum. Nach Satz 2 ist das Quadrat einer solchen Sorm eine lokal uniform konvexe Funktion.

[l] E. ASPLUNU and R. T. ROCKAFELLAR, Gradients of convex functions. Trans. Amer. math. SOC.

[2] R. B. HOJAIEY, A course on optimization and best approximation. Led. Notes Math. 267,

141 A. It. LOVAGLIA, Locally uniform convex Banach spaces. Trans. Amer. math. SOC. 78,225 - 238

[4] B. T. POWIR, Existence theorems and convergence of minimizing sequences in extremum

[5] R. T. ROCKAFELLAR, Convex Analysis, Princeton 1970. [S] I. SINGER, Best approximation in normed linear spaces by elements of linear subspaces.

189,443 -467 (1969).

Berlin-Heidelberg-New Pork 1972.

( 1955).

problems with restrictions. Dokl. 166, 72-75 (1966).

Berlin-Heidelberg-Xew York 1970.

Mathematisches Seminar der Universitat D-23 Kiel Olshusenst@e 40 - 60

13'