W e r n e r V o 2

Minimierung und Optimierung.

Das Problem der Optimierung ist auch in der Statistik yon gro2em theoretischem wie praktisehem Interesse, weil viele statistische Fra- gestellungen auf Optimierungsaufgaben zurfickgeffihrt werden k6nnen. Allgemein kann ein Optimierungsproblem wie folgt formuliert werden:

Gegeben sei eine Zielfunktion F, welche yon n Komponenten X. a b h ~ n g t : 1

F = f(X I, X 2 ..... Xn)

Diese Zielfunktion F ist zu minimieren (jedes Maximierungspro- blem kann leieht in ein Minimierungsproblem transformiert werden), wobei die folgenden m Beschr~nkungen durch die Variablen X. nicht verletzt werden diirfen: l

Bj(X , X 2 . . . . , x) - - , e.j

f i i r j = 1, 2 . . . . . m

Statistisehe Anwendungsf~lle sind zurn Beispieh

u.~.

Bestimmung eines optimalen Stichprobenumfangs,

Bestimmung einer optimalen Stichprobenschichtung,

Optimale Entscheidungen bei Signifikanztests,

Optimale Anpassung theoretischer Funktionen an empirische Daten,

Die verschiedenen Optimierungsprobleme werden - nicht nut bei sta- tistischen Anwendungsf~illen - fiblicherweise nach zwei Kriterien

unterteilt:

a) lineare - niehtlineare Probleme (bei linearen Problemen sind Zielfunktion und Beschr~inkungen linear).

b) konvexe - konkave Probleme (konvex ist ein Problem dann, wenn keine Suboptima auftreten).

314

In der Literatur wird im allgemeinen davon ausgegangen, dab es ein generelles LSsungsverfahren fiir alle denkbaren Optimierungsprobleme nicht gibt und m6glicherweise auch nicht geben kann, sondern daf~ nut Spezialverfahren fiir bestimmte F~lle existieren (siehe z.B. die

Arbeiten yon HADLEY (2), KUNZI/KRELLE (4) und MOLLER-MER- BACH (5)). Diese Feststellung einerseits und die gro/3e praktische Relevanz andererseits sind Anl~sse genug, um zu priifen, ob neuere Rechenverfahren nicht doch zu einer allgemeingtiltigen L6sungsme- rhode for Optimierungsprobleme f~ihren kSnnen.

In den letzten Jahren wurden aufgrund des zunehmenden Einsatzes yon C omputern eine Reihe leistungsf~higer Minimierungsverfahren entwickelt. Da jede Optimierungsaufgabe als Minimierungsaufgabe interpretiert werden kann (Aufsuchen des Zielfunktionsminimums in- nerhalb des Beschr~nkungsraums B), liegt der Gedanke nahe, eines (oder mehrere) der Computer-Minimierungsverfahren zu verwenden. Eine grobe Unterteilung der zur Verfiigung stehenden Methoden l~/~t sich folgenderma~en vornehmen:

I. Gradientenverfahren:

Die Suche des Minimums orientiert sich h[er an der ersten Ablei- tung der Zielfunktion irn jeweils 'erreichten Punkt. Diese Verfahren eignen sich also nicht zur Entwicklung einer allgemeingfiltigen Op- timierungsmethode, weft ihr Anwendungsbereich eingeschr~nkt ist. Einzelheiten zu den Gradientenverfahren finden sich in der Arbeit yon Kappler (3).

2. Suchverfahren:

Der Funktionsbereich wird hier nach verschiedenen Verfahrensmustern abgesucht, zum Beispieh

a) Simplex-Verfahren (nicht zu verwechseln mit der Simplex- Methode zur Lbsung linearer Optimierungsprobleme). Dieses Verfahren wird bei NELDER/MEAD besprochen (6). Geht man der Anschaulichkeit halber davon aus, daf~ ein Problem mit nur zwei unabh~ingigen Variablen X. vorliegt, so gilt: Es werden drei Punkte im Funktionsberleich vorgegeben und die dazugehbrigen Funktionswerte F berechnet. Der dabei schlechteste Weft wird am Schwerpunkt der beiden anderen gespiegelt, wodurch eine neue "Dreiergruppe" entsteht. Man berechnet dann den neu hinzukommenden F-Weft, bestimmt wieder den schlechtesten usw. usw. Durch geeignete Varia- tionen der Schrittweiten und/oder der Spiegelungsvorschriften kann auf diese Weise sehr rasch eine beliebige N~herung an das Minimum yon F erzielt werden.

b) Rosenbrock-Verfahren: Die Orundlagen zu diesem Verfahren finden sich in der Arbeit von Rosenbrock (7). Dieses Verfahren sucht in je einer Koordinatenrichtung mit beeinflu~baren Schritt-

315

weiten das relative Minimum mithilfe von St0tzfunktionen durch jeweils drei Punkte, welche auf einer Ebene liegen. Von dort aus wird in der n~ichsten Richtung weitergearbeitet. Sind alle Koordinatenrichtungen abgearbeitet, wird ein neues Koordinaten-

system erzeugt, in dem dann der gleiche Suchprozef~ abl~iuft usw. Aueh auf diese Weise kann rasch das Minimum beliebiger Funktionen bestimmt werden. Einzelheiten zu der Funktions- weise dieses Verfahrens linden sich in einer frQheren Arbeit des Verfassers (8).

Es gibt noch eine Reihe weiterer Suchverfahren. Die praktische Ar- belt mit verschiedenen Verfahren zeigt jedoch, da~ die beiden ge- nannten Verfahren sich f0r Optimierungsprobleme gut eignen. Um diese Minimierungsverfahren zur L6sung beliebiger Optimierungs- probleme verwenden zu k6nnen, miissen sie um die folgenden Ar- beitsschritte erg~nzt werden:

i. Es ist zun~chst zu pr(ifen, ob ein "echtes" oder ein triviales Optimierungsproblem vorliegt. Als "trivial" bezeichnen wir jene Probleme, bet denen das Zielfunktionsminimum im Be- schr~nkungsraum B liegt und nicht au~erhalb von ihm. Be- rechnet man vor dem eigentlichen Optimierungsprozeg das Minimum M der Zielfunktion F, so ist das Optimierungspro- blem schon gel6st, falls sich herausstellt, dag die zu M ge- h6renden X-Werte keine der Beschr~nkungen verletzen. Nut im gegenteiligen Fall wird der Iterationsprozeg zur Suche des Optimums in Gang gesetzt.

2. Um den Iterationsproze/3 (Simplex- oder Rosenbroek-Methode) in Gang zu setzen, miissen gfiltige Startwerte, d.h. solche, die in B liegen, vorgegeben werden. Oft wird diese Bedingung dureh den Koordinatenursprung erfiillt. In komplizierteren F~llen kSnnen giiltige Startwerte z.B. dadurch ermittelt wet- den, da~ man zwei Beschr~nkungen schneidet und prtift, ob der Schnittpunkt S eine der anderen Beschr~nkungen verletzt. Tut er das nicht, ist ein giiltiger Startwert gefunden, andern- falls pr(ift man einen weiteren Schnittpunkt S. Eine Methode, die auch von Startpunkten augerhalb von B ausgehen kann, zeigen BRACKEN/McCORMICK (I).

3. Das "Kernproblem" bet der Verwendung von Minimierungsver- fahren zu Optimierungszwecken ist die Frage, wie es erreicht werden kann, da~ der Suchprozeg auf den Beschr~nkungsraum B beschr~nkt werden kann. Es bieten sich dazu einige Metho- den an, von denen die sog. "Strafmethode" sich als zweckm~l~ig erwiesen hat. Sie basiert auf der folgenden Uberlegung: Da beim IterationsprozeI~ die Suchrichtung sich danach orientiert, wie eine weitere Verkleinerung yon F erzielt werden kann, werden bet allen "echten" Optimierungsproblemen Restrik- tionen verletzt, well sie in der Verkleinerungsrichtung yon F fiberschritten werden. Dies kann man verhindern, indem man die Zielfunktionswerte au/~erhalb des Beschr~nkungsraums

316

B "kfinstlich" erhbht (mit einer "Strafe" belegt), um so dem Suchproze~ "vorzuspiegeln", dab eine Suche au~erhalb yon B sich nieht lohnt. Uberschreitet er eine Restriktion, so kehrt der Suchproze~ in den Beschr~nkungsraum B zurGck.

Diese "Strafmethode" funktioniert in vielen F/illen, unahh~ngig davon, ob lineare, nichtlineare, konvexe oder konkave Opti- mierungsprobleme zu Ibsen sind. In Ausnahmef~illen kann es jedoch dann zu einem unerwfinschten Abbruch des Suchpro- zesses kommen, wenn nach der durch die "Strafe" verursach- ten ZurGcksehickung keine Verkleinerung der Zielfunktions- werte mehr registriert werden kann. Da bei komplizierten Optimierungsproblemen dieser Fall nicht ausgeschlossen wer- den kann, haben wir eine Methode entwickelt, bei der der Gedanke der "Strafe" zwar beibehalten wird, eine Erg~inzung jedoeh in der Weise vorgenommen wird, da/3 der eventuell mbgliehe, unzul~issige Abbruch des Suchverfahrens zuverl~issig verhindert wird (die Details dieses modifizierten Suchverfah- tens sollen einer sp~iteren Verbffentlichung vorbehalten bleiben).

4. Schlie~lich mfissen Wege gefunden werden, umbei konkaven Problemstellungen ein Verharren des Suchprozesses in einem Suboptimum zu verhindern. Beide genannten Suchverfahren sind in der Lage, Suboptima .zu fibergehen, wenn die Such- schrittweiten in geeigneter Weise variiert werden (z.B. so, da[~ die Ergebnisse der jeweils vorangegangenen Iterations- runde mit vergrb~erter Schrittweite probeweise fiberprfift werden). Eine andere Mbglichkeit bietet sich, wenn man den Suchproze~l parallel an mehreren Startwerten beginnen l~iSt, um zu weiterffihrenden Aussagen fiber die "Grobstruktur" der zu minimierenden Funktion F zu gelangen. Die dadureh ge- wonnenen Informationen kbnnen bei der w.eiteren Suche das tJ~bergehen der eventuell vorhandenen Suboptima wesentlich erleichtern, unter bestimmten Umst~inden sogar sichern.

Das in dieser Weise kurz skizzierte allgemeingfiltige Optimierungs- verfahren l~bt sich in den folgenden Arbeitsschritten zusammenfassen:

I. Berechnung des Zielfunktionsminimums M.

2. Wenn die zu M gehbrenden Variablenwerte X. im Besehr~nkungs- raum B liegen, ist das Optimum schon gefunlden.

3. Wenn nicht, mfissen ffir den Iterationsproze~ giiltige Startwerte vorgegeben werden.

4. Dann beginnen die Iterationen des Suchprozesses.

5. Bei jeder Iteration ist zu prfifen, ob alle Beschr~nkungen ein- gehalten werden.

6. Wenn dies nieht gesehehen ist, mu[~ der Suchproze~ durch geeig- nete Maf~nahmen in den Beschr~nkungsraum B zurfickgeschickt werden und es ist bei Schritt 4. fortzufahren.

317

7. Werden dagegen die Beschr~nkungen eingehalten, ist zu priifen, ob sich der Zielfunktionswert F bet der letzten Iteration im Vergleich zur vorhergehenden signifikant verkleinert hat.

8. Wenn ja, ist wetter zu iterieren (zuriiek nach 4. ).

9. Verkleinert sich F dagegen nicht, und sind alle Koordinaten- richtungen und diejenigen der transformierten Koordinaten- systeme mit unterschiedlichen Sehrittweiten abgearbeitet, so ist das Optimum gefunden.

Die praktische Erprobung dieses Verfahrens zeigte, daft es beliebige Optimierungsprobleme zu 15sen in der Lage ist, also z.B. auch die folgenden Spezialf~lle (diese schliefen sich bet dieser Aufz~hlung nicht gegenseitig aus):

- Lineare und nichtlineare Optimierungsprobleme, Probleme mit Unter- und mit Oberbesehr~nkungen, Probleme mit ein- und ausschliefenden Beschr~nkungen, Probleme mit getrennten Beschr~inkungsr~iumen, beliebig hochdimensionierte Probleme, Probleme mit beliebig vielen Beschr~nkungen,

USW.

Deshalb bietet sich diesem Verfahren ein breiter Anwendungsbereich. Leser, die an seiner Verwendung interessiert sind, m6gen sich mit dem Verfasser in Verbindung setzen.

Literatur:

(I) J. BRACKEN/G. McCORMICK: Ausgew~hlte Anwendungen nicht- linearer Programmierung, Stuttgart u. a., 1970.

(2) G. HADLEY: Nichtlineare und dynamische Programmierung, Wfirz- burg 1969.

(3) H. K A P P L E R : G r a d i e n t e n v e r f a h r e n der n i ch t l inea ren P r o g r a m m i e - rung, G5t t ingen 1967.

(4) H . P . KONZI /W. K R E L L E : Nich t l i nea re P r o g r a m m i e r u n g , B e r l i n u . a . , 1962.

(5) H. M t I L L E R - M E R B A C H : O p e r a t i o n s R e s e a r c h , Be r l in und F r a n k - fur t 1969.

(6) J . A . N E L D E R / R . MEAD: A s i m p l e x method fo r function m i n i m i z a - tion, in: The C o m p u t e r J o u r n a l , No. 7, 1964/65, S. 308 ft.

(7) H.H. ROSENBROCK: An a u t o m a t i c method for finding the g r e a t e s t or l e a s t value of a function, in: The C o m p u t e r Jou rna l , No. 3, 1960, S. 175 ff.

(8) W. VOSS: Die M0gl ichkei t der Sch~tzung der P a r a m e t e r t h e o r e t i - s c h e r Funkt ionen bet g e g e b e n e m D a t e n m a t e r i a l mit Hilfe e ines C o m - p u t e r - P r o g r a m m s i t e r a t i v e r Approx i ma t ion , in: S t a t i s t i s che Hefte , 11. J g . , 1970, Heft 2, S. 130 ff.

318