Temat: Metoda zewnętrznej i wewnętrznej funkcji kary.

1. Opis metod.

Metody funkcji kary polegają na zamianie zadania optymalizacji z ograniczeniami na zadania bez ograniczeń, poprzez wprowadzenie pomocniczej funkcji P¹(x), będącej idealną funkcją kary za naruszenie zbioru dopuszczalnego:

Człon kary jest dodawany do funkcji celu, przez co tworzy się nowa funkcja celu.

Łatwo zauważyć, że minimalizacja funkcji celu Q(x) w zbiorze dopuszczalnym Ф jest równoznaczna z minimalizacją nowej funkcji celu C(x) bez ograniczeń.

Funkcję P¹(x) można interpretować jako nieskończenie wielką karę liczbową nakładaną na funkcję celu za wyjście poza zbiór dopuszczalny Ф.

Jak widać z powyższej funkcji kary P¹(x) dla wartości nie należącej do zbioru dopuszczalnego Ф funkcja ta przyjmuje wartość równą ∞. Aby zaimplementować to na komputerach, przyjmuje się inną funkcję kary:

gdzie L jest bardzo dużą liczbą dodatnią.

Jak widać występuje tutaj problem z nieciągłością funkcji C(x) i jej dużym skokiem w punkcie nieciągłości. Metody optymalizacji bez ograniczeń wymagają, aby funkcja celu była klasy C1, a przynajmniej była funkcją ciągłą.

Przy praktycznej realizacji idei funkcji kary tworzy się ciąg funkcji kary (tym razem ciągłych)

a zadanie optymalizacji z ograniczeniami sprowadza się do ciągu zadań bez ograniczeń.

W wyniku rozwiązywania tych zadań otrzymuje się ciąg punktów optymalnych {x_iopt}.
Taki ciąg rozwiązań optymalnych jest zbieżny do rozwiązania zadania pierwotnego (tego z ograniczeniami)

Funkcje kary można podzielić na dwa rodzaje:

- zewnętrzną funkcję kary

- wewnętrzną funkcję kary

Metoda zewnętrznej funkcji kary:

W tej metodzie funkcje kary P_i(x) dążą do P¹(x) na zewnątrz zbioru dopuszczalnego spełniając następujące warunki:

Jako zewnętrzną funkcję kary można przyjąć funkcję postaci

Można zauważyć, że przy takiej funkcji kary, przy zmniejszającym się do zera, współczynniku r_i funkcja kary będzie dążyć do idealnej funkcji kary P_i(x).

Współczynnik r_i jest przyjmowany na początku zadania, zaś jego wartość w następnych krokach zadnia jest obliczana wg wzoru:

gdzie c jest liczbą z zakresu 4-10 przyjmowaną na początku zadania.

Jeżeli chcielibyśmy zaimplementować tę metodę na komputerze to jako funkcji kary można użyć takiej:

Funkcja ta ma własności podobne do powyżej podanej.

Metoda wewnętrznej funkcji kary (metoda funkcji barierowych):

W tej metodzie funkcje kary P_i(x) dążą do P¹(x) od wewnątrz zbioru dopuszczalnego, w taki sposób, że im bliżej jesteśmy granic tego zbioru, tym funkcja kary przyjmuje większe wartości.

Funkcja celu przyjmuje postać:

Jako wewnętrzną funkcję kary można przyjąć funkcję postaci

Można zauważyć, że przy takiej funkcji kary, przy zmniejszającym się do zera, współczynniku r_i funkcja kary będzie dążyć do idealnej funkcji kary P_i(x).

2. Kryterium zbieżności, algorytm metod.

Jako kryterium zbieżności można przyjąć warunek, aby odległość dwóch punktów optymalnych była mniejsza od zadanej wielkości ε_o.

Algorytm obliczania zadań dla obu metod jest ten sam.

Różni się on tylko obliczaną zastępczą funkcją celu C(x).

Algorytm:

Krok 1. Wybrać ε_o>0, dla kryterium zbieżności. Wybrać punkt początkowy x⁰, wybrać parametr funkcji kary r₀>0, k=0, oraz
.

Krok 2. Startując z punktu x⁰ rozwiązujemy zadanie programowania liniowego bez ograniczeń z zastępczą funkcją celu C(x). Otrzymamy rozwiązanie x^k+1.

Krok 3. Jeśli x^k+1 - x^k < ε_o to kończymy obliczenia, a jeżeli jest większe to liczymy dalej przyjmując za: k=k+1, oraz r_k+1=r_k/c i powracamy do kroku 2.

3. Metoda mieszanej funkcji kary.

Ponieważ często minimum leży na brzegu obszaru dopuszczalnego, dobrą efektywność numeryczną w poszukiwaniu minimum wykazuje algorytm mieszany polegający na zbliżaniu się do minimum z zewnątrz metodą zewnętrznej funkcji kary, a od wewnątrz metodą wewnętrznej funkcji kary.

4. Podsumowanie.

Wady:

• Pewnym utrudnieniem przy stosowaniu metody funkcji barierowych jest konieczność wystartowanie z punktu dopuszczalnego x₀= Ф, często trudno jest znaleźć taki punkt. Wtedy trzeba stosować np. metodę Monte Carlo do znalezienia pierwszego punktu dopuszczalnego, który mógłby być punktem startowym do minimalizacji wewnątrz zbioru dopuszczalnego.

• W przypadku metody funkcji kary zewnętrznej otrzymana zastępcza funkcja celu jest nieciągła, zatem koncepcja nie nadaje się do praktyki numerycznej.

Zalety:

• Dzięki zastosowaniu metod funkcji kary możliwe jest uniknięcie bezpośredniego rozpatrywania wartości ograniczeń i możliwość zastosowania znanych metod optymalizacji bez ograniczeń.

• Zastępuje zadanie programowania nieliniowego ograniczeniami zadaniem programowania nieliniowego bez ograniczeń

• Konstruowanie i rozwiązywanie kolejnych problemów pomocniczych można ciągnąć na ogół dowolnie długo

• Zaletami zewnętrznej funkcji kary jest uniwersalność i prostota

Metoda zewnętrznej i wewnętrznej funkcji kary.

Przygotowali: Adam Klaja, Piotr Krusiński

1

a

b

Ф

x

Q(x)

P¹(x)

x

P¹(x)=+∞

P¹(x)=+∞

b

a

C(x)

x

C(x)=+∞

b

a

C(x)=+∞

x_1opt

C(x)=+∞

C(x)

x

b

a

b

a

P¹(x)=+∞

P₁(x)

P¹(x)

x

Q(x)

x

Ф

b

a

x_2opt

x_3opt

C₁(x)

C₂(x)

C₃(x)

P₂(x)

P₃(x)

a

b

Ф

x

Q(x)

x

B¹(x)

B₁(x)

x

a

b

a

b

x

C(x)

x₃

x_1opt

x_2opt

x_3opt

C₁(x)

C₂(x)

C₃(x)

B₂(x)

B₃(x)

x₂

x₁

x₃

x₂

x₁

Metody wewnętrznej funkcji kary

Metody zewnętrznej funkcji kary

Ф