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 Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Właściwe minimum lokalne:
'"
Funkcja f(x) ma w punkcie x właściwe minimum lokalne, je\
eli istnieje
Funkcja f(x) ma w punkcie właściwe minimum lokalne, je\
eli istnieje
´ > 0
takie, \
e: "x" E
takie, \
e:
)
f (x)< f (x)
E = X )" "
przy czym:
przy czym:
)
" ={x : 0 < x - x < ´}
'"
x
SÅ‚abe minimum lokalne
'"
x
´l > 0
Funkcja f(x) ma w punkcie słabe minimum lokalne, je\
eli istnieje
Funkcja f(x) ma w punkcie słabe minimum lokalne, je\
eli istnieje
takie, \
e
takie, \
e
"x" El
) )
f (x)d" f (xl )
przy czym:
przy czym:
El = X )" "l
)
" = {x : 0 < x - x < ´ }
l l
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Ka\
de minimum globalne jest minimum lokalnym, lecz nie na odwrót.
n
" Zadanie optymalizacji bez ograniczeń dla
X = R
'"
ëÅ‚ öÅ‚
f (x ) = f x
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x" X
" Zadanie optymalizacji z ograniczeniami:
'"
ëÅ‚ öÅ‚
f (x ) = f x
ìÅ‚ ÷Å‚
min
íÅ‚ Å‚Å‚
x" X
Zadanie programowania liniowego ZPL
Zadanie programowania nieliniowego ZPN
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic 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
x1, x2 " X
takie, \
e dla ka\
dego zachodzi:
:
x" X
f (x1) d" f (x) d" f (x2)
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Własności funkcji wypukłych
Definicja zbioru wypukłego:
Definicja zbioru wypukłego:
X ‚" Rn nazywamy wypukÅ‚ym, je\
eli dla ka\
dych dwóch punktów
Zbiór nazywamy wypukłym, je\
eli dla ka\
dych dwóch punktów x1, x2 " X
Zbiór
odcinek Å‚Ä…czÄ…cy te dwa punkty tak\
e nale\
y do X tzn.:
odcinek Å‚Ä…czÄ…cy te dwa punkty tak\
e nale\
y do X tzn.:
X ={x : x = x1 + (1- )x2, 0 d"  d"1}
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.
Definicja funkcji wypukłej:
X ‚" Rn bÄ™dzie zbiorem wypukÅ‚ym. FunkcjÄ™
Niech będzie zbiorem wypukłym. Funkcję f : X R1 będziemy
Niech będziemy
x1, x2 " X
nazywali wypukłą, je\
eli dla dowolnych dwóch punktów i dla
nazywali wypukłą, je\
eli dla dowolnych dwóch punktów i dla
ka\
dego:
ka\
dego:  "[0,1]
f (x1 + (1- )x2)d"  f (x1)+ (1- )f (x2)
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic 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):
2
îÅ‚ Å‚Å‚
" f ( x )
A( x ) =
ïÅ‚ śł
"xi "x
ïÅ‚ śł
j
ðÅ‚ ûÅ‚
Lemat 1
Niech ma ciągłe drugie pochodne cząstkowe oraz niech
f : X R1 X ‚" Rn
będzie zbiorem wypukłym . Funkcja f(x) jest wypukła wtedy i tylko wtedy, gdy jej hesjan
x" X
A(x) jest dodatnio pół-określony dla ka\
dego .
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Definicja macierzy A dodatnio półokreślonej
Macierz A o wymiarze nxn jest dodatnio pół-określona, jeśli
Macierz A o wymiarze nxn jest dodatnio pół-określona, jeśli
dla ka\
dego
dla ka\
dego x " Rn
x, Ax e"0
Definicja macierzy A dodatnio określonej
Macierz A o wymiarze nxn jest dodatnio określona, jeśli
Macierz A o wymiarze nxn jest dodatnio określona, jeśli
dla ka\
dego niezerowego
dla ka\
dego niezerowego x " Rn
x, Ax >0
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Kryterium Sylwestra 
praktyczne sprawdzenie wypukłości funkcji f(x)
Kwadratowa macierz symetryczna A jest dodatnio pół-określona wtedy i
Kwadratowa macierz symetryczna A jest dodatnio pół-określona wtedy i
tylko wtedy, gdy:
tylko wtedy, gdy:
a11 a12,...,a1n
a21 a22,...,a2n
a11 a12
a11 e" 0, e" 0 ,..., e" 0
. ... .
a21 a22
an1 ... ,ann
Kwadratowa macierz symetryczna A jest dodatnio określona wtedy i tylko
Kwadratowa macierz symetryczna A jest dodatnio określona wtedy i tylko
wtedy, gdy:
wtedy, gdy:
a11 a12,...,a1n
a21 a22,...,a2n
a11 a12
a11 > 0, > 0 ,..., > 0
. ... .
a21 a22
an1 ... ,ann
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Rys.1 Zbiór X - wypukły
Funkcja f(x) te\
jest wypukła
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Rys.2 Zbiór X  nie jest wypukły
Funkcja f(x)  funkcja wypukła.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Rys.3 Zbiór X  jest wypukły
Funkcja f(x) nie jest wypukła,
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Rys.4 Zbiór X  nie jest wypukły
Funkcja f(x) te\
nie jest wypukła.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Funkcje wypukłe
Lemat 2
f (x)
Niech funkcja będzie funkcją ró\
niczkowalną oraz zbiór
X ‚" Rn
będzie zbiorem wypukłym.
Funkcja f(x) jest wypukła wtedy i tylko wtedy, gdy
"x, x0 " X
f (x)e" f (x0)+ < "f (x0), x - x0 >
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 x0 z przedziału (a,b).
Lemat 3
f : X R1
Niech funkcja , dla będzie funkcja wypukłą, wówczas dla dowolnego
X ‚" Rn
rzeczywistego ą zbiór
XÄ… = {x : f (x) d" Ä…}
jest wypukły.
Lemat 4
fi : X R1
Niech będzie zbiorem wypukłym. Jeśli funkcje dla
X ‚" Rn
i=1,...,k są funkcjami wypukłymi oraz jeśli wielkości skalarne są większe od zera
skalarne są większe od zera
Ä…i e" 0
dla i=1,...,k to funkcja f(x)
dla i=1,...,k to funkcja f(x)
k
f ( x ) = Ä… f (x )
" i i
i = 1
jest funkcją wypukłą.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Twierdzenie 2
Dowolne minimum lokalne funkcji wypukłej f(x) na wypukłym zbiorze rozwiązań
X ‚" Rn
dopuszczalnych jest na tym zbiorze jej minimum globalnym.
Dowód:
x1 " X
Niech w punkcie funkcja f(x) ma swoje minimum lokalne. Oznacza to, \
e
istnieje takie
µ > 0, \
e:
f (x1)= min f (x)
x"V
gdzie:
V ={x " X , x - x1 d" µ}
Przyjmijmy , . Wybierzmy oraz
0 <  < 1
x1 `" x2
x2 " X
x1 + (1- )x2 "V
Ze względu na wypukłość f(x) :
 f (x1)+ (1- )f (x2)e" f (x1 + (1- )x2)
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
f (x1 + (1- )x2)- f (x1) f (x1)- f (x1)
f (x2)e" e" = f (x1)
1-  1- 
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
f : Rn R1
Niech , . Wykazać, \
e funkcja określona
c"Rn d " R1
formułą liniową:
f (x)= cT x + d
jest jednocześnie wypukła i wklęsła na Rn.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka