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.).