织梦做网站视频教程,做公司网站需要多久,长沙优化网站价格,昆明市环保局建设网站文章目录 0.618 法示例 Newton 法示例 0.618 法
0.618 法是一种一维线性搜索的算法#xff0c;也称为黄金分割法#xff08;Golden Section Method#xff09;。它是一种迭代方法#xff0c;用于确定目标函数在一个区间上的最小值。
以下是 0.618 法的基本步骤#xff1… 文章目录 0.618 法示例 Newton 法示例 0.618 法
0.618 法是一种一维线性搜索的算法也称为黄金分割法Golden Section Method。它是一种迭代方法用于确定目标函数在一个区间上的最小值。
以下是 0.618 法的基本步骤 选取初始数据确定初始搜索区间 [ a 0 , b 0 ] [a_0,b_0] [a0,b0] 和精度要求 δ 0 \delta0 δ0. 计算最初两个试探点 λ 0 , μ 0 \lambda_0,\mu_0 λ0,μ0 λ 0 a 0 0.382 ( b 0 − a 0 ) , \lambda_0a_00.382(b_0-a_0), λ0a00.382(b0−a0), μ 0 a 0 0.618 ( b 0 − a 0 ) . \mu_0a_00.618(b_0-a_0). μ0a00.618(b0−a0). 计算 φ ( λ 0 ) \varphi(\lambda_0) φ(λ0) 和 φ ( μ 0 ) \varphi(\mu_0) φ(μ0)令 k 0. k0. k0. 比较目标函数值。 若 φ ( λ k ) φ ( μ k ) \varphi(\lambda_k)\varphi(\mu_k) φ(λk)φ(μk)转步 3否则转步 4. 若 b k − λ k ⩽ δ b_k-\lambda_k\leqslant\delta bk−λk⩽δ则停止计算输出 μ k \mu_k μk否则令 a k 1 : λ k , b k 1 : b k , λ k 1 : μ k a_{k1}:\lambda_{k},\:b_{k1}:b_{k},\:\lambda_{k1}:\mu_{k} ak1:λk,bk1:bk,λk1:μk φ ( λ k 1 ) : φ ( μ k ) , μ k 1 : a k 1 0.618 ( b k 1 − a k 1 ) . \varphi(\lambda_{k1}):\varphi(\mu_{k}),\:\mu_{k1}:a_{k1}0.618(b_{k1}-a_{k1}). φ(λk1):φ(μk),μk1:ak10.618(bk1−ak1). 计算 φ ( μ k 1 ) \varphi(\mu_{k1}) φ(μk1)转步 5. 若 μ k − a k ⩽ δ \mu_k - a_k\leqslant\delta μk−ak⩽δ则停止计算输出 λ k \lambda_k λk否则令 a k 1 : a k , b k 1 : μ k , μ k 1 : λ k , a_{k1}:a_k,~b_{k1}:\mu_k,~\mu_{k1}:\lambda_k, ak1:ak, bk1:μk, μk1:λk, φ ( μ k 1 ) : φ ( λ k ) , λ k 1 : a k 1 0.382 ( b k 1 − a k 1 ) . \varphi(\mu_{k1}):\varphi(\lambda_{k}),\:\lambda_{k1}:a_{k1}0.382(b_{k1}-a_{k1}). φ(μk1):φ(λk),λk1:ak10.382(bk1−ak1). 计算 φ ( λ k 1 ) \varphi(\lambda_{k1}) φ(λk1)转步 5. k : k 1 k:k1 k:k1转步 2.
0.618 法的优点之一是每次迭代都将搜索区间缩小为当前区间的 0.618 倍因此可以很快地接近最小值。此方法通常适用于连续单峰函数的最小值搜索问题。
示例
用 0.618 法解下述函数搜索区间宽度到 ε 0.5 \varepsilon 0.5 ε0.5. min t ≥ 0 φ ( t ) t 3 − 2 t 1 \min_{t≥0}\:\varphi(t)t^3-2t1 t≥0minφ(t)t3−2t1 根据经验选择初始搜索区间为 [ 0 , 3 ] [0, 3] [0,3]单谷区间.
计算过程 a λ μ b φ ( λ ) φ ( μ ) 0 0 1.146 1.854 3 0.2131 3.6648 1 0 0.708 1.146 1.854 − 0.0611 0.2131 2 0 0.438 0.708 1.146 0.2082 − 0.0611 3 0.438 0.708 0.876 1.146 − 0.0611 − 0.0798 \begin{array}{|r|r|r|r|r|r|r|r|}\hlinea\lambda\mub\varphi(\lambda)\varphi(\mu)\\\hline001.1461.85430.21313.6648\\\hline100.7081.1461.854-0.06110.2131\\\hline200.4380.7081.1460.2082-0.0611\\\hline30.4380.7080.8761.146-0.0611-0.0798\\\hline\end{array} 0123a0000.438λ1.1460.7080.4380.708μ1.8541.1460.7080.876b31.8541.1461.146φ(λ)0.2131−0.06110.2082−0.0611φ(μ)3.66480.2131−0.0611−0.0798 最后输出 t μ 3 0.876 t \mu_3 0.876 tμ30.876.
Newton 法
一维线性搜索是在优化算法中常用的一种方法用于确定在给定搜索方向上的合适步长使得目标函数在该方向上能够有明显的下降。Newton法牛顿法是一种使用二阶导数信息的优化方法它在一维线性搜索中也可以应用。下面是一维线性搜索的 Newton 法的基本步骤 选择初始点 x 0 x_0 x0 在搜索方向上选择一个初始点。 计算目标函数的一阶和二阶导数 计算目标函数 f ( x ) f(x) f(x) 在当前点 x k x_k xk 的一阶导数 f ′ ( x k ) f(x_k) f′(xk) 和二阶导数 f ′ ′ ( x k ) f(x_k) f′′(xk)。 计算搜索步长 计算一维搜索的步长 t k t_k tk通常使用牛顿法的更新公式 t k − f ′ ( x k ) f ′ ′ ( x k ) t_k -\frac{f(x_k)}{f(x_k)} tk−f′′(xk)f′(xk) 更新当前点 使用步长 t k t_k tk 更新当前点 x k 1 x k t k x_{k1} x_k t_k xk1xktk 重复迭代 重复步骤 2-4直到满足停止条件例如梯度足够小或达到最大迭代次数。
需要注意的是上述步骤中的计算是在一维搜索方向上进行的因此 f ′ ( x k ) f(x_k) f′(xk) 和 f ′ ′ ( x k ) f(x_k) f′′(xk) 分别是一维的梯度和二阶导数。在牛顿法中使用二阶导数信息可以更准确地确定搜索步长因此相较于一些基于一阶导数信息的方法牛顿法可能在一维搜索中更快地收敛。
总的来说一维线性搜索的 Newton 法是一种有效的优化方法特别适用于目标函数具有二阶导数信息的情况。
示例
用 Newton 法求 min φ ( t ) ∫ 0 t arctan x d x \min\:\varphi(t)\int_0^t \arctan x\:dx minφ(t)∫0tarctanxdx 的最优解.
解 φ ′ ( t ) arctan t , 1 φ ′ ′ ( t ) 1 t 2 , t k 1 t k − φ ′ ( t k ) 1 φ ′ ′ ( t k ) \varphi^{\prime}(t)\arctan t,\:\frac{1}{\varphi^{\prime\prime}(t)}1t^{2},\:t_{k1}t_{k}-\varphi^{\prime}(t_{k})\frac{1}{\varphi^{\prime\prime}(t_{k})} φ′(t)arctant,φ′′(t)11t2,tk1tk−φ′(tk)φ′′(tk)1 选择 t 1 1 t_11 t11开始计算搜索精度取 ε 0.01 \varepsilon0.01 ε0.01. k t k φ ′ ( t k ) 1 / φ ′ ′ ( t k ) 1 1 0.7854 2 2 − 0.5708 − 0.5187 1.3258 3 0.1169 0.1164 1.0137 4 − 0.0011 − 0.0011 \begin{array}{|r|r|r|r|r|}\hline kt_k\varphi^{\prime}(t_k)1/\varphi^{\prime\prime}(t_k)\\\hline110.78542\\\hline2-0.5708-0.51871.3258\\\hline30.11690.11641.0137\\\hline4-0.0011-0.0011\\\hline\end{array} k1234tk1−0.57080.1169−0.0011φ′(tk)0.7854−0.51870.1164−0.00111/φ′′(tk)21.32581.0137 最后输出 t k − 0.0011 t_k-0.0011 tk−0.0011.
