This volume constitutes the proceedings of the workshop "Optimierung und Operations Research", held at the Elly Holterhoff Backing Stift (Bad Honnef) of the University of Bonn, October 2-8, 1977. This conference was devoted to recent advances in the field of mathe- matical programming, optimization techniques, and operations research. It was attended by about 50 invited participants. Furthermore many scholars in these areas showed a great interest in this workshop, despite several other conferences and activities on similar topics in the year 1977. The organizers regret that considerations of avail- able space for conference activities limited the number of participants. This widespread interest, the high quality of the lectures presented and the active and stimulating discussions at the conference mani- fested the breadth of the activity ongoing in the field covered by this workshop and the necessity that this field be cultivated to a greater extent by the scientific community. The workshop was organized by the Institute of Operations Research (Sonderforschungsbereich 21), University of Bonn and was generously sponsored by the Gesellschaft der Freunde und Forderer der Rheinischen Friedrich-Wilhelms-Universitat and by IBM Germany. Only through this invaluable support was this workshop possible; for this the editors wish to express their sincere thanks and appreciation. Bonn, December 1977 R. Henn B. Korte W. Oettli III TABLE OF CONTENTS A. Bachem The theorem of Minkowski for polyhedral monoids and aggregated linear diophantine systems * * * . * * * * * * * S. Baum and L.E. Trotter, Jr.

The variable metric algorithm is widely recognised as one of the most efficient ways of solving the following problem:- Locate x* a local minimum point n ( 1) of f(x) x E R Considerable attention has been given to the study of the convergence prop- ties of this algorithm especially for the case where analytic expressions are avai- ble for the derivatives g. = af/ax. i 1 *** n * (2) ~ ~ In particular we shall mention the results of Wolfe (1969) and Powell (1972), (1975). Wolfe established general conditions under which a descent algorithm will converge to a stationary point and Powell showed that two particular very efficient algorithms that cannot be shown to satisfy \,olfe's conditions do in fact converge to the minimum of convex functions under certain conditions. These results will be st- ed more completely in Section 2. In most practical problems analytic expressions for the gradient vector g (Equ. 2) are not available and numerical derivatives are subject to truncation error. In Section 3 we shall consider the effects of these errors on Wolfe's convergent prop- ties and will discuss possible modifications of the algorithms to make them reliable in these circumstances. The effects of rounding error are considered in Section 4, whilst in Section 5 these thoughts are extended to include the case of on-line fu- tion minimisation where each function evaluation is subject to random noise.

Die mathematische Optimierung - auch mathematische Programmierung genannt - befal3t sich mit dem Problem der Extremwertermittlung einer Funktion tiber einem zuiassigen Bereich, der wesentlich durch Gleichungs- und Unglei- chungsrestriktionen beschrieben ist. Zahlreiche praktische und theoretische Fragestellungen lassen sich auf dieses Problem zurtickfUhren. 1m vorliegenden Band soli ein Oberblick tiber die mathematische Optimierung in endlich-dimen- sionalen Raumen gegeben werden. Naturgemal3 steht dabei die nichtlineare Optimierung im Vordergrund, da die lineare Theorie weitgehend abgeschlossen und bereits in zahlreichen Lehrbtichem dargestellt ist. Immerhin findet sich auch die lineare Programmierung in einem eigenen Kapitel eingehend behandelt. 1m nichtlinearen Fall konzentrieren wir uns einerseits auf konvexe, andererseits auf ditTerenzierbare Probleme. Bei der Auswahl des Materials wurde den Grund- lagen - darunter verstehen wir die Charakterisierungstheorie der Optimal- losungen und die Dualitatstheorie - gleiches Gewicht beigemessen wie den eigentlichen Losungsverfahren. Die letzteren wurden nach Familien geordnet, wobei einige typische Vertreter aus jeder Familie vorgestellt werden. Wir haben grol3eren Wert darauf gelegt, den begriffiichen Ablauf eines Verfahrens klar- zumachen, als darauf, computerfertige Rechenanweisungen zu liefem. Es wurde versucht, die Resultate der konvexen Analysis auch fUr die Verfahren nutzbar zu machen, indem beispielsweise bei konvexen Funktionen nach Moglichkeit auf DitTerenzierbarkeitsforderungen verzichtet und stattdessen die Theorie der Sub- gradienten herangezogen wurde. Besondere Aufmerksamkeit wurde den Proble- men mit unendlich vielen Nebenbedingungen gewidmet; solche Probleme treten etwa in der Approximationstheorie in ganz nattirlicher Weise auf. Einige ein- gestreute Beispiele sind theoretischer Natur und sollen die Anwendungsmoglich- keit der Optimierung auf andere Fachgebiete illustrieren.

,, "'------ / I, I I I \ I, I I, 0 I ------- I ", \ I \ I, \, ", "- -, \ \ \ \ \,, I I J I, Fig. 5 gungen von (3. I) entsprechen, nlimlich: II: min {p' x + x' C x I A x = b, x O} (4. 6) und ill: min {p' x + x' C x I A x b}. (4. 7) Diese heiden Formulierungen dienen nur der mathematischen Vereinfachung. 'Sachlich bringen auch sie nichts Neues gegeniiber I, da man die abgeanderten Ne- benbedingungen von II und ill mittels der in Kapitel II (Abschnitt 3) beschriebenen Verfahren auf die Form I bringen kann, indem man etwa eine Gleichungsrestriktion durch zwei Ungleichungsrestriktionen ersetzt oder eine unbeschrlinkte Variable als Differenz zweier nicht-negativer Variablen ansetzt. Will man umgekehrt Problem I auf die Form II bringen, so fUhrt man fUr jede Ungleichungsrestriktion aus (4. 3) eine Schlupfvariable Yj ein und ersetzt aj x b durch aj x + Yj= b, Yj 0, kurz j j Ax+y=b, y O. (4. 8) Mit (4. 9) x= 11---;--l A* = II AlE II, C* = 11-- -+-g--l p* = 11---s---11 ist Problem I aquivalent dem Problem min {p*' x* + X*' C* x* I A* x* = b, x* OJ, (4. 10) das die gewiinschte Form II hat.

Das vorliegende Heft der Lecture Notes in Operations Research and Mathematical Systems verfolgt den Zweck, Interessenten der Nicht- linearen Optimierung (Programmierung) mit einigen gangigen Algo- rithrnen vertraut zu machen. Die Auswahl erhebt keinen Anspruch auf Vollstandigkeit, am ehesten konnte man sie als Erganzung zu den in der II Nichtlinearen Programmierung" von KUnzi-Krelle-Oettli be- schriebenen Methoden betrachten. Eine ausfUhrlichere und vollstandigere Darstellung wird einer Neu- auflage des erwahnten Buches vorbehalten bleiben. Besonderes Gewicht im Sinne einer Materialsammlung legten wir auf die im Anschluss an die Verfahren beigefUgte Bibliographie der Nicht- linearen Programmierung nebst ihren Grundlagen und Erweiterungen. Sie wird dem Leser die Moglichkeit geben, sich - auch unabhangig von der Sekundarliteratur - ein getreues Bild Uber den heutigen Stand dieser Theorie zu verschaffen. Eine derart ausfUhrliche Bestandesauf- nahrne existierte unseres Wissens bisher nicht. Wir mochten noch darauf hinweisen, dass die einzelnen Kapitel durch- gehend numeriert sind. FUr die Formelnumerierung wurden runde Klammern verwendet, eckige Klammern beziehen sich auf die am Schluss jedes Kapitels zitierten Arbeiten. Abschliessend mochten wir der Stiftung Volkswagenwerk in Hannover fUr den uns gewahrten Forschungskredit den herzlichsten Dank aus- sprechen.