Idczak D Badania operacyjne w logistyce

Badania Operacyjne w Logistyce

kierunek Informatyka, studia I stopnia, III rok

wyklad

Programowanie nieliniowe

1.1

Funkcje jednej zmiennej

W rozdziale tym przypomnimy wybrane fakty dotycz ˛

ace minimalizacji funkcji jednej

zmiennej.

1.1.1

Istnienie rozwi ˛

aza´

n - twierdzenie Weierstrassa

Rozwa˙zmy zadanie postaci







J(u) → min .,

u ∈ U

(1)

gdzie J : U → R, U ⊂ R jest ustalonym zbiorem.

Punkt u

∗

∈ U nazywamy punktem lokalnego minimum funkcji J na zbiorze U

(lokalnym rozwi ˛

azaniem zadania (1)), je´sli istnieje przedział otwarty V , zawieraj ˛

acy

punkt u

∗

, taki, ˙ze

J(u

∗

) ≤ J(u)

dla dowolnego u ∈ V ∩ U. Punkt u

∗

∈ U nazywany jest punktem minimum global-

nego funkcji J na zbiorze U , gdy powy˙zsza nierówno´s´c jest spełniona przez wszystkie

punkty u ∈ U . Zbiór wszystkich punktów minimum globalnego funkcji J na zbiorze

U oznaczamy symbolem U

∗

. Kres dolny warto´sci funkcji J na zbiorze U oznaczamy

symbolem J

∗

, t.zn. J

∗

= inf

∈U

J(u).

Zanim sformułujemy klasyczne twierdzenie o istnieniu punktu minimum global-

nego, podamy okre´slenie funkcji półci ˛

agłej z dołu.

Mówimy, ˙ze funkcja J : U → R jest półci ˛agła z dołu w punkcie u

∈ U, je´sli dla

dowolnego ε > 0 istnieje przedział otwarty V , zawieraj ˛

acy punkt u

, taki, ˙ze

J(u

) − ε ≤ J (u)

dla dowolnego u ∈ V ∩ U . Mówimy, ˙ze J jest półci ˛agła z dołu na zbiorze U, je´sli

jest półci ˛

agła w ka˙zdym punkcie u ∈ U.

Mo˙zna pokaza´c, ˙ze funkcja J : U → R jest półci ˛agła z dołu w punkcie u

∈ U

wtedy i tylko wtedy, gdy dla dowolnego ci ˛

agu (u

) ⊂ U takiego, ˙ze lim

→∞

= u

zachodzi

J(u

) ≤ lim inf

→∞

J(u

Klasycznym wynikiem jest nast ˛epuj ˛

ace twierdzenie o istnieniu minimum global-

nego funkcji jednej zmiennej, nazywane twierdzeniem Weierstrassa.

Twierdzenie 1 (Weierstrassa) Je´sli funkcja J : [a, b] → R jest półci ˛

agł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 ˛epuj ˛

aca zasada Fermata.

Twierdzenie 2 (Fermata) Je´sli u

∗

jest punktem lokalnego minimum funkcji J:(a, b) →

i funkcja J ma w punkcie u

∗

pochodn ˛

a J

′

∗

), to

′

∗

) = 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˙zsze twierdzenie.

Twierdzenie 3 Je´sli funkcja J : (a, b) → R ma w punkcie u

∗

∈ (a, b) pochodn ˛

drugiego rz ˛

edu J

′′

∗

), przy czym J

′

∗

) = 0 i J

′′

∗

) > 0, to u

∗

jest punktem

lokalnego minimum funkcji J na (a, b).

Uwaga 4 Je´sli spełnione s ˛

a zało˙zenia powy˙zszego twierdzenia, to punkt u

∗

, o którym

mowa 3w powy˙zszym twierdzeniu, jest punktem ´scisłego minimum lokalnego funkcji

J, t.zn. istnieje przedział otwarty V taki, ˙ze u

∗

∈ V oraz

J(u

∗

) < J(u)

dla dowolnego u ∈ V , u = u

∗

Uwaga 5 Analogicznie definiuje si ˛

e punkt (´scisł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´s´c nale˙zy zast ˛

api´c nierówno´sci ˛

a odwrotn ˛

1.1.4

Zało˙zenie wypukło´sci

Niech I ⊂ R b ˛edzie przedziałem (otwartym, domkni ˛etym lub jednostronnie domkni ˛e-

tym). Funkcj ˛e J : I → R nazywamy wypukł ˛

a, gdy

J(αu

+ (1 − α)u

) ≤ αJ(u

) + (1 − α)J (u

)

dla dowolnych α ∈ [0, 1], u

, u

∈ I.

Wa˙zne własno´sci funkcji wypukłych opisuj ˛a poni˙zsze dwa twierdzenia.

Twierdzenie 6 Niech dana b ˛

edzie funkcja wypukła J : I → R. Wówczas, ka˙zdy

punkt minimum lokalnego jest punktem minimum globalnego.

Dowód. Niech u

∗

∈ I b ˛edzie punktem minimum lokalnego, t.zn. istnieje przedział

otwarty V taki, ˙ze u

∗

∈ V oraz

J(u

∗

) ≤ J(u)

dla dowolnego u ∈ I ∩ V . Przypu´s´cmy, ˙ze u

∗

nie jest punktem minimum globalnego,

t.zn. istnieje punkt u ∈ I taki, ˙ze

J(u) < J(u

∗

Rozwa˙zmy punkty u

postaci u

= αu

∗

+ (1 − α)u, gdzie α ∈ [0, 1]. Z wypukło´sci

przedziału I wynika, ˙ze u

∈ I dla dowolnego α ∈ [0, 1]. Ponadto, dla α ∈ (0, 1)

dostatecznie bliskich jedno´sci u

∈ V i w konsekwencji u

∈ I ∩ V , przy czym

J(u

) ≤ αJ(u

∗

) + (1 − α)J(u) < αJ(u

∗

) + (1 − α)J(u

∗

) = J(u

∗

Przeczy to lokalnej optymalno´sci punktu u

∗

Przy zało˙zeniu wypukło´sci prawdziwe jest nast ˛epuj ˛ace odwrócenie twierdzenia

Fermata.

Twierdzenie 7 (odwrócenie twierdzenia Fermata) Niech dana b ˛

edzie funkcja

wypukła J : (a, b) → R. Je´sli J

′

∗

) = 0, to u

∗

jest punktem minimum globalnego

funkcji J na (a, b).

1.1.5

Metody numeryczne - metoda łamanych

Opiszemy teraz jedn ˛

a z wielu metod numerycznych słu˙z ˛acych do przybli˙zonego

wyznaczania punktów minimum globalnego funkcji jednej zmiennej okre´slonej na

ograniczonym przedziale domkni ˛etym [a, b] ⊂ R.

Mówimy, ˙ze funkcja J : [a, b] → R spełnia warunek Lipschitza, je´sli istnieje stała

L > 0 taka, ˙ze

|J(u) − J(v)| ≤ L |u − v|

dla dowolnych u, v ∈ [a, b]. Łatwo pokaza´c, ˙ze je´sli a = a

< a

< ... < a

= b

jest podziałem przedziału [a, b] i funkcja J spełnia warunek Lipschitza na ka˙zdym

przedziale [a

−1

, a

] ze stał ˛

a L

, to J spełnia warunek Lipschitza na przedziale [a, b]

ze stał ˛

a L = max

1≤i≤n

. Ponadto, je´sli J jest ró˙zniczkowalna na [a, b] i jej pochodna

′

jest ograniczona na [a, b], to J spełnia warunek Lipschitza na [a, b] ze stał ˛

a L =

sup

∈[a,b]

′

(u)|.

Niech dana b ˛edzie funkcja J : [a, b] → R spełniaj ˛

aca warunek Lipschitza ze stał ˛

L. Ustalmy dowolny punkt u

i rozwa˙zmy funkcj ˛e g(·, u

) jednej zmiennej u ∈ [a, b]

postaci

g(u, u

) = J(u

) − L |u − u

| =







J (u

) + Lu − Lu

; u < u

J (u

) − Lu + Lu

; u ≥ u

Jest to funkcja kawałkami liniowa, której wykres jest łaman ˛

a, składaj ˛

ac ˛

a si ˛e z dwóch

odcinków prostych o współczynnikach kierunkowych L, −L, ł ˛

acz ˛

acych si ˛e w punkcie

, J(u

)). Z warunku Lipschitza wynika natychmiast, ˙ze

g(u, u

) = J(u

) − L |u − u

| ≤ J(u)

dla dowolnego u ∈ [a, b]. A wi ˛ec wykres funkcji J le˙zy powy˙zej łamanej i ma z ni ˛a

punkt wspólny (u

, J(u

)). Oznaczmy p

(u) = g(u, u

). Niech u

∈ [a, b] b ˛edzie

takim punktem, ˙ze

) = min

∈[a,b]

(u)

(oczywi´scie u

= a lub u

= b). Okre´slmy now ˛

a funkcj ˛e

(u) = max{g(u, u

), p

(u)}, u ∈ [a, b].

Punkt u

∈ [a, b] niech b ˛edzie taki, ˙ze

) = min

∈[a,b]

(u).

Załó˙zmy, ˙ze w wy˙zej opisany sposób utworzyli´smy sko´nczony ci ˛ag punktów u

, u

...,u

i funkcji p

, p

,...,p

−1

. Wówczas okre´slamy funkcj ˛e

(u) = max{g(u, u

), p

−1

(u)} = max

0≤i≤n

g(u, u

), u ∈ [a, b],

i punkt u

przy pomocy warunku

) = min

∈[a,b]

(u)

(je´sli wybór punktu u

przy pomocy powy˙zszego warunku nie jest jednoznaczny,

wybieramy dowolny punkt spełniaj ˛

acy ten warunek).

Wykresem funkcji p

jest łamana, zło˙zona z odcinków prostych o współczyn-

nikach kierunkowych równych −L, L. Oczywi´scie,

−1

(u) = max

0≤i≤n−1

g(u, u

) ≤ max

0≤i≤n

g(u, u

) = p

(u)

dla u ∈ [a, b]. Ponadto, z faktu, ˙ze

g(u, u

) ≤ J(u)

dla u ∈ [a, b], i = 0, ..., n, wynika, ˙ze

(u) ≤ J (u)

dla u ∈ [a, b], n = 0, 1, ...

Mamy nast ˛epuj ˛

ace

Twierdzenie 8 Je´sli funkcja J spełnia warunek Lipschitza na przedziale [a, b] i

∗

:= inf

∈[a,b]

J(u), to ci ˛

ag (u

) otrzymany przy pomocy metody łamanych ma nast ˛

epu-

j ˛

ace własno´sci:

1) lim

→∞

J(u

) = J

∗

2) 0 ≤ J (u

) − J

∗

≤ J(u

) − p

), n = 0, 1, ...

3) lim

→∞

ρ(u

, U

∗

) = 0, gdzie ρ(u

, U

∗

) = inf

∈U

∗

− u|

(oczywi´scie, U

∗

= ∅).

1.2

Funkcje wielu zmiennych - cz ˛

e´s´c I

Rozwa˙zmy zadanie postaci







J(u) → min .,

u ∈ U

(3)

gdzie J : U → R, U ⊂ R

jest ustalonym zbiorem.

1.2.1

Istnienie rozwi ˛

aza´

n - twierdzenie Weierstrassa

Okre´slenie funkcji półci ˛

agłej z dołu i charakteryzacja "ci ˛

agowa" takich funkcji s ˛

po zast ˛

apieniu przedziału kul ˛

a w przypadku definicji, takie same, jak w przypadku

funkcji jednej zmiennej. Podobnie rzecz ma si ˛e z definicj ˛

a (´scisłego) minimum,

maksimum lokalnego. Dla przykladu, punkt u

∗

∈ U nazywamy punktem lokalnego

minimum funkcji J na zbiorze U (lokalnym rozwi ˛

azaniem zadania (3)), je´sli istnieje

kula K(u

∗

, r) taka, ˙ze

J(u

∗

) ≤ J(u)

dla dowolnego u ∈ K(u

∗

, r) ∩ U .

W dalszym ci ˛

agu przydatna b ˛edzie nast ˛epuj ˛

aca charakteryzacja funkcji pół-

ci ˛

agłych z dołu na zbiorze domkni ˛etym.

Lemat 9 Niech U ⊂ R

b ˛

edzie zbiorem domkni ˛

etym. Funkcja J : U → R jest

półci ˛

agła z dołu na zbiorze U wtedy i tylko wtedy, gdy dla dowolnego c ∈ R zbiór

M (c) = {u ∈ U ; J(u) ≤ c}

jest zbiorem domkni ˛

etym.

Mamy nast ˛epuj ˛

ace twierdzenia o istnieniu rozwi ˛

aza´n optymalnych.

Twierdzenie 10 (Weierstrassa) Je´sli U ⊂ R

jest zbiorem zwartym i funkcja

J : U → R jest półci ˛

agła z dołu na zbiorze U , to istnieje punkt minimum globalnego

funkcji J na zbiorze U.

Dowód. Niech (u

) ⊂ U b ˛edzie ci ˛

agiem minimalizuj ˛

acym, t.zn. lim

→∞

J(u

) = J

∗

inf

∈U

J(u) ∈ R ∪ {−∞}. Ze zwarto´sci zbioru U wynika, ˙ze istniej ˛a podci ˛ag (u

) oraz

punkt u

∗

∈ U takie, ˙ze lim

→∞

= u

∗

. Wówczas,

∗

≤ J(u

∗

) ≤ lim inf

→∞

J (u

) = lim

→∞

J(u

) = lim

→∞

J(u

) = J

∗

St ˛

ad wynika, ˙ze J(u

∗

) = J

∗

∈ R.

Twierdzenie 11 (Weierstrassa) Je´sli U ⊂ R

jest zbiorem domkni ˛

etym i nieogranic-

zonym, funkcja J : U → R jest półci ˛

agła z dołu oraz

lim

→∞

J (u

) = ∞

dla dowolnego ci ˛

agu (u

) ⊂ U takiego, ˙ze lim

→∞

| = ∞ (mówimy w takim przypadku,

˙ze funkcja J jest koercytywna), to istnieje punkt minimum globalnego funkcji J na

U .

Proof. Z nieograniczono´sci zbioru U wynika, ˙ze istnieje ci ˛ag (u

) ⊂ U taki, ˙ze

lim

→∞

| = ∞. St ˛

ad i z zało˙zenia wynika, ˙ze lim

→∞

J(u

) = ∞. Niech v ∈ U b ˛edzie

takim punktem, ˙ze J(v) > J

∗

= inf

∈U

J(u) (taki punkt istnieje w´sród punktów u

k ∈ N). Rozwa˙zmy zbiór

M (J(v)) = {u ∈ U; J (u) ≤ J(v)}.

Jest to zbiór niepusty. Z Lematu 9 wynika, ˙ze M(J(v)) jest zbiorem domkni ˛etym. Z

koercytywno´sci J wynika jego ograniczono´s´c. Zatem, funkcja J, zaw ˛e˙zona do zbioru

M (J(v)), ma punkt minimum globalnego na zbiorze M (J(v)). Oczywi´scie jest to

te˙z punkt minimum globalnego funkcji J na zbiorze U.

1.2.2

Warunki konieczne - zasada Fermata

Rozwa˙zmy zadanie (3). Mamy nast ˛epuj ˛ace:

Twierdzenie 12 (zasada Fermata) Je´sli U ⊂ R

jest zbiorem otwartym i u

∗

jest punktem lokalnego minimum funkcji J : U → R, przy czym istnieje gradient

∇J(u

∗

) = (

∂J

∂u

∗

), ...,

∂J

∂u

∗

)), to

∇J(u

∗

) = 0.

(4)

Dowód.

Istnienie gradientu funkcji J w punkcie u

∗

oznacza istnienie, dla dowol-

nego i = 1, ..., n, pochodnej funkcji

: (−δ, δ) ∋ t → J(u

∗

+ te

) ∈ R

w punkcie t = 0, gdzie δ jest pewn ˛

a liczb ˛

a dodatni ˛

a, e

jest i-tym wektorem jednos-

tkowym. Poniewa˙z u

∗

jest punktem lokalnego minimum funkcji J, wi ˛ec punkt 0 jest

punktem minimum lokalnego funkcji ϕ

i w konsekwencji

′
i

(0) = 0, i = 1, ..., n.

A wi ˛ec ∇J(u

∗

) = (ϕ

′

(0), ..., ϕ

′

(0)) = 0, co ko´nczy dowód.

Przyklad 13 Niech v

,...,v

∈ R

b ˛

ed ˛

a ustalonymi punktami w przestrzeni R

Nale˙zy znale´z´c punkt, dla którego suma kwadratów odległo´sci od tych punktów jest

najmniejsza. Innymi słowy, nale˙zy znale´z´c punkt minimum globalnego funkcji

J(u) =

u − v

na przestrzeni R

Łatwo sprawdzi´c, ˙ze gradient ∇J(u) funkcji J w dowolnym punkcie u ∈ R

jest

postaci

∇J(u) = 2

u − v

Zatem, warunek (4) przyjmuje posta´c

mu −

= 0.

i w konsekwencji jedynym punktem podejrzanym o globalne minimum jest punkt

∗

Jest to oczywi´scie tak˙ze jedyny punkt podejrzany o lokalne minimum.

Poniewa˙z

J(u) = m |u|

− 2m u, u

∗

m
i

dla u ∈ R

, wi ˛

J(u) ≥ m |u|

− 2m |u| |u

∗

| +

m
i

−→

|u|→∞

∞.

To oznacza, ˙ze funkcja J spełnia warunek z Twierdzenia 11 na przestrzeni R

i, w

konsekwencji, istnieje punkt minimum globalnego funkcji J na R

. Ostatecznie wi ˛

ec,

punkt u

∗

jest jedynym punktem minimum globalnego funkcji J na R

1.2.3

Warunki dostateczne

U˙zyteczne jest nast ˛epuj ˛ace

Twierdzenie 14 (warunki dostateczne drugiego rz ˛

edu) Niech U ⊂ R

b ˛

edzie

zbiorem otwartym, funkcja J : U → R niech b ˛

edzie klasy C

(t.zn. posiadaj ˛

ac ˛

a na

U ci ˛

agłe wszystkie pochodne cz ˛

astkowe rz ˛

edu drugiego) oraz ∇J(u

∗

) = 0.

Je´sli macierz ∇

J(u

∗

) =

∂

∂u

∗

)

1≤i,j≤n

jest dodatnio okre´slona, tzn.

∇

J(u

∗

)h, h

0 dla dowolnego h = 0 (równowa˙znie, det

∂

∂u

∗

)

1≤i,j≤k

> 0 dla dowolnego

k = 1, ..., n), to u

∗

jest punktem ´scisłego minimum lokalnego funkcji J na U .

Je´sli macierz ∇

J(u

∗

) =

∂

∂u

∗

)

1≤i,j≤n

jest ujemnie okre´slona, tzn.

∇

J(u

∗

)h, h

0 dla dowolnego h = 0 (równowa˙znie, (−1)

det

∂

∂u

∗

)

1≤i,j≤k

> 0 dla dowolnego

k = 1, ..., n), to u

∗

jest punktem ´scisłego maksimum lokalnego.

Je´sli iloczyn skalarny

∇

J(u

∗

)h, h

przyjmuje warto´sci zarówno dodatnie jak i

ujemne, to J nie ma w punkcie u

∗

ani minimum lokalnego ani maksimum lokalnego.

Przyklad 15 Zauwa˙zmy, ˙ze macierz drugich pochodnych ∇

J(u) funkcji J z Przykładu

13, w dowolnym punkcie u ∈ R

jest postaci

∇

J(u) = 2mI,

gdzie I jest macierz ˛

a jednostkow ˛

a wymiaru n × n. To oznacza, ˙ze J jest klasy

. Ponadto, stosuj ˛

ac powy˙zszy warunek dostateczny, stwierdzamy, ˙ze punkt u

∗

jest

punktem ´scisłego minimum lokalnego funkcji J na przestrzeni R

. Z jednoznaczno´sci

minimum globalnego (por. Przykład 13) wynika, ˙ze jest to punkt ´scisłego minimum

globalnego funkcji J na R

1.2.4

Zało˙zenie wypukło´sci

Mówimy, ˙ze zbiór U ⊂ R

jest wypukły, gdy spełniony jest warunek

αx + (1 − α)y ∈ U

dla dowolnych α ∈ [0, 1], x, y ∈ U .

Mówimy, ˙ze funkcja J : U → R, gdzie U ⊂ R

jest zbiorem wypukłym, jest

wypukła, gdy spełniony jest warunek

J(αx + (1 − α)y) ≤ αJ(x) + (1 − α)J(y)

dla dowolnych α ∈ [0, 1], x, y ∈ U .

Podamy teraz trzy twierdzenia pozwalaj ˛

ace rozstrzyga´c o wypukło´sci funkcji

ró˙zniczkowalnych. Przypomnijmy, ˙ze mówimy, i˙z funkcja J : R

⊃ K(u

∗

, ε) → R

jest ró˙zniczkowalna w punkcie u

∗

, je´sli istnieje wektor a ∈ R

taki, ˙ze

J(u

∗

+ h) − J(u

∗

) = a, h + o(h)

dla 0 < |h| < ε

, gdzie o : (−ε

, ε

) \ {0} → R, 0 < ε

< ε, jest tak ˛

a funkcj ˛

˙ze lim

→0

(h)

|h|

= 0 (funkcja o(·) zale˙zy od u

∗

). Łatwo wida´c, ˙ze w takim przypadku

a = ∇J (u

∗

Ponadto, mówimy, ˙ze funkcja J : U → R okre´slona na zbiorze U ⊂ R

(niekoniecznie

otwartym) jest klasy C

, je´sli jest ró˙zniczkowalna w ka˙zdym punkcie tego zbioru i

wszystkie pochodne cz ˛

astkowe pierwszego rz ˛edu funkcji J s ˛

a funkcjami ci ˛

agłymi na

U (gdy zbiór U jest otwarty, wystarczy ˙z ˛ada´c jedynie ci ˛agło´sci na U wszystkich

pochodnych cz ˛

astkowych pierwszego rz ˛edu).

Twierdzenie 16 Niech U ⊂ R

b ˛

edzie zbiorem wypukłym, J : U → R - funkcj ˛

klasy C

. Wówczas, funkcja J jest wypukła na U wtedy i tylko wtedy, gdy

J(u) ≥ J (v) + ∇J(v), u − v

(5)

dla dowolnych u, v ∈ U.

Twierdzenie 17 Niech U ⊂ R

b ˛

edzie zbiorem wypukłym, J : U → R - funkcj ˛

klasy C

. Wówczas, funkcja J jest wypukła na U wtedy i tylko wtedy, gdy

∇J(u) − ∇J(v), u − v ≥ 0

dla dowolnych u, v ∈ U.

Mamy tak˙ze

Twierdzenie 18 Niech U ⊂ R

b ˛

edzie zbiorem wypukłym, V - zbiorem otwartym

zawieraj ˛

acym U , J : V → R - funkcj ˛

a klasy C

. Wówczas, je´sli

∇

J(u)h, h

≥ 0

dla dowolnych u ∈ U , h ∈ R

, to J jest wypukła na U .

Podobnie, jak w przypadku funkcji jednej zmiennej, prawdziwe jest nast ˛epuj ˛

ace

twierdzenie.

Twierdzenie 19 Je´sli funkcja J : U → R jest wypukła, to ka˙zdy punkt lokalnego

minimum funkcji J na zbiorze U jest punktem jej minimum globalnego.

Kolejne twierdzenie nazywane jest kryterium optymalno´sci dla funkcji wypukłych

na zbiorze wypukłym.

Twierdzenie 20 (kryterium optymalno´sci dla funkcji wypukłych) Niech U ⊂

b ˛

edzie zbiorem wypukłym, J : U → R - funkcj ˛

a klasy C

. Wówczas, je´sli punkt

∗

∈ U jest punktem minimum globalnego, to

∇J(u

∗

)), u − u

∗

≥ 0

(6)

dla dowolnego u ∈ U, przy czym je´sli u

∗

∈ IntU, to warunek (6) równowa˙zny jest

warunkowi

∇J(u

∗

) = 0.

Je´sli ponadto, funkcja J jest wypukła na U i u

∗

∈ U , to warunek (6) jest wystarcza-

j ˛

acy na to, aby punkt u

∗

był punktem minimum globalnego.

Dowód.

Załó˙zmy, ˙ze punkt u

∗

jest punktem minimum globalnego. Wówczas, z

rózniczkowalno´sci funkcji J w punkcie u

∗

mamy

0 ≤ J(u

∗

+ α(u − u

∗

)) − J(u

∗

) = α ∇J(u

∗

)), u − u

∗

+ o(α),

sk ˛

0 ≤ ∇J(u

∗

)), u − u

∗

o(α)

dla dostatecznie małych α > 0 (tutaj o(α) jest tak ˛

a funkcj ˛

a, ˙ze

(α)

→ 0 gdy α → 0).

Przechodz ˛

ac w powy˙zszej nierówno´sci z α do 0, otrzymujemy ˙z ˛adana nierówno´s´c.

Je´sli u

∗

∈ IntU, to dla dowolnego e ∈ R

istnieje ε

o tej własno´sci, ˙ze u

∗

+ εe ∈ U

dla |ε| < ε

. Stosuj ˛

ac warunek (6) do punktów postaci u = u

∗

+ εe z ε ∈ (0, ε

dostajemy

∇J(u

∗

), e ≥ 0

dla dowolnego e ∈ R

. To oznacza, ˙ze ∇J(u

∗

) = 0.

Załó˙zmy teraz, ˙ze 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

∗

) ≥ ∇J(u

∗

)), u − u

∗

≥ 0

dla dowolnego u ∈ U , co oznacza, ˙ze u

∗

jest punktem minimum globalnego.

Uwaga 21 Druga cz ˛

e´s´c powy˙zszego kryterium optymalno´sci jest uogólnieniem odwróce-

nia twierdzenia Fermata (przy zało˙zeniach wypukło´sci i gładko´sci funkcji J).

1.2.5

Metody numeryczne - metoda gradientowa

Rozwa˙zmy zadanie bez ogranicze´n







J(u) → min

u ∈ R

zakładaj ˛

ac, ˙ze funkcja J : R

→ R jest klasy C

Korzystaj ˛

ac z definicji ró˙zniczkowalno´sci funkcji J oraz nierówno´sci Cauchy’ego

- Buniakowskiego (− |∇J(u)| |v| ≤ ∇J (u), v ≤ |∇J(u)| |v| dla dowolnego v ∈ R

przy czym je´sli ∇J(u) = 0, to prawa nierówno´s´c jest równo´sci ˛

a tylko dla v =

α∇J(u), a lewa nierówno´s´c - tylko dla v = −α∇J(u), gdzie α ≥ 0), mo˙zna pokaza´c,

˙ze je´sli ∇J(u

∗

) = 0, to kierunkiem najszybszego spadku warto´sci funkcji J w punkcie

∗

jest kierunek antygradientu −∇J(u

∗

) (tzn. dla dowolnego h ∈ R

\ {0}, h =

−∇J(u

∗

), |h| = |∇J (u

∗

)|, istnieje τ

> 0 takie, ˙ze

J(u

∗

+ τ (−∇J(u

∗

))) < J (u

∗

+ τ h)

dla 0 < τ < τ

). Na tym spostrze˙zeniu opiera si ˛e konstrukcja tzw. metody gradien-

towej - metody wyznaczania przybli˙zonych rozwi ˛aza´n powy˙zszego zadania. Podamy

teraz opis jednego z wariantów tej metody.

Niech dany b ˛edzie dowolny punkt u

∈ R

. Rozwa˙zmy ci ˛ag (u

)

∈N∪{0}

okre´slony

w sposób rekurencyjny wzorem

= u

− α

∇J(u

), k = 0, 1, ...,

(7)

gdzie α

> 0 dla k = 0, 1, ... jest tzw. krokiem k-tej iteracji.

Uwaga 22 Je´sli ∇J(u

) = 0, to α

> 0 mo˙zna wybra´c tak, by spełniona była

nierówno´s´c J(u

) < J (u

) (

). Je´sli ∇J(u

) = 0, to post ˛

epowanie nale˙zy prz-

erwa´c (ci ˛

ag tworzony zgodnie z powy˙zszym wzorem b ˛

edzie stały). Punkt u

jest

wówczas punktem spełniaj ˛

acym warunek konieczny istnienia minimum funkcji J na

przestrzeni R

. Warto przypomnie´c, ˙ze gdy funkcja J jest wypukła, ka˙zdy punkt, w

którym gradient zeruje si ˛

e, jest punktem minimum globalnego funkcji J na R

Sposób ustalania warto´sci parametru α

wyznacza wariant metody gradientowej.

Opiszemy teraz dwa takie warianty. Symbolem J

, k = 0, 1, ..., oznaczmy funkcj ˛e

postaci

: [0, ∞) ∋ α −→ J(u

− α∇J(u

)) ∈ R.

Z okre´slenia ró˙zniczkowalno´sci funkcji J w punkcie u:

(u + h) = J(u) + ∇J(u), h + o(u, h), h ∈ R

wynika, ˙ze

k+1

) − J(u

) = α

[− |∇J (u

(α

)α

−1

] < 0

dla dostatecznie małych warto´sci α

0, gdzie

(α) = o(u

−α∇J(u

))

Metod ˛

a najszybszego spadku nazywamy wariant, w którym krok α

> 0 ustalany

jest na podstawie warunku

inf

≥0

(α) = J

(α

)

(8)

(zgodnie z Uwag ˛

a 22, je´sli powy˙zszy kres dolny jest osi ˛agany przez funkcj ˛e J

oraz

∇J(u

) = 0, to punktem realizuj ˛

acym ów kres jest punkt α

> 0).

Przyklad 23 Rozwa˙zmy zadanie badane w Przykładach 13 i 15, z punktami v

(1, 2), v

= (2, 4), v

= (3, 3), t.zn.

J : R

∋ u −→

u − v

∈ R.

Jak zauwa˙zyli´smy w Przykładzie 13,

∇J(u) = 2(3u − (v

+ v

)) = (6x − 12, 6y − 18)

dla u = (x, y) ∈ R

. Ustalmy punkt pocz ˛

atkowy u

= (0, 0). Wówczas, ∇J(u

) =

(−12, −18) oraz

[0, ∞) ∋ α −→ J((0, 0) − α∇J (0, 0)) = J(12α, 18α)

= |(12α, 18α) − (1, 2)|

+ |(12α, 18α) − (2, 4)|

+ |(12α, 18α) − (3, 3)|

= (12α − 1)

+ (18α − 2)

+ (12α − 2)

+ (18α − 4)

+ (12α − 3)

+ (18α − 3)

∈ R

Jest to funkcja kwadratowa, która osi ˛

aga swój kres dolny w punkcie α

1
6

. W

konsekwencji,

= (0, 0) −

1
6

(−12, −18) = (2, 3)

oraz

∇J(2, 3) = (6 · 2 − 12, 6 · 3 − 18) = (0, 0).

Tworzenie kolejnych punktów ci ˛

agu (u

) nale˙zy przerwa´c, poniewa˙z pocz ˛

awszy od u

ci ˛

ag ten b ˛

edzie stały. Zauwa˙zmy te˙z, ˙ze funkcja J jest wypukła, bowiem

∇

J(u)h, h

= 2 · 3 Ih, h = 6 |h|

≥ 0

dla dowolnych u ∈ R

, h ∈ R

. A wi ˛

ec z odwrócenia zasady Fermata (przy zało˙zeniu

wypukło´sci i gładko´sci) wynika, ˙ze punkt (2, 3) jest punktem minimum globalnego.

Jest to zgodne z konkluzj ˛

a przykładów 13 i 15, poniewa˙z

∗

1
3

+ v

) =

1
3

(6, 9) = (2, 3).

Je´sli nie jest mo˙zliwe wyznaczenie punktu α

spełniaj ˛

acego równo´s´c (8), to mo˙zna

za α

przyj ˛

a´c punkt, który realizuje powy˙zszy kres dolny z dokładno´sci ˛a δ

> 0. A

mianowicie, niech dla dowolnego k = 0, 1, ... liczba α

> 0 b ˛edzie taka, ˙ze

inf

≥0

(α) ≤ J

(α

) ≤ inf

≥0

(α) + δ

(9)

Z okre´slenia kresu dolnego i z ci ˛

agło´sci funkcji J

wynika, ˙ze α

> 0 spełniaj ˛

ace (9)

istnieje.

W monografii [V] udowodnione jest nast ˛epuj ˛

ace

Twierdzenie 24 (o zbie˙zno´sci metody gradientowej) Załó˙zmy, ˙ze szereg

∞
k

jest zbie˙zny, funkcja J jest wypukła, ró˙zniczkowalna, przy czym gradient ∇J jest

funkcj ˛

a spełniaj ˛

ac ˛

a warunek Lipschitza na R

, tzn. istnieje stała L ≥ 0 taka, ˙ze

|∇J(u) − ∇J(y)| ≤ L |u − y| , u, y ∈ R

Załó˙zmy te˙z, ˙ze dla pewnego u

zbiór M

) = {u ∈ R

; J (u) ≤ J(u

) + δ},

gdzie δ =

∞
k

, jest ograniczony. Wówczas, J

∗

= inf

∈R

J(u) > −∞, U

∗

= {u ∈

; J (u) = J

∗

} = ∅, ci ˛

ag (u

)

∈N∪{0}

okre´slony warunkami (7)-(9) jest taki, ˙ze

lim

→∞

J(u

) = J

∗

oraz

lim

→∞

ρ(u

, U

∗

) = 0,

gdzie ρ(u

, U

∗

) = inf

∈U

∗

− u|.

Dowód. Fakt, ˙ze

∗

= inf

∈R

J(u) > −∞ oraz U

∗

= {u ∈ R

; J(u) = J

∗

} = ∅

wynika ze zwarto´sci zbioru M

), ci ˛

agło´sci J i twierdzenia Weierstrassa. Oczywi´s-

cie U

∗

⊂ M

Je´sli ∇J(u

) = 0 dla pewnego k ≥ 0, to u

= u

= ... i teza twierdzenia

jest oczywista na mocy Twierdzenia ??. Mo˙zemy wi ˛ec zało˙zy´c, ˙ze ∇J(u

) = 0 dla

dowolnego k ≥ 0. Poniewa˙z

J(u

) = J

(α

) ≤ inf

≥0

(α) + δ

≤ J(u

− α∇J(u

)) + δ

dla dowolnego α ≥ 0, to (

)

J(u

) − J(u

) ≥ J(u

) − J(u

− α∇J(u

)) − δ

≥ α |∇J(u

− α

|∇J(u

− δ

= α(1 − α

) |∇J(u

− δ

dla α ≥ 0 i k = 0, 1, ... St ˛

J(u

) − J(u

) ≥ max

≥0

α(1 − α

)

|∇J(u

− δ

|∇J(u

− δ

(10)

dla k = 0, 1, ... i w konsekwencji

J(u

) ≤ J(u

) + δ

(11)

dla k = 0, 1, ... Poniewa˙z

J(u

) ≥ J

∗

> −∞,

wi ˛ec (

) istnieje granica

∗

≤ lim J(u

) < ∞.

Korzystamy tu z nierówno´sci (zastosowanej do punktów u = u

− α∇J(u

), v = u

)

|J(u) − J(v) − ∇J(v), u − v| ≤

|u − v|

prawdziwej dla dowolnych punktów u, v ∈ U , o ile funkcja J jest ró˙zniczkowalna na zbiorze wy-

pukłym U i gradient ∇J jest lipschitzowski ze stał ˛

a L (por. [V, Lemat 2.3.1]).

Jesli ci ˛

ag liczbowy (a

) jeswt taki, ˙ze

k+1

≤ a

+ δ

, k

= 0, 1, ...

przy czym δ

≥ 0,

∞, to istnieje granica lim a

∞. Je´sli ci ˛

ag (a

) jest tak˙ze ograniczony

z dołu, to lim a

∈ R.

W konsekwencji lim(J(u

) − J(u

)) = 0 i z (10) wynika, ˙ze lim ∇J(u

) = 0.

Zauwa˙zmy tak˙ze, ˙ze z (11) wynika, i˙z

J(u

) ≤ J(u

) +

−1

≤ J(u

) + δ

dla dowolnego k = 1, 2, ..., t.zn.

∈ M

)

(12)

dla dowolnego k = 1, 2, ...

Zauwa˙zmy teraz, ˙ze dla dowolnego u

∗

∈ U

∗

z nierówno´sci (5) wynika, i˙z

0 ≤ J(u

) − J

∗

= J(u

) − J(u

∗

) ≤ ∇J(u

), u

− u

∗

≤ |∇J(u

)| |u

− u

∗

| ≤ R |∇J(u

dla k = 1, 2, ..., gdzie R jest stał ˛

a ograniczaj ˛

aca moduły elementów zbioru M

Ze zbie˙zno´sci lim ∇J(u

) = 0 wynika, ˙ze

lim J(u

) = J

∗

Ze zwarto´sci zbioru M

) i (12) wynika, ˙ze istnieje podci ˛ag (u

) ci ˛

agu (u

), który

jest zbie˙zny do pewnego punktu u ∈ M

). Z ci ˛

agło´sci J wynika, ˙ze J(u) = J

∗

, co

oznacza, ˙ze u ∈ U

∗

i tym samym lim ρ(u

, U

∗

) = 0. St ˛

ad wynika, ˙ze lim ρ(u

, U

∗

) = 0

(wystarczy zaprzeczy´c temu).

1.3

Funkcje wielu zmiennych - cz ˛

e´s´c II

1.3.1

Warunki konieczne - zasady mno˙zników Lagrange’a

Rozwa˙zmy zadanie postaci







J(u) → inf ,

u ∈ U = {u ∈ R

; f

(u) = θ, i = 1, ..., m}

(13)

gdzie J : R

→ R, f

: R

→ R, i = 1, ..., m.

Mówimy, ˙ze punkt u

∗

∈ U jest punktem lokalnego minimum dla zadania (13),

je´sli istnieje kula K(u

∗

, r) taka, ˙ze dla dowolnego punktu u ∈ K(u

∗

, r), spełniaj ˛

acego

ograniczenia

(u) = θ, i = 1, ..., m,

spełniona jest nierówno´s´c

J (u

∗

) ≤ J(u).

Przypomnijmy

Twierdzenie 25 (o funkcji uwikłanej) Niech dane b ˛

ed ˛

a funkcje g

= g

(w, z) :

→ R, i = 1, ..., n, klasy C

oraz punkt (a, b) ∈ R

taki, ˙ze

(a, b) = 0, i = 1, ..., n

det[

∂g

∂z

(a, b)]

1≤i,j≤n

= 0.

Wówczas istnieje δ > 0 i funkcja z = z(w) = (z

(w), ..., z

(w)) : K(a, δ) → R

klasy

taka, ˙ze

z(a) = b,

(w, z(w)) = 0, w ∈ K(a, δ), i = 1, ..., n.

Twierdzenie 26 (pierwsza zasada mno˙zników Lagrange’a) Je´sli funkcje J, f

i = 1, ..., m, s ˛

a klasy C

na R

i punkt u

∗

jest punktem lokalnego minimum dla zada-

nia (13), to istniej ˛

a liczby (mno˙zniki Lagrange’a) λ

, λ

, ..., λ

∈ R, nie wszystkie

równe zero i takie, ˙ze

∇J(u

∗

) +

m
i

∇f

∗

) = 0.

(14)

Je´sli dodatkowo wektory ∇f

∗

), i = 1, ..., m, s ˛

a liniowo niezale˙zne, to λ

= 0 i

mo˙zna przyj ˛

a´c λ

= 1.

Dowód. Warunek dany w tezie twierdzenia oznacza liniow ˛

a zale˙zno´s´c wektorów

∇J(u

∗

), ∇f

∗

), ..., ∇f

∗

)

w przestrzeni R

. Przypu´s´cmy, ˙ze warunek ten nie jest spełniony, tzn. powy˙zsze wek-

tory s ˛

a liniowo niezale˙zne. Oznacza to, ˙ze m + 1 ≤ n. W przypadku, gdy m + 1 < n

mo˙zemy uzupełni´c (i uzupełniamy) układ wektorów ∇J(u

∗

), ∇f

∗

), ..., ∇f

∗

)

wektorami d

, ..., d

−1

tak, by układ wektorów ∇J(u

∗

), ∇f

∗

), ..., ∇f

∗

), d

, ..., d

−1

był układem liniowo niezale˙znym w R

Rozwa˙zmy teraz funkcje (gdy m + 1 = n, nie rozwa˙zamy ostatniej grupy funkcji)

(t, u) = J(u) − J (u

∗

) + t,

(t, u) = f

(u), i = 1, ..., m,

(t, u) = d

, u − u

∗

, i = m + 1, ..., n − 1,

okre´slone na R

1+n

Łatwo wida´c, ˙ze powy˙zszy układ funkcji spełnia zało˙zenia

twierdzenia o funkcji uwikłanej z punktem (a, b) postaci (0, u

∗

). Z twierdzenia tego

wynika, ˙ze istnieje δ > 0 i funkcja u = u(t) = (u

(t), ..., u

(t)) : (−δ, δ) → R

klasy

(wykorzystamy tylko ci ˛

agło´s´c funkcji u) taka, ˙ze

u(0) = u

∗

oraz

J(u(t)) = J(u

∗

) − t,

(u(t)) = 0, i = 1, ..., m,

dla t ∈ (−δ, δ). To oznacza w szczególno´sci, ˙ze dla t ∈ (0, δ) punkty u(t) spełniaj ˛a

ograniczenia typu równo´sci wyst ˛epuj ˛

ace w zadaniu (13), przy czym

J(u(t)) = J (u

∗

) − t < J(u

∗

Przeczy to optymalno´sci punktu u

∗

, gdy˙z u(t) → u

∗

, gdy t → 0.

Przypu´s´cmy teraz, ˙ze λ

= 0. Wówczas

m
i

∇f

∗

) = 0

przy czym λ

= 0 dla pewnego i ∈ {1, ..., m}. Jest to sprzeczne z liniow ˛

a nieza-

le˙zno´sci ˛a wektorów ∇f

∗

), i = 1, ..., m.

Przyklad 27 Nale˙zy znale´z´c na okr ˛

egu jednostkowym w przestrzeni R

, o ´srodku

w punkcie 0, punkt, dla którego suma kwadratów odległo´sci od danych punktów

,...,v

∈ R

jest najmniejsza. Innymi słowy, nale˙zy znale´z´c punkt minimum glob-

alnego funkcji

J(u) =

u − v

na zbiorze opisanym równo´sci ˛

(u) = |u|

− 1 = 0.

(15)

Z twierdzenia Weierstrassa wynika, ˙ze funkcja J osi ˛

aga na zbiorze opisanym równo´s-

ci ˛

a (15) minimum globalne, które jest oczywi´scie te˙z minimum lokalnym. Je´sli u jest

tym punktem, to istniej ˛

a mno˙zniki Lagrange’a λ

, λ ∈ R, nie wszystkie równe zero i

takie, ˙ze

∇J(u

∗

) + λ

∇f

∗

) = 0,

czyli

2m(u − u

∗

) + λ

2u = 0,

(16)

gdzie u

∗

m
i

Przypadek λ

= 0 jest niemo˙zliwy, bo (λ

, λ

) = 0 i |u|

= 1. Mo˙zna wi ˛

ec zało˙zy´c,

˙ze λ

= 1.

Rozwa˙zmy dwa przypadki.

∗

= 0. Z (16) wynika, ˙ze

(m + λ)u = mu

∗

(17)

St ˛

ad z kolei wynika, ˙ze u = 0 oraz u = αu

∗

dla pewnego α = 0. Wówczas

1 = |u| = |α| |u

∗

| ,

sk ˛

|α| =

∗

i w konsekwencji

u =

∗

lub u = −

∗

Poniewa˙z

J(u) = m |u|

− 2m u, u

∗

m
i

(18)

wi ˛

ec wida´c, ˙ze rozwi ˛

azaniem jest punkt u =

∗

= 0. Wówczas z (18) wynika, ˙ze funkcja J jest stała na zbiorze (15) i, w

konsekwencji, ka˙zdy punkt okr ˛egu jednostkowego jest punktem minimum globalnego

funkcji J na tym˙ze okr ˛egu.

Uwaga 28 Fakt, ˙ze λ

= 0 mo˙zna zauwa˙zy´c, korzystaj ˛

ac z drugiej cz ˛

e´sci zasady

mno˙zników Lagrange’a. Rzeczywi´scie, ∇f

(u) = 2u i je´sli u jest punktem minimum

lokalnego na okr ˛

egu jednostkowym, to w szczegolno´sci u = 0 i jednoelementowy układ

∇f

(u) jest układem liniowo niezale˙znym.

Rozwa˙zmy teraz zadanie z ograniczeniami mieszanymi







J(u) → inf ,

u ∈ U = {u ∈ R

; f

(u) = θ, i = 1, ..., m, h

(u) ≤ 0, k = 1, ..., s}

(19)

Wprowadzaj ˛

ac nowe zmienne w

,...,w

, rozwi ˛

azywanie zadania (19) mo˙zna zast ˛api´c

rozwi ˛

azywaniem zadania postaci











J (u, w) = J(u) → inf

(u, w) = f

(u) = θ, i = 1, ..., m

(u, w) = w

+ h

(u) = 0, k = 1, ..., s

(20)

gdzie w = (w

, ...w

). Dokładniej, je´sli punkt u

∗

jest punktem lokalnego minimum

dla zadania (19), to punkt (u

∗

, w

∗

), gdzie w

∗

= (w

∗

, ..., w

∗

), w

∗

−h

∗

), k =

1, ..., s, jest punktem lokalnego minimum dla zadania (20). Na odwrót, je´sli punkt

∗

, w

∗

) jest punktem lokalnego minimum dla zadania (20), to punkt u

∗

jest punktem

lokalnego minimum dla zadania (19).

Przyklad 29 Znale´z´c na kuli jednostkowej o ´srodku w punkcie 0 punkt, dla którego

suma kwadratów odległo´sci od danych punktów v

,...,v

∈ R

jest najmniejsza. In-

nymi słowy, nale˙zy znale´z´c punkt minimum globalnego funkcji

J(u) =

u − v

na zbiorze opisanym nierówno´sci ˛

(u) = |u|

− 1 ≤ 0.

(21)

Z twierdzenia Weierstrassa wynika, ˙ze taki punkt istnieje.

Z Przykładu 13 wynika, ˙ze punktem globalnego minimum funkcji J na przestrzeni

jest punkt u

∗

m
i

. Je´sli wi ˛

ec |u

∗

| ≤ 1, to jest to punkt globalnego

minimum na zbiorze opisanym nierówno´sci ˛

a (21).

Załó˙zmy wi ˛

ec, ˙ze |u

∗

| > 1. Wprowad´zmy pomocnicz ˛

a zmienn ˛

a w i wyznaczmy

punkty "podejrzane" o minimum lokalne funkcji

J(u, w) =

u − v

na zbiorze opisanym równo´sci ˛

(u, w) = w

+ |u|

− 1 = 0.

(22)

Z postaci funkcji

J i

wynika, ˙ze

∇

J(u, w) + λ

∇

(u, w) = (λ

2m(u − u

∗

) + λ

2u, λ

2w).

Z zasady mno˙zników Lagrange’a wynika wi ˛

ec, ˙ze je´sli punkt (u, w) jest punktem

minimum lokalnego funkcji

J na zbiorze opisanym równo´sci ˛

a (22), to istnieje punkt

(λ

, λ

) taki, ˙ze

m(u − u

∗

) + λ

u = 0,

w = 0,

+ |u|

= 1,

(λ

, λ

) = 0.

Przy λ

= 0 powy˙zszy układ (równa´n i nierówno´sci) nie posiada rozwi ˛

azania. Za-

łó˙zmy wi ˛

ec, ˙ze λ

= 1. Wówczas

(m + λ

)u = mu

∗

, λ

w = 0, w

+ |u|

= 1

i, jak zało˙zyli´smy,

∗

| > 1.

Przypadek λ

= 0 jest niemo˙zliwy. Je´sli natomiast λ

= 0, to w = 0 i w kon-

sekwencji „podejrzanymi” punktami lokalnego minimum dla zadania pomocniczego

s ˛

a dwa punkty (

∗

, 0) oraz (−

∗

, 0). Oznacza to, ˙ze rozwi ˛

azaniem zadania wyj´s-

ciowego jest punkt

∗

lub −

∗

. Z postaci (18) funkcji J wynika, ˙ze jedynym

rozwi ˛

azaniem zadania wyj´sciowego jest punkt

∗

Prawdziwe jest tak˙ze nast ˛epuj ˛ace

Twierdzenie 30 (druga zasada mno˙zników Lagrange’a) Je´sli funkcje J, f

i = 1, ..., m, h

, k = 1, ..., s s ˛

a klasy C

na R

i punkt u

∗

jest punktem lokalnego

minimum dla zadania (19), to istniej ˛

a mno˙zniki Lagrange’a λ

, λ

, ..., λ

, µ

, ..., µ

∈

, nie wszystkie równe zero i takie, ˙ze

≥ 0, µ

≥ 0, ..., µ

≥ 0

∇J(u

∗

) +

m
i

∇f

∗

) +

s
k

∇h

∗

) = 0

∗

) = 0, k = 1, ..., s.

Przyklad 31 Znale´z´c punkt minimum globalnego funkcji

J(u) =

u − v

na zbiorze opisanym nierówno´sci ˛

(u) = |u|

− 1 ≤ 0

przy pomocy drugiej zasady mno˙zników Lagrange’a. Jak zostało ju˙z stwierdzone, z

klasycznego twierdzenia Weierstrassa wynika, ˙ze powy˙zsze zadanie posiada rozwi ˛

azanie,

przy czym je´sli |u

∗

| ≤ 1, to rozwi ˛

azaniem tym jest u

∗

Załó˙zmy wi ˛

ec, ˙ze |u

∗

| > 1. Z Twierdzenia 30 wynika, ˙ze je´sli u jest punktem

minimum lokalnego, to istniej ˛

a mno˙zniki Lagrange’a λ

≥ 0, λ

≥ 0, nie znikaj ˛

ace

jednocze´snie i takie, ˙ze

∇J(u) + λ

∇h

(u) = λ

2m(u − u

∗

) + 2λ

u = 0,

(|u|

− 1) = 0

(23)

|u| ≤ 1.

Przypadek λ

= 0 jest niemo˙zliwy, wi ˛

ec mo˙zemy zało˙zy´c, ˙ze λ

= 1. Zatem pierwsz ˛

z powy˙zszych nierówno´sci mo˙zemy zapisa´c w postaci

(m + λ

)u = mu

∗

St ˛

ad wynika, ˙ze u = αu

∗

, sk ˛

|α| |u

∗

| ≤ 1, czyli |α| ≤

∗

(bo |u| ≤ 1). Przypu´s´cmy, ˙ze |α| <

∗

. Wówczas

|u|

− 1 = |α|

∗

− 1 <

∗

− 1 = 0,

sk ˛

ad, wobec (23), λ = 0 i w konsekwenscji u = u

∗

, co jest niemo˙zliwe, bowiem

∗

| > 1. Zatem |α| =

∗

, czyli punktami „podejrzanymi” s ˛

∗

lub −

∗

. Znów z

postaci (18) funkcji J wynika, ˙ze jedynym rozwi ˛

azaniem zadania jest punkt

∗

1.3.2

Warunki dostateczne

Twierdzenie 32 Niech dane b ˛

edzie zadanie







J(u) → inf ,

u ∈ U = {u ∈ R

; f

(u) = θ, i = 1, ..., m}

Załó˙zmy, ˙ze funkcje J, f

, i = 1, ..., m s ˛

a klasy C

na R

, t.zn. maj ˛

a na R

ci ˛

agłe

wszystkie pochodne cz ˛

astkowe do rz ˛

edu drugiego wł ˛

acznie. Je´sli istnieje punkt u

∗

∈ U

i mno˙zniki Lagrange’a λ

, λ

, ..., λ

∈ R nie wszystkie równe zero i takie, ˙ze λ

≥ 0,

spełniony jest warunek

∇J(u

∗

) +

m
i

∇f

∗

) = 0

oraz

(λ

[

∂

∂u

∗

)]

1≤j,k≤n

[

∂

∂u

∗

)]

1≤j,k≤n

)h, h

> 0 (< 0)

dla wszystkich h = 0 takich, ˙ze

∇J(u

∗

), h ≤ 0 (≥ 0),

(24)

∇f

∗

), h = 0, i = 1, ..., m,

(25)

to u

∗

jest punktem ´scisłego lokalnego minimum (maksimum) funkcji J na zbiorze U.

Dowód.

Załó˙zmy, ˙ze dla punktu u

∗

spełnione s ˛

a zało˙zenia twierdzenia i przy-

pu´s´cmy, ˙ze punkt ten nie jest punktem ´scisłego minimum lokalnego. Istnieje wówczas

ci ˛

ag (u

) taki, ˙ze

= u

∗

) = 0, ..., f

) = 0,

J(u

) ≤ J(u

∗

)

dla k = 1, 2, ... i u

→ u

∗

, gdy k → ∞. Punkt u

mo˙zna zapisa´c w postaci

= u

∗

+ |u

− u

∗

− u

∗

− u

∗

= u

∗

+ t

gdzie t

= |u

− u

∗

| → 0, e

−u

∗

−u

∗

. Poniewa˙z |e

| = 1 dla k = 1, 2, ..., bez

zmniejszania ogólno´sci rozwa˙za´n mo˙zna zało˙zy´c, ˙ze istnieje punkt e

taki, ˙ze e

→ e

| = 1.

Z ró˙zniczkowalno´sci funkcji J, f

, i = 1, ..., m otrzymujemy

0 ≥ J(u

) − J(u

∗

) = ∇J(u

∗

), e

+ o

− u

∗

0 = f

) − f

∗

) = ∇f

∗

), e

+ o

)

dla i = 1, ..., m, k = 1, 2, ... (tutaj o

(u) dla i = 0, 1, ..., m jest tak ˛

a funkcj ˛

a, ˙ze

(u)

|u|

→ 0, gdy |u| → 0). Dziel ˛

ac obie strony powy˙zszych równo´sci i nierówno´sci

przez t

i przechodz ˛

ac do granicy, otrzymujemy

0 ≥ ∇J(u

∗

), e

0 = ∇f

∗

), e

A wi ˛ec punkt e

spełnia warunki (24), (25).

Oznaczmy teraz

L(u) = λ

J(u) +

m
i

(u), u ∈ R

Jest to oczywi´scie funkcja klasy C

taka, ˙ze ∇L(u

∗

) = 0. Ponadto,

L(u

) = λ

J(u

) +

m
i

) = λ

J(u

) ≤ λ

J(u

∗

)

= λ

J(u

∗

) +

m
i

∗

) = L(u

∗

)

dla k = 1, 2, ... St ˛

ad i z dwukrotnej ró˙zniczkowalno´sci L otrzymujemy

0 ≥ L(u

) − L(u

∗

) =

1
2

2
k

∇

L(u

∗

, e

+ α(u

− u

∗

)

dla k = 1, 2, ... (tutaj α(u) jest tak ˛

a funkcj ˛

a, ˙ze

(u)

|u|

→ 0, gdy |u| → 0). Dziel ˛

powy˙zsz ˛a nierówno´s´c stronami przez t

i przechodz ˛

ac do granicy, otrzymujemy

(λ

[

∂

∂u

∗

)]

1≤j,k≤n

[

∂

∂u

∗

)]

1≤j,k≤n

, e

∇

L(u

∗

, e

≤ 0,

przy czym, przypomnijmy,

0 ≥ ∇J(u

∗

), e

0 = ∇f

∗

), e

, i = 1, ..., m.

Jest to sprzeczne z zało˙zeniem twierdzenia i tym samym ko´nczy dowód twierdzenia.

Uwaga 33 Korzystaj ˛

ac z warunku dostatecznego zamiast twierdzenia Weierstrassa

w Przykladzie 27, mo˙zna wykaza´c, ˙ze, gdy u

∗

= 0, znaleziony punkt podejrzany u =

∗

jest punktem minimum globalnego. Istotnie, w tym przypadku mamy (λ

= 1,

= m(|u

∗

| − 1)) i w konsekwencji

[

∂

∂u

(

∗

)]

1≤j,k≤n

[

∂

∂u

(

∗

)]

1≤j,k≤n

) = 2mI+2m(|u

∗

|−1)I = 2m |u

∗

| I.

Jest to macierz dodatnio okre´slona, wi ˛

ec z powy˙zszego twierdzenia o warunkach

dostatecznych wynika, ˙ze u =

∗

jest punktem ´scisłego lokalnego minimum funkcji

J na zbiorze U . Tak samo mo˙zna pokaza´c, ˙ze u = −

∗

jest punktem ´scisłego

maksimum lokalnego. Zatem, u =

∗

jest jedynym punktem minimum lokalnego.

1.3.3

Zało˙zenie wypukło´sci - twierdzenie Kuhna-Tuckera

Rozwa˙zmy nast ˛epuj ˛ace zadanie







J(u) → inf ,

u ∈ U = {u ∈ R

; u ∈ A, f

(u) ≤ θ, i = 1, ..., m}

(26)

gdzie A ⊂ R

, J, f

: R

→ R, i = 1, ..., m.

Mówimy, ˙ze punkt u

∗

∈ U jest rozwi ˛

azaniem globalnym zadania (26), je´sli

J(u

∗

) ≤ J(u)

dla dowolnego u ∈ U .

Dowód kolejnego twierdzenia oparty jest na nastepuj ˛

acym klasycznym wyniku o

odzielaniu.

Lemat 34 Niech D b ˛

edzie niepustym wypukłym podzbiorem przestrzeni R

takim,

˙ze 0 /

∈ D. Wówczas istnieje wektor (a

, ..., a

) ∈ R

\ {0} taki, ˙ze

≥ 0

dla dowolnego (x

, ..., x

) ∈ D.

Poni˙zsze twierdzenie pokazuje, ˙ze tak˙ze w przypadku zadania (26), przy do-

datkowych zało˙zeniach wypukło´sci, warunek konieczny istnienia minimum jest warunk-

iem dostatecznym

Twierdzenie 35 (Kuhna-Tuckera) Niech J, f

,...,f

: R

→ R b ˛

ed ˛

a funkcjami

wypukłymi i A ⊂ R

- zbiorem wypukłym. Je´sli u

∗

jest rozwi ˛

azaniem globalnym zada-

nia (26), to istniej ˛

a mno˙zniki Lagrange’a λ

≥ 0, λ

≥ 0,...,λ

≥ 0 nie znikaj ˛

ace

jednocze´snie i takie, ˙ze

J (u

∗

) +

∗

) = min

∈A

(λ

J(u) +

(u))

(27)

∗

) = 0, i = 1, ...m.

(28)

Jesli ponadto istnieje punkt u ∈ A taki, ˙ze

(u) < 0, i = 1, ..., m,

(29)

to λ

= 0 i mo˙zna przyj ˛

a´c λ

= 1. Na odwrót, je´sli istniej ˛

a λ

> 0, λ

≥ 0,...,λ

≥ 0

i punkt u

∗

∈ U taki, ˙ze

J(u

∗

) +

∗

) = min

∈A

(λ

J(u) +

(u)),

∗

) = 0, i = 1, ...m,

to u

∗

jest rozwi ˛

azaniem globalnym zadania (26).

Dowód twierdzenia.

Konieczno´s´c. Niech u

∗

b ˛edzie rozwi ˛

azaniem globalnym

zadania (26). Bez zmniejszania ogólno´sci rozwa˙za´n mo˙zemy zało˙zy´c, ˙ze

J(u

∗

) = 0.

Rozwa˙zmy nast ˛epuj ˛acy zbiór

C = {µ = (µ

, µ

, ..., µ

) ∈ R

1+m

; istnieje punkt u ∈ A taki, ˙ze

J (u) < µ

oraz f

(u) ≤ µ

dla i = 1, ..., m}.

Zbiór C jest niepusty. Istotnie, wystarczy rozwa˙zy´c punkt µ = (1, 0, ..., 0),

który nale˙zy do C, bowiem J(u

∗

) = 0 < 1, f

∗

) ≤ 0, i = 1, ..., m oraz u

∗

∈ A.

Zbiór C jest wypukły. Istotnie, niech (µ

, µ

, ..., µ

) ∈ C, (µ

, µ

, ..., µ

) ∈ C,

, u

∈ A b ˛ed ˛

a takie, ˙ze

J(u

) < µ

, J(u

) < µ

) ≤ µ

1
i

, f

) ≤ µ

2
i

, i = 1, ...m.

Wówczas, dla dowolnego α ∈ (0, 1) mamy

αu

+ (1 − α)u

∈ A

J(αu

+ (1 − α)u

) ≤ αJ(u

) + (1 − α)J(u

) < αµ

+ (1 − α)µ

(αu

+ (1 − α)u

) ≤ αf

) + (1 − α)f

) ≤ αµ

1
i

+ (1 − α)µ

2
i

, i = 1, ..., m.

Oznacza to, ˙ze

α(µ

, µ

, ..., µ

1
m

) + (1 − α)(µ

, µ

, ..., µ

2
m

) ∈ C.

∈ C. Istotnie, w przeciwnym bowiem razie istniałby punkt u ∈ A taki, ˙ze

u) < 0,

(

u) ≤ 0, i = 1, ...m,

co przeczyłoby temu, ˙ze u

∗

jest rozwi ˛

azaniem zadania (26).

Zatem, z twierdzenia o oddzielaniu wynika istnienie punktu (λ

, λ

, ..., λ

) ∈

1+m

{0} takiego, ˙ze

≥ 0

(30)

dla (µ

, µ

, ..., µ

) ∈ C.

≥ 0, i = 0, 1, ..., m. Istotnie, ustalmy bowiem dowolne ε > 0, wska´znik i

∈

{0, 1, ..., m} i rozwa˙zmy punkt postaci µ

= (ε, ..., ε, 1, ε, ..., ε) ∈ R

1+m

, którego i

owa współrz ˛edna jest równa 1. Oczywi´scie, µ

∈ C (wystarczy rozwa˙zy´c punkt

∗

∈ A). A wi ˛ec z ostatniej nierówno´sci

≥ −ε

=0, i =i

co, wobec dowolno´sci ε > 0, oznacza, ˙ze λ

≥ 0.

Mno˙zniki λ

, i = 1, ..., m, spełniaj ˛

a warunek (28). Ustalmy dowolny wska´znik

∈ {1, ..., m}. Je´sli f

∗

) = 0, to oczywi´scie λ

∗

) = 0. Przypu´s´cmy wi ˛ec,

˙ze f

∗

) < 0 i rozwa˙zmy punkt µ

= (δ, 0, ..., 0, f

∗

), 0, ..., 0) ∈ R

1+m

z dowol-

nie ustalon ˛

a liczb ˛

a δ > 0 i i

-ow ˛

a współrz ˛edn ˛

a równ ˛

a f

∗

). Oczywi´scie µ

∈ C

(wystarczy rozwa˙zy´c punkt u

∗

∈ A). Z nierówno´sci (30) wynika, ˙ze

∗

) ≥ −λ

δ,

co, wobec dowolno´sci δ > 0, oznacza, ˙ze

∗

) ≥ 0,

czyli λ

≤ 0. Wobec faktu, ˙ze λ

≥ 0, mamy wi ˛ec równo´s´c λ

= 0 i w konsekwencji

∗

) = 0.

Spełniony jest warunek (27). Niech u ∈ A. Rozwa˙zmy punkt postaci (J(u)+

δ, f

(u), ..., f

(u)) ∈ R

1+m

, gdzie δ > 0 jest dowolnie ustalone. Oczywi´scie punkt ten

nale˙zy do zbioru C (wystarczy rozwa˙zy´c punkt u). Zatem, korzystaj ˛ac z nierówno´sci

(30), mamy

J(u) +

(u) ≥ −λ

δ.

St ˛

ad, wobec dowolno´sci δ > 0,

J(u) +

(u) ≥ 0

dla u ∈ A. Ponadto z (28) i faktu, ˙ze J(u

∗

) = 0 mamy

0 = λ

J(u

∗

) +

∗

(31)

A wi ˛ec

J(u

∗

) +

∗

) = min

∈A

(λ

J(u) +

(u)).

(32)

Przypu´s´cmy teraz, ˙ze spełniony jest warunek (29), t.zn. istnieje punkt u ∈ A taki,

˙ze

(u) < 0, i = 1, ..., m,

oraz λ

= 0. Wówczas z (31) wynika, ˙ze

J(u) +

(u) =

(u)

< 0 =

∗

) = λ

J(u

∗

) +

∗

co jest sprzeczne z (32). Zatem λ

> 0.

Dostateczno´s´c. Załó˙zmy, ˙ze istniej ˛a mno˙zniki λ

, λ

, ..., λ

≥ 0 takie, ˙ze λ

> 0

i spełnione s ˛

a warunki (27), (28), przy czym u

∗

∈ A, f

∗

) ≤ 0,...,f

∗

) ≤ 0.

Bez zmniejszania ogólno´sci rozwa˙za´n mo˙zemy zało˙zy´c, ˙ze λ

= 1. Wówczas, dla

dowolnego u ∈ A takiego, ˙ze f

(u) ≤ 0, i = 1, ..., m, mamy

J(u) ≥ J (u) +

(u) ≥ J(u

∗

) +

∗

) = J(u

∗

Oznacza to, wobec dowolno´sci u ∈ A takiego, ˙ze f

(u) ≤ 0, i = 1, ..., m, i˙z u

∗

jest

rozwi ˛

azaniem globalnym zadania (26).

Uwaga 36 Łatwo wida´c, ˙ze przy zało˙zeniach wypukło´sci (podobnie, jak wcze´sniej)

ka˙zde rozwi ˛

azanie lokalne zadania (26) jest jego rozwi ˛

azaniem globalnym.

Z faktu, ˙ze w przypadku funkcji wypukłej na przestrzeni R

punkt, w którym

jest ona ró˙zniczkowalna jest punktem minimum globalnego wtedy i tylko wtedy, gdy

gradient w tym punkcie znika, wynika nast ˛epuj ˛

acy

Wniosek 37 Niech J, f

,...,f

: R

→ R b ˛

ed ˛

a funkcjami wypukłymi i ró˙zniczkowal-

nymi w punkcie u

∗

. Je´sli u

∗

jest rozwi ˛

azaniem globalnym zadania (26) ze zbiorem

A = R

, to istniej ˛

a mno˙zniki Lagrange’a λ

≥ 0, λ

≥ 0,...,λ

≥ 0 nie znikaj ˛

ace

jednocze´snie i takie, ˙ze

∇J(u

∗

) +

m
i

∇f

∗

) = 0,

∗

) = 0, i = 1, ...m.

Je´sli ponadto istnieje punkt u ∈ R

taki, ˙ze

(u) < 0, i = 1, ..., m,

to λ

= 0 i mo˙zna przyj ˛

a´c λ

= 1.

Na odwrót, je´sli istniej ˛

a λ

> 0, λ

≥ 0,...,λ

≥ 0, takie, ˙ze

∇J(u

∗

) +

m
i

∇f

∗

) = 0,

∗

) = 0, i = 1, ...m,

∗

) ≤ 0, ..., f

∗

) ≤ 0,

to u

∗

jest rozwi ˛

azaniem globalnym zadania (26) ze zbiorem A = R

Drug ˛

a cz ˛e´s´c powy˙zszego twierdzenia mo˙zna traktowa´c jako odwrócenie drugiej

zasady mno˙zników Lagrange’a (przy zało˙zeniu wypukło´sci).

Przyklad 38 Rozwa˙zmy zadanie z Przykładu 31:







J(u) =

|u − v

→ min .,

u ∈ U = {u ∈ R

; h

(u) = |u|

− 1 ≤ θ}

w przypadku, gdy |u

∗

| > 1, gdzie u

∗

Korzystaj ˛

ac z przeprowadzonej

tam analizy i nie korzystaj ˛

ac z twierdzenia Weierstrassa, stwierdzamy, ˙ze punktami

"podejrzanymi" s ˛

∗

i −

∗

, przy czym odpowiednie mno˙zniki Lagrange’a (λ

)

wynosz ˛

a m(|u

∗

| − 1), m(− |u

∗

| − 1), odpowiednio; oczywi´scie λ

= 1 w obu przypad-

kach. Łatwo wida´c, ˙ze "trójka"

= 1, λ

= m(|u

∗

| − 1),

∗

spełnia warunki dane w drugiej cz ˛

e´sci powy˙zszego wniosku i tym samym jest rozwi ˛

azaniem

zadania. Aby stwierdzi´c, ˙ze punkt −

∗

nie jest rozwi ˛

azaniem wystarczy na przykład

porówna´c warto´sci funkcji J w obu znalezionych punktach.

1.3.4

Metody numeryczne - metoda projekcji gradientu

Mówimy, ˙ze funkcja J : U → R, gdzie U jest wypukłym podzbiorem R

, jest silnie

wypukła, je´sli istnieje stała κ > 0 taka, ˙ze

J(αu + (1 − α)v) ≤ αJ(u) + (1 − α)J (v) − α(1 − α)κ |u − v|

dla α ∈ [0, 1], u, v ∈ U . Mo˙zna pokaza´c, ˙ze J jest silnie wypukła na U ze stał ˛a κ

wtedy i tylko wtedy, gdy funkcja g(u) = J(u) − κ |u|

jest wypukła na U.

Symbolem P

(u) oznaczamy rzut punktu u ∈ R

na wypukły i domkni ˛ety zbiór

U ⊂ R

, t.zn. punkt nale˙z ˛acy do zbioru U i spełniaj ˛acy warunek

|u − P

(u)| = inf

∈U

|u − v| .

Metod ˛e projekcji gradientu, słu˙z ˛ac ˛a do numerycznego rozwi ˛azywania minimaliza-

cyjnych zada´n z ograniczeniami, opisuje poni˙zsze twierdzenie. Dowód tego twierdzenia

mo˙zna znale´z´c w [V].

Twierdzenie 39 (o zbie˙zno´sci metody projekcji gradientu) Niech U ⊂ R

b ˛

edzie zbiorem wypukłym i domkni ˛

etym, J : U → R - funkcjonałem klasy C

ograniczonym z dołu, którego gradient spełnia warunek Lipschitza (ze stał ˛

a L). Je´sli

) ⊂ R

jest ci ˛

agiem okre´slonym wzorem rekurencyjnym

= P

− α

∇J(u

)), k = 0, 1, ...,

(33)

przy dowolnie ustalonym u

∈ U, gdzie parametr α

, k = 0, 1, ..., jest taki, ˙ze

≤ α

≤

L + 2ε

(34)

(tutaj ε

, ε s ˛

a ustalonymi dodatnimi parametrami metody), to ci ˛

ag (J(u

)) jest

nierosn ˛

acy oraz

lim

→∞

− u

= 0.

(35)

Je´sli, dodatkowo, J jest silnie wypukły na U, to ci ˛

ag (u

) jest zbie˙zny do u

∗

- jedynego

punktu minimum funkcji J na U, przy czym istnieje stała c ≥ 0 taka, ˙ze

− u

∗

≤

, k = 1, 2, ...

(36)

Uwaga 40 Stał ˛

a c mo˙zna wyznaczy´c (por. [V]).

Przyklad 41 Rozwa˙zmy zadanie







J(u = (u

, u

)) = (u

− 1)

+ (u

+ 1)

→ min ,

u ∈ U = {u = (u

, u

) ∈ R

; f

(u) = −u

≤ θ, f

(u) = −u

≤ θ}

Aby rozwi ˛

aza´c to zadanie, zastosujemy metod ˛

e projekcji gradientu, z punktem pocz ˛

atkowym

= (0, 0).

Zauwa˙zmy, ˙ze gradient ∇J(u

, u

) = (2(u

− 1), 2(u

+ 1)) funkcji J spełnia

warunek Lipschitza ze stał ˛

a L = 2:

∇J(u

, u

) − ∇J(v

, v

)

(2(u

− 1), 2(u

− 1)) − (2(v

− 1), 2(v

− 1))

(2(u

− v

), 2(u

− v

))

= 2

, u

) − (v

, v

)

Przyjmuj ˛

ac ε

1
4

, ε = 3 wida´c, ˙ze musi by´c α

1
4

dla dowolnego k = 0, 1, ...

Mamy

∇J(u

) = ∇J(0, 0) = (−2, 2)

i w konsekwencji

= P

((0, 0) −

1
4

(−2, 2)) = P

(

1
2

, −

1
2

) = (

1
2

, 0) = (1 − (

1
2

)

, 0).

Podobnie,

∇J(u

) = ∇J(

1
2

, 0) = (−1, 2)

i w konsekwencji

= P

((

1
2

, 0) −

1
4

(−1, 2)) = P

(

3
4

, −

1
2

) = (

3
4

, 0) = (1 − (

1
2

)

, 0).

Poka˙zemy, korzystaj ˛

ac z zasady indukcji matematycznej, ˙ze

= (1 − (

1
2

)

, 0), k = 0, 1, ...

Istotnie, wzór jest prawdziwy dla k = 0. Załó˙zmy, ˙ze jest prawdziwy dla ustalonej

liczby naturalnej k ≥ 0. Wówczas,

= P

− α

∇J(u

)) = P

((1 − (

1
2

)

, 0) −

1
4

(2(1 − (

1
2

)

) − 2, 2 · 0 + 2)

= P

(1 − (

1
2

)

−

1
2

(1 − (

1
2

)

) +

1
4

· 2), 0 −

1
4

· 2) = P

(1 − (

1
2

)

1
2

(

1
2

)

, −

1
2

)

= P

(1 − (

1
2

)

(1 −

1
2

), −

1
2

) = P

(1 − (

1
2

)

, −

1
2

) = (1 − (

1
2

)

, 0)

Zatem, korzystaj ˛

ac z silnej wypukło´sci funkcji J na zbiorze U, a nawet R

(bo

J(u

, u

) − |(u

, u

= −2u

+ 2u

+ 2), stwierdzamy, ˙ze ci ˛

ag (u

) jest zbie˙zny

do jedynego rozwi ˛

azania u

∗

. Tym samym

∗

= lim u

= lim(1 − (

1
2

)

, 0) = (1, 0).

Wyszukiwarka

Podobne podstrony:
Badania operacyjne w logistyce Nieznany
Jadczak R Badania operacyjne, Wykład 4 Optymalizacja w logistyce
Jadczak R Badania operacyjne, Wykład 1 Optymalizacja w logistyce
Jadczak R Badania operacyjne, Wykład 2 Optymalizacja w logistyce
Jadczak R - Badania operacyjne Wykład 3, Optymalizacja w logistyce
Jadczak R Badania operacyjne, Wykład 3 Optymalizacja w logistyce
Jadczak R Badania operacyjne, Wykład 4 Optymalizacja w logistyce
Badania operacyjne wyklad 2 id Nieznany
badania operacyjne 3 id 76767 Nieznany (2)
Lab 1 Analiza wrazliwosci, Materiały AGH- zarządzanie finansami, badania operacyjne
progr siec, Materiały Ekonomiczna, badania operacyjne
Kolorowanie grafów, badania operacyjne
bo2T, Szkoła, Semestr 3, Semestr 3, Badania operacyjne
badania operacyjne 5
badania operacyjne poss intro i Nieznany (2)
Badania operacyjne, zadanie id Nieznany (2)
Projekt Badania operacyjne

więcej podobnych podstron