Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Kategorie klasyfikacji zadań optymalizacji

Model procesu:

Statyczny

Dynamiczny

Model procesu bez ograniczeń

Model procesu z ograniczeniami

Przestrzeń rozwiązań zmiennych decyzyjnych

Zmienne rzeczywiste

Zmienne całkowitoliczbowe

Zmienne binarne

Zmienne mieszane

Postać funkcji celu:

Funkcja skalarna

Funkcja wektorowa

Dane o procesie niezbędne w algorytmie optymalizacji

Wartości funkcji celu

Gradient funkcji – algorytm pierwszego rzędu

Hesjan funkcji - algorytm drugiego rzędu

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Właściwe minimum lokalne:

Funkcja f(x) ma w punkcie

Funkcja f(x) ma w punkcie

w

w

ł

ł

a

a

ś

ś

ciwe minimum lokalne, je

ciwe minimum lokalne, je

ż

ż

eli istnieje

eli istnieje

takie,

takie,

ż

ż

e:

e:

0

>

δ

E

x ∈

∀

( ) ( )

x

f

x

f

<

)

przy czym

przy czym

:

:

∆

∩

= X

E

{

}

δ

<

−

<

=

∆

x

x

x

)

0

:

Słabe minimum lokalne

Funkcja f(x) ma w punkcie

Funkcja f(x) ma w punkcie

s

s

ł

ł

abe

abe

minimum lokalne, je

minimum lokalne, je

ż

ż

eli istnieje

eli istnieje

takie,

takie,

ż

ż

e

e

0

>

l

δ

l

E

x ∈

∀

( ) ( )

l

x

f

x

f

)

) ≤

przy czym

przy czym

:

:

l

l

X

E

∆

∩

=

{

}

l

l

x

x

x

δ

<

−

<

=

∆

)

0

:

∧

x

∧

x

∧

x

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Każde minimum globalne jest minimum lokalnym, lecz nie na odwrót.

•

Zadanie optymalizacji bez ograniczeń dla

• Zadanie optymalizacji z ograniczeniami:

Zadanie programowania liniowego ZPL

Zadanie programowania nieliniowego ZPN

( )













=

∧

∈

x

x

x

f

f

X

min

n

R

X =

( )













=

∧

∈

x

x

x

f

f

X

min

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Twierdzenie Weierstrass’a

Funkcja f(x) ciągła na zwartym zbiorze rozwiązań dopuszczalnych [zbiorze
ograniczonym i domkniętym]

jest na tym zbiorze ograniczona i osiąga swe kresy tzn.: istnieją punkty

takie, że dla każdego

zachodzi

:

:

X

x

x

∈

2

1

,

X

x ∈

)

(

)

(

)

(

2

1

x

f

x

f

x

f

≤

≤

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Własności funkcji wypukłych

Definicja zbioru wypuk

Definicja zbioru wypuk

ł

ł

ego:

ego:

Zbi

Zbi

ó

ó

r

r

nazywamy wypuk

nazywamy wypuk

ł

ł

ym, je

ym, je

ż

ż

eli dla ka

eli dla ka

ż

ż

dych dw

dych dw

ó

ó

ch punkt

ch punkt

ó

ó

w

w

odcinek

odcinek

łą

łą

cz

cz

ą

ą

cy te dwa punkty tak

cy te dwa punkty tak

ż

ż

e nale

e nale

ż

ż

y do X tzn.:

y do X tzn.:

n

R

X ⊂

X

x

x

∈

2

1

,

(

)

{

}

1

0

,

1

:

2

1

≤

≤

−

+

=

=

λ

λ

λ

x

x

x

x

X

Definicja funkcji wypukłej:

Niech

Niech

b

b

ę

ę

dzie zbiorem wypuk

dzie zbiorem wypuk

ł

ł

ym. Funkcj

ym. Funkcj

ę

ę

b

b

ę

ę

dziemy

dziemy

nazywali wypuk

nazywali wypuk

łą

łą

, je

, je

ż

ż

eli dla dowolnych dw

eli dla dowolnych dw

ó

ó

ch punkt

ch punkt

ó

ó

w

w

i dla

i dla

ka

ka

ż

ż

dego

dego

:

:

n

R

X ⊂

1

:

R

X

f

→

X

x

x

∈

2

1

,

[ ]

1

,

0

∈

λ

(

)

(

)

( )

(

)

( )

2

1

2

1

1

1

x

f

x

f

x

x

f

λ

λ

λ

λ

−

+

≤

−

+

Zbiór wypukły – intuicyjnie, podzbiór pewnej

przestrzeni euklidesowej

, o tej własności,

że dowolny

odcinek

, którego końce należą do tego zbioru, w całości się w nim zawiera.

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Kiedy funkcja f(x) jest wypukła

Macierz A o wymiarze nxn nazywamy hesjanem, gdy jej elementami są drugie
pochodne cząstkowe funkcji f(x):

















∂

∂

∂

=

j

i

x

x

x

f

x

A

)

(

)

(

2

Lemat 1

Niech

ma ciągłe drugie pochodne cząstkowe oraz niech

będzie zbiorem wypukłym . Funkcja f(x) jest wypukła wtedy i tylko wtedy, gdy jej hesjan

A(x) jest dodatnio pół-określony dla każdego

.

1

:

R

X

f

→

n

R

X ⊂

X

x ∈

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Definicja macierzy A dodatnio półokreślonej

Macierz A o wymiarze

Macierz A o wymiarze

nxn

nxn

jest dodatnio p

jest dodatnio p

ó

ó

ł

ł

-

-

okre

okre

ś

ś

lona, je

lona, je

ś

ś

li

li

0

,

≥

Ax

x

dla ka

dla ka

ż

ż

dego

dego

n

R

x ∈

Definicja macierzy A dodatnio określonej

Macierz A o wymiarze

Macierz A o wymiarze

nxn

nxn

jest dodatnio okre

jest dodatnio okre

ś

ś

lona, je

lona, je

ś

ś

li

li

0

,

>

Ax

x

dla ka

dla ka

ż

ż

dego niezerowego

dego niezerowego

n

R

x ∈

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Kryterium Sylwestra –

praktyczne sprawdzenie wypukłości funkcji f(x)

Kwadratowa macierz symetryczna A jest dodatnio p

Kwadratowa macierz symetryczna A jest dodatnio p

ó

ó

ł

ł

-

-

okre

okre

ś

ś

lona wtedy i

lona wtedy i

tylko wtedy, gdy:

tylko wtedy, gdy:

0

.

...

.

,...,

,...,

,...,

0

,

0

,

...

1

2

22

21

1

12

11

22

21

12

11

11

≥

≥

≥

nn

a

n

n

n

a

a

a

a

a

a

a

a

a

a

a

a

Kwadratowa macierz symetryczna A jest dodatnio okre

Kwadratowa macierz symetryczna A jest dodatnio okre

ś

ś

lona wtedy i tylko

lona wtedy i tylko

wtedy, gdy:

wtedy, gdy:

0

.

...

.

,...,

,...,

,...,

0

,

0

,

...

1

2

22

21

1

12

11

22

21

12

11

11

>

>

>

nn

a

n

n

n

a

a

a

a

a

a

a

a

a

a

a

a

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Rys.1 Zbiór X - wypukły

Funkcja f(x) też jest wypukła

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Rys.2 Zbiór X – nie jest wypukły

Funkcja f(x) – funkcja wypukła.

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Rys.3 Zbiór X – jest wypukły

Funkcja f(x) nie jest wypukła,

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Rys.4 Zbiór X – nie jest wypukły

Funkcja f(x) też nie jest wypukła.

Lemat 2

Niech funkcja będzie funkcją różniczkowalną oraz zbiór

będzie zbiorem wypukłym.

Funkcja f(x) jest wypukła wtedy i tylko wtedy, gdy

>

−

∇

<

+

≥

0

0

0

),

(

)

(

)

(

x

x

x

f

x

f

x

f

X

x

x

∈

∀

0

,

Lemat 3

Niech funkcja , dla

będzie funkcja wypukłą, wówczas dla dowolnego

rzeczywistego α zbiór

1

:

R

X

f

→

n

R

X ⊂

{

}

α

α

≤

=

)

(

:

x

f

x

X

jest wypukły.

n

R

X ⊂

Funkcje wypukłe

)

(x

f

Funkcja f(x) jest wypukła w przedziale (a,b) wtedy i tylko wtedy, gdy wykres funkcji leży ponad
wykresem stycznej dla każdego punktu x

0

z przedziału (a,b).

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Lemat 4

Niech

będzie zbiorem wypukłym. Jeśli funkcje dla

i=1,...,k są funkcjami wypukłymi oraz jeśli wielkości

skalarne s

skalarne s

ą

ą

wi

wi

ę

ę

ksze od zera

ksze od zera

dla i=1,...,k to funkcja

dla i=1,...,k to funkcja

f(x)

f(x)

jest funkcją wypukłą.

1

:

R

X

f

i

→

0

≥

i

α

( )

x

f

x

f

i

k

i

i

∑

=

=

1

)

(

α

n

R

X ⊂

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

Twierdzenie 2

Dowolne minimum lokalne funkcji wypukłej f(x) na wypukłym zbiorze rozwiązań
dopuszczalnych

jest na tym zbiorze jej minimum globalnym.

Dowód:

Niech w punkcie

funkcja f(x) ma swoje minimum lokalne. Oznacza to, że

istnieje takie

, że:

gdzie:

Przyjmijmy

,

. Wybierzmy

oraz

Ze względu na wypukłość f(x) :

X

x ∈

1

n

R

X ⊂

0

>

ε

( )

( )

x

f

x

f

V

x∈

= min

1

{

}

ε

≤

−

∈

=

1

,

x

x

X

x

V

X

x ∈

2

2

1

x

x ≠

1

0

<

<

λ

(

)

V

x

x

∈

−

+

2

1

1

λ

λ

( )

(

)

( )

(

)

(

)

2

1

2

1

1

1

x

x

f

x

f

x

f

λ

λ

λ

λ

−

+

≥

−

+

Teoria i metody optymalizacji
Dr inż. Ewa Szlachcic

Wydział Elektroniki studia II st.

kier. Automatyka i Robotyka

( )

(

)

(

) ( ) ( ) ( ) ( )

1

1

1

1

2

1

2

1

1

1

x

f

x

f

x

f

x

f

x

x

f

x

f

=

−

−

≥

−

−

−

+

≥

λ

λ

λ

λ

λ

λ

ckd

ckd

Wniosek

Ściśle wypukła funkcja f(x) określona na wypukłym zbiorze rozwiązań

dopuszczalnych X ma na tym zbiorze co najwyżej jedno minimum.

Przykład

Niech , . Wykazać, że funkcja określona

formułą liniową:

jest jednocześnie wypukła i wklęsła na R

n.

n

R

c∈

1

R

d ∈

1

:

R

R

f

n

→

( )

d

x

c

x

f

T

+

=