Metody numeryczne  laboratorium nr 6
Programowanie nieliniowe
Wprowadzenie
Zadanie minimalizacji funkcji bez ograniczeń polega na znalezieniu w punktu x �� Rn, dla którego
funkcja przyjmuje minimalną wartość. Szukamy więc:
)�
f (�x)� =� min f (�x)�,
x��Rn
gdzie f: R��Rn, oraz f ograniczona z dołu. Należy zwrócić uwagę na fakt, że funkcja f ma dowolną
postać, w związku z tym niezbędne staje się zastosowanie narzędzi bardziej ogólnych od tych
służących do rozwiązywania zadań programowania liniowego.
Przy realizacji tego ćwiczenia interesować nas będą metody numeryczne poszukiwania
minimum funkcji bez ograniczeń polegające na przeszukiwaniu przestrzeni rozwiązań wzdłuż pewnych
prostych, zwanych kierunkami poszukiwań. Podzielić je można między innymi na dwa główne typy:
metody poszukiwań prostych, w których bada się zachowanie funkcji w kilku punktach leżących na
kierunku poszukiwań, przy czym ich wybór ustalany jest na początku każdej iteracji; oraz na metody z
minimalizacją, inaczej metody kierunków popraw, w których określa się minimum wzdłuż kierunku
poszukiwań, używając jednego z algorytmów minimalizacji kierunkowej.
Minimalizacja kierunkowa polega na znalezieniu minimum funkcji wzdłuż kierunku
określanego w myśl zasady:
xk+�1 ��T(�xk ,dk )�,
gdzie
)�
T(�x,d)� =� {�y : y =� x +�t�d,t� ��j�(�x,d)�}�,
)�
przy czym j� jest zbiorem optymalnych wartości współczynnika kroku.
Metoda złotego podziału (minimalizacja kierunkowa)
Algorytm obliczeń
k k
1. Jeśli f (�x2 )�>� f (�x1 )�, to
k
bk +�1 =� x2 ,
k+�1 k
x2 =� x1 ,
k+�1
x1 =� a�ak +� (�1-�a�)�bk+�1 .
k k
2. Jeśli f (�x2 )�Ł� f (�x1 )�, to
k
ak+�1 =� x1 ,
k+�1 k
x1 =� x2 ,
k+�1
x2 =� a�bk +� (�1-�a�)�ak+�1 .
k k
Kryterium zbieżności: x1 -� ak =� bk -� x2 <� D� .
Oznaczenia wielkości wejściowych:
a, b  krańce przedziału początkowego
x1, x2  punkty odpowiadające regule złotego podziału, spełniające zależność:
x2 -� a b -� x1
=� =� a� , gdzie a� @� 0.618.
b -� a b -� a
D� - dokładność bezwzględna.
1
Metoda Gaussa-Seidla (metoda kierunków popraw)
Minimalizacja funkcji f(x) wzdłuż ortogonalnej bazy d1, d2, ..., dn. Wersory układu współrzędnych
kartezjańskich. Jest to minimalizacja funkcji w kierunku.
Di (x) =� (�x,di)�
G
Odwzorowanie algorytmiczne metody Gaussa-Seidela można przedstawić w postaci złożenia 2n
n n 2 1
odwzorowań A(xk ) =� TDGTDG-�1...TDGTDG
Definiuje się odwzorowanie:
k k k k k
T(�x,di)�=�{�xi : f (�xi )�=� mij� f (�xi-�1 +� l�idi)�, xi =� xi-�1 +� l�idi}�.
n
x���
Algorytm obliczeń:
k
k = 1, x0 =� x0
Iteracja k-ta.
1. Dla i = 1...n oblicz kolejno:
k k
xi ��T(�xi-�1,di)�.
k k
2. Zbadaj, czy zostało spełnione kryterium zbieżności, jeżeli nie, to podstaw x0+�1 =� xn , k = k+1 i
powtórz punkt 1.
Kryterium zbieżności: przesunięcie wzdłuż wszystkich kierunków bazy jest mniejsze od wymaganej
dokładności l�i <� e� .
Oznaczenia wielkości wejściowych:
x0  dowolnie wybrany punkt startowy,
[d1, d2, ..., dn]  baza wejściowa utworzona ze wzajemnie ortogonalnych wektorów, na przykład
wersorów układu współrzędnych,
e� - wymagana dokładność obliczeń.
Przykładowy schemat działania algorytmu Gaussa-Seidla
2
Metoda Hooka i Jeevsa (poszukiwań prostych)
Algorytm obliczeń:
xB0 = x0
I. Etap próbny
1. Podstaw k = 1 oraz oblicz w punkcie x0 wartość funkcji q0 = f(x0).
2. Wzdłuż kierunku dk wykonaj krok próbny
xk = xk-1 + t�dk,
oraz oblicz wartość funkcji q = f(xk).
3. Zbadaj, czy q < q0, jeśli tak, to podstaw q pod q0 i przejdz
do punktu 6. Jeśli nie, przejdz
do
punktu nr 4.
4. Wykonaj krok w przeciwnym kierunku:
xk = xk - 2t�dk,
oraz oblicz q = f(xk).
5. Zbadaj, czy q < q0, jeśli tak, to podstaw q pod q0 i przejdz
do punktu 6. Jeśli nie, to podstaw
xk-1 w miejsce xk.
6. Sprawdz
, czy k = n. Jeśli nie, k = k + 1 i przejdz
do punktu 2. Jeśli tak, przejdz
do punktu 7.
7. Zbadaj, czy wystąpiły kroki, w których f(xB0) > f(xk). Jeśli tak, to podstaw xk w miejsce xB i
przejdz
do etapu roboczego. Jeśli nie, wykonaj krok 8.
8. Jeśli nie spełnione kryterium stopu, sprawdz
, czy jest to pierwsza iteracja. Jeśli tak, zmień
punkt startowy i powtórz czynności od punktu 1. Jeśli nie, to powróć do przeszukiwanego
wcześniej obszaru podstawiając x0 = xB0 , zmniejsz długość kroku o b�, podstawiając t� = b�t�,
oraz rozpocznij od kroku 1.
II. Etap roboczy:
1. Wykonaj krok roboczy
x0 = xB + (xB  xB0) = 2xB  xB0.
2. Podstaw xB w miejsce xB0 i wróć do etapu próbnego.
Kryterium zbieżności: Aktualna długość kroku t� < e�.
Oznaczenia wielkości wejściowych:
x0  dowolnie wybrany punkt startowy,
[d1, d2, ..., dn]  baza wejściowa utworzona ze wzajemnie ortogonalnych wektorów, na przykład
wersorów układu współrzędnych,
e� - wymagana dokładność obliczeń,
t� - początkowa długość kroku,
b� - współczynnik korekcyjny.
3
Przykładowy schemat działania algorytmu Hooka- Jeevesa
1 - start
4 - etap próbny (xB)
5 - etap roboczy
8 - etap próbny
9 - etap roboczy
13 - nie jest spełniony warunek (7), powrót do (8), zmniejszenie e
Zadanie:
Zaimplementuj i zbadaj wybrany algorytm (poszukiwań prostych, bądz
kierunków popraw z
minimalizacją kierunkową, na przykład jeden z powyższych, lub inny). Program powinien pozwalać co
najmniej na minimalizację funkcji dwóch zmiennych. Zbadaj jego działanie dla kilku różnych funkcji,
punktów startowych (najlepiej w okolicy różnych ekstremów) i kryteriów stopu. Opisz zachowanie
algorytmu dla różnych zestawów tych parametrów.
4