TECHNIKA OPTYMALIZACJI laboratorium
Ćwiczenie III: Zadanie programowania nieliniowego bez ograniczeń

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z jedną z metod rozwiązywania nieliniowego zadania optymalizacji bez ograniczeń na przykładzie algorytmu optymalizacji lokalnej.

Algorytm optymalizacji lokalnej dla zadania nieliniowej optymalizacji bez ograniczeń pozwala na wyliczenie takiego wektora zmiennych decyzyjnych $\hat{x}$, dla którego funkcja celu f(x) osiąga minimum:

$$\operatorname{}{f\left( x \right) = f(\hat{x})}$$

1. Przebieg ćwiczenia

   1. Zadanie testowe numer 3

f(x) = x₁ ² + x₁ * x₂ + 0.5 * x₂ ² − x₁ − x₂, punkt startowy x₀ = [3,  3]

Punkt optymalny: $\hat{x} = \left\lbrack 0,\ 1 \right\rbrack,$ $f(\hat{x}) = - 0.5$

Warstwice funkcji:

Z warstwic można w przybliżeniu odczytać położenie punktu optymalnego.

Wykres obliczeń w kolejnych iteracjach algorytmu

Rozwiązanie obliczone za pomocą Matlaba:
(przyjęte kryterium stopu dla wektora x TolX = 10^-6)

x = 0.0000 1.0000	fval = -0.5000	exitflag = 1	output = iterations: 59 algorithm: 'Nelder-Mead simplex direct search'

Optimization terminated: the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-006 and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-004

Wykres obliczeń w kolejnych iteracjach algorytmu

Kod z Matlaba:

[x,y]=meshgrid(-4:0.2:4, -4:0.2:4);

z=x.^2+x.*y+0.5.*y.^2-x-y;

figure(2)

contourf(x,y,z);

grid

figure(3)

surf(x,y,z);

tolx=10^-6;

tolfun=10^-1;

options=optimset('TolFun',tolfun,'PlotFcns',@optimplotfval);

fun = @(x)x(1).^2+x(1).*x(2)+0.5.*x(2).^2-x(1)-x(2);

x0=[2,4];

[x,fval,exitflag,output]=fminsearch(fun,x0,options)

1. Obliczenia zadania testowego 3 metodą analityczną

f(x) = x₁ ² + x₁ * x₂ + 0.5 * x₂ ² − x₁ − x₂

Liczymy gradient funkcji:

$$\text{grad\ f}\left( x \right) = \left\lbrack \frac{\partial f}{\partial x_{1}},\frac{\partial f}{\partial x_{2}} \right\rbrack = \lbrack 2x_{1} + x_{2} - 1,\ x_{1} + x_{2} - 1\rbrack$$

Rozwiązujemy równanie:

grad f(x) = 0

$\left\{ \begin{matrix} 2x_{1} + x_{2} - 1 = 0 \\ x_{1} + x_{2} - 1 = 0 \\ \end{matrix} \right.\ $ ⇒ $\left\{ \begin{matrix} x_{1} = 0 \\ x_{2} = 1 \\ \end{matrix} \right.\ $

$$\hat{x} = \lbrack 0,\ 1\rbrack$$

Liczymy macierz Hessego funkcji f(x)

$$H\left( \hat{x} \right) = \begin{bmatrix} \frac{\partial^{2}f}{\partial x_{1}^{\ 2}}\left( \hat{x} \right) & \frac{\partial^{2}f}{\partial x_{1}x_{2}}\left( \hat{x} \right) \\ \frac{\partial^{2}f}{\partial x_{2}x_{1}}\left( \hat{x} \right) & \frac{\partial^{2}f}{\partial x_{2}^{\ 2}}\left( \hat{x} \right) \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 1 \\ \end{bmatrix}$$

Liczymy wyznacznik macierzy Hessego:

$\det{H\left( \hat{x} \right)} = \left| \begin{matrix} 2 & 1 \\ 1 & 1 \\ \end{matrix} \right| = 1 > 0$ <= stąd wiemy, że w tym punkcie istnieje ekstremum lokalne

$\frac{\partial^{2}f}{\partial x_{1}^{\ 2}}\left( \hat{x} \right) = 2 > 0$ <= jest to minimum lokalne

1. Metoda „pełzającego” simpleksu Neldera-Meada - opis teoretyczny

Metoda simpleksu Neldeara i Meada jest bezgradientową metodą minimalizacji funkcji o n zmiennych decyzyjnych. W n-wymiarowej przestrzeni simpleks tworzy wielościan o n+1 wierzchołkach.

Jej zaletą jest fakt, że dobrze radzi sobie nawet z mocno nieliniowymi funkcjami. Dotarcie do punktu minimalnego wymaga jednak dużych nakładów obliczeniowych, zwłaszcza jeśli mamy do czynienia z funkcją o dużej ilości zmiennych decyzyjnych. Dlatego też zaleca się jej używanie jedynie do optymalizacji funkcji o mniej niż 10 zmiennych decyzyjnych.

Na początku procedury simpleksowej wylicza się punktów wierzchołkowych przy założeniu pewnej odległości między nimi (kroku). W następnych iteracjach dokonuje się takich przekształceń, aby odległość pomiędzy wierzchołkami simpleksu w pobliżu poszukiwanego ekstremum była mniejsza od założonej dokładności obliczeń.

Algorytm simpleksu składa się z trzech podstawowych operacji:

• odbicie punktu Ph względem P'

• ekspansja punktu P** względem P'

• kontrakcja punktu Ph względem P'

Oznaczenia:

x0 - punkt startowy

e - wymagana dokładność obliczeń

Ph - wybrany punkt wierzchołkowy simplexu spośród n+1 wierzchołków Pi, w którym wartość badanej funkcji osiąga maksimum.

PL - wybrany punkt wierzchołkowy simplexu spośród n+1 wierzchołków Pi, w którym wartość badanej funkcji osiąga minimum.

P' - środek symetrii simplexu z wyłączeniem punktu Ph zdefiniowany jako $P^{'} = \frac{\sum_{j = 1}^{n + 1}P_{j}}{n},\ j \neq h$

d - początkowa odległość pomiędzy wierzchołkami wyjściowego simplexu

a - współczynnik odbicia (a>0)

b - współczynnik kontrakcji (0<b<1)

c - współczynnik ekspansji (c>1)

n - liczba zmiennych niezależnych

Schemat blokowy algorytmu:

Źródła:

optymalizacja.w8.pl

kmg.ps.pl/opt/

1. Zadanie 17

>> [x y]=meshgrid(-1:.01:1);

>> z=4*x.^2-2.1*x.^4+1/3*x.^6+x.*y-4*y.^2+4*y.^4;

>> contour(z)

>> [x,fval,exitlog,out]=fminsearch(fun,[-0.5 0.5],options)

x =

-0.0902 0.7126

fval =

-1.0316

exitlog =

1

out =

iterations: 28

funcCount: 54

algorithm: 'Nelder-Mead simplex direct search'

>> [x,fval,exitlog,out]=fminsearch(fun,[0 -1.5],options)

x =

0.0900 -0.7130

fval =

-1.0316

exitlog =

1

out =

iterations: 46

funcCount: 87

algorithm: 'Nelder-Mead simplex direct search'

>> [x y]=meshgrid(-3:.1:3);

>> z=4*x.^2-2.1*x.^4+1/3*x.^6+x.*y-4*y.^2+4*y.^4;

>> contour(z)

>> [x,fval,exitlog,out]=fminsearch(fun,[-1.6 -2],options)

x =

-1.7034 0.7961

fval =

-0.2155

exitlog =

1

out =

iterations: 28

funcCount: 54

algorithm: 'Nelder-Mead simplex direct search'

>> [x,fval,exitlog,out]=fminsearch(fun,[1.6 2],options)

x =

1.7034 -0.7961

fval =

-0.2155

exitlog =

1

out =

iterations: 28

funcCount: 54

algorithm: 'Nelder-Mead simplex direct search'

>> [x y]=meshgrid(-1.8:.01:-1,-0.8:0.01:-0.3);

>> z=4*x.^2-2.1*x.^4+1/3*x.^6+x.*y-4*y.^2+4*y.^4;

>> contour(z)

>> [x,fval,exitlog,out]=fminsearch(fun,[-2 -0.5],options)

x =

-1.6070 -0.5683

fval =

2.1043

exitlog =

1

out =

iterations: 19

funcCount: 38

algorithm: 'Nelder-Mead simplex direct search'

>> [x y]=meshgrid(1:.01:1.8,0.3:0.01:0.8);

>> z=4*x.^2-2.1*x.^4+1/3*x.^6+x.*y-4*y.^2+4*y.^4;

>> contour(z)

>> [x,fval,exitlog,out]=fminsearch(fun,[2 0.5],options)

x =

1.6070 0.5683

fval =

2.1043

exitlog =

1

out =

iterations: 19

funcCount: 38

algorithm: 'Nelder-Mead simplex direct search'

3. Wnioski:

W ramach laboratorium rozwiązywaliśmy zadania z programowania nieliniowego przy pomocy programu MATLAB. Żaden z przykładów nie zawierał ograniczeń i dotyczył znajdowania minimum wartości funkcji według algorytmu zaimplementowanego w procedurze fminsearch. Odpowiednie ustawienie opcji wykonywania procedury pozwoliło na zaobserwowanie następujących zależności. Dobór punktu startowego oraz dokładność obliczeń mają bezpośredni wpływ na liczbę wykonanych iteracji. Im większa dokładność oraz im dalszy punkt startowy względem szukanego punktu tym więcej kroków, iteracji potrzebuje algorytm do znalezienia minimum. Ponadto tabela wartości funkcji w kolejnych iteracjach pokazuje, że w pierwszych krokach zmiana wartości funkcji jest znacznie większa niż w kolejnych iteracjach. Poruszając się w kierunku minimaizuje wartość funkcji. Warunkiem stopu jest . W każdym z rozwiązanych zadań wkorzystaliśmy funkcję contour z pakietu MATLAB, która umożliwia szacowanie położenia punktu minimalnego dla funkcji trójwymiarowych. Na podstawie otrzymanego wykresu wprowadzaliśmy punkt startowy do funkcji fminsearch, który decydował, które minimum wyznaczy algorytm.