Wykład 1 cd.doc

Metody optymalizacji

Rozpatrywane będą jednowskaźnikowe zadania programowania, przy czym elementy zbioru rozwiązań dopuszczalnych należą do przestrzeni skończenie wymiarowej Rn. Zadanie optymalizacji polega na znalezieniu takiego wektora należącego do zbioru , że dla każdego x  należącego do zbioru X0, f () £ f (x). W zadaniu tym X0, jest zbiorem rozwiązań dopuszczalnych, f : Rn ® R1 jest funkcją celu, g: Rn ® i h: Rn ® są wektorowymi funkcjami ograniczeń.

Jeden ze sposobów podziału zadań programowania:

a)  programowanie liniowe - jeśli funkcje f , g i h są liniowe, a więc
                                                        f (x) = ác, xñ
oraz
                                          [ g (x)T, h (x)T]T = Ax - b,
gdzie wektory c Î Rn, b Î Rm oraz macierz A o wymiarach m ´ n są znane.

b)  programowanie nieliniowe - jeśli co najmniej jedna z funkcji f , g bądź h jest nieliniowa.

              Wśród wymienionych wyżej typów zadań, za podstawowe zadanie programowania należy uznać ciągłe deterministyczne zadanie programowania nieliniowego o postaci:

znaleźć takie, że

f () = ,

gdzie

,

przy czym

f : Rn ® R1, g: Rn ® , h: Rn ® .

Warunki konieczne optymalności Kuhna - Tuckera

              Warunki te sformułujemy dla uproszczonej postaci zadania programowania nieliniowego, mianowicie: znaleźć takie, że

f () = f (x),

gdzie

X0 = {x Î Rn: gi (x) £ 0,              i = 1, ..., m}.

              Niech funkcje f : Rn ® R1 oraz gi : Rn ® R1 mają ciągłe pochodne cząstkowe oraz niech będzie minimum lokalnym. Niech ponadto x będzie dowolnym punktem należącym do zbioru X0. W punkcie x określimy zbiór indeksów ograniczeń aktywnych

A(x) = {i Î [1: m]: gi (x) = 0}.

              Z ciągłości funkcji gi wynika, że jeśli ograniczenie nie jest aktywne
w x, tzn. gi (x) < 0 dla i Ï A(x), to można dokonać małego przesunięcia z x w dowolnym kierunku bez naruszenia tego ograniczenia. Stąd w małym otoczeniu punktu x wystarczy brać pod uwagę tylko zbiór ograniczeń aktywnych, tzn. ograniczeń o indeksach i Î A(x).

              Kierunkiem dopuszczalnym w x będzie kierunek d, dla którego istnieje s>0 takie, że dla  t Î [0; s] zachodzą nierówności

gi (x + td) £ 0,              "i Î A(x).

              Warunkiem koniecznym na to, aby kierunek d był dopuszczalny jest

áÑgi (x), dñ £ 0,              "i Î A(x).

              Wynika stąd, że jeśli kierunek d jest dopuszczalny, to musi spełniać powyższy warunek. Natomiast nie każdy kierunek spełniający ten warunek jest kierunkiem dopuszczalnym.

Warunek regularności Kuhna - Tuckera

Dla dowolnego kierunku d Î D (), gdzie zbiór D () określony jest przez

D () = {d: áÑgi (), dñ £ 0,              i Î A()}

istnieją:

n-wymiarowa różniczkowalna funkcja wektorowa

e(q) = [e1 (q), ..., en (q)]T

określona w przedziale [0; 1],

oraz liczba t > 0 takie, że

a)                 e (0) = ,

b)                e (q) Î X0, dla 0 £ q £ 1,

c)                 = td.

              Inaczej mówiąc, warunki regularności Kuhna - Tuckera są spełnione w , jeśli dla każdego d Î Rn spełniony jest warunek konieczny, istnieje różniczkowalna krzywa e (q) styczna do kierunku d w punkcie , wychodząca z tego punktu i zawarta w zbiorze dopuszczalnym X0 dla q Î [0 ; 1].

              Twierdzenie Kuhna - Tuckera

Jeśli:

a)  funkcje f i gi, i = 1, ..., m, mają ciągłe pochodne cząstkowe,

b)  jest lokalnym minimum zadania,

c)  w jest spełniony warunek regularności ograniczeń,

to istnieje wektor l Î Rm, ³ 0, taki, że

Ñf () + Ñgi() = 0,

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

Wektor nosi nazwę wektora mnożników Lagrange’a.

Warunki konieczne Kuhna - Tuckera w przypadku ograniczeń nierównościowych i równościowych

              Niech będzie dane zadanie programowania nieliniowego, gdzie
X = Rn. Załóżmy, że funkcje f : Rn ® R1, g: Rn ...