Оптимизация стохастической целевой функции
В этом примере показано, как найти минимум стохастической целевой функции с помощью patternsearch. Это также показывает, как решатели Optimization Toolbox™ не подходят для этого типа задачи. В примере используется простая 2-мерная целевая функция, которая затем возмущается шумом.
Инициализация
X0 = [2.5 -2.5]; % Starting point. LB = [-5 -5]; % Lower bound UB = [5 5]; % Upper bound range = [LB(1) UB(1); LB(2) UB(2)]; Objfcn = @smoothFcn; % Handle to the objective function. % Plot the smooth objective function fig = figure('Color','w'); showSmoothFcn(Objfcn,range); hold on; title('Smooth objective function'); ph = []; ph(1) = plot3(X0(1),X0(2),Objfcn(X0)+30,'or','MarkerSize',10,'MarkerFaceColor','r'); hold off; ax = gca; ax.CameraPosition = [-31.0391 -85.2792 -281.4265]; ax.CameraTarget = [0 0 -50]; ax.CameraViewAngle = 6.7937; % Add legend information legendLabels = {'Start point'}; lh = legend(ph,legendLabels,'Location','SouthEast'); lp = lh.Position; lh.Position = [1-lp(3)-0.005 0.005 lp(3) lp(4)];
0 0
Выполняйте fmincon на сглаживающей целевой функции
Целевая функция гладкая (дважды непрерывно дифференцируемая). Решите задачу оптимизации, используя Optimization Toolbox fmincon решатель. fmincon находит ограниченный минимум функции из нескольких переменных. Эта функция имеет уникальный минимум в точке x* = [-5,-5] где оно имеет значение f(x*) = -250.
Установите опции, чтобы вернуть итеративное отображение.
options = optimoptions(@fmincon,'Algorithm','interior-point','Display','iter'); [Xop,Fop] = fmincon(Objfcn,X0,[],[],[],[],LB,UB,[],options) figure(fig); hold on;
First-order Norm of
Iter F-count f(x) Feasibility optimality step
0 3 -1.062500e+01 0.000e+00 2.004e+01
1 6 -1.578420e+02 0.000e+00 5.478e+01 6.734e+00
2 9 -2.491310e+02 0.000e+00 6.672e+01 1.236e+00
3 12 -2.497554e+02 0.000e+00 2.397e-01 6.310e-03
4 15 -2.499986e+02 0.000e+00 5.065e-02 8.016e-03
5 18 -2.499996e+02 0.000e+00 9.708e-05 3.367e-05
6 21 -2.500000e+02 0.000e+00 1.513e-04 6.867e-06
7 24 -2.500000e+02 0.000e+00 1.161e-06 6.920e-08
Local minimum found that satisfies the constraints.
Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
Xop =
-5.0000 -5.0000
Fop =
-250.0000
Постройте график конечной точки
ph(2) = plot3(Xop(1),Xop(2),Fop,'dm','MarkerSize',10,'MarkerFaceColor','m'); % Add a legend to plot legendLabels = [legendLabels, '|fmincon| solution']; lh = legend(ph,legendLabels,'Location','SouthEast'); lp = lh.Position; lh.Position = [1-lp(3)-0.005 0.005 lp(3) lp(4)]; hold off;
Стохастическая целевая функция
Теперь возмущайте целевую функцию, добавляя случайный шум.
rng(0,'twister') % Reset the global random number generator peaknoise = 4.5; Objfcn = @(x) smoothFcn(x,peaknoise); % Handle to the objective function. % Plot the objective function (non-smooth) fig = figure('Color','w'); showSmoothFcn(Objfcn,range); title('Stochastic objective function') ax = gca; ax.CameraPosition = [-31.0391 -85.2792 -281.4265]; ax.CameraTarget = [0 0 -50]; ax.CameraViewAngle = 6.7937;
0 0
Выполняйте fmincon по стохастической целевой функции
Возмущенная целевая функция является стохастической и не гладкой. fmincon является общим ограниченным решателем оптимизации, который находит локальный минимум, используя производные целевой функции. Если вы не предоставляете первые производные целевой функции, fmincon использует конечные различия для аппроксимации производных. В этом примере целевая функция является случайной, поэтому производные конечных оценок различий, следовательно, могут быть ненадежными. fmincon может потенциально остановиться в точке, которая не является минимальной. Это может произойти, потому что оптимальные условия, по-видимому, выполняются в конечной точке из-за шума или fmincon не удалось добиться дальнейшего прогресса.
[Xop,Fop] = fmincon(Objfcn,X0,[],[],[],[],LB,UB,[],options) figure(fig); hold on; ph = []; ph(1) = plot3(X0(1),X0(2),Objfcn(X0)+30,'or','MarkerSize',10,'MarkerFaceColor','r'); ph(2) = plot3(Xop(1),Xop(2),Fop,'dm','MarkerSize',10,'MarkerFaceColor','m'); % Add legend to plot legendLabels = {'Start point','|fmincon| solution'}; lh = legend(ph,legendLabels,'Location','SouthEast'); lp = lh.Position; lh.Position = [1-lp(3)-0.005 0.005 lp(3) lp(4)]; hold off;
First-order Norm of
Iter F-count f(x) Feasibility optimality step
0 3 -1.925772e+01 0.000e+00 2.126e+08
1 6 -7.107849e+01 0.000e+00 2.623e+08 8.873e+00
2 11 -8.055890e+01 0.000e+00 2.401e+08 6.715e-01
3 20 -8.325315e+01 0.000e+00 7.348e+07 3.047e-01
4 48 -8.366302e+01 0.000e+00 1.762e+08 1.593e-07
5 64 -8.591081e+01 0.000e+00 1.569e+08 3.111e-10
Local minimum possible. Constraints satisfied.
fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are
satisfied to within the value of the constraint tolerance.
Xop =
-4.9628 2.6673
Fop =
-85.9108
Выполняйте patternsearch
Теперь минимизируйте стохастическую целевую функцию с помощью Global Optimization Toolbox patternsearch решатель. Методы оптимизации поиска шаблона являются классом методов прямого поиска для оптимизации. Алгоритм поиска шаблона не использует производные целевой функции, чтобы найти оптимальную точку.
PSoptions = optimoptions(@patternsearch,'Display','iter'); [Xps,Fps] = patternsearch(Objfcn,X0,[],[],[],[],LB,UB,PSoptions) figure(fig); hold on; ph(3) = plot3(Xps(1),Xps(2),Fps,'dc','MarkerSize',10,'MarkerFaceColor','c'); % Add legend to plot legendLabels = [legendLabels, 'Pattern Search solution']; lh = legend(ph,legendLabels,'Location','SouthEast'); lp = lh.Position; lh.Position = [1-lp(3)-0.005 0.005 lp(3) lp(4)]; hold off
Iter Func-count f(x) MeshSize Method
0 1 -7.20766 1
1 3 -34.7227 2 Successful Poll
2 3 -34.7227 1 Refine Mesh
3 5 -34.7227 0.5 Refine Mesh
4 8 -96.0847 1 Successful Poll
5 10 -96.0847 0.5 Refine Mesh
6 13 -132.888 1 Successful Poll
7 15 -132.888 0.5 Refine Mesh
8 17 -132.888 0.25 Refine Mesh
9 20 -197.689 0.5 Successful Poll
10 22 -197.689 0.25 Refine Mesh
11 24 -197.689 0.125 Refine Mesh
12 27 -241.344 0.25 Successful Poll
13 30 -241.344 0.125 Refine Mesh
14 33 -241.344 0.0625 Refine Mesh
15 36 -241.344 0.03125 Refine Mesh
16 39 -241.344 0.01562 Refine Mesh
17 42 -242.761 0.03125 Successful Poll
18 45 -242.761 0.01562 Refine Mesh
19 48 -242.761 0.007812 Refine Mesh
20 51 -242.761 0.003906 Refine Mesh
21 55 -242.761 0.001953 Refine Mesh
22 59 -242.761 0.0009766 Refine Mesh
23 63 -242.761 0.0004883 Refine Mesh
24 67 -242.761 0.0002441 Refine Mesh
25 71 -242.761 0.0001221 Refine Mesh
26 75 -242.761 6.104e-05 Refine Mesh
27 79 -242.761 3.052e-05 Refine Mesh
28 83 -242.761 1.526e-05 Refine Mesh
29 87 -242.761 7.629e-06 Refine Mesh
30 91 -242.761 3.815e-06 Refine Mesh
Iter Func-count f(x) MeshSize Method
31 95 -242.761 1.907e-06 Refine Mesh
32 99 -242.761 9.537e-07 Refine Mesh
Optimization terminated: mesh size less than options.MeshTolerance.
Xps =
-4.9844 -4.5000
Fps =
-242.7611
Поиск шаблона не так сильно зависит от случайного шума в целевой функции. Поиск шаблона требует только значений функции, а не производных, следовательно, шум (некоторого однородного рода) может не повлиять на него. Однако поиск шаблона требует большего вычисления функции, чтобы найти истинный минимум, чем основанные на производной алгоритмы, стоимость для не использования производных.