Badania Operacyjne w Logistyce
kierunek Informatyka, studia I stopnia, III rok
wyklad
1 Programowanie nieliniowe
1.1 Funkcje jednej zmiennej
W rozdziale tym przypomnimy wybrane fakty dotyczÄ…ce minimalizacji funkcji jednej
zmiennej.
1.1.1 Istnienie rozwiązań - twierdzenie Weierstrassa
Rozważmy zadanie postaci
Å„Å‚
òÅ‚
J(u) min .,
(1)
ół
u " U
gdzie J : U R, U ‚" R jest ustalonym zbiorem.
Punkt u" " U nazywamy punktem lokalnego minimum funkcji J na zbiorze U
(lokalnym rozwiązaniem zadania (1)), jeśli istnieje przedział otwarty V , zawierający
punkt u", taki, że
J(u") d" J(u)
dla dowolnego u " V )" U. Punkt u" " U nazywany jest punktem minimum global-
nego funkcji J na zbiorze U, gdy powyższa nierówność jest spełniona przez wszystkie
punkty u " U. Zbiór wszystkich punktów minimum globalnego funkcji J na zbiorze
1
U oznaczamy symbolem U". Kres dolny wartości funkcji J na zbiorze U oznaczamy
symbolem J", t.zn. J" = inf J(u).
u"U
Zanim sformułujemy klasyczne twierdzenie o istnieniu punktu minimum global-
nego, podamy określenie funkcji półciągłej z dołu.
Mówimy, że funkcja J : U R jest półciągła z dołu w punkcie u0 " U, jeśli dla
dowolnego µ > 0 istnieje przedziaÅ‚ otwarty V , zawierajÄ…cy punkt u0, taki, że
J(u0) - µ d" J(u)
dla dowolnego u " V )" U. Mówimy, że J jest półciągła z dołu na zbiorze U, jeśli
jest półciągła w każdym punkcie u " U.
Można pokazać, że funkcja J : U R jest półciągła z dołu w punkcie u0 " U
wtedy i tylko wtedy, gdy dla dowolnego ciÄ…gu (un) ‚" U takiego, że lim un = u0
n"
zachodzi
J(u0) d" lim infJ(un).
n"
Klasycznym wynikiem jest następujące twierdzenie o istnieniu minimum global-
nego funkcji jednej zmiennej, nazywane twierdzeniem Weierstrassa.
Twierdzenie 1 (Weierstrassa) Jeśli funkcja J : [a,b] R jest półciagła z dołu
Û
na [a,b], to istnieje punkt minimum globalnego u" " [a,b].
1.1.2 Warunki konieczne - zasada Fermata
Prawdziwa jest następująca zasada Fermata.
Twierdzenie 2 (Fermata) Jeśli u" jest punktem lokalnego minimum funkcji J:(a, b)
R i funkcja J ma w punkcie u" pochodna J2 (u"), to
Û
J2 (u") = 0. (2)
1.1.3 Warunki dostateczne
Jeden z warunków dostatecznych na to, by punkt u" był punktem lokalnego mini-
mum funkcji J:(a,b) R opisuje poniższe twierdzenie.
2
Twierdzenie 3 Jeśli funkcja J : (a, b) R ma w punkcie u" " (a, b) pochodną
drugiego rzędu J2 2 (u"), przy czym J2 (u") = 0 i J2 2 (u") > 0, to u" jest punktem
lokalnego minimum funkcji J na (a, b).
Uwaga 4 Jeśli spełnione są założenia powyższego twierdzenia, to punkt u", o którym
mowa 3w powyższym twierdzeniu, jest punktem ścisłego minimum lokalnego funkcji
J, t.zn. istnieje przedział otwarty V taki, że u" " V oraz
J(u") < J(u)
dla dowolnego u " V , u = u".

Uwaga 5 Analogicznie definiuje się punkt (ścisłego) maksimum lokalnego i maksi-
mum globalnego. Warunek konieczny istnienia maksimum lokalnego w punkcie jest
taki sam, jak w przypadku minimum, natomiast w warunku dostatecznym stosownÄ…
nierówność należy zastapić nierównością odwrotną.
Û
1.1.4 Założenie wypukłości
Niech I ‚" R bÄ™dzie przedziaÅ‚em (otwartym, domkniÄ™tym lub jednostronnie domkniÄ™-
tym). Funkcję J : I R nazywamy wypukłą, gdy
J(Ä…u1 + (1 - Ä…)u2) d" Ä…J(u1) + (1 - Ä…)J(u2)
dla dowolnych Ä… " [0, 1], u1, u2 " I.
Ważne własności funkcji wypukłych opisują poniższe dwa twierdzenia.
Twierdzenie 6 Niech dana będzie funkcja wypukła J : I R. Wówczas, każdy
punkt minimum lokalnego jest punktem minimum globalnego.
Dowód. Niech u" " I będzie punktem minimum lokalnego, t.zn. istnieje przedział
otwarty V taki, że u" " V oraz
J(u") d" J(u)
3
dla dowolnego u " I )"V . Przypuśćmy, że u" nie jest punktem minimum globalnego,
t.zn. istnieje punkt u " I taki, że
J(u) < J(u").
Rozważmy punkty uą postaci uą = ąu" + (1 - ą)u, gdzie ą " [0, 1]. Z wypukłości
przedziału I wynika, że uą " I dla dowolnego ą " [0, 1]. Ponadto, dla ą " (0, 1)
dostatecznie bliskich jedności uą " V i w konsekwencji uą " I )" V , przy czym
J(uÄ…) d" Ä…J(u") + (1 - Ä…)J(u) < Ä…J(u") + (1 - Ä…)J(u") = J(u").
Przeczy to lokalnej optymalności punktu u".
Przy założeniu wypukłości prawdziwe jest następujące odwrócenie twierdzenia
Fermata.
Twierdzenie 7 (odwrócenie twierdzenia Fermata) Niech dana będzie funkcja
wypukła J : (a,b) R. Jeśli J2 (u") = 0, to u" jest punktem minimum globalnego
funkcji J na (a, b).
1.1.5 Metody numeryczne - metoda Å‚amanych
Opiszemy teraz jedną z wielu metod numerycznych służących do przybliżonego
wyznaczania punktów minimum globalnego funkcji jednej zmiennej określonej na
ograniczonym przedziale domkniÄ™tym [a, b] ‚" R.
Mówimy, że funkcja J : [a, b] R spełnia warunek Lipschitza, jeśli istnieje stała
L > 0 taka, że
|J(u) - J(v)| d" L |u - v|
dla dowolnych u, v " [a,b]. A
atwo pokazać, że jeśli a = a0 < a1 < ... < an = b
jest podziałem przedziału [a, b] i funkcja J spełnia warunek Lipschitza na każdym
przedziale [ai-1,ai] ze stałą Li, to J spełnia warunek Lipschitza na przedziale [a, b]
ze stałą L = maxLi. Ponadto, jeśli J jest różniczkowalna na [a, b] i jej pochodna
1d"id"n
4
J2 jest ograniczona na [a, b], to J spełnia warunek Lipschitza na [a, b] ze stałą L =
sup |J2 (u)|.
u"[a,b]
Niech dana będzie funkcja J : [a, b] R spełniająca warunek Lipschitza ze stałą
L. Ustalmy dowolny punkt u0 i rozważmy funkcjÄ™ g(·, u0) jednej zmiennej u " [a, b]
postaci
Å„Å‚
òÅ‚
J(u0) + Lu - Lu0; u < u0
g(u, u0) = J(u0) - L|u - u0| = .
ół
J(u0) - Lu + Lu0; u e" u0
Jest to funkcja kawałkami liniowa, której wykres jest łamaną, składającą się z dwóch
odcinków prostych o współczynnikach kierunkowych L, -L, łączących się w punkcie
(u0, J(u0)). Z warunku Lipschitza wynika natychmiast, że
g(u,u0) = J(u0) - L |u - u0| d" J(u)
dla dowolnego u " [a, b]. A więc wykres funkcji J leży powyżej łamanej i ma z nią
punkt wspólny (u0,J(u0)). Oznaczmy p0(u) = g(u, u0). Niech u1 " [a,b] będzie
takim punktem, że
p0(u1) = min p0(u)
u"[a,b]
(oczywiście u1 = a lub u1 = b). Określmy nową funkcję
p1(u) = max{g(u, u1),p0(u)}, u " [a, b].
Punkt u2 " [a, b] niech będzie taki, że
p1(u2) = min p1(u).
u"[a,b]
Załóżmy, że w wyżej opisany sposób utworzyliśmy skończony ciąg punktów u0, u1,
...,un i funkcji p0, p1,...,pn-1. Wówczas określamy funkcję
pn(u) = max{g(u, un), pn-1(u)} = maxg(u, ui), u " [a, b],
0d"id"n
i punkt un+1 przy pomocy warunku
pn(un+1) = min pn(u)
u"[a,b]
5
(jeśli wybór punktu un+1 przy pomocy powyższego warunku nie jest jednoznaczny,
wybieramy dowolny punkt spełniający ten warunek).
Wykresem funkcji pn jest łamana, złożona z odcinków prostych o współczyn-
nikach kierunkowych równych -L, L. Oczywiście,
pn-1(u) = max g(u, ui) d" maxg(u, ui) = pn(u)
0d"id"n-1 0d"id"n
dla u " [a, b]. Ponadto, z faktu, że
g(u, ui) d" J(u)
dla u " [a, b], i = 0, ..., n, wynika, że
pn(u) d" J(u)
dla u " [a, b], n = 0, 1,...
Mamy następujące
Twierdzenie 8 Jeśli funkcja J spełnia warunek Lipschitza na przedziale [a, b] i
J" := inf J(u), to ciąg (un) otrzymany przy pomocy metody łamanych ma następu-
u"[a,b]
jące własności:
1) lim J(un) = J"
n"
2) 0 d" J(un+1) - J" d" J(un+1) - pn(un+1), n = 0, 1, ...
3) lim Á(un,U") = 0, gdzie Á(un, U") = inf |un - u|
n" u"U"
(oczywiście, U" = ").

1.2 Funkcje wielu zmiennych - część I
Rozważmy zadanie postaci
Å„Å‚
òÅ‚
J(u) min .,
(3)
ół
u " U
gdzie J : U R, U ‚" Rn jest ustalonym zbiorem.
6
1.2.1 Istnienie rozwiązań - twierdzenie Weierstrassa
Określenie funkcji półciągłej z dołu i charakteryzacja "ciągowa" takich funkcji są,
po zastąpieniu przedziału kulą w przypadku definicji, takie same, jak w przypadku
funkcji jednej zmiennej. Podobnie rzecz ma się z definicją (ścisłego) minimum,
maksimum lokalnego. Dla przykladu, punkt u" " U nazywamy punktem lokalnego
minimum funkcji J na zbiorze U (lokalnym rozwiązaniem zadania (3)), jeśli istnieje
kula K(u", r) taka, że
J(u") d" J(u)
dla dowolnego u " K(u", r) )" U.
W dalszym ciągu przydatna będzie następująca charakteryzacja funkcji pół-
ciągłych z dołu na zbiorze domkniętym.
Lemat 9 Niech U ‚" Rn bÄ™dzie zbiorem domkniÄ™tym. Funkcja J : U R jest
półciągła z dołu na zbiorze U wtedy i tylko wtedy, gdy dla dowolnego c " R zbiór
M(c) = {u " U; J(u) d" c}
jest zbiorem domkniętym.
Mamy następujące twierdzenia o istnieniu rozwiązań optymalnych.
Twierdzenie 10 (Weierstrassa) JeÅ›li U ‚" Rn jest zbiorem zwartym i funkcja
J : U R jest półciagła z dołu na zbiorze U, to istnieje punkt minimum globalnego
Û
funkcji J na zbiorze U.
Dowód. Niech (uk) ‚" U bÄ™dzie ciÄ…giem minimalizujÄ…cym, t.zn. lim J(uk) = J" =
k"
inf J(u) " R *" {-"}. Ze zwartości zbioru U wynika, że istnieją podciąg (uk ) oraz
i
u"U
punkt u" " U takie, że limuk = u". Wówczas,
i
i"
J" d" J(u") d" lim infJ(uk ) = limJ(uk ) = lim J(uk) = J".
i i
i" i" k"
Stąd wynika, że J(u") = J" " R.
7
Twierdzenie 11 (Weierstrassa) JeÅ›li U ‚" Rn jest zbiorem domkniÄ™tym i nieogranic-
zonym, funkcja J : U R jest półciagła z dołu oraz
Û
lim J(uk) = "
k"
dla dowolnego ciÄ…gu (uk) ‚" U takiego, że lim |uk| = " (mówimy w takim przypadku,
k"
że funkcja J jest koercytywna), to istnieje punkt minimum globalnego funkcji J na
U.
Proof. Z nieograniczonoÅ›ci zbioru U wynika, że istnieje ciÄ…g (uk) ‚" U taki, że
lim |uk| = ". Stąd i z założenia wynika, że lim J(uk) = ". Niech v " U będzie
k" k"
takim punktem, że J(v) > J" = inf J(u) (taki punkt istnieje wśród punktów uk,
u"U
k " N). Rozważmy zbiór
M(J(v)) = {u " U; J(u) d" J(v)}.
Jest to zbiór niepusty. Z Lematu 9 wynika, że M(J(v)) jest zbiorem domkniętym. Z
koercytywności J wynika jego ograniczoność. Zatem, funkcja J, zawężona do zbioru
M(J(v)), ma punkt minimum globalnego na zbiorze M(J(v)). Oczywiście jest to
też punkt minimum globalnego funkcji J na zbiorze U.
1.2.2 Warunki konieczne - zasada Fermata
Rozważmy zadanie (3). Mamy następujące:
Twierdzenie 12 (zasada Fermata) JeÅ›li U ‚" Rn jest zbiorem otwartym i u"
jest punktem lokalnego minimum funkcji J : U R, przy czym istnieje gradient
"J "J
"J(u") = ("u (u"), ..., (u")), to
"un
1
"J(u") = 0. (4)
Dowód. Istnienie gradientu funkcji J w punkcie u" oznacza istnienie, dla dowol-
nego i = 1, ..., n, pochodnej funkcji
Õi : (-´,´) " t J(u" + tei) " R
8
w punkcie t = 0, gdzie ´ jest pewnÄ… liczbÄ… dodatniÄ…, ei jest i-tym wektorem jednos-
tkowym. Ponieważ u" jest punktem lokalnego minimum funkcji J, więc punkt 0 jest
punktem minimum lokalnego funkcji Õi i w konsekwencji
Õ2 (0) = 0, i = 1,...,n.
i
A wiÄ™c "J(u") = (Õ2 (0), ..., Õ2 (0)) = 0, co koÅ„czy dowód.
1 n
Przyklad 13 Niech v1,...,vm " Rn będą ustalonymi punktami w przestrzeni Rn.
Należy znalez
ć punkt, dla którego suma kwadratów odległości od tych punktów jest
najmniejsza. Innymi słowy, należy znalez
ć punkt minimum globalnego funkcji
m
2
J(u) = u - vi
i=1
na przestrzeni Rn.
A
atwo sprawdzić, że gradient "J(u) funkcji J w dowolnym punkcie u " Rn jest
postaci
m
"J(u) = 2 u - vi .
i=1
Zatem, warunek (4) przyjmuje postać
m
mu - vi = 0.
i=1
i w konsekwencji jedynym punktem podejrzanym o globalne minimum jest punkt
m
1
u" = vi.
i=1
m
Jest to oczywiście także jedyny punkt podejrzany o lokalne minimum.
Ponieważ
2
m
J(u) = m |u|2 - 2m u, u" + vi
i=1
dla u " Rn, więc
2
m
J(u) e" m|u|2 - 2m |u| |u"| + vi - ".
i=1
|u|"
To oznacza, że funkcja J spełnia warunek z Twierdzenia 11 na przestrzeni Rn i, w
konsekwencji, istnieje punkt minimum globalnego funkcji J na Rn. Ostatecznie więc,
punkt u" jest jedynym punktem minimum globalnego funkcji J na Rn.
9
1.2.3 Warunki dostateczne
Użyteczne jest następujące
Twierdzenie 14 (warunki dostateczne drugiego rzÄ™du) Niech U ‚" Rn bÄ™dzie
zbiorem otwartym, funkcja J : U R niech będzie klasy C2 (t.zn. posiadająca na
Û
U ciagłe wszystkie pochodne cząstkowe rzędu drugiego) oraz "J(u") = 0.
Û
"2J
Jeśli macierz "2J(u") = (u") jest dodatnio określona, tzn. "2J(u")h, h >
"ui"uj 1d"i,jd"n
"2J
0 dla dowolnego h = 0 (równoważnie, det (u") > 0 dla dowolnego

"ui"uj 1d"i,jd"k
k = 1, ..., n), to u" jest punktem ścisłego minimum lokalnego funkcji J na U.
"2J
Jeśli macierz "2J(u") = (u") jest ujemnie określona, tzn. "2J(u")h, h <
"ui"uj 1d"i,jd"n
"2J
0 dla dowolnego h = 0 (równoważnie, (-1)kdet (u") > 0 dla dowolnego

"ui"uj 1d"i,jd"k
k = 1, ..., n), to u" jest punktem ścisłego maksimum lokalnego.
Jeśli iloczyn skalarny "2J(u")h, h przyjmuje wartości zarówno dodatnie jak i
ujemne, to J nie ma w punkcie u" ani minimum lokalnego ani maksimum lokalnego.
Przyklad 15 Zauważmy, że macierz drugich pochodnych "2J(u) funkcji J z Przykładu
13, w dowolnym punkcie u " Rn jest postaci
"2J(u) = 2mI,
gdzie I jest macierzÄ… jednostkowÄ… wymiaru n × n. To oznacza, że J jest klasy
C2. Ponadto, stosujac powyższy warunek dostateczny, stwierdzamy, że punkt u" jest
Û
punktem ścisłego minimum lokalnego funkcji J na przestrzeni Rn. Z jednoznaczności
minimum globalnego (por. Przykład 13) wynika, że jest to punkt ścisłego minimum
globalnego funkcji J na Rn.
1.2.4 Założenie wypukłości
Mówimy, że zbiór U ‚" Rn jest wypukÅ‚y, gdy speÅ‚niony jest warunek
Ä…x + (1 - Ä…)y " U
10
dla dowolnych Ä… " [0, 1], x, y " U.
Mówimy, że funkcja J : U R, gdzie U ‚" Rn jest zbiorem wypukÅ‚ym, jest
wypukła, gdy spełniony jest warunek
J(Ä…x + (1 - Ä…)y) d" Ä…J(x) + (1 - Ä…)J(y)
dla dowolnych Ä… " [0, 1], x, y " U.
Podamy teraz trzy twierdzenia pozwalające rozstrzygać o wypukłości funkcji
różniczkowalnych. Przypomnijmy, że mówimy, iż funkcja J : Rn ƒ" K(u",µ) R
jest różniczkowalna w punkcie u", jeśli istnieje wektor a " Rn taki, że
J(u" + h) - J(u") = a, h + o(h)
dla 0 < |h| < µ1, gdzie o : (-µ1, µ1) \ {0} R, 0 < µ1 < µ, jest takÄ… funkcjÄ…,
że limo(h) = 0 (funkcja o(·) zależy od u"). A
atwo widać, że w takim przypadku
|h|
h0
a = "J(u").
Ponadto, mówimy, że funkcja J : U R okreÅ›lona na zbiorze U ‚" Rn (niekoniecznie
otwartym) jest klasy C1, jeśli jest różniczkowalna w każdym punkcie tego zbioru i
wszystkie pochodne cząstkowe pierwszego rzędu funkcji J są funkcjami ciągłymi na
U (gdy zbiór U jest otwarty, wystarczy żądać jedynie ciągłości na U wszystkich
pochodnych cząstkowych pierwszego rzędu).
Twierdzenie 16 Niech U ‚" Rn bÄ™dzie zbiorem wypukÅ‚ym, J : U R - funkcjÄ…
klasy C1. Wówczas, funkcja J jest wypukła na U wtedy i tylko wtedy, gdy
J(u) e" J(v) + "J(v), u - v (5)
dla dowolnych u, v " U.
Twierdzenie 17 Niech U ‚" Rn bÄ™dzie zbiorem wypukÅ‚ym, J : U R - funkcjÄ…
klasy C1. Wówczas, funkcja J jest wypukła na U wtedy i tylko wtedy, gdy
"J(u) - "J(v), u - v e" 0
dla dowolnych u, v " U.
11
Mamy także
Twierdzenie 18 Niech U ‚" Rn bÄ™dzie zbiorem wypukÅ‚ym, V - zbiorem otwartym
zawierającym U, J : V R - funkcją klasy C2. Wówczas, jeśli
"2J(u)h, h e" 0
dla dowolnych u " U, h " Rn, to J jest wypukła na U.
Podobnie, jak w przypadku funkcji jednej zmiennej, prawdziwe jest następujące
twierdzenie.
Twierdzenie 19 Jeśli funkcja J : U R jest wypukła, to każdy punkt lokalnego
minimum funkcji J na zbiorze U jest punktem jej minimum globalnego.
Kolejne twierdzenie nazywane jest kryterium optymalności dla funkcji wypukłych
na zbiorze wypukłym.
Twierdzenie 20 (kryterium optymalnoÅ›ci dla funkcji wypukÅ‚ych) Niech U ‚"
Rn będzie zbiorem wypukłym, J : U R - funkcją klasy C1. Wówczas, jeśli punkt
u" " U jest punktem minimum globalnego, to
"J(u")), u - u" e" 0 (6)
dla dowolnego u " U, przy czym jeśli u" " IntU, to warunek (6) równoważny jest
warunkowi
"J(u") = 0.
Jeśli ponadto, funkcja J jest wypukła na U i u" " U, to warunek (6) jest wystarcza-
jący na to, aby punkt u" był punktem minimum globalnego.
Dowód. Załóżmy, że punkt u" jest punktem minimum globalnego. Wówczas, z
rózniczkowalności funkcji J w punkcie u" mamy
0 d" J(u" + Ä…(u - u")) - J(u") = Ä… "J(u")), u - u" + o(Ä…),
12
skÄ…d
o(Ä…)
0 d" "J(u")), u - u" +
Ä…
o(Ä…)
dla dostatecznie małych ą > 0 (tutaj o(ą) jest taką funkcją, że 0 gdy ą 0).
Ä…
Przechodząc w powyższej nierówności z ą do 0, otrzymujemy żądana nierówność.
JeÅ›li u" " IntU, to dla dowolnego e " Rn istnieje µ0 o tej wÅ‚asnoÅ›ci, że u" + µe " U
dla |µ| < µ0. StosujÄ…c warunek (6) do punktów postaci u = u" + µe z µ " (0, µ0),
dostajemy
"J(u"), e e" 0
dla dowolnego e " Rn. To oznacza, że "J(u") = 0.
Załóżmy teraz, że funkcja J jest wypukła i spełniony jest warunek (6). Wówczas,
z warunku (5) zastosowanego do punktu v = u" otrzymujemy
J(u) - J(u") e" "J(u")), u - u" e" 0
dla dowolnego u " U, co oznacza, że u" jest punktem minimum globalnego.
Uwaga 21 Druga część powyższego kryterium optymalności jest uogólnieniem odwróce-
nia twierdzenia Fermata (przy założeniach wypukłości i gładkości funkcji J).
1.2.5 Metody numeryczne - metoda gradientowa
Rozważmy zadanie bez ograniczeń
Å„Å‚
òÅ‚
J(u) min
,
ół
u " Rn
zakładając, że funkcja J : Rn R jest klasy C1.
Korzystając z definicji różniczkowalności funkcji J oraz nierówności Cauchy ego
- Buniakowskiego (- |"J(u)| |v| d" "J(u), v d" |"J(u)| |v| dla dowolnego v " Rn,
przy czym jeśli "J(u) = 0, to prawa nierówność jest równością tylko dla v =

ą"J(u), a lewa nierówność - tylko dla v = -ą"J(u), gdzie ą e" 0), można pokazać,
że jeśli "J(u") = 0, to kierunkiem najszybszego spadku wartości funkcji J w punkcie

13
u" jest kierunek antygradientu -"J(u") (tzn. dla dowolnego h " Rn \ {0}, h =

-"J(u"), |h| = |"J(u")|, istnieje Ä1 > 0 takie, że
J(u" + Ä(-"J(u"))) < J(u" + Äh)
dla 0 < Ä < Ä1). Na tym spostrzeżeniu opiera siÄ™ konstrukcja tzw. metody gradien-
towej - metody wyznaczania przybliżonych rozwiązań powyższego zadania. Podamy
teraz opis jednego z wariantów tej metody.
Niech dany będzie dowolny punkt u0 " Rn. Rozważmy ciąg (uk)k"N*"{0} określony
w sposób rekurencyjny wzorem
uk+1 = uk - Ä…k"J(uk), k = 0, 1,..., (7)
gdzie Ä…k > 0 dla k = 0,1, ... jest tzw. krokiem k-tej iteracji.
Uwaga 22 Jeśli "J(uk) = 0, to ąk > 0 można wybrać tak, by spełniona była

nierówność J(uk+1) < J(uk) (1). Jeśli "J(uk) = 0, to postępowanie należy prz-
erwać (ciąg tworzony zgodnie z powyższym wzorem będzie stały). Punkt uk jest
wówczas punktem spełniającym warunek konieczny istnienia minimum funkcji J na
przestrzeni Rn. Warto przypomnieć, że gdy funkcja J jest wypukła, każdy punkt, w
którym gradient zeruje się, jest punktem minimum globalnego funkcji J na Rn.
Sposób ustalania wartości parametru ąk wyznacza wariant metody gradientowej.
Opiszemy teraz dwa takie warianty. Symbolem Jk, k = 0, 1, ..., oznaczmy funkcjÄ™
postaci
Jk : [0, ") " Ä… - J(uk - Ä…"J(uk)) " R.
1
Z określenia różniczkowalności funkcji J w punkcie u:
J(u + h) = J(u) + "J(u), h + o(u, h), h " Rn,
wynika, że
J(uk+1) - J(uk) = Ä…k[- |"J(uk)|2 + ok(Ä…k)Ä…-1] < 0
k
dla dostatecznie małych wartości ąk > 0, gdzie ok(ą) = o(uk, -ą"J(uk))
14
Metodą najszybszego spadku nazywamy wariant, w którym krok ąk > 0 ustalany
jest na podstawie warunku
infJk(Ä…) = Jk(Ä…k) (8)
Ä…e"0
(zgodnie z Uwagą 22, jeśli powyższy kres dolny jest osiągany przez funkcję Jk oraz
"J(uk) = 0, to punktem realizującym ów kres jest punkt ąk > 0).

Przyklad 23 Rozważmy zadanie badane w Przykładach 13 i 15, z punktami v1 =
(1,2), v2 = (2, 4), v3 = (3, 3), t.zn.
2 2 2
J : R2 " u - u - v1 + u - v2 + u - v3 " R.
Jak zauważyliśmy w Przykładzie 13,
"J(u) = 2(3u - (v1 + v2 + v3)) = (6x - 12,6y - 18)
dla u = (x, y) " R2. Ustalmy punkt poczatkowy u0 = (0, 0). Wówczas, "J(u0) =
Û
(-12, -18) oraz
J0 : [0, ") " Ä… - J((0, 0) - Ä…"J(0, 0)) = J(12Ä…, 18Ä…)
= |(12Ä…, 18Ä…) - (1, 2)|2 + |(12Ä…, 18Ä…) - (2, 4)|2 + |(12Ä…, 18Ä…) - (3, 3)|2
= (12Ä… - 1)2 + (18Ä… - 2)2 + (12Ä… - 2)2 + (18Ä… - 4)2 + (12Ä… - 3)2 + (18Ä… - 3)2 " R
1
Jest to funkcja kwadratowa, która osiąga swój kres dolny w punkcie ą0 = . W
6
konsekwencji,
1
u1 = (0,0) - (-12,-18) = (2, 3)
6
oraz
"J(2, 3) = (6 · 2 - 12, 6 · 3 - 18) = (0,0).
Tworzenie kolejnych punktów ciągu (uk) należy przerwać, ponieważ począwszy od u1
ciąg ten będzie stały. Zauważmy też, że funkcja J jest wypukła, bowiem
"2J(u)h, h = 2 · 3 Ih, h = 6 |h|2 e" 0
15
dla dowolnych u " R2, h " R2. A więc z odwrócenia zasady Fermata (przy założeniu
wypukłości i gładkości) wynika, że punkt (2, 3) jest punktem minimum globalnego.
Jest to zgodne z konkluzją przykładów 13 i 15, ponieważ
1 1
u" = (v1 + v2 + v3) = (6, 9) = (2, 3).
3 3
Jeśli nie jest możliwe wyznaczenie punktu ąk spełniającego równość (8), to można
za Ä…k przyjąć punkt, który realizuje powyższy kres dolny z dokÅ‚adnoÅ›ciÄ… ´k > 0. A
mianowicie, niech dla dowolnego k = 0, 1,... liczba ąk > 0 będzie taka, że
infJk(Ä…) d" Jk(Ä…k) d" infJk(Ä…) + ´k. (9)
Ä…e"0 Ä…e"0
Z określenia kresu dolnego i z ciągłości funkcji Jk wynika, że ąk > 0 spełniające (9)
istnieje.
W monografii [V] udowodnione jest następujące
"
Twierdzenie 24 (o zbieżnoÅ›ci metody gradientowej) Załóżmy, że szereg ´k
k=0
jest zbieżny, funkcja J jest wypukła, różniczkowalna, przy czym gradient "J jest
funkcja spełniającą warunek Lipschitza na Rn, tzn. istnieje stała L e" 0 taka, że
Û
|"J(u) - "J(y)| d" L |u - y| , u, y " Rn.
Załóżmy też, że dla pewnego u0 zbiór M´(u0) = {u " Rn; J(u) d" J(u0) + ´},
"
gdzie ´ = ´k, jest ograniczony. Wówczas, J" = inf J(u) > -", U" = {u "
k=0
u"Rn
Rn; J(u) = J"} = ", ciąg (uk)k"N*"{0} określony warunkami (7)-(9) jest taki, że

lim J(uk) = J"
k"
oraz
lim Á(uk, U") = 0,
k"
gdzie Á(uk, U") = inf |uk - u|.
u"U"
Dowód. Fakt, że
J" = inf J(u) > -" oraz U" = {u " Rn; J(u) = J"} = "

u"Rn
16
wynika ze zwartoÅ›ci zbioru M´(u0), ciÄ…gÅ‚oÅ›ci J i twierdzenia Weierstrassa. OczywiÅ›-
cie U" ‚" M´(u0).
Jeśli "J(uk) = 0 dla pewnego k e" 0, to uk = uk+1 = ... i teza twierdzenia
jest oczywista na mocy Twierdzenia ??. Możemy więc założyć, że "J(uk) = 0 dla

dowolnego k e" 0. Ponieważ
J(uk+1) = Jk(Ä…k) d" infJk(Ä…) + ´k d" J(uk - Ä…"J(uk)) + ´k
Ä…e"0
dla dowolnego Ä… e" 0, to (2)
J(uk) - J(uk+1) e" J(uk) - J(uk - Ä…"J(uk)) - ´k
L L
e" Ä… |"J(uk)|2 - Ä…2 |"J(uk)|2 - ´k = Ä…(1 - Ä… ) |"J(uk)|2 - ´k
2 2
dla Ä… e" 0 i k = 0, 1, ... StÄ…d
L 1
J(uk) - J(uk+1) e" max Ä…(1 - Ä… ) |"J(uk)|2 - ´k = |"J(uk)|2 - ´k (10)
Ä…e"0
2 2L
dla k = 0,1, ... i w konsekwencji
J(uk+1) d" J(uk) + ´k (11)
dla k = 0,1, ... Ponieważ
J(uk) e" J" > -",
więc (3) istnieje granica
J" d" lim J(uk) < ".
2
Korzystamy tu z nierówności (zastosowanej do punktów u = uk - ą"J(uk), v = uk)
L
|J(u) - J(v) - "J(v), u - v | d" |u - v|2
2
prawdziwej dla dowolnych punktów u, v " U, o ile funkcja J jest różniczkowalna na zbiorze wy-
pukłym U i gradient "J jest lipschitzowski ze stałą L (por. [V, Lemat 2.3.1]).
3
Jesli ciąg liczbowy (ak) jeswt taki, że
ak+1 d" ak + ´k, k = 0, 1, ...
przy czym ´k e" 0, ´k < ", to istnieje granica limak < ". JeÅ›li ciÄ…g (ak) jest także ograniczony
z dołu, to limak " R.
17
W konsekwencji lim(J(uk) - J(uk+1)) = 0 i z (10) wynika, że lim"J(uk) = 0.
Zauważmy także, że z (11) wynika, iż
k-1
J(uk) d" J(u0) + ´k d" J(u0) + ´
i=0
dla dowolnego k = 1, 2, ..., t.zn.
uk " M´(u0) (12)
dla dowolnego k = 1, 2, ...
Zauważmy teraz, że dla dowolnego u" " U" z nierówności (5) wynika, iż
0 d" J(uk) - J" = J(uk) - J(u") d" "J(uk), uk - u"
d" |"J(uk)| |uk - u"| d" R |"J(uk)|
dla k = 1,2, ..., gdzie R jest staÅ‚Ä… ograniczajÄ…ca moduÅ‚y elementów zbioru M´(u0).
Ze zbieżności lim "J(uk) = 0 wynika, że
lim J(uk) = J".
Ze zwartoÅ›ci zbioru M´(u0) i (12) wynika, że istnieje podciÄ…g (uk ) ciÄ…gu (uk), który
i
jest zbieżny do pewnego punktu u " M´(u0). Z ciÄ…gÅ‚oÅ›ci J wynika, że J(u) = J", co
oznacza, że u " U" i tym samym lim Á(uk , U") = 0. StÄ…d wynika, że lim Á(uk, U") = 0
i
(wystarczy zaprzeczyć temu).
1.3 Funkcje wielu zmiennych - część II
1.3.1 Warunki konieczne - zasady mnożników Lagrange a
Rozważmy zadanie postaci
Å„Å‚
òÅ‚
J(u) inf ,
(13)
ół
u " U = {u " Rn; fi(u) = ¸, i = 1, ..., m}
gdzie J : Rn R, fi : Rn R, i = 1,...,m.
18
Mówimy, że punkt u" " U jest punktem lokalnego minimum dla zadania (13),
jeśli istnieje kula K(u", r) taka, że dla dowolnego punktu u " K(u", r), spełniającego
ograniczenia
fi(u) = ¸, i = 1, ..., m,
spełniona jest nierówność
J(u") d" J(u).
Przypomnijmy
Twierdzenie 25 (o funkcji uwikłanej) Niech dane będą funkcje gi = gi(w, z) :
Rs+n R, i = 1, ..., n, klasy C1 oraz punkt (a, b) " Rs+n taki, że
gi(a,b) = 0, i = 1,...,n
"gi
det[ (a, b)]1d"i,jd"n = 0.

"zj
Wówczas istnieje ´ > 0 i funkcja z = z(w) = (z1(w), ...,zn(w)) : K(a, ´) Rn klasy
C1 taka, że
z(a) = b,
gi(w, z(w)) = 0, w " K(a, ´), i = 1, ..., n.
Twierdzenie 26 (pierwsza zasada mnożników Lagrange a) Jeśli funkcje J, fi,
i = 1, ..., m, sÄ… klasy C1 na Rn i punkt u" jest punktem lokalnego minimum dla zada-
nia (13), to istnieją liczby (mnożniki Lagrange a) 0, 1, ..., m " R, nie wszystkie
równe zero i takie, że
m
0"J(u") + i"fi(u") = 0. (14)
i=1
Jeśli dodatkowo wektory "fi(u"), i = 1, ..., m, są liniowo niezależne, to 0 = 0 i

można przyjąć 0 = 1.
Dowód. Warunek dany w tezie twierdzenia oznacza liniową zależność wektorów
"J(u"), "f1(u"), ..., "fm(u")
19
w przestrzeni Rn. Przypuśćmy, że warunek ten nie jest spełniony, tzn. powyższe wek-
tory są liniowo niezależne. Oznacza to, że m+1 d" n. W przypadku, gdy m+1 < n
możemy uzupełnić (i uzupełniamy) układ wektorów "J(u"), "f1(u"), ..., "fm(u")
wektorami dm+1, ..., dn-1 tak, by układ wektorów "J(u"),"f1(u"), ..., "fm(u"), dm+1, ..., dn-1
był układem liniowo niezależnym w Rn.
Rozważmy teraz funkcje (gdy m+1 = n, nie rozważamy ostatniej grupy funkcji)
g0(t,u) = J(u) - J(u") + t,
gi(t, u) = fi(u), i = 1, ..., m,
gi(t, u) = di, u - u" , i = m + 1, ..., n - 1,
określone na R1+n. A
atwo widać, że powyższy układ funkcji spełnia założenia
twierdzenia o funkcji uwikłanej z punktem (a, b) postaci (0,u"). Z twierdzenia tego
wynika, że istnieje ´ > 0 i funkcja u = u(t) = (u1(t), ..., un(t)) : (-´, ´) Rn klasy
C1 (wykorzystamy tylko ciągłość funkcji u) taka, że
u(0) = u"
oraz
J(u(t)) = J(u") - t,
fi(u(t)) = 0, i = 1, ..., m,
dla t " (-´, ´). To oznacza w szczególnoÅ›ci, że dla t " (0, ´) punkty u(t) speÅ‚niajÄ…
ograniczenia typu równości występujące w zadaniu (13), przy czym
J(u(t)) = J(u") - t < J(u").
Przeczy to optymalności punktu u", gdyż u(t) u", gdy t 0.
Przypuśćmy teraz, że 0 = 0. Wówczas
m
i"fi(u") = 0
i=1
przy czym i = 0 dla pewnego i " {1, ..., m}. Jest to sprzeczne z liniowÄ… nieza-

leżnością wektorów "fi(u"), i = 1,...,m.
20
Przyklad 27 Należy znalez
ć na okręgu jednostkowym w przestrzeni Rn, o środku
w punkcie 0, punkt, dla którego suma kwadratów odległości od danych punktów
v1,...,vm " Rn jest najmniejsza. Innymi słowy, należy znalez
ć punkt minimum glob-
alnego funkcji
m
2
J(u) = u - vi
i=1
na zbiorze opisanym równością
f1(u) = |u|2 - 1 = 0. (15)
Z twierdzenia Weierstrassa wynika, że funkcja J osiaga na zbiorze opisanym równoś-
Û
cią (15) minimum globalne, które jest oczywiście też minimum lokalnym. Jeśli u jest
tym punktem, to istnieja mnożniki Lagrange a 0, " R, nie wszystkie równe zero i
Û
takie, że
0"J(u") + 1"f1(u") = 0,
czyli
02m(u - u") + 12u = 0, (16)
m
1
gdzie u" = vi.
i=1
m
Przypadek 0 = 0 jest niemożliwy, bo (0, 1) = 0 i |u|2 = 1. Można więc założyć,

że 0 = 1.
Rozważmy dwa przypadki.
10 u" = 0. Z (16) wynika, że

(m + )u = mu". (17)
Stąd z kolei wynika, że u = 0 oraz u = ąu" dla pewnego ą = 0. Wówczas

1 = |u| = |Ä…| |u"| ,
skÄ…d
1
|Ä…| =
|u"|
21
i w konsekwencji
u" u"
u = lub u = - .
|u"| |u"|
Ponieważ
2
m
J(u) = m |u|2 - 2m u, u" + vi (18)
i=1
u"
więc widać, że rozwiązaniem jest punkt u = .
|u"|
20 u" = 0. Wówczas z (18) wynika, że funkcja J jest stała na zbiorze (15) i, w
konsekwencji, każdy punkt okręgu jednostkowego jest punktem minimum globalnego
funkcji J na tymże okręgu.
Uwaga 28 Fakt, że 0 = 0 można zauważyć, korzystając z drugiej części zasady

mnożników Lagrange a. Rzeczywiście, "f1(u) = 2u i jeśli u jest punktem minimum
lokalnego na okręgu jednostkowym, to w szczegolności u = 0 i jednoelementowy układ

"f1(u) jest układem liniowo niezależnym.
Rozważmy teraz zadanie z ograniczeniami mieszanymi
Å„Å‚
òÅ‚
J(u) inf ,
(19)
ół
u " U = {u " Rn; fi(u) = ¸, i = 1, ..., m, hk(u) d" 0, k = 1, ..., s}
Wprowadzając nowe zmienne w1,...,ws, rozwiązywanie zadania (19) można zastąpić
rozwiÄ…zywaniem zadania postaci
Å„Å‚
ôÅ‚
ôÅ‚
J (u, w) = J(u) inf
ôÅ‚
òÅ‚
, (20)
f i(u, w) = fi(u) = ¸, i = 1, ..., m
ôÅ‚
ôÅ‚
ôÅ‚
ół 2
hk(u, w) = wk + hk(u) = 0, k = 1,...,s
gdzie w = (w1, ...ws). Dokładniej, jeśli punkt u" jest punktem lokalnego minimum
" " "
dla zadania (19), to punkt (u", w"), gdzie w" = (w1,...,ws), wk = -hk(u"), k =
1, ..., s, jest punktem lokalnego minimum dla zadania (20). Na odwrót, jeśli punkt
(u", w") jest punktem lokalnego minimum dla zadania (20), to punkt u" jest punktem
lokalnego minimum dla zadania (19).
22
Przyklad 29 Znalez
ć na kuli jednostkowej o środku w punkcie 0 punkt, dla którego
suma kwadratów odległości od danych punktów v1,...,vm " Rn jest najmniejsza. In-
nymi słowy, należy znalez
ć punkt minimum globalnego funkcji
m
2
J(u) = u - vi
i=1
na zbiorze opisanym nierównościa
Û
f1(u) = |u|2 - 1 d" 0. (21)
Z twierdzenia Weierstrassa wynika, że taki punkt istnieje.
Z Przykładu 13 wynika, że punktem globalnego minimum funkcji J na przestrzeni
m
1
Rn jest punkt u" = ui. Jeśli więc |u"| d" 1, to jest to punkt globalnego
i=1
m
minimum na zbiorze opisanym nierównością (21).
Załóżmy więc, że |u"| > 1. Wprowadz
my pomocnicza zmiennÄ… w i wyznaczmy
Û
punkty "podejrzane" o minimum lokalne funkcji
m
2
J(u, w) = u - vi
i=1
na zbiorze opisanym równością
h1(u,w) = w2 + |u|2 - 1 = 0. (22)
Z postaci funkcji J i h1 wynika, że
0"J(u, w) + 1" h1(u,w) = (02m(u - u") + 12u, 12w).
Z zasady mnożników Lagrange a wynika więc, że jeśli punkt (u, w) jest punktem
minimum lokalnego funkcji J na zbiorze opisanym równością (22), to istnieje punkt
(0, 1) taki, że
0m(u - u") + 1u = 0,
1w = 0,
w2 + |u|2 = 1,
23
(0, 1) = 0.

Przy 0 = 0 powyższy układ (równań i nierówności) nie posiada rozwiazania. Za-
Û
łóżmy więc, że 0 = 1. Wówczas
(m + 1)u = mu", 1w = 0, w2 + |u|2 = 1
i, jak założyliśmy,
|u"| > 1.
Przypadek 1 = 0 jest niemożliwy. Jeśli natomiast 1 = 0, to w = 0 i w kon-

sekwencji  podejrzanymi punktami lokalnego minimum dla zadania pomocniczego
u" u"
są dwa punkty (|u |, 0) oraz (-|u |, 0). Oznacza to, że rozwiązaniem zadania wyjś-
" "
u" u"
ciowego jest punkt lub -|u |. Z postaci (18) funkcji J wynika, że jedynym
|u"|
"
u"
rozwiazaniem zadania wyjściowego jest punkt .
Û
|u"|
Prawdziwe jest także następujące
Twierdzenie 30 (druga zasada mnożników Lagrange a) Jeśli funkcje J, fi,
i = 1,...,m, hk, k = 1, ..., s sÄ… klasy C1 na Rn i punkt u" jest punktem lokalnego
minimum dla zadania (19), to istniejÄ… mnożniki Lagrange a 0, 1, ..., m, µ1, ..., µs "
R, nie wszystkie równe zero i takie, że
0 e" 0, µ1 e" 0, ..., µs e" 0
m s
0"J(u") + i"fi(u") + µk"hk(u") = 0
i=1 k=1
µkhk(u") = 0, k = 1,...,s.
Przyklad 31 Znalez
ć punkt minimum globalnego funkcji
m
2
J(u) = u - vi
i=1
na zbiorze opisanym nierównościa
Û
h1(u) = |u|2 - 1 d" 0
24
przy pomocy drugiej zasady mnożników Lagrange a. Jak zostało już stwierdzone, z
klasycznego twierdzenia Weierstrassa wynika, że powyższe zadanie posiada rozwiązanie,
przy czym jeśli |u"| d" 1, to rozwiązaniem tym jest u".
Załóżmy więc, że |u"| > 1. Z Twierdzenia 30 wynika, że jeśli u jest punktem
minimum lokalnego, to istnieja mnożniki Lagrange a 0 e" 0, 1 e" 0, nie znikające
Û
jednocześnie i takie, że
0"J(u) + 1"h1(u) = 02m(u - u") + 21u = 0,
1(|u|2 - 1) = 0 (23)
i
|u| d" 1.
Przypadek 0 = 0 jest niemożliwy, więc możemy założyć, że 0 = 1. Zatem pierwszą
z powyższych nierówności możemy zapisać w postaci
(m + 1)u = mu".
Stąd wynika, że u = ąu", skąd
1
|Ä…| |u"| d" 1, czyli |Ä…| d"
|u"|
1
(bo |u| d" 1). Przypuśćmy, że |ą| < . Wówczas
|u"|
1
|u|2 - 1 = |Ä…|2 |u"|2 - 1 < |u"|2 - 1 = 0,
|u"|2
skąd, wobec (23),  = 0 i w konsekwenscji u = u", co jest niemożliwe, bowiem
1 u" u"
|u"| > 1. Zatem |ą| = , czyli punktami  podejrzanymi są lub -|u |. Znów z
|u"| |u"|
"
u"
postaci (18) funkcji J wynika, że jedynym rozwiązaniem zadania jest punkt .
|u"|
1.3.2 Warunki dostateczne
Twierdzenie 32 Niech dane będzie zadanie
Å„Å‚
òÅ‚
J(u) inf ,
ół
u " U = {u " Rn; fi(u) = ¸, i = 1, ..., m}
25
Załóżmy, że funkcje J, fi, i = 1,...,m są klasy C2 na Rn, t.zn. maja na Rn ciągłe
Û
wszystkie pochodne czastkowe do rzędu drugiego włącznie. Jeśli istnieje punkt u" " U
Û
i mnożniki Lagrange a 0, 1, ..., m " R nie wszystkie równe zero i takie, że 0 e" 0,
spełniony jest warunek
m
0"J(u") + i"fi(u") = 0
i=1
oraz
m
"2J "2fi
(0[ (u")]1d"j,kd"n + i[ (u")]1d"j,kd"n)h, h > 0 (< 0)
"uj"uk "uj"uk
i=1
dla wszystkich h = 0 takich, że

"J(u"),h d" 0 (e" 0), (24)
"fi(u"), h = 0, i = 1,...,m, (25)
to u" jest punktem ścisłego lokalnego minimum (maksimum) funkcji J na zbiorze U.
Dowód. Załóżmy, że dla punktu u" spełnione są założenia twierdzenia i przy-
puśćmy, że punkt ten nie jest punktem ścisłego minimum lokalnego. Istnieje wówczas
ciąg (uk) taki, że
uk = u",

f1(uk) = 0, ..., fm(uk) = 0,
J(uk) d" J(u")
dla k = 1,2, ... i uk u", gdy k ". Punkt uk można zapisać w postaci
uk - u"
uk = u" + |uk - u"| = u" + tkek,
|uk - u"|
uk-u"
gdzie tk = |uk - u"| 0, ek = . Ponieważ |ek| = 1 dla k = 1, 2, ..., bez
|uk-u"|
zmniejszania ogólności rozważań można założyć, że istnieje punkt e0 taki, że ek e0,
|e0| = 1.
26
Z różniczkowalności funkcji J, fi, i = 1,...,m otrzymujemy
0 e" J(uk) - J(u") = "J(u"), ek tk + o0(uk - u"),
0 = fi(uk) - fi(u") = "fi(u"), ek tk + oi(tk)
dla i = 1, ..., m, k = 1,2, ... (tutaj oi(u) dla i = 0,1, ..., m jest taką funkcją, że
oi(u)
0, gdy |u| 0). Dzieląc obie strony powyższych równości i nierówności
|u|
przez tk i przechodzÄ…c do granicy, otrzymujemy
0 e" "J(u"), e0 ,
0 = "fi(u"),e0 .
A więc punkt e0 spełnia warunki (24), (25).
Oznaczmy teraz
m
L(u) = 0J(u) + ifi(u), u " Rn.
i=1
Jest to oczywiście funkcja klasy C2 taka, że "L(u") = 0. Ponadto,
m
L(uk) = 0J(uk) + ifi(uk) = 0J(uk) d" 0J(u")
i=1
m
= 0J(u") + ifi(u") = L(u")
i=1
dla k = 1,2, ... Stąd i z dwukrotnej różniczkowalności L otrzymujemy
1
0 e" L(uk) - L(u") = t2 "2L(u")ek, ek + Ä…(uk - u")
k
2
Ä…(u)
dla k = 1, 2, ... (tutaj ą(u) jest taką funkcją, że 0, gdy |u| 0). Dzieląc
|u|2
powyższą nierówność stronami przez t2 i przechodząc do granicy, otrzymujemy
k
m
"2J "2fi
(0[ (u")]1d"j,kd"n + i[ (u")]1d"j,kd"n)e0, e0 = "2L(u")e0,e0 d" 0,
"uj"uk "uj"uk
i=1
przy czym, przypomnijmy,
0 e" "J(u"), e0 ,
0 = "fi(u"), e0 , i = 1, ..., m.
Jest to sprzeczne z założeniem twierdzenia i tym samym kończy dowód twierdzenia.
27
Uwaga 33 KorzystajÄ…c z warunku dostatecznego zamiast twierdzenia Weierstrassa
w Przykladzie 27, można wykazać, że, gdy u" = 0, znaleziony punkt podejrzany u =

u"
jest punktem minimum globalnego. Istotnie, w tym przypadku mamy (0 = 1,
|u"|
1 = m(|u"| - 1)) i w konsekwencji
m
"2J u" "2fi u"
0[ ( )]1d"j,kd"n+ i[ ( )]1d"j,kd"n) = 2mI+2m(|u"|-1)I = 2m |u"| I.
"uj"uk |u"| "uj"uk |u"|
i=1
Jest to macierz dodatnio określona, więc z powyższego twierdzenia o warunkach
u"
dostatecznych wynika, że u = jest punktem ścisłego lokalnego minimum funkcji
|u"|
u"
J na zbiorze U. Tak samo można pokazać, że u = -|u | jest punktem ścisłego
"
u"
maksimum lokalnego. Zatem, u = jest jedynym punktem minimum lokalnego.
|u"|
1.3.3 Założenie wypukłości - twierdzenie Kuhna-Tuckera
Rozważmy następujące zadanie
Å„Å‚
òÅ‚
J(u) inf ,
(26)
ół
u " U = {u " Rn; u " A, fi(u) d" ¸, i = 1, ..., m}
gdzie A ‚" Rn, J, fi : Rn R, i = 1, ..., m.
Mówimy, że punkt u" " U jest rozwiązaniem globalnym zadania (26), jeśli
J(u") d" J(u)
dla dowolnego u " U.
Dowód kolejnego twierdzenia oparty jest na nastepującym klasycznym wyniku o
odzielaniu.
Lemat 34 Niech D będzie niepustym wypukłym podzbiorem przestrzeni Rm takim,
że 0 " D. Wówczas istnieje wektor (a1,...,am) " Rm \ {0} taki, że
/
m
aixi e" 0
i=1
dla dowolnego (x1, ..., xm) " D.
28
Poniższe twierdzenie pokazuje, że także w przypadku zadania (26), przy do-
datkowych założeniach wypukłości, warunek konieczny istnienia minimum jest warunk-
iem dostatecznym
Twierdzenie 35 (Kuhna-Tuckera) Niech J, f1,...,fm : Rn R będa funkcjami
Û
wypukÅ‚ymi i A ‚" Rn - zbiorem wypukÅ‚ym. JeÅ›li u" jest rozwiÄ…zaniem globalnym zada-
nia (26), to istnieją mnożniki Lagrange a 0 e" 0, 1 e" 0,...,m e" 0 nie znikające
jednocześnie i takie, że
m m
0J(u") + ifi(u") = min(0J(u) + ifi(u)) (27)
u"A
i=1 i=1
ifi(u") = 0, i = 1,...m. (28)
Jesli ponadto istnieje punkt u " A taki, że
fi(u) < 0, i = 1,...,m, (29)
to 0 = 0 i można przyjać 0 = 1. Na odwrót, jeśli istnieją 0 > 0, 1 e" 0,...,m e" 0
Û
i punkt u" " U taki, że
m m
0J(u") + ifi(u") = min(0J(u) + ifi(u)),
u"A
i=1 i=1
ifi(u") = 0, i = 1, ...m,
to u" jest rozwiÄ…zaniem globalnym zadania (26).
Dowód twierdzenia. Konieczność. Niech u" będzie rozwiązaniem globalnym
zadania (26). Bez zmniejszania ogólności rozważań możemy założyć, że
J(u") = 0.
Rozważmy następujący zbiór
C = {µ = (µ0, µ1, ..., µm) " R1+m; istnieje punkt u " A taki, że
J(u) < µ0 oraz fi(u) d" µi dla i = 1, ..., m}.
29
Zbiór C jest niepusty. Istotnie, wystarczy rozważyć punkt µ = (1, 0, ..., 0),
który należy do C, bowiem J(u") = 0 < 1, fi(u") d" 0, i = 1,...,m oraz u" " A.
Zbiór C jest wypukÅ‚y. Istotnie, niech (µ1,µ1, ..., µ1 ) " C, (µ2,µ2,...,µ2 ) " C,
0 1 m 0 1 m
u1, u2 " A będą takie, że
J(u1) < µ1, J(u2) < µ2,
0 0
fi(u1) d" µ1, fi(u2) d" µ2, i = 1, ...m.
i i
Wówczas, dla dowolnego ą " (0, 1) mamy
Ä…u1 + (1 - Ä…)u2 " A
J(Ä…u1 + (1 - Ä…)u2) d" Ä…J(u1) + (1 - Ä…)J(u2) < Ä…µ1 + (1 - Ä…)µ2,
0 0
fi(Ä…u1 + (1 - Ä…)u2) d" Ä…fi(u1) + (1 - Ä…)fi(u2) d" Ä…µ1 + (1 - Ä…)µ2, i = 1, ..., m.
i i
Oznacza to, że
Ä…(µ1, µ1,...,µ1 ) + (1 - Ä…)(µ2,µ2,...,µ2 ) " C.
0 1 m 0 1 m
0 " C. Istotnie, w przeciwnym bowiem razie istniałby punkt u " A taki, że
/
J(u) < 0,
fi(u) d" 0, i = 1, ...m,
co przeczyłoby temu, że u" jest rozwiązaniem zadania (26).
Zatem, z twierdzenia o oddzielaniu wynika istnienie punktu (0, 1, ..., m) "
R1+m {0} takiego, że
m
iµi e" 0 (30)
i=0
dla (µ0,µ1, ..., µm) " C.
ie" 0, i = 0,1, ...,m. Istotnie, ustalmy bowiem dowolne µ > 0, wskaz
nik i0 "
{0, 1, ..., m} i rozważmy punkt postaci µµ = (µ, ..., µ, 1, µ, ..., µ) " R1+m, którego i0-
owa współrzÄ™dna jest równa 1. OczywiÅ›cie, µµ " C (wystarczy rozważyć punkt
u" " A). A więc z ostatniej nierówności
m
i e" -µ i,
0
i=0, i =i0
30
co, wobec dowolnoÅ›ci µ > 0, oznacza, że i e" 0.
0
Mnożniki i, i = 1, ...,m, spełniają warunek (28). Ustalmy dowolny wskaz
nik
i0 " {1, ..., m}. Jeśli fi (u") = 0, to oczywiście i fi (u") = 0. Przypuśćmy więc,
0 0 0
że fi (u") < 0 i rozważmy punkt µ´ = (´,0, ..., 0,fi (u"), 0,...,0) " R1+m z dowol-
0 0
nie ustalonÄ… liczbÄ… ´ > 0 i i0-owÄ… współrzÄ™dnÄ… równÄ… fi (u"). OczywiÅ›cie µ´ " C
0
(wystarczy rozważyć punkt u" " A). Z nierówności (30) wynika, że
i fi (u") e" -0´,
0 0
co, wobec dowolnoÅ›ci ´ > 0, oznacza, że
i fi (u") e" 0,
0 0
czyli i d" 0. Wobec faktu, że i e" 0, mamy więc równość i = 0 i w konsekwencji
0 0 0
i fi (u") = 0.
0 0
Spełniony jest warunek (27). Niech u " A. Rozważmy punkt postaci (J(u)+
´, f1(u),...,fm(u)) " R1+m, gdzie ´ > 0 jest dowolnie ustalone. OczywiÅ›cie punkt ten
należy do zbioru C (wystarczy rozważyć punkt u). Zatem, korzystając z nierówności
(30), mamy
m
0J(u) + ifi(u) e" -0´.
i=1
StÄ…d, wobec dowolnoÅ›ci ´ > 0,
m
0J(u) + ifi(u) e" 0
i=1
dla u " A. Ponadto z (28) i faktu, że J(u") = 0 mamy
m
0 = 0J(u") + ifi(u"). (31)
i=1
A więc
m m
0J(u") + ifi(u") = min(0J(u) + ifi(u)). (32)
x"A
i=1 i=1
31
Przypuśćmy teraz, że spełniony jest warunek (29), t.zn. istnieje punkt u " A taki,
że
fi(u) < 0, i = 1, ..., m,
oraz 0 = 0. Wówczas z (31) wynika, że
m m
0J(u) + ifi(u) = ifi(u)
i=1 i=1
m m
< 0 = ifi(u") = 0J(u") + ifi(u"),
i=1 i=1
co jest sprzeczne z (32). Zatem 0 > 0.
Dostateczność. Załóżmy, że istnieją mnożniki 0,1,...,m e" 0 takie, że 0 > 0
i spełnione są warunki (27), (28), przy czym u" " A, f1(u") d" 0,...,fm(u") d" 0.
Bez zmniejszania ogólności rozważań możemy założyć, że 0 = 1. Wówczas, dla
dowolnego u " A takiego, że fi(u) d" 0, i = 1, ..., m, mamy
m m
J(u) e" J(u) + ifi(u) e" J(u") + ifi(u") = J(u").
i=1 i=1
Oznacza to, wobec dowolności u " A takiego, że fi(u) d" 0, i = 1,...,m, iż u" jest
rozwiÄ…zaniem globalnym zadania (26).
Uwaga 36 A
atwo widać, że przy założeniach wypukłości (podobnie, jak wcześniej)
każde rozwiazanie lokalne zadania (26) jest jego rozwiązaniem globalnym.
Û
Z faktu, że w przypadku funkcji wypukłej na przestrzeni Rn punkt, w którym
jest ona różniczkowalna jest punktem minimum globalnego wtedy i tylko wtedy, gdy
gradient w tym punkcie znika, wynika następujący
Wniosek 37 Niech J, f1,...,fm : Rn R będą funkcjami wypukłymi i różniczkowal-
nymi w punkcie u". Jeśli u" jest rozwiązaniem globalnym zadania (26) ze zbiorem
A = Rn, to istnieja mnożniki Lagrange a 0 e" 0, 1 e" 0,...,m e" 0 nie znikające
Û
jednocześnie i takie, że
m
0"J(u") + i"fi(u") = 0,
i=1
32
ifi(u") = 0, i = 1,...m.
Jeśli ponadto istnieje punkt u " Rn taki, że
fi(u) < 0, i = 1,...,m,
to 0 = 0 i można przyjąć 0 = 1.

Na odwrót, jeśli istnieja 0 > 0, 1 e" 0,...,m e" 0, takie, że
Û
m
0"J(u") + i"fi(u") = 0,
i=1
ifi(u") = 0,i = 1,...m,
f1(u") d" 0, ..., fm(u") d" 0,
to u" jest rozwiÄ…zaniem globalnym zadania (26) ze zbiorem A = Rn.
Drugą część powyższego twierdzenia można traktować jako odwrócenie drugiej
zasady mnożników Lagrange a (przy założeniu wypukłości).
Przyklad 38 Rozważmy zadanie z Przykładu 31:
Å„Å‚
m
òÅ‚
J(u) = |u - vi|2 min.,
i=1
ół
u " U = {u " Rn; h1(u) = |u|2 - 1 d" ¸}
m
1
w przypadku, gdy |u"| > 1, gdzie u" = vi KorzystajÄ…c z przeprowadzonej
m
i=1
tam analizy i nie korzystając z twierdzenia Weierstrassa, stwierdzamy, że punktami
u" u"
"podejrzanymi" sa i -|u |, przy czym odpowiednie mnożniki Lagrange a (1)
Û
|u"|
"
wynosza m(|u"| - 1), m(- |u"| - 1), odpowiednio; oczywiście 0 = 1 w obu przypad-
Û
kach. A
atwo widać, że "trójka"
u"
0 = 1, 1 = m(|u"| - 1),
|u"|
spełnia warunki dane w drugiej części powyższego wniosku i tym samym jest rozwiazaniem
Û
u"
zadania. Aby stwierdzić, że punkt -|u | nie jest rozwiązaniem wystarczy na przykład
"
porównać wartości funkcji J w obu znalezionych punktach.
33
1.3.4 Metody numeryczne - metoda projekcji gradientu
Mówimy, że funkcja J : U R, gdzie U jest wypukłym podzbiorem Rn, jest silnie
wypukÅ‚a, jeÅ›li istnieje staÅ‚a º > 0 taka, że
J(Ä…u + (1 - Ä…)v) d" Ä…J(u) + (1 - Ä…)J(v) - Ä…(1 - Ä…)º |u - v|2
dla Ä… " [0, 1], u, v " U. Można pokazać, że J jest silnie wypukÅ‚a na U ze staÅ‚Ä… º
wtedy i tylko wtedy, gdy funkcja g(u) = J(u) - º|u|2 jest wypukÅ‚a na U.
Symbolem PU(u) oznaczamy rzut punktu u " Rn na wypukły i domknięty zbiór
U ‚" Rn, t.zn. punkt należący do zbioru U i speÅ‚niajÄ…cy warunek
|u - PU(u)| = inf |u - v| .
v"U
Metodę projekcji gradientu, służącą do numerycznego rozwiązywania minimaliza-
cyjnych zadań z ograniczeniami, opisuje poniższe twierdzenie. Dowód tego twierdzenia
można znalez
ć w [V].
Twierdzenie 39 (o zbieżnoÅ›ci metody projekcji gradientu) Niech U ‚" Rn
będzie zbiorem wypukłym i domkniętym, J : U R - funkcjonałem klasy C1,
ograniczonym z dołu, którego gradient spełnia warunek Lipschitza (ze stałą L). Jeśli
(uk) ‚" Rn jest ciÄ…giem okreÅ›lonym wzorem rekurencyjnym
uk+1 = PU(uk - Ä…k"J(uk)), k = 0, 1,..., (33)
przy dowolnie ustalonym u0 " U, gdzie parametr ąk, k = 0,1, ..., jest taki, że
2
µ0 d" Ä…k d" (34)
L + 2µ
(tutaj µ0, µ sÄ… ustalonymi dodatnimi parametrami metody), to ciÄ…g (J(uk)) jest
nierosnÄ…cy oraz
lim uk - uk+1 = 0. (35)
k"
Jeśli, dodatkowo, J jest silnie wypukły na U, to ciąg (uk) jest zbieżny do u" - jedynego
punktu minimum funkcji J na U, przy czym istnieje stała c e" 0 taka, że
c
2
uk - u" d" , k = 1, 2, ... (36)
k
34
Uwaga 40 Stałą c można wyznaczyć (por. [V]).
Przyklad 41 Rozważmy zadanie
Å„Å‚
òÅ‚
J(u = (u1, u2)) = (u1 - 1)2 + (u2 + 1)2 min,
ół
u " U = {u = (u1, u2) " R2; f1(u) = -u1 d" ¸, f2(u) = -u2 d" ¸}
Aby rozwiazać to zadanie, zastosujemy metodę projekcji gradientu, z punktem poczatkowym
Û Û
u0 = (0, 0).
Zauważmy, że gradient "J(u1, u2) = (2(u1 - 1), 2(u2 + 1)) funkcji J spełnia
warunek Lipschitza ze stałą L = 2:
"J(u1,u2) - "J(v1, v2) = (2(u1 - 1), 2(u2 - 1)) - (2(v1 - 1), 2(v2 - 1))
= (2(u1 - v1),2(u2 - v2)) = 2 (u1, u2) - (v1, v2) .
1 1
PrzyjmujÄ…c µ0 = , µ = 3 widać, że musi być Ä…k = dla dowolnego k = 0, 1, ...
4 4
Mamy
"J(u0) = "J(0, 0) = (-2, 2)
i w konsekwencji
1 1 1 1 1
u1 = PU((0,0) - (-2, 2)) = PU( , - ) = ( ,0) = (1 - ( )1,0).
4 2 2 2 2
Podobnie,
1
"J(u1) = "J( , 0) = (-1, 2)
2
i w konsekwencji
1 1 3 1 3 1
u2 = PU(( ,0) - (-1, 2)) = PU( , - ) = ( ,0) = (1 - ( )2,0).
2 4 4 2 4 2
Pokażemy, korzystając z zasady indukcji matematycznej, że
1
uk = (1 - ( )k, 0), k = 0, 1, ...
2
35
Istotnie, wzór jest prawdziwy dla k = 0. Załóżmy, że jest prawdziwy dla ustalonej
liczby naturalnej k e" 0. Wówczas,
1 1 1
uk+1 = PU(uk - Ä…k"J(uk)) = PU((1 - ( )k, 0) - (2(1 - ( )k) - 2, 2 · 0 + 2)
2 4 2
1 1 1 1 1 1 1 1 1
= PU(1 - ( )k - (1 - ( )k) + · 2), 0 - · 2) = PU(1 - ( )k + ( )k, - )
2 2 2 4 4 2 2 2 2
1 1 1 1 1 1
= PU(1 - ( )k(1 - ), - ) = PU(1 - ( )k+1, - ) = (1 - ( )k+1,0)
2 2 2 2 2 2
Zatem, korzystając z silnej wypukłości funkcji J na zbiorze U, a nawet R2 (bo
J(u1, u2) - |(u1, u2)|2 = -2u1 + 2u2 + 2), stwierdzamy, że ciąg (uk) jest zbieżny
do jedynego rozwiÄ…zania u". Tym samym
1
u" = lim uk = lim(1 - ( )k,0) = (1, 0).
2
36


Wyszukiwarka

Podobne podstrony:
Badania operacyjne w logistyce wykład 4
[W] Badania Operacyjne Zagadnienia transportowe (2009 04 19)
badania operacyjne 9
zarzadzanie projektami badania operacyjne metoda cpm
symulacja pracy zbiornika retencyjnego w czorsztynie w programie vensim ple badania operacyjne
badania operacyjne 6
przykładowe zadania badania operacyjne
badania operacyjne ii
M Gruszczyński, M Podgórska Ekonometria i badania operacyjne Podręcznik dla studiów licencjackich
[W] Badania Operacyjne Programowanie calkowitoliczbowe (2009 04 19)

więcej podobnych podstron