TECHNIKA OPTYMALIZACJI - LABOLATORIUM
Ćwiczenie IV: Programowanie nieliniowe z ograniczeniami
Skład grupy:
- Dawid Cekus - Mateusz Grzelak

Zadanie programowania nieliniowego z ograniczeniami, algorytmy optymalizacji lokalnej

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z podstawową metodą rozwiązywania

nieliniowego zadania optymalizacji z ograniczeniami ZPN na przykładzie wybranego

algorytmu optymalizacji lokalnej z ograniczeniami.

2. Część zadaniowa

2.1 Znalezienie optymalnego rozwiązania z ograniczeniem liniowym dla funkcji i parametrów

2.1.1 Parametry 1

Funkcja:

f(x) = x₁⁴ + x₂⁴ − 2x₁²x₂ − 4x₁ + 3

Ograniczenie liniowe:

x₁ + x₂ ≥ 6

Punkt startowy:

$$x = \left\lbrack \ \begin{matrix} 2.5\ \\ 2.5 \\ \end{matrix} \right\rbrack$$

TolCon = 1e − 15

Otrzymane rezultaty:

x =

3.0962

2.9038

fval = 97.9406

exitflag = 1

output =

iterations: 7

funcCount: 31

constrviolation: 0

stepsize: 3.3667e-06

algorithm: 'interior-point'

firstorderopt: 3.1778e-05

cgiterations: 3

message: [1x779 char]

Na poniższym rysunku wielokolorowy obszar to funkcja na której szukamy minimum, a obszar „różowy” to funkcja ograniczająca, w tym przypadku liniowa – płaszczyzna, przykrywająca minimum funkcji, co oznacza że jest ona ograniczeniem aktywnym, prostszymi słowy pokrywa ona „najbardziej zaciemniony” obszar.

Poniżej zilustrowałem kolejne kroki – kropki od 0 (punkt startowy) do 7 (rozwiązanie) – zgodnie z liczbą iteracji, którymi poruszał się algorytm szukając optymalnego rozwiązania. Rysunek poniższy został pozbawiony warstwic w celu lepszej widoczności, jest on jednak tym samym obszarem co rysunek powyższy. Część punktów pokrywa się ponieważ kolejne iteracje znajdują się bardzo blisko siebie, tzn coraz bliżej rozwiązania.

Poniższy wykres prezentuje wartość rozwiązania (oś pionowa) w kolejnych iteracjach (oś pozioma). Moim zdaniem położenie kolejnych punktów poniekąd odzwierciedla wygląd funkcji, która w szukanym obszarze dąży do tylko jednego minima względnie bliskiemu punktowi startowemu.

Poniższy wykres przedstawia wartość przekroczenia ograniczenia (oś pionowa) w kolejnych iteracjach algorytmu (oś pozioma)

2.1.2 Parametry 2, wybrany inny punkt startowy – porównanie wyników.

Funkcja:

f(x) = x₁⁴ + x₂⁴ − 2x₁²x₂ − 4x₁ + 3

Ograniczenie liniowe:

x₁ + x₂ ≥ 6

Punkt startowy:

$$x = \left\lbrack \ \begin{matrix} 1\ \\ 1 \\ \end{matrix} \right\rbrack$$

TolCon = 1e − 15

Otrzymane rezultaty:

x =

3.0962

2.9038

fval =97.9406

exitflag =1

output =

iterations: 11

funcCount: 45

constrviolation: 0

stepsize: 2.8202e-06

algorithm: 'interior-point'

firstorderopt: 6.8965e-06

cgiterations: 0

message: 'Local minimum found that satisfies the constraints.

Interpretacja rysunków i wykresów analogiczna jak w pierwszym przykładzie. Różnice widać w większej ilości iteracji niż w przypadku poprzednim. Jest to spowodowane większą odległością punktu startowego od rozwiązania końcowego.

2.1.3 Sprawdzenie wartości przekroczenia ograniczenia i dokładności.

%wartość ograniczenia w punkcie optymalnym x.

cvtest = x(1) + x(2) – 6

cvtest = 2.5490e-08

Wartość przekroczenia ograniczenia wynosi około 7 rzędów wartości więcej niż tolerancja.

2.2 Znalezienie optymalnego rozwiązania z ograniczeniem nieliniowym

Funkcja:

f(x) = x₁⁴ + x₂⁴ − 2x₁²x₂ − 4x₁ + 3

Ograniczenie liniowe:

−12x₁³ − 1.2x₂³ + 6 ≥ 0

Punkt startowy:

$$x = \left\lbrack \ \begin{matrix} 2.5\ \\ 2.5 \\ \end{matrix} \right\rbrack$$

TolCon = 1e − 15

Otrzymane rezultaty:

x =

1.5108

1.1577

fval = -1.3220

exitflag = 1

output =

iterations: 12

funcCount: 43

constrviolation: 0

stepsize: 1.2667e-05

algorithm: 'interior-point'

firstorderopt: 4.0168e-07

cgiterations: 1

message: [1x779 char]

Na poniższym rysunku wielokolorowy obszar to ta sama funkcja na której szukamy minimum jak w punkcie 2.1, a obszar „różowy” to funkcja ograniczająca, w tym jednak przypadku nieliniowa – wypukła, przykrywająca minimum funkcji, co oznacza że jest ona ograniczeniem aktywnym, prostszymi słowy pokrywa ona „najbardziej zaciemniony” obszar.

Poniżej zilustrowałem kolejne kroki – kropki od 0 (punkt startowy) do 12 (rozwiązanie) – zgodnie z liczbą iteracji, którymi poruszał się algorytm szukając optymalnego rozwiązania. Rysunek poniższy został pozbawiony warstwic w celu lepszej widoczności, jest on jednak tym samym obszarem co rysunek powyższy. Część punktów pokrywa się ponieważ kolejne iteracje znajdują się bardzo blisko siebie, tzn coraz bliżej rozwiązania.

Poniższy wykres prezentuje wartość rozwiązania (oś pionowa) w kolejnych iteracjach (oś pozioma). Myślę, że warto zwrócić uwagę na to, że wykres wygląda inaczej niż w przypadku ograniczenia liniowego, pomimo iż punkt startowy pozostał ten sam, głównie dlatego że punkt końcowy (optimum) zmieniło się (tym razem jest ujemne) wykres jest więc tak jakby „odwrócony” ponieważ my zbliżamy się od wartości dodatniej (punkt startowy).

Poniższy wykres przedstawia wartość przekroczenia ograniczenia (oś pionowa) w kolejnych iteracjach algorytmu (oś pozioma)

2.2.1 Sprawdzenie wartości przekroczenia ograniczenia i dokładności.

%wartość ograniczenia w punkcie optymalnym x.

cvtest = -1.2*(x(1).^3)-1.2*(x(2).^3)+6

cvtest = -1.1802e-06

Wartość przekroczenia ograniczenia wynosi około 9 rzędów wartości więcej niż tolerancja.

2.3 Znalezienie optymalnego rozwiązania z ograniczeniem nieliniowym

2.3.1 Parametry 1

Funkcja:

$$f\left( x \right) = 4x_{1}^{2} - 2.1x_{1}^{4} + \frac{1}{3}x_{1}^{6} - x_{1}x_{2} - 4x_{2}^{2} - 4x_{2}^{4}$$

Ograniczenie liniowe:

−(x₁² + 0.1)² + x₂² + 5.5 ≥ 0

Punkt startowy:

$$x = \left\lbrack \ \begin{matrix} 2.5\ \\ 2.5 \\ \end{matrix} \right\rbrack$$

TolCon = 1e − 15

Otrzymane rezultaty:

x =

2.2578

-0.2435

fval = 9.2036

output =

iterations: 15

funcCount: 53

lssteplength: 1

stepsize: 8.9927e-08

algorithm: [1x44 char]

firstorderopt: 1.0869e-06

constrviolation: 2.7426e-10

message: [1x762 char]

Na poniższym rysunku wielokolorowy obszar to funkcja na której szukamy minimum, a obszar „różowy” to funkcja ograniczająca, w tym przypadku nieliniowa, przykrywająca minimum funkcji, co oznacza że jest ona ograniczeniem aktywnym, prostszymi słowy pokrywa ona „najbardziej zaciemniony” obszar. Funkcja celu jest symetryczna, w związku z tym gdyby obszar ograniczenia był liniowy lub też symetryczny istniały by dwa lub więcej rozwiązań. Nie widać tego na rysunku ale ograniczenie jest przesunięte na jednej z osi co powoduje że istnieje tylko jedno minimum przy zadanym ograniczeniu.

Poniżej zilustrowałem kolejne kroki – kropki od 0 (punkt startowy) do 16 (rozwiązanie) – zgodnie z liczbą iteracji, którymi poruszał się algorytm szukając optymalnego rozwiązania. Rysunek poniższy został pozbawiony warstwic w celu lepszej widoczności, jest on jednak tym samym obszarem co rysunek powyższy.

Poniższy wykres prezentuje wartość rozwiązania (oś pionowa) w kolejnych iteracjach (oś pozioma).

Poniższy wykres przedstawia wartość przekroczenia ograniczenia (oś pionowa) w kolejnych iteracjach algorytmu (oś pozioma)

2.3.2 Parametry 2, wybrany inny punkt startowy – porównanie wyników.

Funkcja:

$$f\left( x \right) = 4x_{1}^{2} - 2.1x_{1}^{4} + \frac{1}{3}x_{1}^{6} - x_{1}x_{2} - 4x_{2}^{2} - 4x_{2}^{4}$$

Ograniczenie liniowe:

−(x₁² + 0.1)² + x₂² + 5.5 ≥ 0

Punkt startowy:

$$x = \left\lbrack \ \begin{matrix} 0\ \\ 0 \\ \end{matrix} \right\rbrack$$

TolCon = 1e − 15

Otrzymane rezultaty:

x =

2.2578

-0.2435

fval = 9.2036

exitflag =1

output =

iterations: 10

funcCount: 37

constrviolation: 0

stepsize: 1.2718e-07

algorithm: 'interior-point'

firstorderopt: 3.1721e-06

cgiterations: 0

message: [1x779 char]

Interpretacja rysunków i wykresów analogiczna jak w poprzednim przykładzie. Różnice widać w mniejszej ilości iteracji niż w przypadku poprzednim. Jest to spowodowane mniejszą odległością punktu startowego od rozwiązania końcowego.

2.3.3 Sprawdzenie wartości przekroczenia ograniczenia i dokładności.

%wartość ograniczenia w punkcie optymalnym x.

cvtest =-((x(1)+0.1).^2)+(x(2).^2)+5.5

cvtest =-4.9014e-08

Wartość przekroczenia ograniczenia wynosi około 7 rzędów wartości więcej niż tolerancja.

3. Wnioski

Z przedstawionych rozwiązań wynika, iż funkcja fmincon bardzo dobrze radzi sobie z zagadnieniami optymalizacji funkcji z warunkami ograniczającymi. Zauważono jednak, iż jeśli punkt startowy jest znacznie wysunięty poza obszar ograniczający otrzymywano błędne rezultaty. Warto podkreślić, iż znajdywanie minimum lub maksimum możliwe jest tylko wtedy gdy da się obliczyć hesjan. W przypadku nieciągłych funkcji, w celu znalezienia globalnych lub lokalnych ekstremów optymalizację najlepiej wykonywać przy pomocy algorytmów: globalsearch, patternsearch, czy algorytmem genetycznym.