无约束优化问题之HookeJeeves法（模式搜索法）

  求解无约束优化问题的极小值&＃xff08;最小值&＃xff09;。

  算法步骤中不需要计算目标函数的导数。

  求解min⁡f(x):&＃61;(1−x1)2&＃43;5(x2−x12)2.\min\ f(x):&＃61;(1-x_1)^2&＃43;5{(x_2-{x_1}^2)}^2.min f(x):&＃61;(1−x1​)2&＃43;5(x2​−x1​2)2.
解&＃xff1a;置初始点为(2,0)T(2,0)^T(2,0)T, 初始探测步长δ&＃61;12\delta &＃61; \frac{1}{2}δ&＃61;21​&＃xff0c;加速因子$\alpha \&＃61;1$&＃xff0c;衰减因子β&＃61;12\beta&＃61;\frac{1}{2}β&＃61;21​&＃xff0c;允许误差$ϵ\&＃61;0.2$。
  Python代码求解如下&＃xff1a;

import numpy as npdef function1(x):return (1 - x[0]) ** 2 &＃43; 5 * (x[1] - x[0] ** 2) ** 2# 输入初始探测搜索步长delta, 加速因子alpha(alpha>&＃61;1), 缩减率beta(00)&＃xff0c; 初始点xk
delta, alpha, beta, epsilon, xk &＃61; 0.5, 1, 0.5, 0.2, np.array([2, 0])
yk &＃61; xk.copy()# 求问题维数
dim &＃61; len(xk)# 初始化迭代次数
k &＃61; 1while delta > epsilon:# 输出本次搜索的基本信息print(&＃39;进入第&＃39;, k, &＃39;轮迭代&＃39;)print(&＃39;基点:&＃39;, xk)print(&＃39;基点处函数值:&＃39;, function1(xk))print(&＃39;探测出发点为:&＃39;, yk)print(&＃39;探测出发点处的函数值&＃39;, function1(yk))print(&＃39;探测搜索步长delta:&＃39;, delta)# 进入探测移动for i in range(dim):# 生成本次探测的坐标方向e &＃61; np.zeros([1, dim])[0]e[i] &＃61; 1# 计算探测得到的点t1, t2 &＃61; function1(yk &＃43; delta * e), function1(yk)if t1 < t2:yk &＃61; yk &＃43; delta * eelse:t1, t2 &＃61; function1(yk - delta * e), function1(yk)if t1 < t2:yk &＃61; yk - delta * eprint(&＃39;第&＃39;, i &＃43; 1, &＃39;次探测得到的点为&＃39;, yk)print(&＃39;该点对应的函数值&＃39;, function1(yk))# 确定新的基点和计算新的探测初始点t1, t2 &＃61; function1(yk), function1(xk)if t1 < t2:xk, yk &＃61; yk, yk &＃43; alpha * (yk - xk)else:delta, yk &＃61; delta * beta, xkk &＃43;&＃61; 1print("\n")


  结果

进入第 1 轮迭代
基点: [2 0]
基点处函数值: 81
探测出发点为: [2 0]
探测出发点处的函数值 81
探测搜索步长delta: 0.5
第 1 次探测得到的点为 [1.5 0. ]
该点对应的函数值 25.5625
第 2 次探测得到的点为 [1.5 0.5]
该点对应的函数值 15.5625进入第 2 轮迭代
基点: [1.5 0.5]
基点处函数值: 15.5625
探测出发点为: [1. 1.]
探测出发点处的函数值 0.0
探测搜索步长delta: 0.5
第 1 次探测得到的点为 [1. 1.]
该点对应的函数值 0.0
第 2 次探测得到的点为 [1. 1.]
该点对应的函数值 0.0进入第 3 轮迭代
基点: [1. 1.]
基点处函数值: 0.0
探测出发点为: [0.5 1.5]
探测出发点处的函数值 8.0625
探测搜索步长delta: 0.5
第 1 次探测得到的点为 [1. 1.5]
该点对应的函数值 1.25
第 2 次探测得到的点为 [1. 1.]
该点对应的函数值 0.0进入第 4 轮迭代
基点: [1. 1.]
基点处函数值: 0.0
探测出发点为: [1. 1.]
探测出发点处的函数值 0.0
探测搜索步长delta: 0.25
第 1 次探测得到的点为 [1. 1.]
该点对应的函数值 0.0
第 2 次探测得到的点为 [1. 1.]
该点对应的函数值 0.0


所以求得近似最小值点为(1,1)T(1,1)^T(1,1)T&＃xff0c;对应的最小值为$0$。

  求解min⁡f(x):&＃61;x12&＃43;x22−4x1&＃43;2x2&＃43;7.\min f(x):&＃61;{x_1}^2&＃43;{x_2}^2-4x_1&＃43;2x_2&＃43;7.minf(x):&＃61;x1​2&＃43;x2​2−4x1​&＃43;2x2​&＃43;7.
解&＃xff1a;置初始点为(0,0)T(0,0)^T(0,0)T&＃xff0c;初始探测步长$\delta \&＃61;1$&＃xff0c;加速因子$\alpha \&＃61;1$&＃xff0c;衰减因子$\beta \&＃61;0.25$&＃xff0c;允许误差$ϵ\&＃61;0.05$。
  Python代码如下&＃xff1a;

import numpy as npdef function1(x):return x[0] ** 2 &＃43; x[1] ** 2 - 4 * x[0] &＃43; 2 * x[1] &＃43; 7# 输入初始探测搜索步长delta, 加速因子alpha(alpha>&＃61;1), 缩减率beta(00)&＃xff0c; 初始点xk
delta, alpha, beta, epsilon, xk &＃61; 1, 1, 0.25, 0.05, np.array([0, 0])
yk &＃61; xk.copy()# 求问题维数
dim &＃61; len(xk)# 初始化迭代次数
k &＃61; 1while delta > epsilon:# 输出本次搜索的基本信息print(&＃39;进入第&＃39;, k, &＃39;轮迭代&＃39;)print(&＃39;基点:&＃39;, xk)print(&＃39;基点处函数值:&＃39;, function1(xk))print(&＃39;探测出发点为:&＃39;, yk)print(&＃39;探测出发点处的函数值&＃39;, function1(yk))print(&＃39;探测搜索步长delta:&＃39;, delta)# 进入探测移动for i in range(dim):# 生成本次探测的坐标方向e &＃61; np.zeros([1, dim])[0]e[i] &＃61; 1# 计算探测得到的点t1, t2 &＃61; function1(yk &＃43; delta * e), function1(yk)if t1 < t2:yk &＃61; yk &＃43; delta * eelse:t1, t2 &＃61; function1(yk - delta * e), function1(yk)if t1 < t2:yk &＃61; yk - delta * eprint(&＃39;第&＃39;, i &＃43; 1, &＃39;次探测得到的点为&＃39;, yk)print(&＃39;该点对应的函数值&＃39;, function1(yk))# 确定新的基点和计算新的探测初始点t1, t2 &＃61; function1(yk), function1(xk)if t1 < t2:xk, yk &＃61; yk, yk &＃43; alpha * (yk - xk)else:delta, yk &＃61; delta * beta, xkk &＃43;&＃61; 1print("\n")


  结果&＃xff1a;

进入第 1 轮迭代
基点: [0 0]
基点处函数值: 7
探测出发点为: [0 0]
探测出发点处的函数值 7
探测搜索步长delta: 1
第 1 次探测得到的点为 [1. 0.]
该点对应的函数值 4.0
第 2 次探测得到的点为 [ 1. -1.]
该点对应的函数值 3.0进入第 2 轮迭代
基点: [ 1. -1.]
基点处函数值: 3.0
探测出发点为: [ 2. -2.]
探测出发点处的函数值 3.0
探测搜索步长delta: 1
第 1 次探测得到的点为 [ 2. -2.]
该点对应的函数值 3.0
第 2 次探测得到的点为 [ 2. -1.]
该点对应的函数值 2.0进入第 3 轮迭代
基点: [ 2. -1.]
基点处函数值: 2.0
探测出发点为: [ 3. -1.]
探测出发点处的函数值 3.0
探测搜索步长delta: 1
第 1 次探测得到的点为 [ 2. -1.]
该点对应的函数值 2.0
第 2 次探测得到的点为 [ 2. -1.]
该点对应的函数值 2.0进入第 4 轮迭代
基点: [ 2. -1.]
基点处函数值: 2.0
探测出发点为: [ 2. -1.]
探测出发点处的函数值 2.0
探测搜索步长delta: 0.25
第 1 次探测得到的点为 [ 2. -1.]
该点对应的函数值 2.0
第 2 次探测得到的点为 [ 2. -1.]
该点对应的函数值 2.0进入第 5 轮迭代
基点: [ 2. -1.]
基点处函数值: 2.0
探测出发点为: [ 2. -1.]
探测出发点处的函数值 2.0
探测搜索步长delta: 0.0625
第 1 次探测得到的点为 [ 2. -1.]
该点对应的函数值 2.0
第 2 次探测得到的点为 [ 2. -1.]
该点对应的函数值 2.0


所以求得的近似最小值点为(2,−1)T(2,-1)^T(2,−1)T&＃xff0c;对应的最小值为$2$。