3w to wlasnosci

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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



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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

λ

λ

λ

λ

+

+

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

Rys.1 Zbiór X - wypukły

Funkcja f(x) też jest wypukła

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

Funkcja f(x) – funkcja wypukła.

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

Funkcja f(x) nie jest wypukła,

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

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

background image

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

λ

λ

λ

λ

+

+

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

( )

(

)

(

) ( ) ( ) ( ) ( )

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

Twierdzenie 3

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

background image

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wykład 3

Wydział Elektroniki
EiT III r. subkier. EKA

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

+

=


Wyszukiwarka

Podobne podstrony:
7w to wlasnosci 2011
3w to proglin 2011
4, Mienie: z definicji jakiej dostarcza kodeks cywilny w artykule 44 ustawy, jest to własność i inne
prawo cywilne, 17. Nabycie i utrata wlasnosci, Nieruchomość to jeden z rodzajów rzeczy w rozumieniu
prawo cywilne, 17. Nabycie i utrata wlasnosci, Nieruchomość to jeden z rodzajów rzeczy w rozumieniu
Ślub to nie podpisanie aktu własności
4.WLASNOSCI - przekątne w wielokątach 3, TO może się przydać w 4 klasie, MATEMATYKA klasa 4, klasa
prawo cywilne, 14. Wlasnosc jako prawo rzeczowe, Nieruchomość to jeden z rodzajów rzeczy w rozumieni
Proudhon Co to jest własność
Ochrona własności intelektualnej 7
Introduction to VHDL
Biopreparaty co to
Ochrona prawa własności intelektualnej szkoleni e (1) 0
I wlasnosc intelektualna

więcej podobnych podstron