Programowanie nieliniowe z ograniczeniami


Jedną z nowszych metod programowania nieliniowego z ograniczeniami jest metoda sekwencyjnego programowania kwadratowego (ang. Sequential Quadratic Programming SQP). W każdym kroku metody dla znalezienia kierunku poprawy rozwiązywane jest zadanie programowania kwadratowego.
W pakiecie Optimization Toolbox do rozwiązywania zadań programowania nieliniowego z ograniczeniami służy funkcja fmincon.

Ogólna forma funkcji:

[x,fval,exiflag,output, lambda, grad, hessian] = fmincon(fun, x0, A, b, Aeq, beq, lb, ub, nonlcon, options)

Argumenty wejściowe:

fun nieliniowa funkcja wielu zmiennych
x0 wektor startowy poszukiwań
A macierz ograniczeń liniowych nierównościowych
b kolumnowy wektor współczynników ograniczeń liniowych nierównościowych
Aeq macierz ograniczeń liniowych równościowych
beq kolumnowy wektor współczynników ograniczeń liniowych równościowych
lb dolne ograniczenie na wartości zmiennych niezależnych x
ub górne ograniczenie na wartości zmiennych niezależnych x
nonlcon funkcja opisująca ograniczenia nieliniowe równościowe i nierównościowe
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
lambda wartości współczynników Lagrange'a w punkcie minimum
grad gradient funkcji w punkcie minimum
hessian hesjan H funkcji w punkcie minimum

Zadanie 1

Znajdź minimum funkcji:

f(x) = -x1 * x2 * x3

przy wartościach początkowej x = [10;10;10] oraz przy obecności ograniczeń
0 <= x1 + 2x2 + 2x3 <= 72

Zadanie 2

Znajdź minimum funkcji:

ex1(4x12 + 2x22 + 4x1x2 + 2x2 + 1)
dla zadanego punktu startowego (-1,1).

Ale przy obecności ograniczeń w postaci nierówności nieliniowych

x1x2 - x1 - x2 <= -1.5
x1x2 >= -10

Podpowiedź: Ograniczenia powinny być przedstawione w postaci c(x) <= 0 oraz ceq(x) = 0.

Następnie dla podanego przykładu wprowadź dodatkowe ograniczenia:

x1 >= 0
x2 >= 0

Zadanie 3

Znajdź minimum funkcji:

f(x) = x12 - x1x2 + x22

dla zadanego punktu startowego (0.5,0.5).
Aby wyznaczyć rozwiązanie użyj gradientu funkcji celu.

Podpowiedź: Aby gradient funkcji celu został użyty przez procedurę trzeba to zrobić to poleceniem:

 options = optimset('LargeScale', 'off');   
 options = optimset(options,'GradObj','on','GradConstr','on');

Zadanie 4

Znajdź minimum funkcji:

f(x) = x12 + x23 + x34

przy ograniczeniach funkcyjnych:
x1 + x2 + x3 = 10
1.5 + x1x2 - x3 <= 0

x1x2 >= -10
oraz ograniczeniach nakładanych na zmienne:
-10 <= x1 <= 10
-5 <= x2 <= 5
0 <= x3 <= inf
Jako punkty startowe przyjmujemy (0,0,0).

W przypadku gradientu ograniczeń określająca go zmienna DC jest macierzą, w której każda kolumna odnosi się do jednego ograniczenia funkcyjnego. Macierz wygląda następująco:

Zadanie 5

Znajdź minimum funkcji Rosenbrocka:

f(x) = (1 - x1)2 + (5x2 - x12)2
przy x0 = (2.0, 1.0) i ograniczeniach (x1 - 1)2 + (x2 - 1)2 <= 1