H. BECKERT: uber die Konvergenz des Gradientenverfahrens mit Anwendungen auf Standortprobleme 333

ZAMM 81, 333 -343 (1971)

n e r die Konvergenz des Gradientenverfahrens mit Anwendungen auf Standortprobleme und das R i t z sche Verfahren Von H. BECKERT

Herrn Prof. Dr. E. HOLDEB zum 70. Geburtatag gewidmet

Fur dus Gradientenverfahren zur Minimieruny einer zweinial differenzierbaren, konvexen Punktion E'(x), .c E an, werden unter Zugrundelegung einer global ubersichtlichen Vorschrift fiir die Hchrittweite Konrergenzformeln herqe- leitet. Hieraue ergeben sich einige Folgerungen f2ir Probleme mit Nebenbedingungen. Die Resultate werden auf allge- meine Standortprobleme angewandt, sowie auf das R i t zsche Verfahren bei linearen und nichtlinearen Variationspro- blemen beliebig hoher Ordnung und Dimension ausgerichtet.

Convergence formulas for the gradient method when minimizing a twice differentiable convex function F ( x ) , x E Rn are derived under a global device for the length of the steps. There are some remarks on the case of linear constraints. The results are employed to general locational problems and to the R i t z method in the calculus of cariations.

HCXOAR k13 R C H O ~ O B o614e~ npenmcama AJIR BenwumbI uara BbIBeneHbI I # O ~ M Y J I ~ I cxonmomn nna MeT0.W YpaAkIeHTa, npeHHa3HaW?HHOrO HJISl MUHkIMWPOBaHHH ABYXEQaTHO AkI@I#epeHqkIpyeMOfi Bbl- IIJ'l~JIOfi @YHKUMU P(X), X E Rn. An51 3aAaq C II0609HbIMH YCJlOBUaMU BbITeKamT U 3 3TOrO HeKOTOpble OnpefieJIeHHbIe CJleACTBUrI. Pe3yJIlTaTbI IIPHMeHHIOTCIl K 064kIM CTaHHaPTHbIM 3aAaWM. O H H TaHKe

IIOpHHKa U pa3MepIIOCTU no MeTOfiy PEiTqa. 11pwcnoc06ne~h1 n n ~ peluema n m e h u x II aenaaeiiabIx BapwamoHHMx aanav n1o60fi Benmmm

Zum Gradientenverfahren existiert im Hinblick auf seine vielfaltige Anwendbarkeit in der linearen und nicht- linearen Optimierungstheorie eine umfangreiche Literatur. Sehr gute Uberblicke findet man in [3], [4]. Eine klassische Anwendung ergibt sich bei der Bestimmung der unteren Grenze einer konvexen differenzierbaren Funktion F(x,), xj E Rn, mit oder ohne Nebenbedingungen. Erwiinscht sind genaue Konvergenzabschatzungen zur Gradientenmethode liings der Schritt'kette, wie sie zum Ted bei der Minimierung einer quadratischen Form bekannt sind, [7]. Von besonderem Interesse ist es ferner, wahrend des Verfahrens standig einen Uberblick zu besitzen, innerhalb welcher Entfernungsgrenzen der zu errechnende Minimalpunkt von dem jeweils erreichten Punkt liegt. Wir zeigen, daB man beides zumindest bei der Minimierung einer zweimel differenzierbaren Funk- tion ohne Nebenbedingungen sichern kann, wenn es gelingt, den grijibten Eigenwert der durch die zweiten Ab- leitungen bestimmten quadratischen Form nach oben und den kleinsten Eigenwert im eingeschrankten Sinn nach unten abzuschatzen, vgl. Satz I, 11. Von vornherein liiibt sich dann eine einfache global gultige Vorschrift fur die Schrittliingen angeben. Bei Problemen mit Nebenbedingungen sind so allgemeine Konvergenzabschat- zungen nicht herleitbar, doch ergeben sich auch hier nutzliche Folgerungen. Wir wenden die gewonnenen Ab- schatzungen auf die Optimierungstheorie bei allgemeinen Standortproblemen an und richten dieselben noch auf das RITzsche Verfahren bei linearen und nichtlinearen Variationsproblemen beliebig hoher Ordnung und Dimension aus.

Unsere Uberlegungen griinden sicli auf den Umstand, daB llings der durch das Differentialgleichungs- svsteni

definierten Fallkurven nicht nur die Funktion F ( q ) , sondern auch der Betrag des Gradienten

@(s,) = 2 F& = (grad F(sJ i = l

abnimmt'):

i = l

wenn die im Zahler von (2) stehende quadratische Form

positiv defin it ist: w, 8 = FXI xj 5t 6,

JWl2 I A&,) 16,12 2 Q(6, 6) 2 A,(s,) lEl* 2- ~W Y

Itla= 2'54, -nE>o - n

i-1

1) tfber doppelt auftretende Indices vereinbaren wir zu summieren.

(3')

(3)

334 H. BECKEFLT: uber die Konvergeuz des Gradientenverfahrens mit -inwendungen auf Gtandortprobleme

Hierbei sindll(xJ), &(x,), . . . , &(q) die der GroBe nach geordneten Eigenwerte der quadratischen Form (3’) und H, m beliebige obere bzw. untere Schranken vonln(xf) bzw. l l ( x j ) . Genauer wird bei (2) nur eine Abschatzung von (3‘) nach unten bezuglich der Richtungselemente der jeweiligen Fallkurve benotigt, also nicht unbedingt die positive Definitat von (3’). Da @(xg) = 0 im Minimalpunkt B(xj) zutrifft, folgt aus (2), (3) fiir die LLnge Z(P, &) der die Punkte P(x,), %(zj) verbindenden Fallinie die Abschatzung

(2) und (4) legen es nahe, das klassische Gradientenverfahren auf die Minimierung des Gradientenbetrags anzu- wenden und dabei die Schrittlangen moglichst so zu wiihlen, daB dieser Betrag monoton fallt. Es zeigt sich, daB dabei auch die Funktion F(xi) selbst monoton abnimmt.

1st g(P,) die vom Punkt P,(zg) ausgehende Fallgerade

dann erhalten wir fur die Abnahme von @(xi) langs g(Y,)

mit den vom Index i abhangigen Zwischenwerten xj E g(P,) und weiter:

= 2 z’ F,r,&;) Fr,z,(xj) (x. - xi) (.I* - 21‘) , 1,I- ,1=1

wobei xi* E g(P,) wieder einen geeigneten Zwischenwert bezeichnet,. Wir ersetzen in den Argumenten der Ablei- tungen alle Zwischenpunkte durch x:, beriicksichtigen die dadurch bedingte Korrektur, fuhren ferner die Qua- dratmatrix Qz der Form (3‘) ein und wenden auf die zugehiirige nichtnegative quadratische Form die verallge- mehehe ScHwARzsche Ungleichung an :

Es ergibt sich hieraus leicht die Abschatzung

fur

I n den Korrekturterm s3 Ml gehen offenbar die Schranken fiir die dritten Ableitungen von F(x, ) mit ein. Man kann sich von dieser Abhlngigkeit befreien und eine Abschatzung fiir (8) gewinnen, in welche dann allerdings die Dimension im Hauptterni eingeht :

(8) Iy(x)l 5 122 NZ 8 2 . (8) folgt leicht nach Anwendung der ScHwARzschen Ungleichung auf (7) nebst Berucksichtigung der aus der Invarianz der Spur von Qz folgenden Ungleichung

11

,Z IBz,r*lZ 5 n M2 . I , I-= 1

Wir schatzen jetet die Ableitung von @(x7) in Richtung der Pallgeraden g(P,) ab:

H. BECKERT: tfber die Konvergenz des Gradientenverfahrens mit Anwendungen auf Standortprobleme 335

Hierbei ist n’ gleich der Dimensionszahl n bei (8) oder n‘= 1,5 bei (8) und der Beschriinkung fur die Schrittweite

Bei der Herleitung von (9) wurden (3) und (8) sowie die verallgemeinerte Sclrwmzsche Ungleichung ver-

Mit der Abkiirzung

( 8 ) .

wendet.

@ ( O ) = 1grad P(z’j)I liaben wir also die Differentialungleichung

d@ n‘ M 2 s - m @ ( O ) -<- ds = @(4

Iangs g(P,) erhalten oder

woraus sich @(s) - Q2(0) 4 n’ M 2 s2 - 2 m s @ ( O )

ergibt. Wir bestimmen das Minimum der rechten Seite, das fiir 11L @(O)

r L I 2 2

angenoinmen wird. Einsetzen von (11) fuhrt auf

y = s1 = -~

also

@2(5,) 5 @2(0) 1 - - - { :f(:)} als Abnahme von @(s) liings g(P,) bei der Schrittweite (11). Diese Ungleichung trifft sicher bei n‘ = n zu, wiihrend sie fur n’ = 1,5, da s hier an die Bedingung (8‘) gebunden ist, offenbar nur bei

3 M 4 8 m M l @ ( O ) 5 - -

+chert ist. Wir wenden jet& das Gradientenverfahren mit der Vorschrift (11) insgesamt N ma1 an, wobei n’ wegen (12), (11) - von einer bestimmten Stelle an gleich 1,5 gesetzt werden darf, und gewinnen die Punktreihe

d a m erhalten wir rekursiv Po, Pl = P ( W ) 9 p2, * * * 9 p , *

d. 11. lim grad2 P(P,) = 0 . 8-00

Bei Wald der Schrit1tlangc

(1 1‘) m

n’ M a sp = __ (grad W p - d I

im Punkt Pp-l entlang obiger Punktreihe liegt wegen (4) der gesuchte Minimalpunkt i@ nach dem N-ten Echritt von P, hochstens

entfernt. Wir konnen daher, wenn &(x,) und il,(x,) durch M und m global abgeschiitzt sind,

dist [PN, 81 beliebig vorschreiben und fiir die hierzu erforderliche Schrittzahl vorher eine untere Schranke angeben.

wir alle dureh P, N (9,) laufenden Strahlen

A

Man kann den Lagebereich von M etwa von P, aus gesehen noch genauer einschranken. Hierzu betrachten

336 H. BECKERT : uber die Konvergenz des Gradientenverfahrens mit Anwendungen auf Standortprobleme

bestimmen auf jedem den Minimalpunkt Q, von F(x j ) und leiten in einfacher Weise eine obere und untere Ab- schltzung der Entfernung s, = dist (PN, Qa) her. Es gilt fur s = s,:

, -- also

Durch (13) wird ein von zwei die Ebene

E ( P N ) : F d Y l ) ( x k - ?In) =

in P, beriihrenden Kugeln

mit der Abkurzung

begrenzter, sichelformiger Bereich Sp, definiert, in dem alle Minimalpunkte Q, unserer Geradenschar h,(PN), aIso auch der gesuchte Mkimalpunkt. M liegen. Der Minimalpunkt Qa auf der von P, ausgehenden Fall- gereden g(PN) lie@ zwischen den Grenzen

x k - y k = at 8 = xk ,

(13’)

von PN entfernt. Daher fiillt bei der Schrit.tweitenvorschrift (11’) langs des durch die konstruierte Punktreihe definierten Streckenzuges (*) : Pa, PI) . . . , P N nicht nur der Betrag des Gradienten monoton, sondern auch die zu rninimierende Funktion F(x,) selbst.

S a t z I: Wdhlt man beim klassischen Gradientenverjahren zur Minimierung einer Funktion F(x,) E C2 unter (3) die SchrittGnge in den Teilpunkten Pa, P l , P2, . . . , P,, . . . nach der Vorschrijt (11’) und bestimmt bei Vorgabe einer beliebig kleinen Zahl E > 0 die Zahl

N =

dann liegt der gesuchte MiniGmlpunkt M vwn allen l’eilpunkten Y” itbit N’ 2 N um hdchstens E entfernt, genuuer in dem vorhin definierten sichelfcirmigen Bereich Spx. F(x,) und [grad F(x)I fallen ldngs des Streckenzuges (*) monoton.

Wir haben die in Satz I genannten Abschiitzungen fiir beliebige globaIe obere bzw. untere Schranken M ,

Es ist fur die Konvergenz in (12) am giinstigsten, wenn wir m von A,&), A,(z,) durchgefiihrt.

M = sup&(z,) ) m = infA,(x,) setzen oder als globale Schritt,weitenvorschrift

(11”)

einfdwen. Fur alle Schrittliingen :

a;, = B l P d W n - d l mit 7 /? 5 a bei beliebigem 7 > 0 konvergiert des beschriebene Gradientenverfahren ebenfalls, wenn auch schwiicher. Bei unseren Abschltzungen werden im Grund keine globalen Schranken m, M benotigt, sondern

H. BECKERT : Vber die Konvergenz dea Gradientenverfahrens mit Anwendungen auf Standortprobleme 337

lokale sich auf die jeweilige Fallgerade beziehende Schranken. Dabei geht zwar die globale Schrittweitenvor- schrift (11") verloren, doch verbessert sich die Konvergenz. Weiter geht nicht die untere Grenze von Al(x,) Iangs g(Pj - l ) in unsere Abschiitzungen (9) entlang Pj-1 P , ein, sondern die von Q ( A t , A k ) langs P,-1 P,, wenn konstnn t

_ _ ~

grad F(Pj - , ) A = -

(grad P(Pj-l)l gesetzt wird. Dieser wichtige Umstand erlaubt es, die Voraussetzung (3) der positiven Definitiit von &(A,, A,) fallenzulassen und durch die schwachere

liings der Fallgeraden g(Pj - 1 ) zu ersetzen. Wir bemerken, daB die Anwendung der verallgemeinerten SCHWARZ- schen Ungleichung bei (9) auch im semidefiniten Fall' moglich ist. Fiihren wir noch die Abkiirzungen

Mj = SUP &a(%,) Z F $ ( P j - 1 )

ein, dann gilt S a t z TI: Wcihlt man in den Teilpunkten P jP l , j = 1 , 2 , . . . die Schrittweite nach der Vorschrifl

dann konvergiert das Gradientenverfahren nuch der Abschcitzung

grad2 P ( P N ) 5 grad2 F(Po) fi (1 - $ (gr) j = l

unter Beibehultung der entsprechenden weiteren Konvergenmussngen von Satx I .

schat,zung (15) fur den Minimalwert F(&) nach N Schritten: Da der Gradientenbetrag liings der Fallkurven (1) monoton fiillt, entnimmt man aus (4) und (14) die Ab-

Die Konvergenzformeln (12), (14) zeigen zugleich die Grenzen unserer Vorschrift (ll), (11") fiir die Schritt- weite auf. Bei kleinem m, gegeniiber M , wird im allgemeinen diese Wahl zu vorsichtig sein, wie man im Grenz- fall der Ausartung von Q(Ai, A,) liings g(Pj-1) fiir (3') erkennt. Die Vorschrift (11") ergiibe hier die Schrittweite s = 0, d. h., wir kiimen mit unserer Methode jetzt nicht weiter. Andererseits fiillt die Funktion dieses Beispiela liings g(Pj-1) linear, wie aus der Entwicklung

P(P) = P(Pj-1) - s lgrad P(Pj-l)l (16) wegen des Verschwindens des Restgliedes zweiter Ordnung liings g(Pj-1) ersichtlich ist. Wir haben also Min F(x,) = - 00, und es ware vom Standpunkt des Gradientenverfahrens richtig, statt 8 = 0 eine beliebig gol3e Schrittweite zu wiihlen. Was fur den Grenzfall gilt, trifft auch bedingt in dessen Nachbarschaft zu. In dem fur unsere Konvergenzformeln (12), (14) ungiinstigen Fall, wo m, klein gegeniiber M , ausfallt, nimmt P(x,) nach (16) llngs eines groBeren Abschnitts auf g(Pj- l ) rasch ab. Es wird daher gerade hier zweckmiiBig sein, den relativ steilen Abfall auszunutzen und eine entsprechend groDe Schrittweite vorzuschreiben, solange bis wir eventuell wieder in den Bereich eines groaeren VerhaltnissesA1(x,)/A,(x,) gelangen. Hiiufigwird auch noch die sich auf den gesamten Fallstrahl beziehende Abschatzung zu roh ausfallen und einen unangemessen kleinen Wert von m,/M, ergeben. Deshalb kann es von Vorteil sein, Abschiitzungen herzuleiten, welche sich auf die naherc Umgebung beziehen, falls der laufende Rechenaufwand sich dabei nicht wesentlich erhijht. Es wilre unzweck- miiBig, eine mijgliche Verringerung der Iterationszahl mit einem stark vergr6Berten Rechenaufwand fur die einzelnen SchrittlBngen zu erkaufen. Weniger scharfe lokale Schranken, welche eine einheitliche Festlegung der Schrittweite fiir eine angemessene Zahl von hintereinander laufenden Iterationen gestatten und dann den neuen VerhZiltniasen jeweils angepaBt werden, diirften im allgemeinen den Vonug verdienen.

Die Siitze I und I1 sind auch bei Problemen mit Nebenbedingungen von Nutzen, wenngleich wir hier nicht so scharfe Konvergenzaussagen herleiten konnten. Zur Orientierung betrachten wir unser Minimumproblem uber dem linemen Teilraum

n

i = l En-?: z a ! z t - b, = 0, j = 1, 2,. . . , r , Rang(a$) = r . (17)

Dieses reduziert sich ersichtlich auf den behandelten Fall, wenn wi r das Gradientenfeld von F(z,) im Punkt P(x,) E En-? orthogonal auf En+ projizieren, ein klassisches Verfahren, vgl. etwa [7], wo ausgiebigvon den

338 H. BECHERT : Uber die Konvergenz des Gradientenverfahrens mit Anwendungen auf Standortprobleine

S. HousEHoLDERschen Projektionsmatrizen Gebrauch gemacht wird. Uns geniigt hier die klassische Darstellung des auf En+ orthogonal projizierten Gradienten grad, F

gradB P = grad F - 2 nt ( n t . grad F ) , (n;, n k ) = 8, , i = l

(17’)

dabei entsteht das normiert orthogonale System n,, i = 1, 2, . . . ) r , aus dem ScHMIDTschen Orthogonalisie- rungsprozeB der r linear unabhingigen Vektoren a:, j = 1,2 , . . . , r , in (17). Da gradE F den Gradientenvektor der Einschrankung von F(x,) auf En-r darstellt, kann man die Satze I und I1 bezugl. dieses Feldes genauso herleiten wie vorhin. Im Minimalpunkt .&’ E E,t-r verschwindet grad, F , d . h., grad F steht dort auf E n P r senkrecht, oder es gilt .& = 2‘ mit grad F(&) = 0.

Bei der Ubertragung von Satz I1 beziehen sich natiirlich die Schranken m,, M , hier auf die projizierten Rich- tungen. Von Wichtigkeit ist noch der Hinweis, da13 wir bei Anwendung von Satz I die globalen Schranken M , m fur die Eigenwerte lbn(z,), il,(s,) in (3) erst recht fur das eingeschriinkte Problem iiber EnPr verwenden konnen. Wir benotigen deshalb keine weiteren Abschatzungen zur Festlegung der Schrittweite nach (11’). Dasselbe trifft auf die Entfernungsabschatzung (12’) des Minimalpunktes M E EnPr von: einem Teilpunkt des Gradienten- w-eges zu.

Wir machen noch einige Bemerkungen zur Konvergenz des Gradientenverfahrens beim eingeschrlnkten Optimierungsproblem

P(zl) -+ Min (18)

2 ajz , - 6 1 2 0 ,

unter (3) uber einem konvexen Polyeder, gegeben durch ein System von Ungleichungen n

1 = 1

j = 1 , 2 ) . . . , r ,

oder auch iiber einem nichtkonvexen polyedralen Bereich G [7], [lo], [ l l ] , [12]. Dieses klassische Problem nimmt in der Literatur einen breiten Raum ein. Liegt der Minimalpunkt 3 des freien Problems (18) innerhalb G oder im AuBenraum G , so kann man dies, falls in (3) globale Schranken m, M gefunden wurden, iiber Satz I ent- scheiden, ohne die Nebenbedingungen in Rechnung zu stellen. Bei 2M^ E G sind wir fertig. Liegt dagegen J? E G‘, dann nimmt P(z,) sein Minimum uber G auf dem Rand aG an. Da hier auch lokale Minima auftreten konnen, Trgeben sich fiir das Gradientenverfahren die bekannten Schwierigkeiten, den absoluten Minimalpunkt 9. von F(x,) iiber aG zu treffen. Es ist in mehrfacher Hinsicht vorteilhaft, die Lage von % in c’ zu kennen. Aus der Konvexitat von F(z,) folgtniimlich, daD die siimtlichenMinimalpunkte 2;: F(M;) = Min P ( P ) auf demjenigen

Teil S von aG liegen, der im Blickkegel eines in befindlichen Beobachters liegt. Deshalb kann von vornherein der Randteil aG - S ausgeschlossen werden. In jedem Punkt Po(x!) wird durch die Richtung -grad F(Po) und die hierzu orthogonale Hyperebene

ein Halbraum H-(P,) definiert, in dem die gesuchten Minimalpunkte % bzw. M; E a G liegen miissen. Da hieraus weiter

A

P E G

E(Po): PZk(z,”) (xL: - 29) = 0

2, 3; E H-(P,) n H-(P,) n . n H-(P,) fiir beliebige Pa E G folgt, besitzt man eine weitere Miiglichkeit, durch gunstige Wahl von PI E G zu einer vor- teilhaften Abgrenzung S’ von S zu gelangen. Natiirlich trifft alles auch fur das freie Optimierungsproblem zu, um etwa vor Beginn des Gradientenverfahrens einen zweckmiifligen Anfangspunkt Po E (2 zu finden. Bei der Ermittlung des Minimalpunktes M irn Auaengebiet, ist die giinstige Wahl des Anfangspunktes Po E G nicht allcin unter dem Ziel einer geringen Schrittzahl zu sehen. Der Gradientenweg sollte aG moglichst in einem Punkt P‘ schneiden, der nicht weit von einem Minimalpunkt i@’ entfernt liegt. Dieser ware dann ein giinstiger Anfangs- punkt fur das Gradientenverfahren entlang des Randstucks S’. Zu letzterem denkt man sich das Feld -grad F orthogonal nach (17’) auf die Polygonseiten und Kanten von S’ projiziert und erhalt so das langs der (n - 1)- dimensionalen Seitenflachen stetige, langs deren Kanten sprunghaft unstetige Vektorfeld -grads P. Auf dieses Feld kann man unser Gradientenverfahren von P aus nach der Schrittweitenvorschrift (1 1‘) wie vorhin iiber E*-, anwenden. Solange der resultierende Gradientenzug P , P i , . . . , Pi im Innern einer Seitenhyperflache oder Kante En-, E S’ verlauft, nimmt grads, F nach Satz I ab. Dabei sollte die Entfernungsabschiitzung (4) stets im Auge behalten werden. Wurde vorher vermutet, daD einer der Minimalpunkte i@ innerhalb EA+ liegt, so konnen wir aus dieser Abschiitzung einen Test gewinnen. Fallt dieser positiv aus, existiert in EhpV E S’ ein wie vorhin iiber EnPr zu berechnender Punkt PL-, mit grad,;-, F(P;&-,.) = 0. Wenn r = 1 und G konvex ist oder ganz in einem der durch EA-l bestimmten Halbriiume liegt, gehort Pk-r zu den gesuchten Minimalpunk- ten 2;. Bei r > 1 wird letzteres nur dann zutreffen, wenn die Vektoren - grads# F(P;_,) auf den Ek-, durch- setzenden Seitenflachen aus S’ hinausweisen. Im allgemeinen Fall mu13 man damit rechnen, da13 unser Gra- dientenweg Pi, Pi, . . . , Pi auf eine Kante trifft, wo grads, F(Pi) apringt. Im Treffpunkt sind je nach Dimen- sion der Triigerkante mehrere Fortschreitungsrichtungen denkbar, je nachdem, ob wir langs der Tragerkante

H. BECKERT : Uber die Konvergenz des Gradientenverfahrens mit Anwendungen auf Standortprobleme 339

selbst oder in einer der sie durchsetzenden Seitenflachen weitergehen. Wegen der Unstetigkeit von grads* F sind die Abschatzungen in Satz I nur solange wirksam, wie wir in ein und derselben Kante oder Fliiche bleiben, 0 ulobale Aussagen langs der gesamten Schrittkette erlauben sie nicht mehr. Daher sind allgemeinere Konver- genzaussagen fur das Gradientenverfahren ohne genauere Abschlitzungen offenbar jetzt aus der Konvergenz der Funktion F(zJ langs der Schrittkette allein zu erschlieBen, vgl. [7], [ll]. Es scheint deshalb sinnvoll, die Wahl an den Unstetigkeitsstellen nach einer moglichst starken Abnahme von B’(z,) langs der Streckenabschnitte auszurichten. Dabei sollte die Richtung von - grad F und damit der zugehorige Halbraum H - in dem die gesuchten Minimalpunkte 2; liegen, sowie dieAbschiitzung(4), wenndasverfahrennicht abbricht, und ]gradst FI gegen Null konvergiert, vgl. (7), (12), im Sinne der vorhin gemachten Bemerkungen standig im Auge behalten werden.

Wir betrachten zum Zwecke der Schranken’bestimmung noch einige wichtige Beiapiele.

S t a n d o r t p r o b l e m e Es seien im RVL die 1 festen Punkte Pk($), k = 1,2 , . . . , 1, fest vorgegeben, ferner ein variabler Punkt P(z) . Bei einem allgemeinen freien Standortproblem stellt man die Optimierungsaufgabe :

F(rl, r,, . . . , r l ) +fi , (A 1) wenn F(rl, . . . , r l ) eine konvexe, zweimal stetig differenzierbare Funktion der Abstiinde

rk = 2 (ri - $‘)2 (A 2) lii bedeutet.

Um die Satze I, I1 anzuwenden und die Schrittweite nach (11‘) zu bestimmen, sind die Schranken vom Typ m , M zu ermitteln. Wir erhalten nach leichter Rechnung fur die zu (A 1) gehiirige quadratische Form

mit

wobei - (zh - Zi)

= ~ , r ( a i . ) 2 = 1 , k = I , 2 , . . . , n , i = I , 2 ,..., I , ri k

die Richtungscosinus der Verbindungsgeraden so gilt

bedeuten. Definiert man den Einheitsvektor Y = {& / lA l } ,

also

Urn die Konvexitiit der Zielfunktion (A 1) zu sichern, verlangen wir neben der Positivitiit der Form

noch, daD F(rl, . . . , r I ) mit rl, i = 1 , 2 , . . . , I , monoton wachst:

eine sachgemaDe Forderung. Die positive Definitiit von &(A,, A,) im Sinne von (3) und damit die Herleitung von Schranken m und M ubersieht man auf Grund von (3) besonders einfach, wenn in dem betrachteten Bereich des Rn obere und untere Schrankenfunktionen HM(rl, r,, . . . , r,), H,,,(rl, r,, . . . , TI ) bzw. GM(rl, ?a, . . . , r , ) , Gm(rl, r,, . . . , r l ) fur

(A 6) 1 aF ri ar, GM(rl, . . . , r l ) 2 - - 2 Gm(rl, . . . , r l ) > 0

- hier ist iiicht iiber den doppelt auftretenden Index i zu summieren -

340 H. BECKERT: tZber die Konvergenz des Gradientenverfahem mit Anwendungen auf Standortprobleme

gefunden aind. Dann fiillt die Winkelabhiingigkeit heraus, und wir erhalten die relativ einfache Abschiitzung

bzw.

In dem die Schrittlange (11‘) und die Konvergenz nach den Siitzen I, I1 bestimmenden Verhaltnis

sind nur Entfernungsabschiitzungen keine Winkelabschiitzungen durchzufiihren, was die Herleitung zumindest roher Schranken wesentlich erleichtert.

Ein besonders einfacher Fall liegt bei n

a = 1 F(q) = Cpt< , a 2 2

mit positiven konstanten Gewichten p1 vor. Dann gilt

als Abschatzung von &(At, A&) in jedem festen Punkt P(x).

angeniihert Bei hinreichend guter Entfernungsabschitzung darf man deshalb in der Konvergemformel des Satzes I1

ansetzen. Die beste Konvergenz ergibt sich fur

F(x,) = pi rg +Min mit

Der hier ausgeschlossene Fall 0 < LX < 2 in (A 10) bedarf einer speziellen Behandlung. Hierunter fiillt auch das klassische Standortproblem

F(x,) = pi rt + Min , (A 13)

welches im ebenen Fall als STEINER-WEBER-Problem in der Uteratur bekannt wurde, vgl. [5]. Bei diesen Auf- gaben werden in den Gitterpunkten die ersten Ableitungen von P(x,) unstetig und die zweiten Ableitungen un- endlich. Man kann dessenungeachtet die Konvergenz des Gradientenverfahrens uber die Satze 1, I1 beweisen. Hierzu hat man sich vorher zu vergewissern, ob einer der Gitterpunkte selbst Minimalpunkt ist. Wenn dies nicht der Fall ist, konvergiert das Gradientenverfahren nach den Siitzen I, I1 im Gebiet R” - 2 KQ(Pi) gegen

den gesuchten Minimalpunkt. Dabei bezeichnet &(Pi) die Kugelllx - ztll 5 e urn Pi und Q ist eine geeignete positive Zahl. Wir gehen hier nicht niiher auf Einzelheiten ein.

Natiirlich kann man unsere Bemerkungen zur Optimierungstheorie im Falle von Nebenbedingungen auch bei Standortproblemen beriicksichtigen, zumal diese ihrer Natur nach zwei- oder dreidimensional sind und sich deshalb das Gradientenverfahren ubersichtlich gestaltet.

i

Wir machen zum SchluB noch einige Anwendungen unserer Abschltzungen auf das RITZ s c h e V e r -

Sei bei Verwendung der bekannten Multiindizesschreibweise fahren.

Da = 0”;le.. .o”n* ; .Zai IaI ad *=-

8 a q ’

H. BECKERT: Uber die Konvergenz des Gradientenverfalirens rnit Anwendungen auf Standortprobleme 341

ein st,ark elliptischer hea re r Differentialoperator m-ter Ordnung uber einem Gebiet G 2): x = (xl, x2, . . . , 5,) E E R, mit regularen Koeffizienten und

~ ( u , u) = j a,,+) n-u ~p~ ax

a&&&,) E" 5p2 k,1512m ,

(A 15) L'

tlas zngchorige Variationsintegral. Es gilt dann gleichmaRig in @

ferner die GARDINQ sche Ungleichung

B(', U, 2 klllUllk - c l l u l l : J

u(a) = 0 . . . . . . . . . , OpU(0) = 0 .

Ic,, c > 0 7

etwa bei den DIRIcHLETschen Randbedingungen

a ~ a G = s , O s l , ! ? I 5 m - l

Die m-Norm im SoBoLEwschen HILBEBmaum H$ ,(a) werde rnit

(A 15')

(A 14')

bezeichnet. Aus der Beschriinktheit der Koeffizienten a, b(x) folgt sofort die Abschatzung

IB(% u)l 5 k2llullE *

$(u, U ) = B(u, U ) - (f, u), + Min

(A 16)

(A 17)

Beim RITzschen Verfahren zum Variationsproblem

unter (A 14') bzw. ~ ( x ) E Hh, 2(G), f(z) E H,(G) im Falle der Eindeutigkeit c = 0 wird (A 17) uber einem k-dimen- sionalen Teilraum !JIk E HL, gelost, der von k linear unabhangigen, zulassigen Funktionen y,(s), y&), . . . ,y&) E E H&,? aufgespannt wird. Diese L6sungen u&) uber streben gleichmaDig in der Norm C'(@ gegen die L6- sung U(Z) unseres Variationsproblems (A 17), wenn fiir k -+ 00,

3(U,) 3 inf 3(u) uEn:* 2

konvergiert. C'(@) bezeichnet hier wie iiblich den BANAcHraum der I-ma1 stetig iiber Cdifferenzierbaren Funk- tionen mit der Norm

Die Ordnungszahl E in obiger Behauptung ergibt sich aus der beschrankten Einbettung von Hm, z ( q in Cr(G) fur

als die gro13te ganze Zahl, die kleiner als m - n /2 ist, wenn man weiter bedenkt, da13 aus (A 16') und (A 18)

zu erschlieflen ist. In diesem Zusammenhang sei noch auf den originellen Beweis der Konvergenz des Rrrzschen Verfahrens

von E. TREFFTZ in dessen Arbeit [8] verwiesen, welcher nicht die gebuhrende Beachtung gefunden zu haben scheint. "REFFTZ erliiutert seine Methode an der ersten Randwertaufgabe der Plattengleichung, welche dem Variationsproblem

0 5 I'< m - 4 2

I I u ~ - 4Im + O

(*I

8(u, u) = - ( A U ) ~ rlx - (f, u),, +Min , (A 19) "J au

U(0) = - (a) = 0 , an

a E a G : , (A 1 9 )

aquivalent ist und bettet dieses in die Nebenprobleme

M(E) = 3(u, u) + E u(5,q) +Min (A 20) unter (A 19') ein. Der Zusatzterm entspricht einer zuslitzlichen Einzelkraft des Betrags E , welche im festen Punkt Q ( 6 , q ) E G: angreift, und die fur sich die Durchbiegung E G(x, y; E , q) der Platte bewirkt. Dabei ist G(x, y ; E , q) die passend normierte GREmsche Funktion unseres Problems. Von entscheidender Bedeutung

2, Zum Zwecke der Anwendung der Einbettungssiitze miige a! die klassische Kegelbedingung erfiillen.

342 H. BECKERT: Uber die Konvergenz des Gardientenverfahrens mit Anwendungen auf Standortprobleme

ist nun die Tatsache, daB die Extremalen ii&) von (A 19) uber jeden Teilraum %k(vl(z),vz(z), . . . , ~ ~ ( 2 ) ) durch die Minimalwerte M,( + l), &!k( - 1 ) der Nebenprobleme (A 20) iiber %k nach

dargestellt. werden. Hieraus erschliel3t man leicht die gleichmlBige Konvergenz des Rmzschen Verfahrens fur k -+ 03. Zugleich ergibt sich die MBglichkeit die Funktionswerte von ;(x) in Verbindung mit dem bekannten zweiten TREFFTzschen Verfahren [8] in gewissen interessanten Punkten durch die U m a l w e r t e von Neben- problemen abzuschltzen. Ohne Beweis sei hier mitgeteilt, da13 sich das TREFFTZsche Ergebnis (A 21) auf das stark elliptische Variationsproblem m-ter Ordnung (A 17) ubertragen liiBt und zwar sinngemlfi bis zur 1'-ten Ab- leitungsordnung ( * ) von vorhin, was noch einmal die gleichmaBige Konvergenz des Rmzschen Verfahrens in C"(G) bestltigt. Der Einfachheit halber legten wir nur eine Gleichung zugrunde, doch ist der Hinweis wichtig, da13 alle Ergebnisse auf stark elliptische, lineare Systeme 2 m-ter Ordnung ohne EinschrLnkung ubertragbar sind. Die Losungen der Nebenproblerne (A 20) kann man entlang der schwachen Losungstheorie der Variations- probleme (A 17) k~nstruieren.~)

Wir machen noch einige Bemerkungen zur Anwendung des Gradientenverfahrens bei der Losung von Vari- ationsproblemen uber %k(fpl(Z)) v2(z), . . . , q&)) nach RITZ. Die Schrankenbestimmung gestaltet sich zumindest bei den soeben betrachteten quadratischen Variationsproblemen (A 17) ubersichtlich. Wir erhalten namlich a m (A 15'), c = 0,

F(?/,, * * * , YJ = I % p ( 4 w//l TI) np(Yl9),) dx - ( f l ?/* T2)O 0

sofort

falls die Basiselemente pli(x) von %k in der Hm, 2-Norm normiert orthogonal vorausgesetzt werden. Wir erhalten daher in diesem Fall: 2 k, = m.

Die Schranke M von Satz I ergibt. Rich in analoger Weise aus (A lci), (A 22) nach

(A 23)

zu 2 kz = M . Bezeichnet wie vorhin Uk.5) die Extremale (A 17) iiber % k ( v f ) , dann gelten offenbar die Gleichun- €Yn

Sie enthalten die bekannte Tatsache, daB grad F(y,, g2, . . . , yk-1) in ut(z) beim Ubergang von Sk zu PI-+, auf %k senkrecht steht. Beim ersten Schritt gehen wir daher von u k ( x ) aus in der yk+l-Richtung weiter, deshalb gilt

[grad p('%(z))I = 12 B(Q(z) , V I - + I ( ~ ) ) - (f, v k t 1101 . Eine nutzliche Anwendung von (4) gestattet es, durch den letzten Ansdruck die Entfernung des Minirnal- punktes

E-I 1

1 - 1 Uk 1 1 w = ?l t (Z) + 2 pi T,(4

uber %j..+, von u k ( z ) abzuschiitzen:

oder weniger gunst& beim Ubergang von %,(v,, rpz, . . . , T k ) zu %k+r(Q)1, qz, . . . , T k , . . . , ~ ) k + " ) enhprechend:

( F p ; 2 ) 1 ' 2 j m r2. qA 25')

Die letzten Ungleichungen gestatten einc a-priori-Aussage uber die zu erwartende Gesamtanderung der FoUEIERkoeffizienten der Losungen von (A 17) beim Obergang von 8, zu %,+,, v 2 1 . 4 ) Darin geht die vorher

{ i. 12 B(u,(4, q J k l j ( 4 ) - (.f> p l I - + j ) O l 2

i = l

a) Uber Einzelheiten vgl. man die vom Verf. angeregte Dissertation M. MOUSSA, Uber das TREFFTZsche Verfahren in der

') Offenbar stellt das Maximum der rechten Seite ron (A25) beziiglichvk+~(r), welches fur k --f 00 gegenNull konvergiert, Variationsrechnung, h ipz ig 1971.

eine obere Schranke der zu emartenden Anderung der FouRImkoeffizienten / I , . p2, . . . , p + i dar.

H. BECKERT: Uber dir Konvergeilz des (iradientenverfahrens niit Anwendongen auf Standortprohlrmc 343

nieht bckannte Differenz

dk, k i Y $(a&, U t ) - t v , ?lAi Y ) 2 0

nicht ein. Entwickelt man andererseits dk, t , ~ unter Beaclitung von (A 24) und der GARDINcschen Ungleichung (A 15'), c = 0, so folgt leicht:

(A 36)

Diese Abschatzung a posteriori setzt die bekannte Tatsache in Evidenz, daB bei fortschreitendem RITZ- schen Verfahren sich von einer hinreichend groBen Dimension k ab die FomrERkoeffkienten der LBsungen nur noch wenig andern. Dieser Umstand legt es nahe, das Gradientenverfahren beim Ubergang von 832, zu '%n,+, zur Vereinfachung des Rechenaufwands zunachst im Faktorraum '&+,/'%, durchzufuhren. Die soeben genannte Auftrennung des Verfahrens nach einzelnen Raumkomponenten scheint von allgemeiner Bedeutung zu sein. I n dieser Miiglichkeit liegt sicher ein Vorzug fur die Anwendung des Gradientenverfahrens bei der RrTzschen Methode.

Der Ubergang von linearen zu nichtlinearen Variationsproblemen bereitet keine Schwierigkeiten. Die Be- stimmung der FouRIERkoeffizienten der Losungen iiber g & ( ~ ~ , y~~., . . . , V k ) fuhrt hier auf ein nichtlineares Glei- chungssystem. Wir wollen auch hier gleich ein allgemeines Variationsproblem m-ter Ordnung zugrundelegen :

(A 27)

unter den Bedingungen (A 14') und den analogen Voraussetzungen wie im linearen Fall beziiglieh des Integrals

B'(u, w) = J P(x, u, D1u, . . . , D*u) dx +Min c

G

untl stat>t, (A 22), (A 23) fur dic quadratische Form

aus (A 27') die analoge TJngleichung

m114I2 5 &(LM s Jfll4l2 .

(A 37')

j = l , 2 , . . . ) k ,

Die Voraussetzungen ( A27') links sind bei Variationsproblemen mit stark monotonem LAGRANGEsChem Operator erfullt. 6ie reichen offenbar hin, um alle friiheren Aussagen iiber die Anwendung der Gradientenme- thode beim RITzschen Verfahren sinngemaB auf das obige nichtlineare Variationsproblem (A 27) zu ubertragen. Dasselbe trifft fiir Variationsprobleme mit mehreren gesuchten Funktionen zu bei Bestehen von (A 27') fiir jcden zul&ssigen Funktionenvektor: 6 = {5;(x), . . . , t r ( x ) ) , bezuglich der entsprechenden Vektornorm.

Lit cratiir

1 L. COLLATZ und W. WE:TTEI{LINC:, Optiniierungsaufgaben, Hcidelberger Taschenbticher Bd. 15, 1966, Springer. 2 G. B. DANTZIO and A. F. VEINOT, Mathematics of the Decision Sciences 1,2, Lectures in Appl. Math. 11, 12, Americ. Math.

3 K. H. ELSTER, Nichtlineare Optimierung, Mitteilungen der Math. Ges. d. DDR, Heft 1/2, S. 54-135 (1969). 4 H. P. K ~ ~ N Z I und W. OETTLI, Nichtlineare Optimierung, Neue Verfahren, 16 Lecture Notes in Operational Researrh and

5 H. R'. KUHN, Locational problems and mathematical programming, Prekopa 1956, S. 235-242. 6 S. G. MICHLIN, Numerische Realisiernng von Variationsmethoden, (Ubers.) Math. Lehrbiicher und Monographien, 11. Abt.

7 J. B. ROSEN, The gradient projection method for nonlinear programming I , 11, SIAM J. Appl. Math. 8, 180-217 (1960);

8 E. TREFFTZ, Konvergenz und Fehlerabschatzung beim Ritzschen Verfahren, Math. Ann. 100,s. 503-521 (1928). 9 PH. WOLFE, Bcceleration for cutting plane method for nonlinear programming. SIAM, J. Appl. Math. 9, 481-488 (1961).

Soc. Providence (1968).

Mathematical Systems, Berlin/Heidelberg/New York 1969, Springer.

Bd XXIII Akademie-Verlag. Berlin.

9, 514-532 (1961).

10 G. ZOUTENDIJK, Methods of Feasible Directions, Amsterdam 1960, Elsevier. 1 1 Nonlinear programming: A numerical survey, SIAM J. Control 4, S. 194-210 (1966). 12 S. J. ZUCHOVICKY und L. J. AVDEEV.4, Lineare und konvexe Programmierung, Miinchen/Wien/Oldcnbourg 1968.

Manaskripteingang: 7. 1. 1971

Anachrift: Prof. Dr. HERBERT BECKERT, Karl-Marx-Universitat, Sektion Mathematik, 701 Leipzig, Talstr. 35 (DDR)