寻找全局或多个局部最小值
这个例子说明了 GlobalSearch
如何有效地找到全局最小值,以及 MultiStart
如何找到更多局部极小值。
此例的目标函数有许多局部极小值和一个唯一的全局最小值。在极坐标中,该函数为
其中
绘制函数 和 ,并创建函数 的曲面图。
figure subplot(1,2,1); fplot(@(r)(sin(r) - sin(2*r)/2 + sin(3*r)/3 - sin(4*r)/4 + 4) .* r.^2./(r+1), [0 20]) title(''); ylabel('g'); xlabel('r'); subplot(1,2,2); fplot(@(t)2 + cos(t) + cos(2*t-1/2)/2, [0 2*pi]) title(''); ylabel('h'); xlabel('t');
figure fsurf(@(x,y) sawtoothxy(x,y), [-20 20]) % sawtoothxy is defined in the first step below xlabel('x'); ylabel('y'); title('sawtoothxy(x,y)'); view(-18,52)
全局最小值位于 ,目标函数为 0。函数 在 中近似线性增长,具有重复的锯齿形状。函数 有两个局部极小值,其中一个是全局。
sawtoothxy.m
文件从笛卡尔坐标转换为极坐标,然后计算极坐标中的值。
type sawtoothxy
function f = sawtoothxy(x,y) [t r] = cart2pol(x,y); % change to polar coordinates h = cos(2*t - 1/2)/2 + cos(t) + 2; g = (sin(r) - sin(2*r)/2 + sin(3*r)/3 - sin(4*r)/4 + 4) ... .*r.^2./(r+1); f = g.*h; end
通过 GlobalSearch
实现单一全局最小值
要使用 GlobalSearch
搜索全局最小值,首先创建一个问题结构体。对 fmincon
使用 'sqp'
算法,
problem = createOptimProblem('fmincon',... 'objective',@(x)sawtoothxy(x(1),x(2)),... 'x0',[100,-50],'options',... optimoptions(@fmincon,'Algorithm','sqp','Display','off'));
起点是 [100,-50]
而不是 [0,0]
,所以 GlobalSearch
不是从全局解开始的。
通过运行 fmincon
来验证问题结构体。
[x,fval] = fmincon(problem)
x = 1×2
45.7236 -107.6515
fval = 555.5820
创建 GlobalSearch
对象,并设置迭代显示。
gs = GlobalSearch('Display','iter');
为了实现可再现性,请设置随机数生成器种子。
rng(14,'twister')
运行求解器。
[x,fval] = run(gs,problem)
Num Pts Best Current Threshold Local Local Analyzed F-count f(x) Penalty Penalty f(x) exitflag Procedure 0 200 555.6 555.6 0 Initial Point 200 1463 1.547e-15 1.547e-15 1 Stage 1 Local 300 1564 1.547e-15 5.858e+04 1.074 Stage 2 Search 400 1664 1.547e-15 1.84e+05 4.16 Stage 2 Search 500 1764 1.547e-15 2.683e+04 11.84 Stage 2 Search 600 1864 1.547e-15 1.122e+04 30.95 Stage 2 Search 700 1964 1.547e-15 1.353e+04 65.25 Stage 2 Search 800 2064 1.547e-15 6.249e+04 163.8 Stage 2 Search 900 2164 1.547e-15 4.119e+04 409.2 Stage 2 Search 950 2359 1.547e-15 477 589.7 387 2 Stage 2 Local 952 2423 1.547e-15 368.4 477 250.7 2 Stage 2 Local 1000 2471 1.547e-15 4.031e+04 530.9 Stage 2 Search GlobalSearch stopped because it analyzed all the trial points. 3 out of 4 local solver runs converged with a positive local solver exit flag.
x = 1×2
10-7 ×
0.0414 0.1298
fval = 1.5467e-15
求解器找到三个局部极小值,包括 [0,0] 附近的全局最小值。
通过 MultiStart
找到多个局部最小值
要使用 MultiStart
搜索多个极小值,首先要创建一个问题结构体。由于该问题无约束,因此使用 fminunc
求解器。设置选项以在命令行上不显示任何显示。
problem = createOptimProblem('fminunc',... 'objective',@(x)sawtoothxy(x(1),x(2)),... 'x0',[100,-50],'options',... optimoptions(@fminunc,'Display','off'));
通过运行来验证问题结构体。
[x,fval] = fminunc(problem)
x = 1×2
8.4420 -110.2602
fval = 435.2573
创建一个默认的 MultiStart
对象。
ms = MultiStart;
运行求解器 50 次迭代,记录局部极小值。
rng(1) % For reproducibility
[x,fval,eflag,output,manymins] = run(ms,problem,50)
MultiStart completed some of the runs from the start points. 10 out of 50 local solver runs converged with a positive local solver exitflag.
x = 1×2
-73.8348 -197.7810
fval = 766.8260
eflag = 2
output = struct with fields:
funcCount: 8574
localSolverTotal: 50
localSolverSuccess: 10
localSolverIncomplete: 40
localSolverNoSolution: 0
message: 'MultiStart completed some of the runs from the start points. ...'
manymins=1×10 GlobalOptimSolution array with properties:
X
Fval
Exitflag
Output
X0
求解器未找到 [0,0]
附近的全局最小值。求解器找到 10 个不同的局部极小值。
绘制局部极小值处的函数值:
histogram([manymins.Fval],10)
在三个最佳点处绘制函数值:
bestf = [manymins.Fval]; histogram(bestf(1:3),10)
MultiStart
从起点开始 fminunc
,分量均匀分布在 -1000 到 1000 之间。fminunc
经常会卡在众多局部极小值之一。fminunc
超出其迭代限制或函数评估限制 40 次。
另请参阅
GlobalSearch
| MultiStart
| createOptimProblem