2008-03-05

Szczecin

1

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Zadanie minimalizacji funkcji jednej zmiennej f(x) na zbiorze X,
który jest dowolnym podzbiorem jednowymiarowej przestrzeni

euklidesowej E

1

:

min

x

∈ X ⊂ E

1

f

x

2008-03-05

Szczecin

2

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Definicja
Punkt x* jest punktem, w którym funkcja f(x) osiąga minimum

globalne na zbiorze X, jeśli:

dla wszystkich

x

∗

∈ X i

f

x

∗

 f  x

x

∈ X

2008-03-05

Szczecin

3

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

2008-03-05

Szczecin

4

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Definicja
Punkt x* jest punktem właściwego minimum globalnego

funkcji f(x) na zbiorze X, jeśli:

dla wszystkich

x

∗

∈ X i

f

x

∗

 f  x

x

∈ X , x≠x

∗

2008-03-05

Szczecin

5

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

2008-03-05

Szczecin

6

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Definicja
Punkt jest punktem, w którym funkcja f(x) osiąga

minimum lokalne na zbiorze X, jeśli przy dowolnym

wystarczająco małym

ε

> 0 dla wszystkich

spełniających warunek

spełniona jest nierówność

x

∗

∈ X

x

≠x

∗

, x

∈ X

∣x−x

∗

∣

f

x

∗

 f x

2008-03-05

Szczecin

7

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Definicja

Funkcję f(x) nazywa się unimodalną na odcinku [a,b], jeśli jest

ona monotoniczna z obydwu stron od jedynego, na
rozpatrywanym

przedziale,

punktu

ekstremum

x*.

2008-03-05

Szczecin

8

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Problem istnienia rozwiązania zadania minimalizacji -
przykład

f

x=e

−x

, X

=

{

x : x

a

}

2008-03-05

Szczecin

9

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Twierdzenie Weierstrassa
Funkcja ciągła określona na niepustym, domkniętym i
ograniczonym zbiorze osiąga minimum (maksimum) w co

najmniej jednym punkcie tego zbioru.

2008-03-05

Szczecin

10

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Aby punkt x* był punktem lokalnego minimum dwukrotnie
różniczkowalnej funkcji f(x) na otwartym przedziale (a,b),
konieczne jest spełnienie następujących warunków:

{

df

dx

∣

x

=x

∗

=0

d

2

f

dx

2

∣

x

=x

∗

0

warunek konieczny I rzędu

warunek konieczny II rzędu

2008-03-05

Szczecin

11

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Przykład

Niech f(x)=x

3

. Wówczas punkt x*=0 spełnia konieczne warunki

minimum.

{

df

dx

∣

x

=0

=3 x

2

∣

x

=0

=0

d

2

f

dx

2

∣

x

=0

=6 x

∣

x

=0

=0

Punkt x=0 jest punktem przegięcia,

nie zaś punktem minimum funkcji.

- 2

- 1

0

1

2

- 8

- 6

- 4

- 2

0

2

4

6

8

2008-03-05

Szczecin

12

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Definicja

Punkt x*, w którym spełniony jest warunek

nazywa się punktem stacjonarnym funkcji f(x).

df

dx

∣

x

=x

∗

=0

2008-03-05

Szczecin

13

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Niech w punkcie x=x* pochodne funkcji f(x) do rzędu(n-1)

włącznie przyjmują wartość zero, natomiast pochodna rzędu
(n) jest różna od zera. Wówczas następujące warunki są
wystarczającymi warunkami istnienia ekstremum:

1. jeśli n jest liczbą nieparzystą to x* jest punktem przegięcia,
2. jeśli n jest liczbą parzystą to x* jest punktem ekstremum

lokalnego

d

n

f

dx

n

∣

x

=x

∗

0  minimum

d

n

f

dx

n

∣

x

=x

∗

0  maximum

2008-03-05

Szczecin

14

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

df

dx

∣

x

=0

=

d

2

f

dx

2

∣

x

=0

=0

Ponieważ rząd pierwszej różnej się od zera pochodnej
wynosi 3 (liczba nieparzysta), to zgodnie z warunkiem

wystarczającym punkt x*=0 jest punktem przegięcia.

Przykład

f(x)=x

3

d

3

f

dx

3

∣

x

=0

=6

2008-03-05

Szczecin

15

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej

Algorytmy zerowego rzędu:

metoda połowienia,

metoda oparta na liczbach Fibonacciego,

metoda złotego podziału,

aproksymacja kwadratowa.

Algorytmy pierwszego rzędu:

aproksymacja sześcienna,

algorytm stycznych,

algorytm siecznych.

Algorytm drugiego rzędu:

algorytm Newtona.

2008-03-05

Szczecin

16

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda połowienia

x

m

f(x

m

)

x

1

x

2

f(x

1

)

f(x

2

)

x

m

=

ab

2

x

1

=a0.25⋅L

x

2

=b−0.25⋅L

L

=b−a

L

a

b

f(a)

f(b)

X

f(x)

Krok 0

2008-03-05

Szczecin

17

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda połowienia

x

m

f(x

m

)

a

b

f(a)

f(b)

L

X

f(x)

Krok 1

x

1

f(x

1

)

x

2

f(x

2

)

x

1

=a0.25⋅L

x

2

=b−0.25⋅L

L

=b−a

2008-03-05

Szczecin

18

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda połowienia - przykład

Znajdz minimum funkcji f

 x=5 x

2

−12 x−3, w przedziale 0,2 .

Krok 0

x

m0

=

a

0

b

0



2

=

0

2

2

=1,

f

1=−10

x

10

=a

0

0.25⋅L

0

=00.25⋅2=0.5 , f 0.5=−7.75

x

20

=b

0

−0.25⋅L

0

=2−0.25⋅2=1.5 , f 1.5=−9.75

L

0

=b

0

−a

0

=2−0=2

a

x

10

x

m0

x

20

b

0

a

0

a

0

=0,

f

0=−3

b

0

=2,

f

2=−7

Krok 1

x

11

=a

1

0.25⋅L

1

=0.75 , f 0.75=−9.1875

L

1

=b

1

−a

1

=1.5−0.5=1

a

1

=x

10

=0.5

b

1

=x

20

=1.5

x

21

=b

1

−0.25⋅L

1

=1.25 , f 1.25=−10.1875

x

m1

=x

m0

=1

a

x

11

x

m1

x

21

b

1

a

1

2008-03-05

Szczecin

19

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda połowienia - przykład

Znajdz minimum funkcji f

 x=5 x

2

−12 x−3, w przedziale 0,2 .

Krok 1

x

11

=a

1

0.25⋅L

1

=0.75 , f 0.75=−9.1875

L

1

=b

1

−a

1

=1.5−0.5=1

a

1

=x

10

=0.5

b

1

=x

20

=1.5

x

21

=b

1

−0.25⋅L

1

=1.25 , f 1.25=−10.1875

x

m1

=x

m0

=1

a

x

11

x

m1

x

21

b

1

a

1

Krok 2

x

12

=

L

2

=b

2

−a

2

=0.5

a

2

=x

m1

=1

b

2

=b

1

=1.5

x

22

=

x

m2

=x

21

=1.25

2008-03-05

Szczecin

20

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda złotego podziału

Idea złotego podziału odcinka

A

C

B

a

β

b

C

α

B

A

=

C

B

gdzie:

C

=A−B

B

A

=



5

−1

2

≈0.618

2008-03-05

Szczecin

21

Metody optymalizacji, Informatyka

α

β

=b−0.618⋅L

=a0.618⋅L

L

=b−a

L

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda złotego podziału

a

b

X

f(x)

f(b)

f(a)

f(

α

)

f(

β

)

f(

α1

)

α1 β1

b1

L1

a1

Krok 0

1=

1=b1−0.618⋅L1

a 1

=a

Krok 1

b 1

=

L1

=b1−a1

2008-03-05

Szczecin

22

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda złotego podziału - przykład

Znajdz minimum funkcji f

 x=5 x

2

−12 x−3, w przedziale 0,2 .

Krok 0

L

0

=b

0

−a

0

=2−0=2

a

α

0

β

0

b

0

a

0

a

0

=0,

f

0=−3

b

0

=2,

f

2=−7

Krok 1



0

=b

0

−0.618⋅L

0

=0.764 , f 0.764=−9.2495



0

=a

0

0.618⋅L

0

=1.236 , f 1.236=−10.1935

L

1

=b

1

−a

1

=1.236

a

1

=

0

=0.764 ,

b

1

=b

0

=2



1

=

0

=1.236



1

=a

1

0.618⋅L

1

=1.5278 , f 1.5278=−9.6626

a

α

1

β

1

b

1

a

1

2008-03-05

Szczecin

23

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda połowienia - przykład

Znajdz minimum funkcji f

 x=5 x

2

−12 x−3, w przedziale 0,2 .

Krok 1

Krok 2

L

1

=b

1

−a

1

=1.236

a

1

=

0

=0.764 ,

b

1

=b

0

=2



1

=

0

=1.236



1

=a

1

0.618⋅L

1

=1.5278 , f 1.5278=−9.6626

a

α

1

β

1

b

1

a

1

L

2

=b

2

−a

2

=0.764

a

2

=

1

=1.236 ,

b

2

=b

1

=2



2

=

1

=1.5278



2

=a

2

0.618⋅L

2

=1.7082 , f 1.7082=−8.909

a

α

2

β

2

b

2

a

2

2008-03-05

Szczecin

24

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Aproksymacja kwadratowa funkcji – algorytm Powella

x

1

x

2

x

3

Krok 0

x

2

=x

2

−x

1

=x

3

−x

2

x

m

f(x

m

)

f(x

2

)

x

1

x

3

X

f(x)

f(x

3

)

f(x

1

)

x

m

=x

2

−0.5⋅

f

 x

3

− f x

1



f

 x

1

−2 f  x

2

 f x

3



∆

2008-03-05

Szczecin

25

Metody optymalizacji, Informatyka

x

1

x

3

∆

X

f(x)

Krok 1

f(x

3

)

x

2

x

m

f(x

m

)

f(x

2

)

f(x

1

)

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Aproksymacja kwadratowa funkcji – algorytm Powella

x

1

x

2

x

3

=x

2

−x

1

=x

3

−x

2

x

m

=x

2

−0.5⋅

f

 x

3

− f x

1



f

 x

1

−2 f  x

2

 f x

3



2008-03-05

Szczecin

26

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Aproksymacja kwadratowa - przykład

Znajdz minimum funkcji f

 x=5 x

2

−12 x−3, w przedziale 0,2 .

Krok 0

x

20

=

x

10

x

30



2

=1,

f

1=−10

x

10

=0,

f

0=−3

x

30

=2,

f

2=−7

Krok 1

x

m0

=1.2 ,

f

1.2=−10.2

x

21

=x

m0

=1.2 ,

f

1.2=−10.2

x

11

=x

21

−

1

=0.7 ,

f

0.7=−8.95

x

31

=x

22



1

=1.7 ,

f

1.7=−8.95

x

m1

=1.2 ,

f

1.2=−10.2



0

=x

20

−x

10

=1



1

=



0

2

=0.5

2008-03-05

Szczecin

27

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy pierwszego rzędu

Aproksymacja sześcienna funkcji – algorytm Davidona

a

b

f '

a 0, f ' b0

X

f(x)

Krok 0

f(b)

x

m

f(x

m

)

f(a)

x

m

=b−

f '

bQ−Z

f '

b− f ' a2 Q

b−a

Q

=



Z

2

− f ' a⋅f ' b

Z

=

3

[ f a− f b]

b

−a

 f ' a f ' b

2008-03-05

Szczecin

28

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy pierwszego rzędu

Aproksymacja sześcienna funkcji – algorytm Davidona

a

X

f(x)

Krok 1

b

f(x

m

)

f(a)

x

m

f(b)

f '

a 0, f ' b0

x

m

=b−

f '

bQ−Z

f '

b− f ' a2 Q

b−a

Q

=



Z

2

− f ' a⋅f ' b

Z

=

3

[ f a− f b]

b

−a

 f ' a f ' b

2008-03-05

Szczecin

29

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Aproksymacja sześcienna - przykład

Znajdz minimum funkcji f

 x=5 x

2

−12 x−3, w przedziale 0,2 .

Krok 0

f '

 x=10 x−12

x

m

=b−

f '

bQ−Z

f '

b− f ' a2 Q

b−a=1.2 , f 1.2=−10.2

Q

=



Z

2

− f ' a⋅f ' b=10

Z

=

3

[ f a− f b]

b

−a

 f ' a f ' b=2

a

0

=0,

f

0=−3,

f '

0=−12

b

0

=2,

f

2=−7,

f '

2=8

f '

a 0, f ' b0

f '

1.2=0

2008-03-05

Szczecin

30

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy drugiego rzędu

algorytm Newtona

x

0

X

f(x)

f(x

0

)

x

1

f(x

1

)

x

2

f(x

2

)

x

n

1

=x

n

−

f '

 x

n



f ' '

 x

n



2008-03-05

Szczecin

31

Metody optymalizacji, Informatyka

Ekstremum funkcji jednej zmiennej - algorytmy zerowego rzędu

Metoda Newtona - przykład

Znajdz minimum funkcji f

 x=5 x

2

−12 x−3, w przedziale 0,2 .

Krok 0

f '

 x=10 x−12,

f ' '

x=10

a

=0,

f

0=−3,

f '

0=−12,

f ' '

0=10

b

=2,

f

2=−7,

f '

2=8,

f ' '

2=10

x

1

=x

0

−

f '

 x

0



f ' '

 x

0



=0−−

12

10

=1.2 ,

f

1.2=−10.2

x

0

=a

x

0

=b

x

1

=x

0

−

f '

 x

0



f ' '

 x

0



=2−

8

10

=1.2 ,

f

1.2=−10.2