Metody optymalizacji

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

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

1. 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 ∈ Rⁿ, b ∈ R^m oraz macierz A o wymiarach m × n są znane.

2. 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 : Rⁿ → R¹, g: Rⁿ → , h: Rⁿ → .

Warunki konieczne optymalności Kuhna - Tuckera

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

f () = f (x),

gdzie

X₀ = {x ∈ Rⁿ: g_i (x) ≤ 0, i = 1, ..., m}.

Niech funkcje f : Rⁿ → R¹ oraz g_i : Rⁿ → R¹ mają ciągłe pochodne cząstkowe oraz niech będzie minimum lokalnym. Niech ponadto x będzie dowolnym punktem należącym do zbioru X₀. W punkcie x określimy zbiór indeksów ograniczeń aktywnych

A(x) = {i ∈ [1: m]: g_i (x) = 0}.

Z ciągłości funkcji g_i wynika, że jeśli ograniczenie nie jest aktywne
w x, tzn. g_i (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 σ>0 takie, że dla  ∈  σ zachodzą nierówności

g_i (x + d) ≤ 0, ∀i ∈ A(x).

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

<∇g_i (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: <∇g_i (), d〉 ≤ 0, i ∈ A()}

istnieją:

n-wymiarowa różniczkowalna funkcja wektorowa

e() = [e₁ (), ..., e_n ()]^T

określona w przedziale [0; 1],

oraz liczba  > 0 takie, że

1. e (0) = ,

2. e () ∈ X₀, dla 0 ≤  ≤ 1,

3. = d.

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

Twierdzenie Kuhna - Tuckera

Jeśli:

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

2. jest lokalnym minimum zadania,

3. w jest spełniony warunek regularności ograniczeń,

to istnieje wektor  ∈ R^m, ≥ 0, taki, że

∇f () + ∇g_i() = 0,

g_i() = 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 = Rⁿ. Załóżmy, że funkcje f : Rⁿ → R¹, g: Rⁿ → , h: Rⁿ → mają ciągłe pochodne cząstkowe oraz, że w minimum lokalnym spełniony jest warunek regularności ograniczeń.

Wówczas istnieją wektory ∈ , ≥ 0, oraz ∈ , takie, że

∇f () + ∇g_i() + ∇h_i() = 0,

g_i() = 0, i = 1, ..., m_g.

Ograniczeniom nierównościowym odpowiadają mnożniki nieujemne  ≥ 0, natomiast ograniczeniom równościowym - mnożniki  o dowolnym znaku.

Inna postać warunków Kuhna - Tuckera

Dla zadania programowania nieliniowego utwórzmy funkcję Lagrange'a, a mianowicie

L(x, ) = f (x) + _i g_i (x).

Warunki konieczne można zapisać w postaci

∇_x L(,) = 0,

<, ∇_ L(,)〉 = 0,

∇_ L(,) ≤ 0,

≥ 0,

gdzie ∇_x oznacza gradient funkcji Lagrange'a względem x, zaś ∇_ - gradient względem .

Dla ogólnej postaci zadania programowania, przy X = Rⁿ, można sformułować warunki konieczne optymalności Kuhna - Tuckera. Definiując funkcję Lagrange'a

L(x, , ) = f (x) + _i g_i(x) + _i h_i(x),

warunki te można zapisać następująco

∇_x L(,, ) = 0,

<, ∇_ L(,,)〉 = 0,

∇_ L(,,) ≤ 0,

∇_μ L(,,) = 0,

≥ 0, nieograniczone w znaku.

Warunki wystarczające optymalności

Jak wynika z poprzednich rozważań, warunki Kuhna - Tuckera są tylko warunkami koniecznymi optymalności, tzn. każdy regularny punkt będący rozwiązaniem zadania programowania nieliniowego spełnia warunki Kuhna - Tuckera, lecz nie każdy punkt spełniający te warunki jest szukanym minimum zadania. Warunki Kuhna - Tuckera mogą zatem służyć jedynie do stwierdzenia nieoptymalności danego punktu.

Warunki wystarczające optymalności wiążą się ściśle z wypukłością funkcji f i g_i. Jeśli w zadaniu programowania nieliniowego:

1. funkcje f i g_i są różniczkowalne,

2. funkcje f i g_i są wypukłe,

3. w ∈ X₀ spełnione są warunki Kuhna - Tuckera,
   ∇f () + ∇g_i() = 0, g_i() = 0, i = 1, ..., m.

to punkt jest rozwiązaniem zadania programowania nieliniowego.

Inna postać warunków Kuhna - Tuckera

Program postaci:

Dla zadania programowania nieliniowego utwórzmy funkcję Lagrange'a, a mianowicie

Zdefiniowano podstawienia:

Warunki konieczne można zapisać w postaci