Sformułowanie zadania optymalizacji nieliniowej
Sformułowanie zadania optymalizacji nieliniowej
bez ograniczeń:
bez ograniczeń:
Funkcja celu f(x) :
f (x):Rn çÅ‚
çÅ‚ R1
Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych x,
nale\
ącego do zbioru rozwiązań dopuszczalnych Rn
'"
x
"x"Rn
takiego, \
e dla
'"
ëÅ‚ öÅ‚
f x d" f (x )
ìÅ‚ ÷Å‚
íÅ‚ Å‚Å‚
Co jest równoznaczne zapisowi:
'"
ëÅ‚xöÅ‚
f (x)= f
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x"Rn
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Zadanie programowania nieliniowego bez ograniczeń
DEFINICJA.
Kierunkiem d w przestrzeni Rn nazywamy dowolny n-wymiarowy wektor
x"Rn
kolumnowy. Niech będzie dany punkt oraz skalar
Ä "[0;+").
y " Rn
Dowolny punkt le\
ący na półprostej wychodzącej z
d `" 0
punktu x w kierunku będzie wówczas określony zale\
nością
y = x + Ä d
LEMAT.
0
f : X = Rn R1 będzie funkcją ró\
niczkowalnÄ… w punkcie x " X
Niech
Załó\
my, \
e istnieje d, dla którego:
0
" f ( x ), d < 0 ,
Ä " (0,Ã ]
Wówczas istnieje takie à > 0, ,\
e dla wszystkich zachodzi
0 0
f ( x + Äd ) < f ( x ).
Dowód: wynika z własności ró\
niczki Gateaux.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Zadanie programowania nieliniowego bez ograniczeń
f : X = Rn R1
Twierdzenie. Niech będzie funkcją ró\
niczkowalną . Jeśli
'"
x " X
minimalizuje funkcjÄ™ f(x) tzn.
'"
f (x) d" f (x), "x"X,
to
Ć
"f (x) =0
Dowód: nie wprost.
'"
x
Punkt jest nazywany punktem stacjonarnym.
f : X = Rn R1
Twierdzenie. Niech będzie funkcją wypukłą i
Ć
x"X
ró\
niczkowalnÄ…. Punkt stanowi minimum funkcji f(x), tzn.
Ć
f (x) d" f (x),
'"
x " X
dla ka\
dego wtedy i tylko wtedy, gdy spełnia warunek
x
Ć
"f (x) = 0
'"
x
Jest to warunek konieczny istnienia ekstremum lokalnego f(x) w punkcie .
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Minimum lokalne i globalne funkcji f(x)
'"
x
Punkt stanowi minimum lokalne funkcji f(x) w przestrzeni Rn, je\
eli istnieje takie
'"
x
E ‚" Rn
otwarte otoczenie punktu , \
e
'"
"x " E f (x) d" f (x)
'" '"
f (x) < f (x)
dla to istnieje wtedy ścisłe minimum lokalne.
x `" x
Przy czym jeśli zachodzi
'"
x
Punkt stanowi minimum globalne funkcji f(x) w przestrzeni Rn, je\
eli istnieje takie
'"
x
otwarte otoczenie Rn punktu , \
e
'"
"x " Rn f (x) d" f (x)
'"
'"
x `" x
f (x) < f (x)
Przy czym jeśli zachodzi dla to ten punkt stanowi ścisłe minimum
globalne.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Minimum globalne funkcji f(x)
Twierdzenie:
f : X = Rn R1
Jeśli będzie funkcją ściśle wypukłą i
Ć
x"X
ró\
niczkowalną, to wektor spełniający warunek
konieczny jest jedynym minimum globalnym
Ć
"f (x) = 0
funkcji f(x).
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Warunki wystarczające optymalizacji dla zadania bez ograniczeń
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
A
i
"2 f
A1 = (x)
2
"x1
"2 f "2 f "2 f
(x) ... (x) ... (x)
2
"x1 "x1xi "x1xn
"2 f "2 f
... ... ... ... ...
(x) ..... (x)
2
"x1 "x1xi "2 f "2 f "2 f
A = (x) ... (x) ... (x)
A = ..... ......
n
i
"xix1 "xi2 "xi xn
"2 f "2 f
... ... ... ... ...
(x) ..... (x)
"xix1 "xi2
"2 f "2 f "2 f
(x) ... (x) ... (x)
2
"xnx1 "xnxi "xn
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Warunki stacjonarności dla zadania optymalizacji nieliniowej bez
ograniczeń cd.
Twierdzenie:
'"
x
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
A(x) > 0 dla i =1,..., n
i
funkcja f(x) ma minimum lokalne w tym punkcie
'"
i
2. Jeśli hesjan A jest ujemnie określony tzn: to
(-1) A(x) > 0 dla i = 1,..., n
i
funkcja f(x) ma maksimum lokalne w tym punkcie
'" '"
A(x) e" 0 dla i = 1,..., n -1 oraz A(x) = 0
3. Jeśli hesjan A jest pół-dodatnio określony tzn:
i n
bÄ…dz
hesjan pół-ujemnie określony
'" '"
i
(-1) A(x) e" 0 dla i = 1,..., n -1 oraz A(x) = 0
i n
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
x
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Warunek stacjonarności:
poprawić gradient i hesjan A
"f (x)
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ń.
'"
ëÅ‚
"f xöÅ‚ = 0
ìÅ‚ ÷Å‚ warunek I rzÄ™du
íÅ‚ Å‚Å‚
'"
T
dla warunek II rzędu
d A(x) d > 0 "d `" 0
'"
A = "2 f (x)
Macierz A jest macierzą ściśle dodatnio określoną
" 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.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Sformułowanie zadania optymalizacji nieliniowej
z ograniczeniami PN :
'"
x
Znalez
ć takie, \
e:
Ć
f (x) = min f (x),
x"X
gdzie:
X ={x: gi(x) d" 0, i =1,...,m},
f : X = Rn R1
oraz gi : X = Rn R1.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Sformułowanie zadania optymalizacji nieliniowej
z ograniczeniami
DEFINICJA. Kierunek d poprowadzony z punktu x jest
DEFINICJA. Kierunek d poprowadzony z punktu x jest
à > 0
dopuszczalny, jeśli istnieje takie \
e dla dowolnego
dopuszczalny, jeśli istnieje takie \
e dla dowolnego
Ä " [0;Ã ], x + Äd " X ,
gdzie X0 oznacza zbiór określony jako PN.
gdzie X0 oznacza zbiór określony jako PN.
Zbiór wszystkich kierunków dopuszczalnych :
Zbiór wszystkich kierunków dopuszczalnych :
D(x) = {d : "Ã > 0 takie, \
e
Ä "[0;Ã ] Ò! x +Äd " X }.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Funkcja Lagrange a
DEFINICJA.
FunkcjÄ… Lagrange a zadania PN nazywamy skalarnÄ…
funkcjÄ™
L ( x,  ) = f ( x ) +  , g ( x ) ,
 " Rn
gdzie jest wektorem mno\
ników Lagrange a.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Ograniczenia aktywne:
Ć Ć
1 . g (x + Äd ) d" 0, " i " A (x )
i
przy czym Ä " [0,Ä ]
Ć Ć Ć
2. g (x + Äd ) = g (x) + Ä " g (x), d + O (Ä ) d" 0
i i i
3. warunkiem koniecznym na to, aby kierunek d był
dopuszczalny jest:
Ć Ć
" g ( x ), d d" 0, " i " A ( x )
i
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Lemat Farkasa
Niech będzie dany w Rn zbiór n-wymiarowych wektorów
i
{b, a , i = 1,..., m}.
Nierówność
b, x e" 0
zachodzi dla ka\
dego spełniającego
x"Rn,
- ai , x e" 0,
 = [1,..., m ]T e" 0
Wtedy i tylko wtedy, gdy istnieje
takie, \
e
m
b +
" ai = 0.
1
i=1
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Wzajemnie rozłączne zbiory kierunków
'" '" '" '"
Å„Å‚d
D1(x) = : < "gi (x),d > d" 0, i "A(x), < "f (x),d > e" 0üÅ‚
òÅ‚ żł
ół þÅ‚
'" '" '" '"
Å„Å‚d
D2(x) = : < "gi (x), d > d" 0, i "A(x), < "f (x),d > < 0üÅ‚
òÅ‚ żł
ół þÅ‚
'" '" '"
Å„Å‚d
D3(x) = : < "gi (x),d > > 0 dla pewnych i "A(x)üÅ‚
òÅ‚ żł
ół þÅ‚
'" '" '" '"
D(x) = D1(x) *" D2(x) *" D3(x)
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Warunki konieczne Kuhn a-Tucker a-Karusch a
TWIERDZENIE. Jeśli
f i g
a)funkcje i są ró\
niczkowalne;
Ć e" 0, dim Ć = m.
Ć
b) x jest lokalnym minimum ZPN, to istnieje
Takie, \
e
m
Ć
Ć Ć
"f (x) +
" "gi (x) = 0
i
i=1
Ć
Ć
igi (x) = 0, i = 1,..., m,
Wtedy i tylko wtedy, gdy
Ć
D2(x) = Ć
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Dowód warunków koniecznych Kuhn a-Tucker a-Karusch a
Ć
b = "f (x)
DOWÓD. Niech oraz
Ć Ć
ai = "gi (x), "i " A(x)
Ć
Ć
wówczas zgodnie z lematem Farkasa, istnieje i e" 0, i " A(x)
takie, \
e
Ć Ć
" f ( x ) = Ći ( -" g ( x ))
" i
Ć
i" A ( x )
wtedy i tylko wtedy, gdy
Ć
"f (x), d e" 0, "d " Rn ,
Spełniającego warunek dla ograniczeń:,
Ć Ć
" g (x ), d d" 0, " i " A ( x )
i
tzn. wtedy i tylko wtedy, gdy
Ć
D2 ( x) = Ć
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Dowód warunków koniecznych Kuhn a-Tucker a-Karusch a
Ć
Ć
i " A(x)
Dla nale\
y przyjąć i = 0
Więc są spełnione dwa równania:
Więc są spełnione dwa równania:
m
Ć
Ć Ć
"f (x) +
""g (x) = 0
i
i=1
Ć
Ć
igi (x) = 0, i = 1,..., m,
Ckd
Ckd
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Warunki konieczne Kuhn a-Tucker a-Karusch a z wykorzystaniem
funkcji Lagrange a
m
L ( x,  ) = f ( x ) +  g ( x ) .
" i i
i = 1
warunki konieczne:
Ć
Ć
" L ( x ,  ) = 0 ,
x
Ć Ć
Ć
 , " L (x,  ) = 0

Ć
Ć
" L ( x ,  ) d" 0

Ć
 e" 0
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Warunki wystarczające optymalizacji określane jako
warunki regularności ograniczeń:
1. Wszystkie funkcje ograniczeń gi(x) są liniowe  warunek
1. Wszystkie funkcje ograniczeń gi(x) są liniowe  warunek
regularności Karlina.
regularności Karlina.
2. Wszystkie funkcje ograniczeń gi(x) są funkcjami wypukłymi
Wszystkie funkcje ograniczeń gi(x) są funkcjami wypukłymi
oraz zbiór rozwiązań dopuszczalnych ma niepuste wnętrze 
oraz zbiór rozwiązań dopuszczalnych ma niepuste wnętrze 
warunek regularności Slatera
warunek regularności Slatera
'"
"gi (x),
3. Gradienty wszystkich ograniczeń aktywnych, a więc
'"
i " A(x),
dla sÄ… liniowo niezale\
ne  warunek regularności
Fiacco i McCormicka.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Twierdzenie Kuhn a-Tucker a-Karusch a  warunki konieczne i
wystarczajÄ…ce dla zadania optymalizacji nieliniowej z ograniczeniami
TWIERDZENIE. Jeśli
a)funkcje f i g są ró\
niczkowalne;
i
Ć
b) x jest lokalnym minimum ZPN,
c) Warunek regularności ograniczeń Kuhn a-Tucker a-
Ć
x
Karusch a jest spełniony w
Ć Ć
 e" 0, dim  = m.
to istnieje
'"
x
Takie, \
e w punkcie zachodzÄ… warunki konieczne
Kuhn a-Tucker a.
m
Ć
Ć Ć
"f (x) +
" "gi (x) = 0
i
i=1
Ć
Ć
igi (x) = 0, i = 1,..., m,
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka