Programowanie nieliniowe –
metody numeryczne
Programowanie nieliniowe –
metody numeryczne
Metody numeryczne rozwiązywania zadań
programowania nieliniowego
Analityczne metody rozwiązywania zadań programowania nieliniowego mogą się okazać
nieskuteczne:
•
gdy funkcja celu i/lub ograniczenia mają złożoną postać,
•
gdy funkcja celu i/lub ograniczenia nie są dane w postaci jawnych funkcji zależnych
od zmiennych decyzyjnych,
•
gdy funkcja celu i/lub ograniczenia nie spełniają założenia o ciągłości i
różniczkowalności.
Brak możliwości wykorzystania metod analitycznych
=>
Wykorzystanie metod numerycznych
=>
Algorytmy iteracyjne, prowadzące do uzyskania rozwiązań przybliżonych.
Metody numeryczne rozwiązywania zadań
programowania nieliniowego
ETAPY REALIZACJI ALGORYTMÓW ITERACYJNYCH
1. wybór punktu startowego x
0
, etap k = 0,
2. wyznaczenie kierunku d
k
, w którym należy podążać, aby poprawić wartość funkcji
celu Q(x) według wybranej strategii,
3. określenie długości kroku
l
k
od punktu x
k
w kierunku d
k
do punktu x
k+1
będącego
poprawionym rozwiązaniem zadania,
4. wyznaczenie kolejnego (poprawionego) rozwiązania zadania x
k+1
= x
k
+
l
k
d
k
,
5. sprawdzenie, czy przybliżenie rozwiązania optymalnego jest zadowalające. Jeśli TAK
=> STOP, jeśli NIE => k = k + 1 i powrót do punktu 2.
Metody numeryczne rozwiązywania zadań
programowania nieliniowego
ISTOTNE CECHY ALGORYTMÓW NUMERYCZNYCH
•
zbieżność algorytmu:
algorytm jest zbieżny, jeśli istnieje granica ciągu rozwiązań przybliżonych x
k
otrzymanych w kolejnych
iteracjach:
lim
𝑘→∞
𝑥
𝑘
= 𝑥
∗
•
wybór punktu startowego x
0
:
–
determinuje znalezienie najbliższego minimum lokalnego,
–
może być zdeterminowany lub wybrany w sposób losowy,
•
kryteria zatrzymania algorytmu:
–
Q(x
k+1
) - Q(x
k
) ≤
e,
–
x
k
– x* ≤
e,
–
czas realizacji algorytmu,
–
liczba iteracji algorytmu.
Minimalizacja funkcji jednej zmiennej –
algorytmy bezgradientowe
ALGORYTMY BEZGRADIENTOWE
•
zakładając, że funkcja jest wypukła i na obszarze <a, b> ma minimum, możliwe jest
zaistnienie przypadków:
–
Q(x
1
) < Q(x
2
) => można odrzucić przedział (x
2
, b) z obszaru poszukiwań,
–
Q(x
1
) > Q(x
2
) => można odrzucić przedział (a, x
1
) z obszaru poszukiwań,
–
Q(x
1
) = Q(x
2
) => można ograniczyć obszar poszukiwań do obszaru (x
1
, x
2
).
Minimalizacja funkcji jednej zmiennej –
algorytmy bezgradientowe
ALGORYTMY BEZGRADIENTOWE - ETAPY
1. wybór przeszukiwanego obszaru <a, b>,
D
0
= b - a,
2. ustalenie punktów wewnętrznych x
1
, x
2
w przeszukiwanym obszarze, dla których
obliczana będzie wartość funkcji celu Q(x),
3. sprawdzenie warunku:
–
Q(x
1
) ≤ Q(x
2
) => nowy koniec obszaru przeszukiwanego: b = x
2
,
D
k
= b - a,
–
Q(x
1
) > Q(x
2
) => nowy początek obszaru przeszukiwanego: a = x
1
,
D
k
= b - a,
4. sprawdzenie czy spełnione jest kryterium zatrzymania algorytmu:
–
jeśli TAK => STOP,
–
Jeśli NIE => powrót do punktu 2 algorytmu.
Minimalizacja funkcji jednej zmiennej –
algorytmy bezgradientowe
ALGORYTM PODZIAŁU NA RÓWNE CZĘŚCI
•
jeśli wiadomo, że funkcja:
–
jest wypukła na obszarze <a, b>,
–
ma minimum na obszarze <a, b>,
•
można podzielić obszar poszukiwań na równe części za pomocą K punktów
wewnętrznych,
•
należy sprawdzić czy Q(x
i
) < Q(x
i+1
) i odpowiednio odrzucić przedział:
–
<a, x
i
), gdy Q(x
i
) > Q(x
i+1
) => a = x
i
,
–
(x
i+1
, b>, gdy Q(x
i
) ≤ Q(x
i+1
) => b = x
i+1
,
•
jeśli dokładność przybliżenia
x
k
– x* ≤
e,
–
1
𝐾+1
≤ 𝜀 ⇒ 𝐾 ≥
1
𝜀
− 1
Minimalizacja funkcji jednej zmiennej –
algorytmy bezgradientowe
ALGORYTM DYCHOTOMII
•
jeśli wiadomo, że funkcja:
–
jest wypukła na obszarze <a, b>,
–
ma minimum na obszarze <a, b>,
•
należy sprawdzić czy Q(x
1
) < Q(x
2
), gdzie:
–
x
1
= a + (
D
0
-
d)/2,
–
x
2
= a + (
D
0
+
d)/2,
•
w zależności od wyniku, należy odpowiednio odrzucić przedział:
–
<a, x
1
), gdy Q(x
1
) > Q(x
2
) => a = x
1
,
–
(x
2
, b>, gdy Q(x
1
) ≤ Q(x
2
) => b = x
2
,
•
jeśli
x
k
– x* ≤
e,
– ∆
1
=
1
2
∆
0
+ 𝛿 ; ∆
2
=
1
2
∆
0
+𝛿
2
+
𝛿
2
; … ; ∆
𝑘
=
∆
0
2
𝑘
+ 𝛿 1 −
1
2
𝑘
;
–
∆
𝐾
∆
0
=
1
2
𝐾
+
𝛿
∆
0
1 −
1
2
𝐾
≤ 𝜀
Minimalizacja funkcji jednej zmiennej –
algorytmy bezgradientowe
ALGORYTM FIBONACCIEGO
•
jeśli wiadomo, że funkcja:
–
jest wypukła na obszarze <a, b>,
–
ma minimum na obszarze <a, b>,
•
należy sprawdzić czy Q(x
1
k
) < Q(x
2
k
), gdzie:
–
x
1
k=2
= a +
a
2
D
0
,
x
2
k=2
= b -
a
2
D
0
=
a + (1 -
a
2
)D
0
, 𝛼
2
=
𝐹
𝐾−2
𝐹
𝐾
–
x
1
k
= a
k-1
+
a
k
D
k-1
,
x
2
k
= a
k-1
+ (1 –
a
k
)D
k
-1
, 𝛼
𝑘
=
𝐹
𝐾−𝑘
𝐹
𝐾− 𝑘−1
, dla k = 3, 4, 5, …
–
ciąg liczb Fibonacciego {F
k
}: F
0
= F
1
= 1; F
k
= F
k-1
+ F
k-2
dla k = 2,3,4…
•
w zależności od wyniku, należy odpowiednio odrzucić przedział:
–
<a, x
1
), gdy Q(x
1
) > Q(x
2
) => a = x
1
,
–
(x
2
, b>, gdy Q(x
1
) ≤ Q(x
2
) => b = x
2
,
•
jeśli
x
k
– x* ≤
e,
– ∆
2
= 1 − 𝛼
2
∆
0
= 1 −
𝐹
𝐾−2
𝐹
𝐾
∆
0
=
𝐹
𝐾−1
𝐹
𝐾
∆
0
; ∆
𝑘
=
𝐹
𝐾− 𝑘−1
𝐹
𝐾
∆
0
; …
–
∆
𝐾
∆
0
=
𝐹
1
2𝐹
𝐾
≤ 𝜀
Minimalizacja funkcji jednej zmiennej –
algorytmy gradientowe
ALGORYTM PRZESZUKIWANIA JEDNOWYMIAROWEGO
•
jeśli wiadomo, że funkcja:
–
jest wypukła i ma minimum na obszarze <a, b>,
–
jest funkcją różniczkowalną na obszarze <a, b>,
•
należy wyznaczyć wartość pochodnej funkcji Q(x) w punkcie x
1
:
–
x
1
= a +
D
0
/ 2
=
a + (b-a)/ 2
,
•
w zależności od wyniku, należy odpowiednio odrzucić przedział:
–
<a, x
1
), gdy Q’(x
1
) < 0 => a = x
1
,
–
(x
1
, b>, gdy Q’(x
1
) > 0 => b = x
1
,
•
jeśli
x
k
– x* ≤
e =>
𝑏 − 𝑎 ≤ 2𝜀.
x
1
Q(x)
Q’(x
1
) > 0
Minimalizacja funkcji jednej zmiennej –
algorytmy gradientowe
ALGORYTM SIECZNYCH
•
jeśli wiadomo, że funkcja:
–
jest wypukła i ma minimum na obszarze <a, b>,
–
jest funkcją różniczkowalną na obszarze <a, b>,
•
należy wyznaczyć wartość pochodnej funkcji Q(x) w punkcie x
1
, x
2
:
–
x
1
= a
,
x
2
= b,
•
wyznaczyć współrzędną punktu x
m
przecięcia odcinka łączącego Q’(x
1
) i Q’(x
2
):
– 𝑥
𝑚
=
𝑄
′ 𝑥1 𝑥2−𝑄′ 𝑥2 𝑥1
𝑄
′ 𝑥1 −𝑄′ 𝑥2
,
•
należy sprawdzić warunek: Q’(x
m
)Q’(x
2
) < 0 i, w zależności
od wyniku, odpowiednio odrzucić przedział:
–
<a, x
m
), gdy Q’(x
m
)Q’(x
2
) < 0 => a = x
m
,
–
(x
m
, b>, gdy Q’(x
m
)Q’(x
2
) > 0 => b = x
m
,
•
jeśli
x
k
– x* ≤
e =>
𝑏 − 𝑎 ≤ 2𝜀.
Minimalizacja funkcji jednej zmiennej –
przykład
Z prostokąta o wymiarach 8 x 3 cm, wycinając jego rogi, wykonane ma zostać
prostopadłościenne pudełko jak na rysunku. Objętość pudełka powinna być jak
największa. Jaką przyjąć wysokość pudełka x, aby nie różniła się ona od rozwiązania
optymalnego o więcej niż
e
:
x – x* ≤
e
= 0,05D
0
.
Minimalizacja funkcji wielu zmiennych
ALGORYTM GAUSSA – SEIDELA (RELAKSACYJNY)
•
polega na poruszaniu się wzdłuż kierunków poszukiwań, zgodnych z kierunkami układu
współrzędnych, tak aby osiągnąć szukane minimum za pomocą zmiany tylko jednej współrzędnej
w jednym kroku.
•
Etapy:
1.
wybierz punkt startowy x
i
, i = 0,
2.
wybierz kierunek poszukiwań / przemieszczenia e
i
,
3.
w kierunku e
i
znajdź taką odległość
l
i
od punktu x
1
, w jakiej funkcja Q(x
i
+
l
i
e
i
) ma minimum,
4.
wyznacz nowy punkt x
i+1
= x
i
+
l
i
e
i
i przyjmij go za punkt początkowy kolejnej minimalizacji,
5.
sprawdź, czy Q(x
i+1
) - Q(x
i
) ≤
e
i – gdy warunek niespełniony –
wybierz nowy kierunek poszukiwań i wróć do punktu 2 algorytmu.
•
Zaletą jest prostota algorytmu,
wadą – niedostosowanie kierunków
poszukiwań do postaci funkcji.
Minimalizacja funkcji wielu zmiennych
ALGORYTM NAJSZYBSZEGO SPADKU
•
Algorytm bazuje na twierdzeniu, że:
wektor gradientu grad Q(x
0
) wyznacza kierunek najszybszego wzrostu funkcji Q(x) od punktu x
0
, a wektor
przeciwny do gradientu, -grad Q(x
0
), wyznacza kierunek najszybszego spadku funkcji Q(x) od punktu x
0
.
•
Etapy:
1.
wybierz punkt startowy x
i
, i = 0,
2.
oblicz gradient grad Q(x
i
) i przyjmij za kierunek poszukiwań wektor d
i
= - grad Q(x
i
),
3.
w kierunku d
i
znajdź taką odległość
l
i
od punktu x
i
, w jakiej funkcja Q(x
i
+
l
i
e
i
) ma minimum,
4.
wyznacz nowy punkt x
i+1
= x
i
+
l
i
e
i
i przyjmij go
za punkt początkowy kolejnej minimalizacji,
5.
sprawdź, czy Q(x
i+1
) - Q(x
i
) ≤
e
i – gdy warunek niespełniony –
wybierz nowy kierunek poszukiwań i wróć do punktu
2 algorytmu.
Minimalizacja funkcji wielu zmiennych –
przykład
Startując z punktu x = (0,0) należy znaleźć minimum funkcji:
𝑄 𝑥 = 𝑥
1
2
− 𝑥
1
𝑥
2
+ 𝑥
2
2
− 2𝑥
2