Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej 5 kwietnia 2009
MINIMUM FUNKCJI UNIMODALNEJ
Niech oznacza pewien niepusty przedział w i niech b dzie dana funkcja
.
DEFINICJA. Mówimy, e funkcja przyjmuje w punkcie minimum lokalne
( local minimum), je eli istnieje liczba
taka, e dla ka dego
prawdziwa
jest nierówno
.
(*)
Punkt
nazywamy punktem lokalnego minimum ( local minimum point) funkcji .
UWAGA. Przypominamy, e przez
oznaczamy kul otwart o rodku w punkcie
i promieniu , przy czym w przypadku, gdy
, kul t jest przedział otwarty
.
DEFINICJA. Je eli
, to punkt
nazywamy punktem lokal-
nego maksimum ( local maximum point), a warto funkcji w tym punkcie nazywamy maksimum lokalnym ( local maximum).
Minima i maksima lokalne nazywamy ekstremami lokalnymi ( local extremes).
DEFINICJA. Je eli istnieje
, takie e
and
,
to mówimy, e punkt
jest punktem cisłego minimum lokalnego ( strict local minimum point), a
jest cisłym minimum lokalnym ( strict local minimum) funkcji .
DEFINICJA. Je eli relacja (*) spełniona jest dla ka dego
, to
nazywamy punktem
globalnego minimum ( global minimum point), a nazywamy minimum globalnym
( global minimum) funkcji .
DEFINICJA. Je eli istnieje
, takie e
dla ka dego
,
przy czym
jest jednym z ko ców przedziału , to mówimy, e w tym punkcie funkcja osi ga minimum brzegowe ( boundary minimum).
DEFINICJA. Funkcj
nazywamy funkcj wypukł ( convex function), je eli dla dowolnych punktów
,
wykresu tej funkcji, ci ciwa ( chord)
le y nad t cz ci wykresu, któr okre la przedział wyznaczony przez punkty
.
Zapisujemy to wzorem
,
.
Podstawowe własno ci funkcji wypukłych opisuje nast puj ce:
TWIERDZENIE. Na to, aby funkcja
była wypukła potrzeba i wystarcza, aby
miała nast puj ce własno ci:
1. Funkcja jest ci gła we wn trzu
przedziału i ponadto, gdy przedział jest pół-
otwarty, albo domkni ty, wtedy w odpowiednim ko cu
przedziału funkcja spełnia
warunek
.
2. W ka dym punkcie
funkcja ma pochodn lewostronn
i prawostronn
i pochodne te s równe, z wyj tkiem by mo e przeliczalnej liczby punktów z
, przy czym spełnione s nierówno ci
1
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej 5 kwietnia 2009
,
,
.
St d w szczególno ci wynika, e je eli jest ró niczkowalna, to jest wypukła wtedy i tylko wtedy, gdy
jest funkcj rosn c oraz, je eli jest dwukrotnie ró niczkowalna, to jest wypukła wtedy i tylko wtedy, gdy
jest nieujemna.
Dowód: (Schwartz, 1979, 208).
Zadanie. Pokaza , e funkcja
jest funkcj wypukł .
DEFINICJA. Funkcj
nazywamy funkcj ci le wypukł ( strictly convex
function), je eli dla dowolnych, ró nych punktów
,
.
DEFINICJA. Funkcja
jest nazywana funkcj wkl sł ( concave function), je eli funkcja
jest wypukła. Funkcj nazywamy ci le wkl sł ( strictly concave), je eli funkcja
jest ci le wypukła.
TWIERDZENIE. Niech
b dzie punktem lokalnego minimum funkcji
. Je-
eli jest funkcj wypukł , to
jest punktem globalnego minimum tej funkcji, a je eli
funkcja jest funkcj ci le wypukł , to
jest jedynym punktem globalnego minimum tej
funkcji.
Dowód: (Bazarra, Shetty, 1982, 107).
Poj cie funkcji wypukłej (wkl słej) mo na uogólni w ró ny sposób (Bazarra, Shetty, 1982). Jednym z uogólnie , które jest wa ne przy projektowaniu algorytmów znajduj cych minimum funkcji rzeczywistej w danym przedziale sko czonym jest poj cie funkcji quasi-wypukłych ( quasi convex functions).
DEFINICJA. Funkcj
nazywamy quasi-wypukł , je eli dla dowolnych
i
spełniona jest nierówno
.
Przykład (Canon, Cullum, Polak, 1970, 253). Funkcja
jest quasi-
wypukła, ale nie jest wypukła.
TWIERDZENIE. Funkcja
jest funkcj quasi-wypukł wtedy i tylko wtedy, gdy
zbiór
jest zbiorem wypukłym albo pustym dla dowolnego
.
Dowód: (Bazarra, Shetty, 1982, 107).
DEFINICJA. Funkcja
nazywana jest funkcj ci le quasi-wypukł ( strictly quasi convex), je eli dla dowolnych
takich, e
i dowolnego
spełniona jest nierówno
.
TWIERDZENIE. Niech
b dzie funkcj ci le quasi-wypukł . Je eli punkt
jest punktem lokalnego minimum funkcji , to jest on tak e punktem globalnego minimum tej funkcji.
Dowód: (Bazarra, Shetty, 1982, 117).
2
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej 5 kwietnia 2009
Nale y tu doda , e poj cie funkcji ci le quasi-wypukłej jest równowa ne (Bazarra, Shetty, 1982) poj ciu funkcji unimodalnej ( unimodal function), której definicja jest nast pu-j ca:
DEFINICJA. Funkcj nazywamy funkcj unimodaln w przedziale
, je eli
istnieje w tym przedziale punkt
, w którym funkcja osi ga minimum na
oraz dla
takich, e
,
i
spełnione s warunki
, gdy
i
, gdy
.
Dalej interesowa nas b dzie problem algorytmicznego wyznaczenia minimum funkcji ci-le quasi-wypukłej w przedziale domkni tym
. Je eli znajdziemy punkt mini-
mum lokalnego tej funkcji, to zgodnie z odpowiednim twierdzeniem, podanym wy ej, b dzie to jednocze nie punkt minimum globalnego rozwa anej funkcji.
Niech b dzie dana funkcja
, przy czym zakładamy, e nie znamy punktu
minimum lokalnego tej funkcji w przedziale
, o ile taki punkt istnieje. W takim przy-
padku przedział
nazywamy przedziałem niepewno ci ( uncertainty interval).
TWIERDZENIE. Niech
b dzie funkcj ci le quasi-wypukł i niech
i
.
1. Je eli
, to
.
2. Je eli
, to
.
Dowód: Pierwsza teza. Przypu my, e
. Poniewa mo na przedstawi jako
kombinacj wypukł punktów i , a jest funkcj ci le quasi-wypukł , to
, co jest sprzeczne z zało eniem.
Podobnie mo na wykaza drug tez .
Z podanego twierdzenia wynika, e je eli funkcja jest ci le quasi-wypukła, to mo na zmniejszy przedział niepewno ci w nast puj cy sposób:
Je eli
, to nowym przedziałem niepewno ci jest
, a w przeciwnym przy-
padku
.
Pozostało jeszcze podanie sposobów, czyli algorytmów zmniejszania przedziału niepewno-ci.
ALGORYTM DWUDZIELNY (DYCHOTOMICZNY). Pomysł polega na podzieleniu pocz tko-wego przedziału niepewno ci
na pół, przy czym, aby dosta
przyjmujemy
i kładziemy
i
.
Mo na teraz sformułowa algorytm dwudzielny.
Inicjacja – krok pocz tkowy.
Niech
b dzie pocz tkowym przedziałem niepewno ci. Przyj numer iteracji
,
i minimaln , dopuszczaln długo
przedziału niepewno ci.
Krok podstawowy.
1. Je eli
, to koniec. Punkt minimum funkcji nale y do przedziału
.
Mo na przyj
i
.
W przeciwnym przypadku wyznaczy
,
i przej do punktu 2.
3
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej 5 kwietnia 2009
2. Je eli
, to podstawi
,
,
w przeciwnym przypadku podstawi
,
.
Zwi kszy o i wróci do punktu 1.
Zadanie. Pokaza , e długo przedziału
dana jest wzorem
.
Zadanie obliczeniowe 1. Napisa , uruchomi i przetestowa program w j zyku Ada wyznaczaj cy w sposób przybli ony punkt minimum i warto minimum funkcji ci le quasi-wypukłej wg algorytmu dwudzielnego. Program powinien te wyznaczy liczb oblicze funkcji oraz prezentowa dane wej ciowe i histori przedziałów niepewno ci. Zwróci uwag na to, e długo ko cowego przedziału niepewno ci nie mo e by wi ksza od pocz tkowej długo ci tego przedziału. Nie wolno stosowa instrukcji goto. Funkcje testowe: a).
,
,
b).
,
,
c).
,
.
ALGORYTM ZŁOTEGO PODZIAŁU. Efektywno algorytmu zmniejszaj cego przedział niepewno ci zale y od współczynnika zw enia tego przedziału. Bardziej efektywn metod zw ania przedziału niepewno ci ni stosowana w algorytmie dwudzielnym jest nast puj ca metoda złotego podziału:
Inicjacja – krok pocz tkowy.
Niech
b dzie pocz tkowym przedziałem niepewno ci. Przyj numer iteracji
,
minimaln , dopuszczaln długo
przedziału niepewno ci oraz
,
,
przy czym
oznacza współczynnik złotego podziału.
Obliczy
,
i przej do kroku podstawowego.
Krok podstawowy.
1. Je eli
, to koniec. Punkt minimum funkcji nale y do przedziału
.
Mo na przyj
i
.
W przeciwnym przypadku je eli
, to przej do punktu 2., a je eli
, to przej do punktu 3.
2. Podstawi
,
,
,
,
Obliczy
i przej do punktu 4.
3. Podstawi
,
,
,
,
Obliczy
i przej do punktu 4.
4. Zwi kszy o i wróci do punktu 1.
Zadanie obliczeniowe 2. Napisa , uruchomi i przetestowa program w j zyku Ada wyznaczaj cy w sposób przybli ony punkt minimum i warto minimum funkcji ci le quasi-4
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej 5 kwietnia 2009
wypukłej wg algorytmu złotego podziału. Wymagania i funkcje testowe takie same jak w po-przednim zadaniu obliczeniowym.
LITERATURA
Bazarra, M.S. i C.M. Shetty. (1982). Nieliniejnoje programirowanije. Tieorija i algoritmy.
Mir, Moskwa (tłum. z ang.).
Canon, M.D., C.D. Cullum, E. Polak. (1970). Theory of optimal control and mathematical programming. McGraw-Hill, New York.
Findeisen, W., J. Szymanowski, A. Wierzbicki. (1980). Teoria i metody obliczeniowe optymalizacji. PWN, Warszawa, wyd. II.
Luenberger, D.G. (1973). Introduction to linear and nonlinear programming. Addison-Wesley, Reading, Mass.
Ławrynowicz, J. (1977). Rachunek wariacyjny ze wst pem do programowania matematycznego. WNT, Warszawa.
Schwartz, L. (1979). Kurs analizy matematycznej. Tom I. PWN, Warszawa (tłum. z franc.).
5