Vol. XXVI, 1975 193

Proximinalit~it und Algorithmen bei konvexer Approximation

Von

PETER KOSMOL und MICHAEL WRIEDT

Ffir stetige und symmetrische konvexe Funktionen wird die Existenz minimaler Elemente mit Hilfe der Minkowski-Funktionale der zugeh6rigen Niveau-Mengen un- tersucht. Angewendet auf Orlicz-Ri~ume ergibt sieh, dal3 minimale Elemente bezfiglich des Modulars genau dann existieren, werm sie bezfiglich der Luxemburg-Norm existieren. I m zweiten Teil wird der Satz yon Kripke fiber Stabilit~tt bei Approxima- tion bezfiglieh Normen auf konvexe Funktionen verallgemeinert.

1. Proximinalitiit. Sei X ein separierter topologischer Vektorraum, / : X - - > ~ eine stetige und symmetrische konvexe Funktion mit /(0) = 0 trod /(x) > 0 / f i r x ~= 0. I m weiteren schreiben wit daffir (X,/) .

Ffir eine Teilmenge M c X und x e X sei

/(x - - M) = in//(X -- m) . m e M

Gilt / f i r ein m0 e M

/ ( x - M ) = / ( x - - too),

�9 so heil~t m0 eine bes te / -Approximat ion yon x durch M. Die Menge aller Punkte mit dieser Eigenschaft wird mit PM (x, /) bezeichnet. M heil3t/-proximinal, wenn PM(X,/) # O/fir alle x e X ist.

Ffir r > 0 bezeichne Sf(r) die absolutkonvexe und abgeschlossene Nullumgebung

(x If (x) _< Aus den Voraussetzungen fiber / fo!gt, dab S/(r) linear beschr/inkt ist, und daher

definiert das Minkowski-Funktional

/IX!Iv = in/{,Tt > O l x e 2 S y ( r ) }

eine stetige Norm auf X. Versehen wir den Vektorraum X mit der yon H" [1 r herrfih- renden Normtopologie, so wird dieser Raum mit Xv bezeiehnet.

Lemma 1. Ist r > 0 undc > O, so gilt

r q - c Sz(r) c Sz ( r + c) c $i(~) . ?*

Archly der Mathematik XXVI 13

194 P. KOSMOL und M. WRIEDT ARCH. MATH.

B e w e i s . . S f ( r ) c Sf (r ~- c) ist offensichtlich. Sei x e s f ( r -~ c), a l s o / ( x ) ~ r ~- c. r

Es ist zu zeigen - - x ~ S/(r). Es gilt r ~ c

( r - - - ~ ) ( ( r ) ) r r r x + 1 . . . . 0 < / ( x ) _ < r . q.e.d. ! x ----! r - ~ c r - ~ c = r ~ c

Aus Lemma 1 folgt insbesondere, dab je zwei Normen 1[" Ii r, ll" II r" auf X s sind.

Lemma 2. a) / (X) <= r ist gleichwertig mit [[X]ir ~ 1.

b) ] (x) = r ist gleichwertig mit ]] x ][ r = 1.

B e w e i s . a) Offenbar folgt nxHr -<_ 1 aus f(x) <- r. Is t andererseits ]]X]Ir <= 1, so gilt ](x) <= r, weft S1(r ) abgesehlossen in X ist.

b) Sei ](x) ---- r, so ist !Ix!It __< 1. Angenommen fix!It < 1; dann gibt es d > 1 mit lldxl[r <-_ 1, folglich nach a ) / (dx ) <= r. Es gilt aber

r = ! (x) = / < / ( d x ) < r ,

was ein Widerspruch ist. Is t II x t]r ~-- 1 und ! (x) < r, so existiert wegen der Stet igkeit yon ! d > 1 mit

/(dx) ~ r, also nach a) IIdxHr ~ 1, Widerspruch! q.e.d. I s t / nicht notwendig konvex, sondern eine normart ige Metrik, s~ gilt das Lemma 2

entsprechende Ergebnis, und die folgenden S~itze 1 und 2 besitzen ein Analogon in der Approximationstheorie beziiglich dieser Metriken (siehe [8]).

Satz 1. Sei K eine Teilmenge yon X , x ~ K und ! (x - - K) ~- r ~ O. Die Aussagen PK(x, ]t" llr) :~= 0 und PK(x, 1) ~ 0 sind gleichwertig.

B e w e i s . Es ist fiir jedes k e K nach Lemma 2 I[x--k]lr ~ 1, also I lx - -Kl l r ~ 1 . W~re ][ x - - K l! r ~ d > 1, dann gilt nach Lemma 1 ftir c ---- d - - 1

S:(r + c) c dS/(r) .

Sei ! (x -- lc0) =< r q- c ffir k0 e K. Man hat

0:4= Sf (r + c) ~ (x - - K) c dSf(r) N (x -- K) :

---- {Y [ II Y IIr ----< d} n (x - - g ) , Widerspruch !

Also ist 11 x -- g ]l r -~ 1. Sei nun PK(x, If" Ur) ~ 0, d .h . es existiert ein kl e K mit

II x - k l II, = 1 ,

woraus mit Lem ma 2

] (x - - /e l ) ---- r folgt.

Die Umkehrung folgt analog aus Lemma 2. q.e.d.

Vol. XXVI, 1975 Konvexe Approximation 195

Korollar. Sei K eine Teilmenge von X mit

/ ( x - - K) > O ]iir alle x e X - - K .

Is t K / i~r jedes r ][-U r-proximinal, so ist K f-proximinal.

Ffir Hyperebenen gilt im Korollar auch die Umkehrung:

Satz 2. Sei H e i n e Hyperebene in X . H ist genau dann f-proximinal, wenn die beiden/olgenden Aussagen er/iillt sind.

a) H ist /iir jedes r > 0 ]I" fIr-proximinal,

b) / ( x - - H ) > O fiiraUe x e X - - H .

Beweis . DaB aus a) un4 b) die/-Proximinalit~t yon H folgt, ist die Aussage des Korollars. Sei umgekehrt H/-proximinal und x ~ H. Es ist klar, dab / (x -- H) ---- r0 > 0. Nach Lemma 2 gilt

ll~ - H[I~. > l ;

folglieh ist H in Xr0 abgesehlossen und damit aueh in jedem Raum X r (Lemma 1). Insbesondere ist

[ l x - n l I r > 0 fUralle r > 0 .

Ffir die Proximinalit/~t einer Hyperebene in einem normierten Raum reicht es aus, zu zeigen, dab PH(X) ~ 0 fur ein x ~ H ([7], Abschn. 2, Lemma 2.1). Sei also

I Ix-Hl l r >= 1.

(Anderenfalls gibt es d mit II d x - - H []r ~ 1.) Folglich gilt

/ ( x - - H ) ~ r (Lemma2) .

Die Funktion

x ~ / ( x - - H )

ist konvex ([2], Seite 47). Insbesondere ist fur ein festes x0

f~ : d ~-> f (dxo - - H)

eine stetige konvexe Funktion JR+->JR+. Weft/~(0) ----0 und ~(1) ~ r, existiert nach dem Zwischenwertsatz ein do mit

fiR(do) = / ( d o x - - H) = r .

Weil H/-proximinal ist, gibt es h0 e H mit

/(dox - - ho) : r .

Wieder aus Lemma 2 ergibt sich

II dox - ho ]lr = 1, damit ho ~ PH (dox, 1[" lit),

womit gezeigt ist, dab H [[-llr-pr~ ist. q.e.d. Fiir den n~chsten Satz wird die folgende Bedingung verlangt:

(*) xn --> O genau dann, wenn / (xn) -->0.

13"

196 P. KOSMOL und M. WRIEDT ARCH. MATH.

Sie ist nur in normierten R/iumen X erffillbar. Denn ist X nicht normierbar und Xn ~ 1/n. S/(1), dann folgt aus Lemma 1

/ (xn) - 7 0 .

Sei VcSf(1) eine zu S/(1) nieht ~quivalente Nullumgebung, d.h. fiir alle n e N gilt

1 - - S / ( 1 ) ~ V . n

Sei also Xn so gewi~hlt, dab Xn ~ V ist. Das bedeutet aber, dab Xn nicht gegen 0 konvergiert.

Sei nun X ein normierter Raum und ffir (X , / ) die Br (*) erffillt. Aus den vorangehenden ~berlegungen folgt, dab die Norm [I" ]11 die Topologie yon X erzeugt, d.h. zu der auf X gegebenen Norm i~quivalent ist.

Satz 3. Sei (X, I[" ':[) ein Banachraum und (X, /) er/i~lle die Bedingung (*). Es sind 5quivalent:

a) X ist reflexly. b) Alle abgeschlossenen konvexen Mengen sind /-proximinal.

c) Alle abgeschlossenen Hyperebenen sind /-proximinal.

Beweis . Ist X reflexly, so sind nach der vorangehenden Bemerkung und Lemma 1 alle R~ume Xr reflexly. Jede abgeschlossene konvexe Menge ist daher I1" I[r-proxi- minal. Sei K c X abgeschlossen und konvex, x ~ K. Aus (*) folgt

I] x -- K H = 0 gleichwertig mit / (x -- K) = 0.

Folglich ist / (x- - K) > 0, auBerdem ist K ]]. I1 r-proximinal, womit aus dem Korollar die Aussage b) folgt.

DaB c) aus b) folgt, ist trivial. Es bleibt zu zeigen, dab a) aus e) folgt. Dieses ergibt sich aber sofort aus Satz 2 und der ~quivalenz yon ]]. ][ und I]']11. q.e.d.

Bemerkungen. Falls der Raum X1 ein nicht reflexiver Banachraum ist, so folgt aus Satz 2, dab es eine nicht/-proximinale Hyperebene gibt. Diese Aussage gilt also ohne die Bedingung (*).

Andererseits sind die Aussagen a) und c) yon Satz 3 ohne irgendeine Voraussetzung fiber / nicht ~quivalent. Denn sei X = 12 und / (x) = sup I xi I �9 ] is t auf 12 eine stetige Norm, die eine echt gr6bere Topologie als die vorhandene erzeugt. Da normierte R/iume die feinste zul~ssige Topologie besitzen (Maekey-R/iume), gibt es in l 2 eine abgeschlossene Hyperebene H, die nicht bezfiglich / abgeschlossen ist. Ftir jeden Punkt x e l~ gilt dann / ( x - - H ) =-0, also gibt es zu keinem x ~ H e i n e beste/-Ap- proximation.

Aus der Tatsache, dab X1 reflexiv ist, folgt wieder mit Satz 2, dab alle Hyperebenen /-proximinal sind, die / (x -- H) ~ 0 ffir alle x e X -- H erfiillen.

Ist der Raum X nicht normierbar, so gibt es eine stetige Norm II" H, die nicht zu ]I" ]i 1 ~quivalent ist und

II l]~ < II" I1

Vol. XXVI, 1975 Konvexe Approximation 197

erfiillt. Darm existiert wieder eine bezfiglich [1" II abgeschlossene Hyperebene H, die in X1 dicht liegt. Wegen Lemma 1 ist H auch in jedem Xr dicht, folglich gilt ffir jedes r > O u n d x C H

0~- []x-- Hnr < 1

und damit wegen Lemma 2

[ ( x - - H ) < r f f i r jedes r > 0 .

Also ist PH (x, [) = O. Damit ist gezeigt, dab es auf einem nicht normierbaren Raum eine nicht ]-proxi-

minale Hyperebene gibt. Sei ~b : ~ -+ ~ eine nicht identisch verschwindende, stetige symmetr ische konvexe

Funk t ion mit ~5 (0) ---- 0. Ferner sei T eine kompakte Teilmenge yon ]Kn Ffir Lebesgue mel3bare Funkt ionen x auf T definieren wir (die Luxemburg Norm)

ilxl[ : = inf{c -11 ~qS(cx)dt ~ 1} c > 0 T

u~d den Orliezraum L r als die Menge aller meBbaren :Yunktionen x auf T, ffir die H x ]1 r < oo ist. Das Funkt ional ]1" 11r definiert eine Norm auf L r mit der L ~ ein Banachraum ist.

Weiter sei M v der yon Treppenfunkt ionen aus L r aufgespannte abgesehlossene Tei l raum yon L r Es gilt (s. [6], S. 557)

{x L I f (kx)< alle k>0), T

und mit Hilfe des Lebesgueschen Satzes yon der monotonen Konvergenz folgt daraus

(1) ][ x I] ~ = 1 ~ f r (x) d# = 1, x e M* (#). T

Das Modular ] : M r --~ ~ mit

](x) :-= ~qS(x) dt T

ist stetig und konvex. Die Konvexit/~t yon / folgt unmit te lbar aus der Konvexit/~t yon ~b, und die Stetig-

kei t folgt, da wegen (1) [ auf der Einheitskugel yon M ~ beschr/~nkt ist ([1], S. 341).

Satz. Es sind die ]olgenden Aussagen gleichwertig:

(a) A lle abgeschlossenen H yper ebenen ( lconvexe M engen ) yon M ~ s~nd ]- pr oximinal.

(b) Alle abgeschlossenen Hyperebenen (lconvexe Mengen) von M ~ sind 1[" ]1 r

(c) Alle abgeschlossenen Hyperebenen (konvexe Mengen) yon L r sind I1" II r

(d) Fi~r die Fun]ction q5 gilt :

(i) Es existieren so > 0 und k > O, so daft ~b(2s) < k~b(s) ]iir s >~ so, (ii) die kon]ugierte Funktion ~P von q5 ist stetig.

(e) L ~ ist re/lexiv.

198 P. KOSMOL und M. WRIEDT AP, CH. MATH.

Beweis . Die Gleichwertigkeit yon (c), (d) und (e) wurde in [3] gezeigt. Da L ~ genau dann reflexly ist, wenn M e reflexly ist (s. [6], [4] S. 150) gilt (c) ~ (b). Aus der Reflexivit~t yon L ~ folgt bereits die Bedingung (*) (s. [5] und [4] S. 93). Nach Satz 3 folgt damit (a) aus (b) und aus der Bemerkung zu Satz 3 die Umkehrung.

2. Algorithmen. Seien [~, [ : Rn __> ]Ft wie in Abschnitt 1 und [g gegen / punktweise konvergent.

Da X - = R n, ist die Bedingung (*). ftir ] erfiillt. Sei ngmlich ] ( x - - x n ) --> 0 und x0 ein Hgufungspunkt der Folge xn. Aus der Stetigkeit yon ] f o l g t / ( x - - x o ) = O und damit x = x0. Satz 3 besagt nun, dab jede abgeschlossene konvexe Menge/- und [k-proximinal ist.

Das Ziel ist es, die besten/-Approximationen mit tIilfe der (m6glicherweise leichter zu ermittelnden) besten/k-Approximationen zu berechnen. Zun/~chst beweisen wir das

Lemma 3. Fi~r alle r > 0 und 0 < d < r existiert ein ko , so daft [i~r alle k >= ko

Ss(r - d) c S/~ (r) c~1(r + d) gilt.

Beweis . Zun/ichst wird bewiesen: Es gibt ein c > O, so dag

1 - - S/(r) ~ S f (r - - d) 1~-c

und 1

1 - c S1(r) c S f (r + d)

gilt. Angenommen, zu jedem 1 < i e N gibt es ein xt mit

i (1) x~ e S l (r - - d) (1') xi e ~ - - i S / ( r ) ,

i oder (2) x~ r ~ - ~ Sf(r) (2') xt r S i (r + a) .

Die Folge xn kann als konvergent angenommen werden und sei lira Xn ---- xo. Aus (1) (bzw. (1')) folgt ](xo) <= r - d (bzw. [(xo) <= r) und aus (2) (bzw. (2'))

](xo) >= r (bzw. [(xo) >~ r + d), Widerspruch! Jetzt gentigt zu zeigen, dab

1 1 1 +------c s~,(r) CSf~(r) c y-2V_cs~(~)

fiir groBe k gilt. Das Minkowski-Funktional [l" I[ bzw. []-II~ yon S1(r ) bzw. Sly(r) kann in der Form

IlxlI = inf {a-l[ ](ax) <= r} , g > 0

]l x[]k ---- inf{a -1 ] lk (ax) <= r} a > 0

geschrieben werden.

Vol. XXVI, 19~'5 Konvexe Approximation 199

Sei nun x e ]Rn und n x tt ~- ao 1, d.h. /(aox) ---- r. Aus der punktweisen Konvergenz der fk gegen ] folgt

( 1 - - e ) r ~ / k ( a o x ) ~ r ( l ~ - ~ ) fiir k : > k ( ~ ) .

Hieraus erhalten wir die folgenden Ungleichungen

( aox ~< 1 1~ ] = 1 + e / ~ (ao x) < r

und

] ~ \ l - - e ] = 1 - - e > - [~ (a~ x) => r"

Folglieh ist 1-t-e

I lx lb _-< - IlxlI (1 + ~) , g o

1 - - e jlxlI~ =_> - - - llxll (i - ~) .

ao

Insgesamt folgt

llxll~-~ llx]l. Im Beweise des Satzes yon Kripke (s. [2] S. 118) wird gezeig% dab fiir alle x ~ ]Rn

und k ~/co

(1 - c)Ilxll _-< [lxlJk _-< (1 + c)][xl[

gilt, und das bedeutet

1 1 1 J7----~ Sl(r) cSf~ (r) c ~ S f ( r ) .

Es gilt folgende Verallgemeinerung des Satzes yon Kripke ([2], Seite 118).

Satz 4. Sei K eine konvexe und abgeschlossene Menge, x ~ K . Sei v~ bzw. vo eine beste fk- bzw. /-Approximation von x durch K. Es gilt:

a) Die Menge {v~} ist beschriinkt.

b) lira/~ (x -- vk) ---- ] (x -- K) := r. IC--* oo

c) lim f (x -- v~) = / (x -- K) . /C --> o o

d) Jeder Hgu/ungspunkt der {v~} ist eine beste f-Approximation yon x dutch K .

Beweis . a) Es ist ffir ~ e K und groBe k

I~ (x - v~) _-< & ( x - ~) __< 2 / ( x - ~) = c ,

d.h. x -- v~ e Sf, (c) .

Aus dem Lemma 3 folgt, dal~

S l , ( c ) c Sr ) fiir groBe k

200 P. KOSMOL und M. WRIEDT ARCH. MATH.

gilt. Wei l $ I ( 2 c ) l inear besehr/~nkt ist und au f ]Ftn alle N o r m e n / i q u i v a l e n t sind, is t $ i ( 2 c ) beschr/ inkt . D a m i t folgt a).

b) Sei r > d > 0. Es gi l t f/Jr groBe k

1~ (x - vk) =</k (x - vo) < / (x - vo) + d ,

daher ]k (x - - v D <= / ( x - - vo) 4- d .

Nach L e m m a 3 gil t ffir groBe k

S / k ( r - - d ) c S/ ( r ) .

A n g e n o m m e n es i s t / ~ (x - - Vk) < r - - d, so folgt o o

x - - vk e Sfk (r - - d) c S / ( r ) ,

d . h . / ( x - - v~) < r ,

was ein Wide r sp ruch zur Defini t ion von r ist. Also gi l t ffir groBe k

r - - d < / ~ (x - - v~) < r 4- d ,

und d a m i t b).

c) Aus b) folgt ffir groBe k

r - - d =</~ (x - - v~) =< r 4- d

und d a m i t aus L e m m a 3

r - - 2 d < / ( x - - vk) < r 4- 2 d .

d) is t eine unmi t t e l ba r e Fo lgerung aus c). q.e.d.

Literaturverzeiehnis

[1] G. C~OQ~ET, Lectures on Analysis, I. New York 1969. [2] R. B. HoL~rs, A Course on Optimization and Best Approximation. Lect. Notes Math. 257,

Berlin 1972. [3] P. Kos~o~, l~ber Approximation stetiger Fnnktionen in Orliczr~umen. Erscheint bei

J. Approximation Theory. [4] M. A. KRAS~OSI]~LSKIZ und J. B. RVTICKIJ, Konvexe Funktionen und Orliezr~ume (russisch).

Moskwa 1958. [5] H. W. MIL~ES, Convexity of Orlicz Spaces. Pacific J. Math. 7, 1451--1483 (1957). [6] M. M. RAo, Smoothness of Orliez Spaces. Indag. Math. 27, 671--689 (1965). [7] I. SnCGER, Best Approximation in Normed Linear Spaces by Elements of Linear Subspaces.

Berlin-Heidelberg-New York 1970. [8] M. W~IEnT, Zur Approximationstheorie in metrisierbaren lokalkonvexen R~umen. Disser-

tation, Kiel 1971.

Eingegangen am 11. 11. 1972

Anschrift der Autoren:

Peter Kosmol Michael Wriedt Mathematisches Seminar der UniversitEt D-23 Kiel Olshausenstr. 40--60