Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej
5 kwietnia 2009
1
M
INIMUM FUNKCJI UNIMODALNEJ
Niech oznacza pewien niepusty przedział w i niech b dzie dana funkcja
.
D
EFINICJA
. 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 .
U
WAGA
. Przypominamy, e przez
oznaczamy kul otwart o rodku w punkcie
i promieniu , przy czym w przypadku, gdy
, kul t jest przedział otwarty
.
D
EFINICJA
. Je eli
, to punkt
nazywamy
punktem lokal-
nego maksimum (
local maximum point
), a warto funkcji w tym punkcie nazywamy
mak-
simum lokalnym (
local maximum
).
Minima i maksima lokalne nazywamy
ekstremami lokalnymi (
local extremes
).
D
EFINICJA
. 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 .
D
EFINICJA
. Je eli relacja (*) spełniona jest dla ka dego
, to
nazywamy
punktem
globalnego minimum (
global minimum point
), a
nazywamy
minimum globalnym
(
global minimum
) funkcji .
D
EFINICJA
. 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
).
D
EFINICJA
. 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:
T
WIERDZENIE
. 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
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej
5 kwietnia 2009
2
,
,
.
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ł .
D
EFINICJA
. Funkcj
nazywamy
funkcj ci le wypukł (
strictly convex
function
), je eli dla dowolnych, ró nych punktów
,
.
D
EFINICJA
. 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.
T
WIERDZENIE
. 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
).
D
EFINICJA
. 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.
T
WIERDZENIE
. 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
).
D
EFINICJA
. Funkcja
nazywana jest
funkcj ci le quasi-wypukł (
strictly
quasi convex
), je eli dla dowolnych
takich, e
i dowolnego
spełniona jest nierówno
.
T
WIERDZENIE
. 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
).
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej
5 kwietnia 2009
3
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:
D
EFINICJA
. 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
).
T
WIERDZENIE
. 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.
A
LGORYTM 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.
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej
5 kwietnia 2009
4
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).
,
.
A
LGORYTM ZŁOTEGO PODZIAŁU
. Efektywno algorytmu zmniejszaj cego przedział nie-
pewno 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-
Antoni M. Zaj czkowski: Algorytmy i podstawy programowania – minimum funkcji unimodalnej
5 kwietnia 2009
5
wypukłej wg algorytmu złotego podziału. Wymagania i funkcje testowe takie same jak w po-
przednim zadaniu obliczeniowym.
L
ITERATURA
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.).