|
Showing 1 - 7 of
7 matches in All Departments
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.
|
|