Technika optymalizacji

1

Nieliniowe zadanie optymalizacji
statycznej bez ograniczeń - PN bez
ograniczeń

dr inż. Ewa Szlachcic

Wydział Elektroniki

Kierunek: Elektronika i Telekomunikacja III r.

Potok: Elektronika

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych x,
należącego do zbioru rozwiązań dopuszczalnych R

n

takiego, że dla

n

R

∈

∀x

Co jest równoznaczne zapisowi

:

∧

x

( )

x

x

f

f

≤













∧

( )













=

∧

∈

x

x

x

f

f

n

R

min

( )

1

:

R

R

f

n

→



x

Funkcja celu f(x) :

Sformu

Sformu

ł

ł

owanie zadania optymalizacji

owanie zadania optymalizacji

nieliniowej

nieliniowej

bez ogranicze

bez ogranicze

ń

ń

:

:

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Minimum lokalne i globalne funkcji

f(x)

Punkt stanowi

minimum lokalne

funkcji f(x) w przestrzeni R

n

, jeżeli istnieje takie

otwarte otoczenie punktu , że

∧

x

∧

x

)

(

)

(

x

f

x

f

E

x

≤

∈

∀

∧

Przy czym jeśli zachodzi

)

(

)

(

x

f

x

f

<

∧

dla to istnieje wtedy

ścisłe minimum lokalne.

∧

≠ x

x

n

R

E ⊂

Punkt stanowi

minimum globalne

funkcji f(x) w przestrzeni R

n

, jeżeli

)

(

)

(

x

f

x

f

R

x

n

≤

∈

∀

∧

Przy czym jeśli zachodzi dla to ten punkt stanowi ścisłe minimum
globalne.

)

(

)

(

x

f

x

f

<

∧

∧

≠ x

x

∧

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Zadanie programowania nieliniowego bez ograniczeń

DEFINICJA.

Kierunkiem d w przestrzeni R

n

nazywamy dowolny n-wymiarowy wektor

kolumnowy. Niech będzie dany punkt

oraz skalar

Dowolny punkt

leżący na półprostej wychodzącej z

punktu x w kierunku

będzie wówczas określony zależnością

LEMAT.

Niech

będzie funkcją różniczkowalną w punkcie

Załóżmy, że istnieje d, dla którego:

Wówczas istnieje takie

,że dla wszystkich zachodzi

n

R

∈

x

).

;

0

[ +∞

∈

τ

n

R

∈

y

0

≠

d

d

x

y

τ

+

=

1

:

R

R

f

n

→

=

X

X

x

0

∈

,

0

),

(

0

<

∇

d

x

f

,

0

>

σ

]

,

0

(

σ

τ

∈

).

(

)

(

0

0

x

f

d

x

f

<

+

τ

Dowód: wynika z własności różniczki Gateaux.

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Zadanie programowania nieliniowego bez ograniczeń

X

x ∈

∧

∧

x

Twierdzenie. Niech

będzie funkcją różniczkowalną . Jeśli

minimalizuje funkcję f(x)

tzn.

1

:

R

R

f

n

→

=

X

0

)

ˆ

(

to

,

),

(

)

(

=

∇

∈

∀

≤

∧

x

X

x

x

x

f

f

f

Dowód: nie wprost.

Twierdzenie. Niech

będzie funkcją wypukłą i

różniczkowalną. Punkt

stanowi minimum globalne funkcji

dla każdego wtedy i tylko wtedy, gdy

spełnia warunek

1

:

R

R

X

f

n

→

=

ˆ

X

∈

x

),

(

)

ˆ

(

tzn

),

(

x

f

x

f

x

f

≤

0

)

ˆ

(

=

∇ x

f

Punkt jest nazywany

punktem stacjonarnym.

∧

x

X

x ∈

Jest to warunek konieczny istnienia ekstremum lokalnego f(x) w punkcie

∧

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Minimum globalne funkcji f(x)

Jeśli

będzie funkcją ściśle wypukłą i

różniczkowalną, to wektor

spełniający warunek

konieczny

jest jedynym minimum globalnym

funkcji f(x).

1

:

R

R

X

f

n

→

=

0

)

ˆ

(

=

∇ x

f

Twierdzenie:

ˆ X

∈

x

Technika optymalizacji

2

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Warunki wystarczające optymalizacji dla zadania bez ograniczeń

i

A

)

(

2

1

2

1

x

x

f

A

∂

∂

=

)

(

.....

)

(

......

.....

)

(

.....

)

(

2

2

1

2

1

2

2

1

2

x

x

f

x

x

x

f

x

x

x

f

x

x

f

A

i

i

i

i

∂

∂

∂

∂

∂

∂

∂

∂

=

Funkcja f(x) jest funkcją ciągłą i dwukrotnie różniczkowalną. Posiada macierz
drugich pochodnych (hesjan) - A

Macierz A posiada ciąg podwyznaczników głównych

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

2

2

2

1

2

2

2

2

1

2

1

2

1

2

2

1

2

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

x

x

f

x

x

x

f

x

x

x

f

x

x

x

f

x

x

f

A

n

i

n

n

n

i

i

i

n

i

n

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

=

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Warunki stacjonarności dla nieliniowej zadania optymalizacji bez
ograniczeń cd.

Twierdzenie:

Założono, że jest punktem stacjonarnym funkcji f(x). Wówczas zachodzą poniższe
zależności:
1.

Jeśli hesjan A jest dodatnio określony tzn: to

funkcja f(x) ma minimum lokalne w tym punkcie

2. Jeśli hesjan A jest ujemnie określony tzn: to
funkcja f(x) ma maksimum lokalne w tym punkcie

3. Jeśli hesjan A jest pół-dodatnio określony tzn:
bądź hesjan pół-ujemnie określony

to nie można rozstrzygnąć o typie ekstremum funkcji f(x) w tym punkcie
4. Jeśli nie są spełnione warunki 1 i 2 z nieostrymi nierównościami (wówczas hesjan A

nie jest określony) to funkcja f(x) nie ma ekstremum w punkcie

0

)

(

1

,...,

1

0

)

(

=

−

=

≥

∧

∧

n

i

x

A

oraz

n

i

dla

x

A

n

i

dla

x

A

i

,...,

1

0

)

(

=

>

∧

( )

n

i

dla

x

A

i

i

,...,

1

0

)

(

1

=

>

−

∧

∧

x

( )

0

)

(

1

,...,

1

0

)

(

1

=

−

=

≥

−

∧

∧

n

i

i

x

A

oraz

n

i

dla

x

A

∧

x

Technika optymalizacji
Dr inż. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

Kierunek

Kierunek

EiT

EiT

III r Potok: Elektronika

III r Potok: Elektronika

.

.

Warunek stacjonarności:

poprawić gradient i hesjan A

)

(

2

∧

∇

=

x

f

A

0

)

(

>

∧

d

x

A

d

T

TWIERDZENIE. Jeśli funkcja f(x) jest dwukrotnie różniczkowalna, to w każdym jej
minimum lokalnym bez ograniczeń spełnione są następujące warunki konieczne
optymalności zadania ZPN bez ograniczeń.

0

=













∇

∧

x

f

•Warunek I rzędu jest często nazywamy warunkiem stacjonarności, ponieważ
oznacza zerowanie się pierwszej pochodnej.

•Warunek II rzędu dla funkcji dwukrotnie różniczkowalnych implikuje lokalną
wypukłość minimalizowanej funkcji celu.

)

(x

f

∇

warunek II rzędu

warunek I rzędu

dla

0

≠

∀d

Macierz A jest macierzą ściśle dodatnio określoną