Minimieren von Funktionen

Kapitel 4
Minimierung von Funktionen
In diesem Kapitel werden Methoden diskutiert, mit denen eine Zielfunktion in Hinblick auf
eine endliche Anzahl von Variablen optimiert werden kann. Angenommen die Zielfunktion
sei f (x) mit x ∈ X, dann lautet das Optimierungsproblem
(4.1)
min f (x).
x∈X
Zu beachten ist, dass Maximierung und Minimierung der Funktion nicht getrennt behandelt werden müssen, weil die Maximierung problemlos mittels einer Minimierung der
negativen Zielfunktion erreicht wird. Man erkennt natürlich sofort den Zusammenhang
mit der Nullstellensuche. An den Extrempunkten ist die Ableitung der Zielfunktion Null.
Wenn also die Ableitung bekannt ist, dann müssen lediglich deren Nullstellen gesucht und
ausgewertet werden. Nun kann es jedoch sein, dass die Funktion selbst nicht bekannt ist
und deshalb auch die Ableitung nicht verfügbar ist. Dann muss auf numerische Verfahren zurückgegriﬀen werden. Im Folgenden soll zunächst die sog. Golden Search Methode
erläutert und auch explizit das Programm dazu entwickelt werden. Anschließend wird die
Parabolische Interpolation von Brent skizziert und dessen Erweiterung auf mehrdimensionalen Variablen mittels des Powell Algorithmus.
Die nachfolgende Abbildung stellt den Verlauf der Funktion f (x) im Bereich [a; b] schematisch dar. Klar erkennbar ist, dass die Funktion mehrere lokale Maxima und Minima
hat.
Die Golden-Search-Methode geht nun ähnlich vor wie die Bisektions-Methode bei der
Suche nach einer Nullstelle. Allerdings müssen hier jeweils drei Funktionswerte verglichen
werden. Angenommen, die Werte f (a) und f (b) sind bekannt. Dann wählt die GoldenSearch-Methode zwei Variablenwerte x1 und x2 und berechnet deren Funktionswerte f (x1 )
bzw. f (x2 ). Bei einer Minimierung der Zielfunktion lautet dann die Iterationsregel:
Falls f (x1 ) < f (x2 ), dann suche weiter im Intervall [a; x2 ]. Falls jedoch umgekehrt f (x1 ) >
f (x2 ), dann suche weiter im Intervall [x1 ; b]. Es sollte klar sein, dass bei einer Maximierung
genau die entgegengesetzte Anweisung gelten muss. Das Problem ist nun jedoch, welche
konkreten Werte für x1 und x2 gewählt werden sollten. Es lässt sich zeigen, dass folgende
Vorschrift die Iterationszahl minimiert
3 − (5)
(5) − 1
α2 = 1 − α1 =
.
(4.2)
xi = a + αi (b − a)
mit α1 =
2
2
Es lohnt jetzt nicht darauf näher einzugehen, warum die Abstände genau so zu wählen
sind. Das folgende Programm zeigt die Vorgehensweise für die Funktion f (x) = x cos(x2 ).
25
BN BN B= =
N
N
>
program g o l d e n s e a r c h
use ESPlot
implicit none
real *8 , d i m e n s i o n (301)
real *8
real *8
integer
::
::
::
::
x, f
tol =1.0 d -6
a , b , x1 , x2 , alp1 , alp2 , f1 , f2
i
x =(/ (0.0 d0 +0.01* i , i =0 ,300) /)
f = x * cos ( x **2)
call plot (x , f , plotname = ’ Graph von f ’ , dataname = ’ 1 ’)
call execplot ()
a =0.0 d0
b =3.0 d0
alp1 =(3.0 d0 - sqrt (5.0 d0 ))/2.0 d0
alp2 =( sqrt (5.0 d0 ) -1.0 d0 )/2.0 d0
do while (b -a > tol )
x1 = a + alp1 *( b - a )
x2 = a + alp2 *( b - a )
f1 = x1 * cos ( x1 **2)
f2 = x2 * cos ( x2 **2)
if ( f1 < f2 ) then
26
b = x2
else
a = x1
endif
enddo
if ( f1 < f2 ) write (* ,*) x2
if ( f2 < f1 ) write (* ,*) x1
end program g o l d e n s e a r c h
Das Problem ist jedoch, dass mit dem Golden Search nur lokale Extrempunkte gefunden
werden können. Um globale Extrempunkte zu ﬁnden, muss das Ursprungsintervall [a; b]
in n Bereiche geteilt werden, für die jeweils der lokale Extrempunkt ermittelt wird. Aus
dem Vergleich der lokalen Extrempunkte ergibt sich das globale Maximum oder Minimum
(Vgl. Aufgabenblatt).
Das Golden-Search Verfahren kann problemlos auch auf Mehr-dimensionale Funktionen
übertragen werden. Dazu verwendet man das sog. Downhill Simplex Methode von Nelder
und Mead. Diese Methode ist allerdings (ebenso wie der Golden Search) nicht sehr eﬃzient,
weil die Funktionswerte zu oft ermittelt werden müssen.
Um allzu häuﬁge Funktionsberechnungen zu unterbinden, wird die Funktion mittels dreier
Punkte parabolisch interpoliert. Dann wird das Minimum/Maximum der Approximation mit der tatsächlichen Funktion ermittelt und daraus wieder eine erneute parabolische Approximation ermittelt. Dieses Verfahren wird in der Subroutine fminsearch im
module minimization angewendet:
s u b r o u t i n e f m i n s e a r c h(p , fret , minimum , maximum , minfunc )
Dabei ist p entweder ein Skalar oder ein Vektor p(1:n). fret ist ein Skalar vom Typ
real*8, dass zum Ende der Iteration den Wert der Zielfunktion am Minimum enthält.
minimum und maximum haben die selbe Dimension wie p und legen das Intervall fest, auf
dem das Minimum gesucht werden soll. Schließlich gibt minfunc die Funktion an, die
minimiert werden soll. Das System ist dabei analog zu dem des module rootfinding, d.h.
die Funktion minfunc muss außerhalb des Programms stehen und benötigt ein Interface
der Form
interface
function minfunc ( p )
implicit none
real *8 :: p (:) ! bei e i n d i m e n s i o n a l e n F u n k t i o n e n p
real *8 :: minfunc
end function minfunc
end i n t e r f a c e
Die Subroutine fminsearch kann also wie folgt verwendet werden:
program m i n i m i z a t i o n _ t e s t
use m i n i m i z a t i o n
implicit none
27
real *8
real *8
real *8
real *8
::
::
::
::
p (3)
fret
mini (3)
maxi (3)
interface
function m i n f u n c _ 3( p )
implicit none
real *8 :: p (:)
real *8 :: m i n f u n c _ 3
end function m i n f u n c _ 3
end i n t e r f a c e
p = 0.5 d0
mini = (/ -3 d0 , 0 d0 , 0 d0 /)
maxi = (/4 d0 , 12 d0 , 3 d0 /)
call f m i n s e a r c h(p , fret , mini , maxi , m i n f u n c _ 3)
write (* , ’ (4 f10 .4) ’)p , fret
end program m i n i m i z a t i o n _ t e s t
function m i n f u n c _ 3( p )
implicit none
real *8 , intent ( in ) :: p (:)
real *8 :: m i n f u n c _ 3
m i n f u n c _ 3 = ( p (1) -1 d0 )**2 + ( p (2) -4 d0 )**2 + log (( p (3) -1 d0 )**2+1 d0 )
end function m i n f u n c _ 3
28

Download Report