View
214
Download
1
Category
Preview:
Citation preview
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'
Recommended