2
Kleine Mitteilungcn 459 KLEINE MITTEILUNGEN ZAMDI 68, 459 -460 (1978) UWE MACKENIWTH 1) riuliliit und Approximution bei kunvexen Optinrieruags- I)roblonien 1. Einleitung Sei X ein BANAciI-Raum, f : S - k? ein konvexes, stetiges Funlitional und sei C' eine nichtleerc, konvexeTeilmenge von X. D a m konnen wir das folgende Optimierungsproblem betrachten : (P) Wir dcfinieren inf I' : = inf f(x) . Weiter seien zu jedem n E N ein konvexcs, stetiges Funklional f,, : X --t R iuid eine nichtlecre, konvexe Teilmenge C, von X gegeben. Dic Funktionale f, seien in einem Sinne, der spater praxisiert wird, Approximationen von f. Ebenso seien die Mengen C, Approximationen von C. Dann kann folgendes ,,diskrete" Optimieruiigsprobleni aufgestellt warden: (P,) welchen Voraumctzungen lim inf P, = inf P gilt. Hicrbci sei Minimiercf(z) iiber alle x E c' . X€C Minimieref,(z) iiber alle z E Cn . In dieser Arbeit sol1 die Frage untersuclit werden, nntcr n->a, inf l', := inf fn(x) - X€C* Eine derartige Problematik entsteht z. B., wenn ein liontroll- problem oder ein Variationsproblem niit Nebenbedingungen durch eine Folge diskreter Probleme ersetzt wird. ISs gibt bereits eine R.eihe von Arbeiten, die sich )nit diesem Thema beschaftigen, vcrgleiche etwa den Ubersichtsartikel von KRABS [7] und die dort angegebenen Literaturhinweise. Viele Autoren beschaftigen Rich dabei mit allgemeinen nichtkonvexen Optimierungsproblemen. Wir beschranken uns dagegen in dieser Arbeit auf konvexe Probleme und zeigen, daB diese eine Reihe von Besonderheiten haben, die sich bei konkreten Anwendungen haufig als vorteilhaft erweisen. Setzt man voraus, daB zu den Problemen (P,) und (P) Dualprobleme gegeben sind, so ist es insbesondere moglich, die fur das primale Problem ublichen Voraussetzungen abzuschwichen und dafiir entsprechende Vor- aussetzungen fur die Dualprobleme einzufiihren. Sei also zu (P) ein Dualproblem (D) und fur jedes n E N zu (P,) ein Dualproblem (D,) gegeben: (U) (U,) Hierhci seien C'*, C*, fur alle n E N nichtleere, konvcxc 'l'eil- mengen eines BANACH-Kaunies Y und f* : Y + e, fen: Y -t k? lionkave, stetige Funktionale. Wir nehmen uberdies an, daD die folgenden DU a1 i t B t saussagen rrfullt seien : (VO) Fur allc 7~ E N gilt: inf P = sup D , Hierbei seien slip D, sup I), analog wie inf P, inf 1', definiert. Wciter sei noch angemerkt, daD unter dcr Voraussetzung (VO) alle tLuftretendcn Extremalwcrte groBer als - 00 und klcincr als -1- co sind. Maxiniiere f,(u*) uber alle u* E C, . Maximicro f*n(u*) iiber alle u* E C*, . inf P, = sup D, . 2. lionvergell tc Approxiniatioiicri kollvexer 01)- ti m i e r 11 11 g sp ro b 1 em e W ird ein Koiivcrgenzsatz de,r oben angedenteten Art angestrcbt,, so braucht man im allgenieinen eine Voraussetzung, die in irgend einer Form gleichgradige Stetigkeit der f, beinhaltet. Es zeigt sich, daB man eine derartige Aussage bei ciner Familie konvexer Funktionale allgeniein aus punktwciser Beschranktheit schlieBen kann. Dicwr Sacliverhalt wird durch das folgende Lemma prP- zisicrt. T,(:mma 1: Sei X ein BANAcH-Raum, {f,} eine Pamilie kon- ~o.wr, statiger, awf yanz X rlefinierter Funktionale, die betrags- wiiJ,iy punkluieise yle,ichmuJGj beschranlt sind. Dann gibt es iu beliebigem xu E S eine ieelle Konstante c und eine Kugel KQ(xo) mit Radius Q > 0 um xv, so daJ fn(z) -fn(xo) 5 cJ1x - xoll fur alle x t Kp(.ro) ud nlle n E N . Be w e i s : Fur beliebiges x E X setze P(X) := SUP (fnb) -f?l(ql)) * naV P ist ein auf X nacli unten halbstetigeu konvexcs Funktionid und dalicr auf X stctig (vgl. EKELAND, TEhlAbl [el). Ein stctigcs konvexes Funktional euf einem linearen norniierten Raum iat aber lokal Lll~Sl*H ITZ-Stetig (vgl. ebenfalls EKELAND, TR~A 11 121). Es gibt also eine reelle Konstante c und eiiie Kugel KQ(x,,) mit Radius e > 0 um zo, so daB Iw4 - F(Y)l 5 c112 - YII fur alle 2, y E K,,(xo) gilt. Hieraus folgt sofort die Sehauptriiig. Bcmerkung: Dieses Ergcbiiis folgt such ails aincni Satz von KOSMOL 131. Ein rtnderer Beweis findet sicli in MAC'KEX- Fur den Konvergenzsatz bcnotigeii wir dic folgendcii Vor- Zu jedem z E C existiert eine Polge {xn} c S niit .rn E C', fiir alle n E N wid z = lini 1.)). Y<ir allc :c c S gill ROTli [8]. au s s e t z u n g e n : (Vl) n+m (VZ) lirn supf;&r) 5 f(;c) . n+ w (V3) Zu jedem x c S existicrt cilia rcallc Konstnnte cI, SO daU f,(r) 2 cx fiir alle n E N . Analoge Voraussetzungen machen wir flr die Uiial- pr ob 1 em e : (Vl,) Zu jedem u* E C, cxistiert eine Folge {u?} c Y niit uf t C!*n fiir slle n E N und u* = lirn u:. (V2,) Pdr allr u* E Y gilt IlAW lirn inff,,(u*) -2 ]*(a*) . n+w (V3,) Zu jedem u* c Y existiert eine reelle Konstantc cI*, so daD f*,(u*) 5 cu* fur alle u E N. Satz: Fur die 2C1i~~irr~ierui~~s~rob1e~t~e (PIJ ulid (P) ytlt unhr den Voraussetzungen (VO), (Vl)-(V3) und (Vl*)-(V3.+) die Bc - ziehuny lini iiif PN = inf P . n-t w Reweis: Sei e > 0 gegeben. Es gibt oin .r, c C' init Nach den Voranssrtzuiigeii (V2), (V3) uncl lAeiiiiiir~ 1 gibt cs Iconstanten Q > 0, c >> 0 iriit f&) -jll(.rv) 5 c 1I.c - roll fir allc .r t Ke(.ru) rind tdlc ( IW . ein nv, SO dtlD fur dle n 2 ?lo, 3: E KP,(:rO) fn(4 -Ax") = f&) - fn(:co) i- frd4 - m v ) 5 c 112 - xvll 4- f,(Z") -f'(xo) 5 ~$ E. Nacli Vorausset,zung (Vl) gibt as ein 7t1, so dsD ZII jedeni t1 :L 11 cin zn t C, n K,,(q) esisl.iert. Also folgt fiir dlc 71 .k '11, = niax {no, nl} inf Y, 5 fiL(.r,J 5 f(xo) -$- t' 5 iiif 1' -t E . (2.1 Eine analoge Uberlegung fur die I)ualprobleme wig(, tlaO cs ciri n3 gibt mit sup D - E 5 sup I), far alle Zusammen niit Voraussetiung (VO) und (2.1) folgt liicraris dic Behauptung. Vergleicht man die Voraussetzungen dieses Satzes mit bis- herigeii Ergebnismn im allgemeinen, nichtkonvcxen Fall, so zeigt sich, dall nur Voraussetzungen iiber das punktweise Ver- lialt,en der f, (bzw. fen) benotigt werden, im Uegensatz etwa ZLI n 2 n3.

Dualität und Approximation bei konvexen Optimierungsproblemen

Embed Size (px)

Citation preview

Page 1: Dualität und Approximation bei konvexen Optimierungsproblemen

Kleine Mitteilungcn 459

KLEINE MITTEILUNGEN

ZAMDI 68, 459 -460 (1978)

UWE MACKENIWTH

1) riuliliit und Approximution bei kunvexen Optinrieruags- I)roblonien

1. E i n l e i t u n g

Sei X ein BANAciI-Raum, f : S - k? ein konvexes, stetiges Funlitional und sei C' eine nichtleerc, konvexeTeilmenge von X . D a m konnen wir das folgende Optimierungsproblem betrachten : (P) Wir dcfinieren inf I' : = inf f(x) . Weiter seien zu jedem n E N ein konvexcs, stetiges Funklional f,, : X --t R iuid eine nichtlecre, konvexe Teilmenge C, von X gegeben. Dic Funktionale f, seien in einem Sinne, der spater praxisiert wird, Approximationen von f. Ebenso seien die Mengen C, Approximationen von C . Dann kann folgendes ,,diskrete" Optimieruiigsprobleni aufgestellt warden: (P,)

welchen Voraumctzungen lim inf P, = inf P gilt. Hicrbci sei

Minimiercf(z) iiber alle x E c' .

X€C

Minimieref,(z) iiber alle z E Cn . In dieser Arbeit sol1 die Frage untersuclit werden, nntcr

n->a,

inf l', := inf fn(x) - X€C*

Eine derartige Problematik entsteht z. B., wenn ein liontroll- problem oder ein Variationsproblem niit Nebenbedingungen durch eine Folge diskreter Probleme ersetzt wird.

ISs gibt bereits eine R.eihe von Arbeiten, die sich )nit diesem Thema beschaftigen, vcrgleiche etwa den Ubersichtsartikel von KRABS [7] und die dort angegebenen Literaturhinweise. Viele Autoren beschaftigen Rich dabei mit allgemeinen nichtkonvexen Optimierungsproblemen. Wir beschranken uns dagegen in dieser Arbeit auf konvexe Probleme und zeigen, daB diese eine Reihe von Besonderheiten haben, die sich bei konkreten Anwendungen haufig als vorteilhaft erweisen. Setzt man voraus, daB zu den Problemen (P,) und (P) Dualprobleme gegeben sind, so ist es insbesondere moglich, die fur das primale Problem ublichen Voraussetzungen abzuschwichen und dafiir entsprechende Vor- aussetzungen fur die Dualprobleme einzufiihren.

Sei also zu (P) ein Dualproblem (D) und fur jedes n E N zu (P,) ein Dualproblem (D,) gegeben:

(U) (U,) Hierhci seien C'*, C*, fur alle n E N nichtleere, konvcxc 'l'eil- mengen eines BANACH-Kaunies Y und f* : Y + e, f e n : Y -t k? lionkave, stetige Funktionale. Wir nehmen uberdies an, daD die folgenden DU a1 i t B t s a u s s a g e n rrfullt seien : (VO) Fur allc 7~ E N gilt: inf P = sup D , Hierbei seien slip D, sup I), analog wie inf P, inf 1', definiert. Wciter sei noch angemerkt, daD unter dcr Voraussetzung (VO) alle tLuftretendcn Extremalwcrte groBer als - 00 und klcincr als - 1 - co sind.

Maxiniiere f,(u*) uber alle u* E C, . Maximicro f*n(u*) iiber alle u* E C*, .

inf P, = sup D, .

2. l i o n v e r g e l l t c Approxiniat ioi icr i kol lvexer 01)- t i m i e r 11 11 g sp ro b 1 e m e

W ird ein Koiivcrgenzsatz de,r oben angedenteten Art angestrcbt,, so braucht man im allgenieinen eine Voraussetzung, die in irgend einer Form gleichgradige Stetigkeit der f, beinhaltet. Es zeigt sich, daB man eine derartige Aussage bei ciner Familie konvexer Funktionale allgeniein aus punktwciser Beschranktheit schlieBen kann. Dicwr Sacliverhalt wird durch das folgende Lemma prP- zisicrt.

T,(:mma 1 : Sei X ein BANAcH-Raum, {f,} eine Pamilie kon- ~ o . w r , s ta t iger , awf yanz X rlefinierter Funktionale, die betrags- wiiJ,iy punkluieise yle,ichmuJGj beschranlt sind. Dann gibt es iu beliebigem xu E S eine ieelle Konstante c und eine Kugel KQ(xo)

mit Radius Q > 0 um xv, so daJ fn(z) -fn(xo) 5 cJ1x - xoll f u r alle x t Kp(.ro) u d nlle n E N .

B e w e i s : Fur beliebiges x E X setze

P(X) := SUP (fnb) -f?l(ql)) *

naV P ist ein auf X nacli unten halbstetigeu konvexcs Funktionid und dalicr auf X stctig (vgl. EKELAND, TEhlAbl [el). Ein stctigcs konvexes Funktional euf einem linearen norniierten Raum iat aber lokal Lll~Sl*H ITZ-Stetig (vgl. ebenfalls EKELAND, T R ~ A 11 121). Es gibt also eine reelle Konstante c und eiiie Kugel KQ(x,,) mit Radius e > 0 um zo, so daB

Iw4 - F(Y)l 5 c112 - YII fur alle 2, y E K,,(xo) gilt. Hieraus folgt sofort die Sehauptriiig.

B c m e r k u n g : Dieses Ergcbiiis folgt such ails aincni Satz von KOSMOL 131. Ein rtnderer Beweis findet sicli in MAC'KEX-

Fur den Konvergenzsatz bcnotigeii wir dic folgendcii Vor-

Zu jedem z E C existiert eine Polge { x n } c S niit .rn E C', fiir alle n E N wid z = lini 1.)).

Y<ir allc :c c S gill

ROTli [8].

a u s s e t z u n g e n : ( V l )

n+m

(VZ) lirn supf;&r) 5 f(;c) .

n+ w

(V3) Zu jedem x c S existicrt cilia rcallc Konstnnte c I , SO daU f,(r) 2 cx fiir alle n E N .

Analoge V o r a u s s e t z u n g e n machen wir f l r die Uiial- pr o b 1 em e : (Vl , ) Zu jedem u* E C, cxistiert eine Folge {u?} c Y niit

uf t C!*n fiir slle n E N und u* = lirn u:.

(V2,) Pdr allr u* E Y gilt I l A W

lirn inff,,(u*) -2 ]*(a*) . n + w

(V3,) Zu jedem u* c Y existiert eine reelle Konstantc c I * , so daD f*,(u*) 5 cu* fur alle u E N.

S a t z : Fur die 2 C 1 i ~ ~ i r r ~ i e r u i ~ ~ s ~ r o b 1 e ~ t ~ e (PIJ ulid (P) ytlt unhr den Voraussetzungen (VO), (Vl)-(V3) und (Vl*)-(V3.+) die Bc - ziehuny lini iiif PN = inf P . n-t w

Reweis: Sei e > 0 gegeben. Es gibt oin .r, c C' i n i t

Nach den Voranssrtzuiigeii (V2), (V3) uncl lAei i i i i ir~ 1 gibt c s Iconstanten Q > 0, c >> 0 iriit f&) - j l l ( . r v ) 5 c 1I.c - roll f i r allc .r t Ke(.ru) rind tdlc ( IW .

ein nv, SO dtlD fur dle n 2 ?lo, 3: E KP,(:rO)

f n ( 4 - A x " ) = f&) - fn(:co) i- f r d 4 - m v ) 5 c 112 - xvll 4- f,(Z") - f ' (xo ) 5 ~$ E .

Nacli Vorausset,zung (Vl ) gibt as ein 7t1, so dsD ZII jedeni t1 :L 1 1

cin zn t C , n K , , ( q ) esisl.iert. Also folgt fiir dlc 71 .k '11, = niax {no, nl } inf Y, 5 fiL(.r,J 5 f(xo) -$- t' 5 iiif 1' -t E . (2.1

Eine analoge Uberlegung fur die I)ualprobleme wig(, t l a O cs ciri n3 gibt mit sup D - E 5 sup I), far alle Zusammen niit Voraussetiung (VO) und (2.1) folgt liicraris dic Behauptung.

Vergleicht man die Voraussetzungen dieses Satzes mit bis- herigeii Ergebnismn im allgemeinen, nichtkonvcxen Fall, so zeigt sich, dall nur Voraussetzungen iiber das punktweise Ver- lialt,en der f, (bzw. fen) benotigt werden, im Uegensatz etwa ZLI

n 2 n 3 .

Page 2: Dualität und Approximation bei konvexen Optimierungsproblemen

entslirecheiiden Ergcbnisscn Iwi K l t a H s 141, 151, LU 1) otlcr T)a- 1.11. 1 S i n z i g K o s ~ o ~ [3] ltonimt niit Voraussetzurigcm puiikt-

weiser Art aus. Dort wird allerdings vorausgesetztr, (la0 die RIengen C,, C in eiii Kompaktum cinbcttbar seien. Dariibcr hinaus lassen sich dic Voraussctzungen in KOBMOL [3] mit den unserigen nicht unniittolbar vergleichen, da wir fiir den Konvcr- genzsatz die Dualprobleiiie mit heranziehcn.

Irii AnschluU an den Konvergenzsatz stellt sich natiirlich die It’rage, ob etwa vorhandene Optimallosungcn dcr diskrctcn Problenie (Pn) gegeii cine, ebenfalls als existent angenoniiiicne Optjimalliisung dcs kontinuierlichen Problems (P) konvcrgieren. Uiescni Probleni sol1 hier aber niclit nachgegangcn werden, da, inan Konvergenzaiissagen dicser Art rnit gingigcri Schlusscri atis dcr Konvcrgeiiz der Extremalwerte folgern kaiin. Fur eiiieii Satz dieser Art urid cine Anwendung auf parabolischc I<ontroll- problcnic sei anf MACKENROTH [Sl verwiesen. Dort werdeii fii! parabolischc Kontrollproblenie auch Dualproblenie aufgestellt,, u ~ i d es werden Uiskret,isicrungen cingefiihrt, fur die sich die Voraussct)ziingcn dcs lionvcrgenzsatzcs nacliprufen lilsseri.

T n konkreten Anwendungen tritt liBufig iii der dualen Ziel- funktion ein Terrn auf, in deni das lnfiniuni iiber cine gcwissc konvexe Menge K gebildet wird. Jm diskreten Problem wird dann das Infimum iiber eine Approximation K , von K gebildet. I n einer derartigen Situabion erweist sich bcim Nachweis von Vornussetzung (V2,) dss folgende Lemma als niitzliuh. Eine Anwendung findet sich in MACKENROTH IS].

Lemma, 2 : J‘eierh K , und K nichtleere, konvexe Teilmengen eines BANACE-Raurnes X, und sei g : X --t R ein konvexes, auf teschrankten Mengen gleichni,aJ3ig stetiges Purtktionccl. Palis K nicht beschrankt ist, konvergiere { y ( x n ) } yeyen 00, wen?/. { x l l } eine Polge aus X i s t w i t lim llxnll = cv. Weiter existiere i n diesem

Pall zu jedem n E N ein x: E K,, so dujl {g(x:}) nach oben be- schrankt ist. Schliejllich existiere zu jeder E’olge { x,} rnit 5, € K , C r alle IL E N eine Polge {Zn} c K , so daJ3 lini 112% - Znll = 0.

I)onn gilt

inf g(x) 5 lim inf (inf g(z)) . x< li 11’00 X € K ,

n+m

7L+ w

Ueweis: Sei E > 0 gcgeben. Zu jcdeni ?L E N gibt es ein x, E X , init

Zu {x,} existiert eine Folge {?,2) c K mit linl IjxR - En/] = 0.

Nach iiriscren Voraussetzungen liegen diese bcidcn Folgen in einer bcschriinkten Menge. Ware etwa { x,} nicht bcschrinkt, so gabe es eine Teilfolgc { x n i } rnit lini Il.cnill = 00. und &US (2.2)

wiirde lini (inf ~ ( z ) ) = 00 folgcri, was wcgeri inf y( . r ) .s g(ze,)

nicht sein k a d EB gibt dtzhcr cin riot so daW

n+m

i -, uu

i+oo ZE lie. xcJYni

1Iieraus folgt n i i t (2.2) fur alle n ,. 11”

inf ! j (x) 5 g(i,) 5 inf g(s) + c , xc N Z € K Z

also dic lkliauptung.

Hingereiclit: 11. 2. 1977, revidicrtc E’assitng: 30. 8. 1!)77

A u 4 k r i j t : Dr. Uwx ~ ~ A W E N I W T I I , Universitat BnIrcuth, UniversitfitsstraUe 40, D-8580 Uayretitli, U1:D

Naehkurrchtiir boi iiiiiiwriwhvr t)nittlriiliir

’In dcr Arbeit wird cin Prinzip ziir Vcrklcincrung drs Vcrfiilireiis- felilers bei nuinerischer Quadratur vorgesclilagen. Dioscs Prinzip enthalt als Spezialfall die bckannte Korrekturvorsrhrift dcr RoMBERG-Quadratur, kann aber auch eingesetzt merden, wenn iibcr das Fchlcrgesctz kcinc Information vorliegt bzw. wenn sich der Verfahrensfehler niclit nach h-Potenzen entwickeln laBt. Es wird gezeigt, daD im Fall analytischer I n t e p n d e n allc Korrckturen nach dicsem Prinzip im wcscntlichen 1toniBmG- Korrekturen bind und in Fallen, bei denen die HOMRERC-VOT- schrift verssgt, durch Wahl gceignctcr VerF;ieirhsfunktior~cn Verbesserungcn zu crzielcn sind. Numerische Beispiele bestati- gen die theoretischen Ergebnisse.

Es sei N ( h , j ) ein Naherungswerfahren (Quadraturforinel) zur

Berechnung von P = J f(z) dx niit den1 DiskretisierungsI~aru-

meter (Schrittweite) h. Ausgehend von der trivialen Bezirhung

b

a

(a # 1, fest) (die auch, in [l], [2] bcnutzt wurde) ksnri inan vcrsuchen, t l i i rdi geeignete Approxiniationen des Quotientcn in ( 1 ) gntc Nahcrun- gen fur F zu crhalten.

A) A p p r o x i m a t i o ri d u r c 1i V e r w e n d ti ug e i n e r H i 1 f s f n n k t i o n

b Jh sei g(x) eirie Funktion, fur die G = J g(s) dx leivht exakt zii

berechnen ist. AuDerdeni wird fur N vorausgcsetzt,. daU gilt:

a) 8’ - N ( h , f ) = c . f ,(h) -1 o(f , (h) ) (VN1) b) G N ( h , g) = c E . g,(h) 4 o(g,(h)) fur h -+ 0

mit c, r l = const. uncl g,(h) --f 0 nnd !,(A) + 0 fiir h + +o, tuid fur fcstes a # 1 wid geniigend lileines h > 0 yo11 gcltcn

( V 9 2 )

a

fur h + -i 0 ,

N ( h , g) # N ( & y) . Betrachten wir ncbcn N ( h , , f ) novh

dann gilt dcr folgeiidc

S a t z 1: Ir’ctlls

gilt, d a m ist untcr den Vornussetzungen ( V n ’ l ) u t d (I”-‘) M(h , f, v) ein Nalie~ur~gsoerjul~rer~~ zur Berechnung von F, und es gilt

11 > 10 11111 (1’ - N ( h , j , g))/(P - N(h , f ) ) = 0 . (4)

Beweis : Fur h --f $0 gilt nach (VNl )