Programowanie nieliniowe bez ograniczeń


Metody programowania nieliniowego pozwalają odnaleźć minimum lokalne funkcji wielu zmiennych z dowolną zadaną dokładnością. Wszystkie metody wymagają podania punktu startowego. Działanie metod polega na badaniu własności funkcji w okolicach podanego punktu.

Metody optymalizacji nieliniowej bez ograniczeń można podzielić na dwie grupy ze względu na sposób znajdowania kolejnego punktu wzdłuż danego kierunku poszukiwań:
- metody poszukiwań prostych
- metody kierunków poprawy

Metody metody poszukiwań prostych (metody dyskretne), badają zachowanie funkcji tylko w jednym lub w dwóch punktach leżących na kierunku poszukiwań, przy czym sposób wyboru tych punktów, przy danym punkcie początkowym, jest ustalony na początku każdej iteracji.

Metody kierunków poprawy (metody z minimalizacją w kierunku), w których określa się minimum funkcji wzdłuż kierunku poszukiwań.

Metody poszukiwań prostych

Metoda ta realizowana jest przez funkcję fminsearch.

Ogólna forma funkcji:

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

Argumenty wejściowe:

fun nieliniowa funkcja wielu zmiennych
x0 wektor startowy poszukiwań
options struktura opcji w algorytmie wyszukiwania

Argumenty wyjściowe:

x wektor zmiennych
fval wartość funkcji celu w punkcie minimum
exitflag informacja obliczeniowa
output decyduje o ilości informacji wyświetlanej na ekranie

Zadanie 1

Znajdź minimum funkcji jednej zmiennej:

z = (x+3)(x)(x-1)(x-3)
Dobierz odpowiedni punkt startowy.
Co się stanie gdy punkt startowy x0=1 ?
Odpowiedź: xval1 =-2.0234, fval1 = -30.0118, xval2 =2.2873, fval2 =-11.0954

Zadanie 2

Mając podaną funkcję jednej zmiennej:

z = sin(x)+3
Znajdź wszystkie minima w przedziale [-10, 10].

Odpowiedź: x1 =-7.8540, x2 = -1.5708, x3 = 4.7124

Zadanie 3

Znajdź minimum dla podanej funkcji rozerwanej:

z = x1 + 2x2, gdy x1>0 i x2>=0,
z = -2x1 + x2, gdy x1<=0 i x2>0,
z = -x1 - 2x2, dla x1<0, x2<=0,
z = 2x1 - x2, dla x1>=0, x2<0,
z = 0, dla x1=0 lub x2=0
x0 = (0.5, 0.1)

Zwizualizować działanie algorytmu na trójwymiarowym wykresie funkcji celu, zaznaczając kolejne kroki wykonane przez algorytm (kolejne punkty zapisane w wektorze xval i fval nanieść na trójwymiarowy wykres funkcji celu i połączyć liniami).
Do rysowania możesz zastosować funkcję contour lub mesh.
Odpowiedź: x = 1.0e-03 * 0.0640, 1.0e-03 *-0.1342, fval = 2.6229e-04

Zadanie 4

Funkcja Rosenbrocka (tzw. dolina bananowa, ang. banana valley) jest używana w optymalizacji jako funkcja testowa dla algorytmów optymalizacji. Wartość funkcji Rosenbrocka wyraża się następującym wzorem:

z = 100 (x2 - x12)2 + (1 - x1)2

Funkcja Rosenbrocka ma jedno minimum (będące zarazem minimum globalnym), położone wewnątrz długiej, wąskiej doliny o parabolicznym kształcie. Poziomice funkcji celu przypominają kształtem banan (stąd też pochodzi jej potoczna nazwa), a minimalizacja tej funkcji stanowi klasyczny problem optymalizacji statycznej.

Odpowiedź: x = 1,1, fval = 3.9243e-10

Metody kierunków poprawy

Metoda ta realizowana jest przez funkcję fminunc.

Ogólna forma funkcji:

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

Argumenty wejściowe:

fun nieliniowa funkcja wielu zmiennych
x0 wektor startowy poszukiwań
options struktura opcji w algorytmie wyszukiwania

Argumenty wyjściowe:

x wektor zmiennych
fval wartość funkcji celu w punkcie minimum
exitflag informacja obliczeniowa
output decyduje o ilości informacji wyświetlanej na ekranie
grad poszczególne składowe wektora gradientu

Zadanie 5

Znajdź minimum funkcji zaczynając od punktu (1,1):

z = 3x12 + 2x1x2 + x22
Następnie spróbuj znaleźć bardziej dokładne rozwiązanie używając do tego celu gradient.
Podpowiedź:

  options = optimset('GradObj','on'); 

Odpowiedź: 1.0e-15 * 0.1110, 1.0e-15 *-0.8882, fval = 6.2862e-31

Zadanie 6

Znajdź wszystkie minima w przedziale [-10, 10] dla podanej funkcji:

z = sin(x) + 3

Porównaj wynik z otrzymanym za pomocą funkcji fminsearch.
Odpowiedź: x1 =-7.8540, x2 = -1.5708, x3 = 4.7124

Zadanie 7

Znajdź wartości zmiennych x1 i x2 spełniających rozwiązanie zadanie minimalizacji:

ex1(4x12 + 2x22 + 4x1x2 + 2x2 + 1)
dla zadanego punktu startowego (-1,1).
Odpowiedź: x = 0.5000, -1.0000, fval = 3.6609e-15