479 K. VETTERS: Quadratische Approximationsmetlloden zur konvexen Optimierung -

&AMY 60, 479 -484 (1970)

Quadratische Approxiniationsmethoden zur konvexen Optimierung

Von K. VETTERS

Die Aufgabe der konvexen Optimierung wird durch Approximation der Zielfunktion auf die Losung einer Polge con quadrutischen Optimierungsaufgaben zuriickgefiihrt. Das angegebene Verfahren startet mit einer beliebigen zulassigen Losung und erzeugt eine Folge von Naherungslosungen, die mindestens quadratisch gegen die Minimallosung kon- vergiert. Unter den Verfahren mit hoherer Konvergenzgeschwindigkeit wird dasjenige bestimmt, bei dem die zur Erreichung einer vorgegebenen Genauigkeit erforderliche Zahl der Berechnunyen von Punktions- und Ableitungswerten minimal wird.

The convex programming problem i s reduced to the solution of a sequence of quadratic programming problems by appro- ximating the objective function. The described method starts with a n arbitrary feasible solution and generates a sequence of approximate solutions that converges at least quadratically to the minimal solution. Among various methods with higher convergence orders those are selected which require a minimal number of values of the function and its deriva- tives in order to guarantee a given accuracy.

~ I J ’ T ~ M annpoKcmaum qeneBoi ~ ~ J ’ H K E ~ M I I aa~ava sbinymoro ommmpoBaHzm CBOHMTCR IE pelueHmo

IIO IrpaiiIreii Mepe IrBaXpaTawo IE mwmtaniHoMy peruesaw . kI3 wcna MeToHoB, O ~ ~ C I I ~ ~ M B ~ I ~ I ~ I I X

lEBaAPaTMcIHbIX 3aAat1 01ITtlMLII)OBaHMFI. B IIpeAJlaraeMOM MeTOAe CJleAyeT IICXOAHTb M3 ~11o6oro no- IIJ’CTIiMOTO I>eIIie&ll.iH II OIIpeACJIMTb IIOCJleAOllaTeJILHOCTb IIpH6JIMH<6HHbIX pf2IIIelIMfi, c6n~ i t ca1ou~xc~

CI(OPJ’I0 CXORMMOCTb OIIpf2)JeJIRCTCR TOT MeTOa, HJIFI IEOTOpOrO KOJIHqeCTBO paCq6TOB BeJlMqMH @J’HIEuMfi M I lPOH3BO~HbIX, HeO6XOAMMOe AJlR ~ O C T H H W H M R 3aAaHHOfi T09HOCTII, MMlIMMaJlLHO.

Einleitung

I n dieser Arbeit wird die Aufgabe der Minimierung einer konvexen Zielfunktion iiber einem konvexen Bereich durch Approximation der Zielfunktion iterativ auf die Losung quadratischer Optimierungsaufgaben zuriickge- fuhrt. Die einfachste Variante dieses Verfahrens erzeugt eine Folge von Naherungslosungen, die quadratisch gegen die Minimallosung konvergiert. Dabei werden neben der Zielfunktion auch ihre ersten und zweiten partiellen Ableitungen benotigt. Ferner werden lterationsverfahren rnit hoherer Konvergenzgeschwindigkeit aufgestellt und unter ihnen dasjenige Verfahren bestimmt , das den maximalen Wirkungsgrad aufweist.

Die Behandlung der Aufgabe der konvexen Optimierung durch quadratische Approximationsmethoden ist wiederholt verfolgt worden. Hier wird an Arbeiten von GOLDSTEIN sowie LEVITW und POLJAK angekniipft. GOLDSTEIN [1] behandelte Extremwertaufgaben ohne Nebenbedingungen durch Approximation mit quadra- tischen TAYLOR-Polynomenl) und erzeugte die Konvergenz fur beliebige Ausgangsnaherungen durch zweck- mal3ig konstruierte Startiterationen. Von LEVITIN und POLJAK [4] wurde ein konvexe Restriktionen beriick- sichtigendes Verfahren aufgestellt und dessen Konvergenz fiir hinreichend gute Ausgangsnaherungen bewiesen. Analoge Verfahren, die z. T. mit Differenzenausdriicken statt mit Ableitungen arbeiten, wurden von GOLDSTEIN und PRICE [ZJ, von ULM und POLL [111 und in [9] untersucht. Das Anliegen der vorliegenden Mitteilung besteht in einer Kopplung der Ergebnisse von GOLDSTEIN und von LEVITIN und POLJAK. Es werden fur konvexe Opti- mierungsaufgaben mit Nebenbedingungen Verfahren angegeben, welche fur alle Startvektoren konvergieren. Bei der Aufstellung von Verfahren mit hoherer Konvergenzgeschwindigkeit wird in Anlehnung an ~’RAUB 1101, SCHMIDT und SCHWETLICK [7] sowie [9], [12], vorgegangen.

Fur Anregungen und Hinwcise gebiihrt Herrn Prof. Dr. J. W. SCHMIDT mein herzlicher Dank.

1. Bezeichiiungen und Hilfsniittel Mit f ( x ) , x = (xl, . . . , za) E ad, wird eine auf einer konvexen und abgeschlossenen Teilmenge K des d-dimen- sionalen Vektorraunics Rd erkliirte reellwertige Funktion bezeichnet. Ein Vektor x* E K wird Minimallosung von f auf K genannt, wenn

gilt. Fur das skalare Produkt von Vektoren x, y wird ( x , y) geschrieben; fur (x, x) steht 1 1 ~ 1 1 ~ . Fur den Gradien- ten von f wird die Bezeichnungf’(x) = - gewahlt. Entsprechend wird die HEssE’sche Matrix der zweiten

( aisz{xf) . Damit lassen sich die folgenden Hilfs- partiellen Ableitungen von f mit f ” ( x ) bezeichnet: f”(x) = ___

satze formulieren, die z. B. von LEVITIN und POLJAK [4] zitiert werden. Ein Beweis von Hilfssatz 1 kann in [9] nachgelesen werden. Hilfssatz 2 wird in Anlehnung an [0] bewiesen.

H i l f s sa t z 1 . Xei f konvex und stetig partiell differenzierbar. Eifi Velctor x,, E K ist genau dafim Minimal- losung, wen% f u r alle x E K g i l t :

f@*) 5.w (x E K ) (1)

(EZ)

(f(xo), x - xu) 2 0 , ( x E K ) . ( 2 )

1) Dieses Verfahren ist identisch mit den1 NEWTON-Verfahren zur Bestimmung einer ,,Nullstelle“ des Gradienten. Ein mit Interpolationspolynomen arbeitendes Verfahren dieses Typs wurde yon J. W. SCHMIDT et al. [5], [S], [9] untersucht.

31”

480 K. VETTERS : Quadratische Approximationsmethoden ztir konvexen Optiniierung

H i l f s sa t z 2 : Xei f koortvex und zweimal stetig partiell differenzierbar. Ein Vektor xo E K ist g e m u dann Minimallosung, wemn fur alle x E K gilt :

Beweis: Sei (3) erfiillt, und xo sei keine Minimallosung. Dann gibt es nach Hilfssatz 1 einen Vektor z1 E K mit (f’(xo), - zo) < 0 und folglich auch eine Zahl t rnit 0 < t < 1 und

t 2 y ( t ) = t(f’(ZO), ”1 - zo) + 2 (f”(.o) @l - zo), z1 - ”0) < 0 *

0 > y(t ) = ( f ’ (%), ” - J O ) + 2 - (f”(Z0) (x - xo), z - 5)

Mit x = t z1 + (1 - t) zo erhalt man 1

und damit wegen z E K einen Widerspruch zu (3). Urn die Umkehrung zu beweisen, wird die aus der Konvexitlit von f folgende positive Semidefinitheit (8. z. 13. [3])

(f”(z) U, U ) 2 0 (z E K ; u E Rd) (4 verwendet2). Sei zo Minimallosung von f auf K. Dann gilt (2). Zusammen mit (4) fur z = xo und z = z - xo folgt daraus Ungleichung (3). Damit ist Hilfssatz 2 bewiesen.

Fur den Konvergenzbeweis zu den betrachteten Verfahren wird an f” die Forderung nach gleichmafiiger positiver Definitheit und gleichmaBiger Beschriinktheit gestellt, d. h. es sol1 Zahlen M 2 m > 0 geben mit

(5 ) Bekannte Folgerungen aus ( 5 ) sind :

a) fist streng konvex auf K , b) es existiert genau eine Minimallosung von f auf K (8. z. B. [g]).

9% llU1l2 5 ( Y W u, .) 5 M llU1l2 > ( x E K ; U E R ~ ) .

3. Ein Iterationsverfahren mit quadratischer Konvergenz Mit Hilfe obiger Hilfssiitze ist es moglich, das von A. A. GOLDSTEIN fur Aufgaben ohne Nebenbedingungen ange- wendete Verfahren wie folgt auf die Losung der Aufgabe der konvexen Optimierung zu verallgemeinern.

Verfahren: Nach Wahl einer Konstanten c mit 0 < c < - und eines Vektors xo E K wird eine Folge 1 2

{ x n > (n 1 .

2 . 3.

4.

= 0, 1 , . . .) iterativ bestimmt durch die Vorschriften yn Minimallosung vonf, auf K ; dabei ist

1 fn(z) =f(xn ) + (fl(Xn), 5 - Xn) + 3 ( f ’ (xn) (x - xn), x - Xn) .

Gilt ( f l ( X n ) , yn - xn) = 0, SO ist x, die Minimallosung von f und das Verfahren wird abgebrochen. Sei ( f ‘ ( x n ) , yn - z,) + 0. Unter Verwendung der Hilfsfunktion

wird eine Zahl s, bestimmt gemaW : 31) s,, = 1 ffir y ( sn . 1 ) 2 c;

32) im Falle g(.rn, 1) < c wird s, > 0 so gewahlt, daB gilt c s g(x,, 8,) 5 1 - c .

z n + sn (Yn - xn) . xwk1

Zunachst ist zu zeigen, daB das Verfahren durchfuhrbar ist, d. h. daB fn eine Minimallosung hat und daB im Falle g(x,, 1) < c eine Zahl s, existiert, die (6) erfiillt. Ersteres folgt wegen fz(x) = f”(xn) aus Folgerung b) zu (5 ) . Die TAYLoR-Entwickhng vonf(xn + s (y, - x,)) an der Stelle x, fuhrt mit einer gewissen Zwischenstelle 2, = xn + 0 (yn - x,) E K , 0 < 0 < S, zu

1 s+o 2

und lim g(xn, s) = 1 > 1 - C. Zusammen mit g(xn, 1) < c < - und der Stetigkeit von g(x,, s) bezuglich s

ergibt sich daraus die Existenz einer Zwischenstellea, rnit 0 < s, < 1 und (6). Damit ist die Durchfuhrbarkeit des Verfahrens bewiesen.

2, Ungleichung (4) gilt, wenn f noch auf einer K enthaltenden offenen Menge zweimal stetig differenzierbar ist. 1st f nur auf K zweimal stetig differenzierbar, so laDt sich

(f’(z) (y - z), Y - z) 2 0 zeigen und der Beweis damit fortsetzen.

(z E K 3 Y E K )

K. VETTERS : Quadratische Approximationsmethoden zur konvexen Optimierung - - 481

Ferner ist die in 2) enthaltene Behauptung zu beweisen. Wegen 1) gilt fn(x) 2 ,f,(yn) fur alle x E K. Mit (f’(xn), yn - xn) = 0 und ( 5 ) folgt daraus

und nach Hilfssatz 2 ist x, die Minimallosung von f. Das Verfahren fiihrt zu einer Folge { xn}, fiir die folgende Aussage gilt.

stanten 0 < Tn 5 iM die Ungleichungen (5 ) . Dann gilt fiir jedes xo E K Konvergenzsa tz : Die Funktios f sei xweimal stetig partiell dijferenxierbar und erfulle rnit gewisses Kon-

a) f(xn-1) Z f ( x n ) +f(x*), x n - t x * 7 (n- t a), b) es gibt ein no rnit s, = 1 f u r n 2 so.

Beweis: Es darf(f’(zn), yn - xn) * Ofiir alle n 2 0 angenommen werden, da andernfalls das Verfahren mit xn = z*

(8)

abbricht. Aus

fTX4 = f’(zn) + fl’(zn) (z - 2%) erhalt man mit x = yn und Anwendung von Hilfssatz 1

Im Falle 32) ergibt sich daraus fur s = sn die Abschatzung 2c m 31

Diese Ungleichung gilt auch im Falle 31).

sn 2 --.

Nach dieser Vorbereitung la& sich jetzt die Konvergenz von {f(xn)} nachweisen. Es ist

(11)

Die Folge { f (zn)} ist mithin monoton fallend und hat die untere Schrankef(z*); {.f(zn)} konvergiert also. Aus(l1) folgt dann

2 c2 m f (zn) -f(m 11) = 8s) * sn * (j”(znL zn - ~ n ) 2 7 (f’(zn)7 xn - ~ n ) > 0 .

(f’(4, yn - 4 + 0, aus (9) (f”(zn) (yn - zn), yn - zn) -+ 0 und damit fn(Yn) - f(%) 3 0 * (12)

Weiter wird zum Nachweis der Konvergenz von {zn} die beschrankte und abgeschlossene Menge S = {z E K I f(z). f(z,)), die die Vektoren xn enthalt, benotigt. Es seien ferner { E n } eine beliebige Teilfolge von { zn} und { q,}, { q,} die zugehorigen Teil-

folgen von {y,} und I fn} (d. h. q, ist Minimallosung von qn(z) = f ( E n ) + (f’(tn), x - En) + - ( f ” (En) (z - tn), z - 6,) auf K ) .

Wegen tn E S enthalt { 6,) eine konvergente Teilfolge { zn} ; { ?jn} und { seien die zugehorigen Teilfolgen von { 7%) und { qn}. Der Grenzwert von { cn} wird mit E* bezeichnet: cn + E * . Es gilt dann fur alle x E K

1 2

- 1 Gn( l ln) -- f(&) 5 64%) - fGn) = ( f ( F 9 A x - Fn) + - 2 (f’’(&d (z - Fn), z - En) *

0 5 ( f ’ ( E * ) , z - t*) + 2- (f”(t*, (z - t*), x - E * )

Hieraus erhalt man durch Grenziibergang n --f cc mit (12) und wegen der Stetigkeit der Ableitungen 1

Nach Hilfssatz 2 und wegen der Eindeutigkeit der Minimallosung folgt t* = x*. Es ist damit gezeigt, dal3 jede Teilfolge von { xn} eine gegen z* konvergente Teilfolge enthiilt. Bekanntlich gilt dann xn + z*. Die Stetigkeit vonfliefertf(z,) +f(z*).

Zum Nachweis von b) wird zunachst aus der bereits festgestellten Konvergenz (f’(zn), yn - z,) -+ 0 und aus den Un- gleichungen (9) llxn - ynll 3 0, yn --f z* gefolgert. Wegen 0 < CT < s < 1 ergibt sich damit auch zn -+ x*, und aus der ersten Ungleichung von (10) folgt (mit der euklidischen Matrizennorm)

fur n 3 cu s s 2 2 1 - ----l l f ’(zn) -f ’(zn)ll -+ 1 -

2 2 m und endlich

1 lim g ( s f l , 1 ) 2 > c ,

n+cc

d. h. mit einem Index n, gilt) g(z,, 1) > G fur n 2 no. Damit ist der Konvergenzsatz vollstandig bewiesen.

Nach Aussage b) ist obiges Verfahren von no an mit dem von LEVITIN und POLJAK [4] beschriebenen Verfahren identisch. Die fur n < no konstruierte Abanderung ist so eingerichtet, daI3 die Konvergenz fur be- liebige Startvektoren erzwungen wird.

Um die quadratische Konvergenz nschzuweisen, wird jetzt die Existenz und Stetigkeit der dritten par- tiellen Ableitungen sowie ihre Beschranktheit in der Form ~ ~ j ” f ( x ) ~ / 5 L fur x E K vorausgesetzt. Da zur Be- stimmung der Konvergenzgeschwindigkeit eine endliche Zahl von Iterationen unberucksichtigt bleiben darf,

K. VETTERS: Quadratische Approximat,ionsmethoden zur konvexen Optimierung ~ _ _ ~ 482

betrachten wir nur noch Indizes n. 2 no. Es ist dann s, = 1, also x, +

Umformungen erhalt man = y,. Mit (8) und einigen elementaren

1 fn(Xn,-I) - fn (x* ) = (f’(xn), .,+1 - .*) + 2- ( f f f ( X n ) ( X n + l +?a), %+1- Xn) -

1 1 - - (f”(x,) (x* - x,), x* - xn) = (f;z(x,+1), .,+1 - .*) - y (f”(%) (.,+1 - x*), x,+1 - .*) 2

und durch Anwendung von Hilfssatz 1 auf die Minimallosung x , + ~ vonf,(z) sowie (5) m

fn(xn+1) -f&*) d - 5 II%+l - x*1I2.

Mit den TAYLOR-Entwicklungen

f’(xn) =f ’ (x* ) + f ” ( x * ) (2, - x*) + R, , 1

R, = J t (f”’(x* + t (r, - x*)) (x>& - x*)) (x, - x*) dt , 0

1 R2 = J f ” ’ (x, + t (x* - x,)) (x* - x,) dt

f ” x * ) =f”(x:n) + 4 , 0 wird andererseits

fn(x*) - f iz(xni-~) = - ( f ’ ( ~ * ) +f”(%) (x, - x*) + R, (x, - x*) + R,, X, I 1 - x*) - 1 1 -2 ( f ” ( X n ) (%+1 - X,), X,+ 1 - Xn) + 2 ( f”(2 , ) (X, - x*), x, - x*)

1 = - ( f ’ (x*) , %,+I -z*) - (R,(x,-x*) +R,,x,+l -x*) - --(j”(x,)(~~+ 2 1 -x*),~,~~-x*).

Die Anwendung von Hilfssatz 1 auf die Optimalitat von x, beziiglich f , von llf”’(x)ll 5 L fur x E K sowie ( 5 ) liefert

(14) 3 m

f&*) -fn(.,+d5yLIIX, -x*1I2 IlX,+l - -* I1 - + k + 1 -x*)12.

Zusammenfassung von (13) und (14) ergibt

womit die quadratische Konvergenz des Verfahrens gezeigt ist.

3. Verfahren mit hoherer Konvergenzgeschwindigkeit Durch Konstruktion von Verfahren mit hoherer Konvergenzgeschwindigkeit und nicht wesentlich hoherem Rechenaufwand pro Iterationsschritt wird eine Verringerung des Gesamtaufwands erzielt. Analog zu [lo], [7], [9] wird die Zahl der bis zum Abbrechen des Verfahrens notwendigen Berechnungen von Werten der Ziel- funktion und ihrer Ableitungen als Kriterium fur den Rechenaufwand des Verfahrens genommen. Als geeigne- tes Ma13 fiir diesen Rechenaufwand dient der Wirkungsgrad3)

1 = X I / & ,

wobei oc die Zahl der Funktionswert- ugd Ableitungsberechnungen pro Iterationsschritt und x die Konvergenz- geschwindigkeit des betrachteten Verfahrens ist. Da der im obigen Sinn verstandene Gesamtaufwand des Ver- fahrens umgekehrt proportional zu il ist, hat man Verfahren mit maximalem Wirkungsgrad zu suchen. Zu diesem Zweck wird eine Folge von Verfahren V , mit wachsender Konvergenzgeschwindigkeit aufgestellt und unter diesen Verfahren dasjenige mit maximalem Wirkungsgrad ausgesucht. Unter den Verfahren Vk ist das Verfahren von Abschnitt 2 als Verfahren Vo enthalten. Zur Vermeidung von Wiederholungen werden deshalb in der Folge manche Erlauterungen und Zwischenrechnungen fehlen, da sie bereits in Abschnitt 2 in ahnlicher Weise vorkommen. Wir erklaren jetzt das den ganzzahligen Parameter k = 0, 1, . . . enthaltende

1 Ver fah ren V,: Sei 0 < c < -und xo E K. Ausgehend von x, (n. = 0, 1, . . .) wird fur j = 0, 1, . . . , k festgesetzt : 2

0 ) Wno = Xn 9

1) y,, Minimallosung von fnr auf K mit

1 fn,(x) =f(wnr) + ( W n A 5 - Wn1) + 2 (f”(.n) (I(: - W n h x - Wnr) Y

2) s,j = 1, falls (f’(wnj), Ynr - wnj) = 0 9

3, Nach A. OSTROWSKI: Solution of Equations and Systems of Equations; beziiglich naiherer Aussagen uber Wirkungs- grad und Anfwand wird auf [lo], 171, [9] verwiesen.

K. VETTERS : Quadratische Approximationsmethoden zur konvexen Optimierung 483

3) fur (fl(w,,), yn3 - w,~) + 0 wird die Hilfsfunktion g definiert durch

es werden Zahlen s,, bestimmt gemiil3 31) s,, = 1 falls g(wni, 1) 2 c, 32) im Falle g(wnJ, 1) < c wird snI > 0 so gewlhlt, daB gilt

c 5 S(WR,, s,,) 5 1 - c >

4) wn,j+l = wng + sng (Y~I -. w,!) >

5) xn+1 = wn, k+l . Das Verfahren ist damit vollstandig beschrieben. Hervorzuheben ist, daB bei diesem Verfahren zur Senkung des Aufwandes die aJm aufwendigsten zu bildende Matrix f” nur noch mit jeder ( k + 1)-ten Berechnung von f.’ vorkommt. Die Lijsbarkeit der in 32) vorkommenden Ungleichungen fur s,, ergibt sich iiber TAYLOR-Ent- wicklung aus

1 und aus g(wn,, 1) < %.

Konvergenzsa tz . Die Funktion f sei zweimal stetig differertzierbar und es gelte (5 ) . Die M e w e K sei konvex urtd abgeschlossert. Danrt konvergiert die durch das Verfahren V , definierte Folge { x,) gegen die Mirtimal- losung x*. Die Folge { f ( x n ) } konvergiert monoton gegen f (x*) . Falls auch die dritten partiellem Ableitungen von f existieren und auf K stetig und beschrartkt sind, konvergiert (x , ) mit der Geschwindigkeit x = k + 2.

(.f’(wn~), Y,! - wnj) 5 - (f”(zd (yni - wed, yn j - wnj) 5 - m Ilyn/nl - wnjlla 5 0 . Beweis: Ausf,,(ynj) ~ f n ~ ( w , , ) und ( 5 ) folgt

(15) Im Falle 2) ergibt sich Yn I = wn 1 = wn, j+i: Daraus erhiilt man unmittelbar die Ungleichungen (17). (Gilt 2) fur j = 0, so ist ylao = wno = xn = x* iind das Verfahren bricht ah.) ImFalle(f’(w,g), yn j - w,,) * 0 wird g mitHilfevon(15) abgeschiitzt:

2 c m und hiermit uber 3), 4) und (15) Mit 31), 32) und (16) erhllt man s n j 2 __ M

2 ca m M f(wn1) - . W n , i+l) L - ( 7 ( W ? a j ) , w,, - y,,) 2 0 .

Diese Monotonie liefert bei Beachtung von 0) und 5 ) die Ungleichungenf(z*) 5 f(wn+i, j) 5 f(y,, j + i ) 5 f(w, 1); bei jedem festen j konvergiert also die Folge {f(wnj)} fur n -+ 00 gegen den gleichen Wert. Daraus folgt welter (f (w,,), y,~ - Wnj) + 0 und I J y n j - wnll l+ 0 wegen (15). Wie im Konvergenzbeweis von Abschnitt 2 erhklt manf,,(y,,) -f(w,,) + O und durch Betrach- tung entsprechender Teilfolgen {on, }, { Gn ,} von { w, ,} die Konvergenz Gn j -+ w; sowie f(Gn 1) -+ f(ojf) bei festem j fur n + co. Speziell fu r j = 0 wird mit Hilfssatz 2 o: = x* gezeigt, und es ergibt sich der erste Teil der Behauptung: Xn + X* und f(xn-1) 2

Die Einschliehng f(xn) 2 f(w, ,) 2 f (xn+i) IiiiBt auf f(o7) = f(x*) und wegen der Eindeutigkeit der Minimallosung auf o; = x* schlieaen. Die Folgen {wnf} ( j fest, n +- w) - und damit auch {Y,,}, {z,,} - konvergieren also gegen x*. Unter Beachtung dieser Konvergenz erhiilt man nach weiterer Abschiitzung des mittleren Terms von (16) fur 8 = 1

2 f(xn) -tf(x*).

Von einem gewissen Index no an gilt also s, , = 1 ( j = 0, . . . , b; n 2 no).

von (13) und (14) verwendeten Methoden fuhren jetzt auf Fur den Nachweis der Konvergenzgeschwindigkeit betrachten wir wiederum nur Indizes n 2 n,. Die zur Herleitung

1 fiaj(wn, i + ~ ) - fnr(z*) = (f;lj(wn, j+l), wn, j + l - x*) - y(f”(xn) (wn, j + l - s*), wfl,j+l - x*) 5

m 5 - T I I W n , j + l - ~ * 1 1 ’ und mit

1 R, = i t (f”’ (x* + t (wng - x*)) ( W n j - x*,) (W,, - x*) dt ,

1 R, = Jf”’ ( ~ n + t (z* - z,)) (x* - 2,) dt

0 auf

fnr(z*) - fn j(Wn, $+I) = - (f’(z*), Wn, ?+I - x*) - ( R , (w,, - x*) + R,, W ~ L , ?+I - X* )- 1 - _z (.f”(4 (wn, j+l - z*), wn, j + l - z*)

L 5 L Ilw,, - x*ll llzn - %*I1 Ilwn, j+l - x*IJ + - 2 Ilw,, - X*IP IlWn,i+l - x*ll -

K. VETTERS : Quadratische Approxiniationsniethoden zur konvexen Optimierung ~~ - _ _ - -___-~ ____ ~ - .. 484

Die Zusammenfassung der beiden Abschatzungen ergibt L

Ilwn, i+l - x*ll 5 I lwnf - %*I1 (2 l l rn - ~ * l l + IIwnf - z*ll) - (18)

= - < 1 3 L r 2 m

Die bereits bewiesene Konvergenz zn + x* sichert die Existenz eines Index nl 2 no, fur den I lrnl - z*I I 5 r und gilt. Aufbauend auf den Zahlen rnl = r und qn, = q wcrden rekursiv die Zahlenfolgen

3 L rn+i=qlC, l lrn nnd q n 1 i = - - r T I L ~ i (n = n,, n1 -k 1, . . .) 2m

definiert. Mit diesen Zahlenfolgen gilt fur n 2 n,, j = 0, . . . , k + 1

Nachweis: Esgenugtzuzeigen, da13 ausa)dieGiiltigkeitvon b)folgt, denndannergibt sichuber llzn+i- x*ll = ] / t u n , , t+i -r*ll 5 q$+' T n = m+i die Richtigkeit von (19) fur alle n 2 n,. Wegen 7uA0 = zn gilt b) fur j = 0. Fiir den Schlir13 von.j a o f j 1 1 wird (18) zusammen mit qn =

a) llrn - z*ll 5 rn und b) Ilwnf - x*ll 5 qh r , . (19)

= . < 1 herangezogen: L I;

Ilwn,j+i - x*j[ 5 - q j r (2 rn + qg rn) 5 =qJ rn 3 r , = q&+1 rn . 2m

Wegen rn+l = (g)k+l?$+a konvergiert { r n } und damit auch { s n } mit der Geschwindigkeit x = k + 2. Der Beweis des Kon-

vergenzsatzes ist damit erbracht ,

Die Zahl 01 der Funktions- und Ableitungsberechnungen, die das Verfahren V , fur einen Iterationsschritt von 5, zu T , , ~ 1 rnit n 2 n, benatigt, betragt

Durch Loaung der Aufgabe

3, (k,,,, d ) = max A(k, d ) k=O, 1,. . .

bei festeni d ergibt sich der optimale Wirkungsgrad il und die optimale Stufenzahl k,,, = kn,nx(d). Die charak- teristischen Daten3) kmnx(d), lg3, (0, d) , l g l (k,,,, d ) sowie der am Aufwand des Verfahrens V, in Prozent, ge- messene Aufwand des Verfahrens V,,, sind fur einige Dimensionen der folgenden Tabelle zu entnehmen.

7 10 15 20 30

0 1 1 2 2 2

0,10034 0,05017 0,03010 0,02007 0,01433 0,01075 0,00836 0,00456 0,00221 0,00130 0,00061

0,10034 looyo 0,05301 95% 0,03408 88% 0,02408 83% 0,01824 79%

0,01165 72% 0,00707 64% 0,00391 57%

0,00134 4.5(j0

0,01433 75%

0,00253 52 F ,

Numerische Tests liegen zur Zeit noch nicht vor; hieriiber sol1 zu einem spateren Zeitpunkt berichtet werden. AuBerdem lassen die numerischen Erfahrungen zu den verwandten Verfahren in [2J, [7], [9], [ l l ] Ruckschliisse auf die Brauchbarkeit der vorliegenden Verfahren zu.

Literatur 1 A. A. GOLDSTEIN, Minimizing Functionals on Normed-Linear Spaces, J. SIAM Control 4, 81-89 (1966). 2 A. A. GOLDSTEIN and J. F. PRICE, An Effective Algorithm for Minimization, Nnm. Math. 10, 184-189 (1967). 3 H. P. KUNZI und W. KRELLE, Nichtlineare Programmierung, Berlin-Gottingen-Heidelberg 1962: Springer-Verlag. 4 E. c . DeBMTHH M B. T. n O n r i H , MeToJxhI M H H k i M ~ 3 a l U W f IIpH HaJlHWlM OrpaHMseHMii, a.BLd9. MaT.

5 J. W. SCHMIDT, Extremwertermittlung mit Funktionswerten, Wiss. Zeitschr. TU Dresden 12, 1601 -1605 (1963). 6 J. W. SCHMIDT, Vorlesung iiber nichtlineare Optimierung, gehalten an der TU Dresden 1968/69. 7 J. W. SCHMIDT und H. SCHWETLICK, Ableitungsfreie Verfahren mit hoherer Konvergenzgeschwindigkeit, Computing 3,

8 J. W. SCHMIDT nnd H.-F. TRINKAUS, Extremwertermittlung mit Funktionswerten bei Fnnktioncn von mehrcrcn Verindcr-

9 J. W. SCHMIDT und K. VETTERS, Ableitungsfreie Verfahren fur nichtlineare Optimierungsprobleme, Num. Math. 16,263 -282

@Ma. 6, 787-823 (1966).

215-226 (1968).

lichen, Computing 1, 224-232 (1966).

(1970). 10 J. F. TRAUB, Iterative Methods for the Solution of Equations, Englewood Cliffs, N.J. 1964, Prentice-Hall. 11 c. Y J I b M M B. nOJIJIb, 0 HeKOTopbIX MeToAaX pemeHEla a a ~ a s H a MEIHMMYM, H3B. AH 3ccP 17 , 151-163

12 K. VETTERS. Erhohung der EffektivitLt bei ableitungsfreien Verfahren zur Extremwertberechnnng, Colloquia Mathema-

Manuskripteingang : 25. 6. 1969

Anschrift: Dipl.-Math. K. VETTERS, Sektion Mathematik der Technischen Universitiit, 8027 Dresden, Zellrscher Weg 12 - 14

(1 968).

tics Societatis JBnos Bolyai, 3. Numerical Methods. Tihany (Ungarn) 1968, 167 - 173.