2008-03-05

Szczecin

1

Metody optymalizacji, Informatyka

Jeśli funkcja jest ciągła i różniczkowalna względem wszystkich

zmiennych, to istnieje gradient tej funkcji

Ekstremum funkcji wielu zmiennych

∇ f x=

[

∂ f

∂ x

1

∂ f

∂ x

2

⋯ ∂

f

∂ x

n

]

T

zwrócony w kierunku najszybszego wzrostu wartości funkcji,

ortogonalny do linii poziomu przebiegającej przez dany zadany punkt

2008-03-05

Szczecin

2

Metody optymalizacji, Informatyka

Ekstremum funkcji wielu zmiennych

Y

X

f(x,y)=const

x

k

∇ f x

k



∇ f x=

[

∂ f

∂ x

1

∂ f

∂ x

2

⋯ ∂

f

∂ x

n

]

T

x

min

−∇ f x

k



∇ f x=∇

∇ f x

k

=∇

k

2008-03-05

Szczecin

3

Metody optymalizacji, Informatyka

f

x= f x

k

∇

k

T

x−x

k



1
2

x−x

k



T

H

k

x−x

k



Rozkład w szereg Taylora funkcji wielu zmiennych

Ekstremum funkcji wielu zmiennych

H

=

[

∂

2

f

x

∂ x

1

2

∂

2

f

x

∂ x

1

∂ x

2

⋯ ∂

2

f

x

∂ x

1

∂ x

n

∂

2

f

x

∂ x

2

∂ x

1

∂

2

f

x

∂ x

2

2

⋯ ∂

2

f

x

∂ x

2

∂ x

n

⋮

⋮

⋮

⋮

∂

2

f

x

∂ x

n

∂ x

1

∂

2

f

x

∂ x

n

∂ x

2

⋯ ∂

2

f

x

∂ x

n

2

]

H

x=H

H

x

k

=H

k

x=



x

1

x

2

⋮

x

n



H – macierz Hesse'go

2008-03-05

Szczecin

4

Metody optymalizacji, Informatyka

Ekstremum funkcji wielu zmiennych

Rozłożyć w szereg Taylora funkcję

f

x= f  x

1,

x

2

=x

1

3

2x

2

2

3x

1

x

2

x

k

=

[

1
1

]

w otoczeniu punktu

∇=

[

3x

1

2

3x

2

4x

2

3x

1

]

H

=

[

6x

1

3

3

4

]

f

 x=6

[

6 7

]

[

x

1

−1

x

2

−1

]



1
2

[

x

1

−1 x

2

−1

]

[

6 3
3 4

]

[

x

1

−1

x

2

−1

]

f

x=3x

1

2

2x

2

2

3 x

1

x

2

−3 x

1

1

f

x= f x

k

∇

k

T

x−x

k



1
2

x−x

k



T

H

k

x−x

k



2008-03-05

Szczecin

5

Metody optymalizacji, Informatyka

Ekstremum funkcji wielu zmiennych

Aby w punkcie x* funkcja f(x

1

,x

2

,...,x

n

) miała bezwarunkowe

ekstremum lokalne konieczne jest zerowanie się jej

pierwszych pochodnych cząstkowych, względem każdej ze

zmiennych:

∂ f x

∂ x

j

∣

x

= x

∗

=0,

j

=1,2 , , n

albo

∇ f  x

∗

=0

2008-03-05

Szczecin

6

Metody optymalizacji, Informatyka

Ekstremum funkcji wielu zmiennych

Aby mająca ciągłe pochodne cząstkowe do drugiego rzędu
włącznie funkcja n zmiennych f(x) miała w stacjonarnym

punkcie x* bezwarunkowe minimum lokalne konieczne jest

aby macierz jej drugich pochodnych była w tym punkcie

dodatnio półokreślona:

H

 x

j

0, j=1,2 , , n

2008-03-05

Szczecin

7

Metody optymalizacji, Informatyka

Ekstremum funkcji wielu zmiennych

Warunki konieczne ekstremum funkcji wielu zmiennych

{

∇ f  x

∗

=0

H

 x

j

0, j=1,2 ,, n

H

=

[

∂

2

f

x

∂ x

1

2

∂

2

f

x

∂ x

1

∂ x

2

⋯ ∂

2

f

x

∂ x

1

∂ x

n

∂

2

f

x

∂ x

2

∂ x

1

∂

2

f

x

∂ x

2

2

⋯ ∂

2

f

x

∂ x

2

∂ x

n

⋮

⋮

⋮

⋮

∂

2

f

x

∂ x

n

∂ x

1

∂

2

f

x

∂ x

n

∂ x

2

⋯ ∂

2

f

x

∂ x

n

2

]

∇ f x=

[

∂ f

∂ x

1

∂ f

∂ x

2

⋯ ∂

f

∂ x

n

]

T

2008-03-05

Szczecin

8

Metody optymalizacji, Informatyka

Ekstremum funkcji wielu zmiennych

Aby mająca ciągłe pochodne cząstkowe do drugiego rzędu
włącznie funkcja n zmiennych F(x) miała w stacjonarnym

punkcie x* bezwarunkowe minimum lokalne wystarczające

jest aby macierz jej drugich pochodnych była w tym punkcie

dodatnio określona:

H

 x

j

0, j=1,2 , , n

2008-03-05

Szczecin

9

Metody optymalizacji, Informatyka

Metody poszukiwania ekstremum funkcji

wielu zmiennych

Metody bezgradientowe

metoda spadku względem współrzędnych,

metoda Gaussa-Seidla,

metoda Powella,

metoda Daviesa-Swanna i Campeya,

metoda Zangwilla,

metoda Rosenbrocka

Ekstremum funkcji wielu zmiennych – metody bezgradientowe

2008-03-05

Szczecin

10

Metody optymalizacji, Informatyka

Wersor

Wersor (wektor jednostkowy) – wektor którego długość wynosi 1.

1

1

-1

-1

x

y

e

1

e

2

e

3

e

4

e

=

{

e

1,

e

2,

e

3,

e

4

}

=

{



1
0



,



0
1



,



−1

0



,



0

−1



}

2008-03-05

Szczecin

11

Metody optymalizacji, Informatyka

Wersor

Jak z dowolnego wektora zrobić wersor kierunkowy?

-1

x

y

-3

2

1

d

P

0

=



−3,0



P

1

=



1,2





V

=



1

−−3

2

−0



=



4
2



∣

V

∣=



4

2

2

2

=



20

=2



5

d

=



V

∣



V

∣

=



4
2



2



5

=



2



5

1



5



2008-03-05

Szczecin

12

Metody optymalizacji, Informatyka

[x

10

,x

20

]

Metody bezgradientowe – spadek względem współrzędnych

[x

1m

,x

2m

]

k – numer iteracji k=0,1,2...
e – wersor kierunkowy

α

– długość kroku

j – numer wersora kierunkowego

x

(j)k+1

=x

k

+

α

e

(j)

2008-03-05

Szczecin

13

Metody optymalizacji, Informatyka

Minimalizacja funkcji w zadanym kierunku poszukiwań

X

Y

(x

0

,y

0

)

(x

1

,y

1

)

d

X

Y

Z

(x

0

,y

0

)

(x

1

,y

1

)

d

=



d

x

d

y



2008-03-05

Szczecin

14

Metody optymalizacji, Informatyka

Minimalizacja funkcji w zadanym kierunku poszukiwań



x

1

y

1



=



x

0

y

0



⋅d

d

=



d

x

d

y



−krok

F

x

0

 d

x

, y

0

 d

y

  F 

2008-03-05

Szczecin

15

Metody optymalizacji, Informatyka

Minimalizacja funkcji w zadanym kierunku poszukiwań

Metody bezgradientowe – metoda Gaussa-Seidla

2008-03-05

Szczecin

16

Metody optymalizacji, Informatyka

[x

m

,y

m

]

[x

0

,y

0

]

Metody bezgradientowe – metoda Gaussa-Seidla

k – numer iteracji k=0,1,2...
e – wersor kierunkowy

α

– długość kroku

j – numer wersora kierunkowego

x

(j)k+1

=x

k

+

α

e

(j)

2008-03-05

Szczecin

17

Metody optymalizacji, Informatyka

Metody bezgradientowe – metoda Gaussa-Seidla – przykład



x

1

y

1



=



x

0

y

0



⋅d

1

=



−3

3



⋅



1
0



=



−3

3





x

0

y

0



=



−3

3



f

x , y=2 x

2

 y

2

d

1

=e

1

=



1
0



d

2

=e

2

=



0
1



Krok 1 – Minimalizacja w kierunku d

1

f

−3 ,3=2−3

2

3

2

=2 

2

−1227= f 

min f

 

∂ f 

∂

=4 −12=0  =3



x

1

y

1



=



−3

3



=



0
3



f

0,3=9

2008-03-05

Szczecin

18

Metody optymalizacji, Informatyka

Metody bezgradientowe – metoda Gaussa-Seidla – przykład



x

2

y

2



=



x

1

y

1



⋅d

2

=



0
3



⋅



0
1



=



0

3







x

0

y

0



=



−3

3



f

x , y=2 x

2

 y

2

d

1

=e

1

=



1
0



d

2

=e

2

=



0
1



Krok 2 – Minimalizacja w kierunku d

2

f

0,3=

2

6 9= f 

min f

 

∂ f 

∂

=2 6=0  =−3



x

2

y

2



=



0

3





=



0
0



f

0,0=0

2008-03-05

Szczecin

19

Metody optymalizacji, Informatyka

Metody poszukiwania ekstremum funkcji

wielu zmiennych

Ekstremum funkcji wielu zmiennych – metody gradientowe

Metody gradientowe

metoda gradientu prostego,

metoda najszybszego spadku,

metoda gradientu sprzężonego,

metoda Newtona

2008-03-05

Szczecin

20

Metody optymalizacji, Informatyka

Metody gradientowe – gradient prosty

Y

X

F(x,y)=const

x

0

x

min

x

k

1

= x

k

−

k

∇

k

k – numer iteracji k=0,1,2...

α

κ

– długość w danym kroku



k

=



∥∇

k

∥

λ

κ

– stała długość w danym kroku

x

1

x

2

x

3

x

4

2008-03-05

Szczecin

21

Metody optymalizacji, Informatyka

Metody gradientowe – gradient prosty

x

k

1

= x

k

−

k

∇

k

k – numer iteracji k=0,1,2...

α

κ

– długość w danym kroku



k

=



∥∇

k

∥

λ

κ

– stała długość w danym kroku

∣∣∇∣∣−norma euklidesowa wektora

∣∣∇∣∣=



∇

T

⋅∇=



∑

j

=1

n

∇

j

2

2008-03-05

Szczecin

22

Metody optymalizacji, Informatyka

Metody gradientowe – metoda najszybszego spadku

Y

X

F(x,y)=const

x

0

x

k

1

= x

k

−

k

∇

k



k

=

∇

k

T

∇

k

∇

k

T

H

k

∇

k

x

1

x

2

x

3

x

4

x

min

2008-03-05

Szczecin

23

Metody optymalizacji, Informatyka

Metody gradientowe – metoda najszybszego spadku

Wersja 1

x

k

1

= x

k

−

k

∇

k



k

=

∇

k

T

∇

k

∇

k

T

H

k

∇

k

Wersja 2

F

 x

k

 d

k



Minimalizujemy funkcję

w zadanym kierunku

d

k

d

k

=

∇

k

∣∇

k

∣

przyjmując

2008-03-05

Szczecin

24

Metody optymalizacji, Informatyka

Metody gradientowe – metoda Newtona

x

k

1

= x

k

−

k

∇

k



k

= H

k

−1

Wersja 1

Wersja 2

F

 x

k

 d

k



Minimalizujemy funkcję

w zadanym kierunku

d

k

d

k

=

H

k

−1

∇

k

∣H

k

−1

∇

k

∣

przyjmując