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

Wykład 8

dr inŜ. Ewa Szlachcic

Wydział Elektroniki 

Kierunek: Elektronika i Telekomunikacja  III r. 

Subkierunek: Elektronika

Technika optymalizacji
Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

. 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

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

. 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

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

. 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

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

. 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

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

. 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
Dr inŜ. Ewa Szlachcic

Wydzia

Wydzia

ł

ł

Elektroniki

Elektroniki

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

. 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

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

. 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

EiT

EiT

III r. 

III r. 

Sub

Sub

-

-

kier

kier

. Elektronika

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