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