目录
【问题】在迭代中，已知 \(x^{(k)}\) 和下降方向 \(d^{(k)}\)，如何确定下降步长 \(\alpha^{(k)}\)，使得 \(f(x^{(k)} + \alpha^{(k)} d^{(k)}) < f(x^{(k)})\)？
精确线搜索技术
【思想】\(\alpha^{(k)} = \mathop{\arg\min}\limits_{\alpha \geq 0} = \varphi(\alpha) = f(x^{(k)} + \alpha d^{(k)})\)，通过解以下方程求出 \(\alpha^{(k)}\)：
\[\frac{\mathrm{d} \varphi}{\mathrm{d} \alpha} \bigg|_{\alpha = \alpha^{(k)}} = \nabla f(x^{(k)} + \alpha^{(k)} d^{(k)})^T d^{(k)} = 0 \]【主要框架】
- 确定包含 \(\alpha^{(k)}\) 的搜索区间
- 基于分割技术或插值技术，不断缩小搜索区间，求出 \(d^{(k)}\)
进退法确定搜索区间
【定义】令 \(\alpha^{*} = \mathop{\arg\min}\limits_{\alpha \geq 0} = \varphi (\alpha)\)（即 \(\alpha^*\) 为某个区间的极小值点），若 \([a,b] \subset [0,+\infty)\)，且 \(\alpha^{*} \in [a,b]\)，则称 \([a,b]\) 为一个搜索区间。
【算法步骤】假设搜索区间 \([a,b]\) 是一个单峰区间，
- 第一步：初值 \(\alpha_0 \geq 0, h_0>0, k=0\)，计算 \(\varphi_0 = \varphi(\alpha_0)\)
- 第二步：令 \(\alpha_{k+1} = \alpha_k + h_k\)，计算 \(\varphi_{k+1} =\varphi(\alpha_{k+1})\)
- 若 \(\varphi_{k+1} < \varphi_{k}\)，跳转第三步
- 若 \(\varphi_{k+1} \geq \varphi_{k}\)，跳转第四步
- 第三步：作前进运算，令 \(h_{k+1} \leftarrow 2 h_{k}\)，\(\alpha \leftarrow \alpha_{k}\)，\(\alpha_{k} \leftarrow \alpha_{k+1}\)，\(\varphi_{k} \leftarrow \varphi_{k+1}\)，\(k \leftarrow k+1\)，返回第二步
- 第四步：
- 若 \(k=0\)，作后退运算，令 \(h_{1} \leftarrow -h_{0}\)，\(\alpha \leftarrow \alpha_1\)，\(\alpha_1 \leftarrow \alpha_0\)，\(\varphi_1 \leftarrow \varphi_0\)，\(k=1\)，返回第二步
- 若 \(k>0\)，停止迭代，令 \(a = \min(\alpha, \alpha_{k+1})\)，\(b = \max(\alpha, \alpha_{k+1})\)，则 \([a,b]\) 为包含极小值的搜索区间
分割法确定极小值
二分法
【算法步骤】第 \(k\) 步：\([a_k, b_k]\)，令 \(c = \frac{1}{2} (a_k + b_k)\)，计算 \(\varphi'(c)\)
- 若 \(\varphi'(c) = 0\)，令 \(\alpha^* = c\)，停止迭代
- 若 \(\varphi'(c) > 0\)，说明 \(\alpha^* \in [a_k, c]\)，令 \([a_{k+1}, b_{k+1}] \leftarrow [a_k, c]\)，继续迭代
- 若 \(\varphi'(c) < 0\)，说明 \(\alpha^* \in [c, b_k]\)，令 \([a_{k+1}, b_{k+1}] \leftarrow [c, b_k]\)，继续迭代
黄金分割法
【算法思想】第 \(k\) 步：\([a_k, b_k]\)，往该区间插入两个试探点 \(\lambda_k\) 和 \(\mu_k\)，其中 \(\lambda_k < \mu_k\)，计算 \(\varphi(\lambda_k)\) 和 \(\varphi(\mu_k)\)，
- 若 \(\varphi(\lambda_k) \leq \varphi(\mu_k)\)，说明 \(\alpha^* \in [a_k, \mu_k]\)，令 \([a_{k+1}, b_{k+1}] \leftarrow [a_k, \mu_k]\)，继续迭代
- 若 \(\varphi(\lambda_k) > \varphi(\mu_k)\)，说明 \(\alpha^* \in [\lambda_k, b_k]\)，令 \([a_{k+1}, b_{k+1}] \leftarrow [\lambda_k, b_k]\)，继续迭代
【试探点需满足的条件】（参考资料）两个条件：
- 区间长度相同：\([a_k, \mu_k] = [\lambda_k, b_k]\)，即 \(b_k - \lambda_k = \mu_k - a_k\)，使得分割点是对称的。
- 区间长度的缩短率相同：\(b_{k+1} - a_{k+1} = \rho(b_k - a_k)\)，其中 \(\rho\) 为区间长度缩短率。
因此可得：
\[\begin{cases} \lambda_k = a_k + (1-\rho)(b_k - a_k) \\ \mu_k = a_k + \rho(b_k - a_k) \\ \end{cases} \]现在考虑情形 \(\varphi(\lambda_k) \leq \varphi(\mu_k)\)，此时新的搜索区间为 \([a_{k+1}, b_{k+1}] = [a_k, \mu_k]\)。为进一步缩短搜索区间，需取新的试探点 \(\lambda_{k+1}, \mu_{k+1}\)，由上式可得：
\[\begin{aligned} \mu_{k+1} &= a_{k+1} + \rho(b_{k+1} - a_{k+1}) \\ &= a_{k} + \rho^2 (b_k - a_k) \end{aligned} \]每次缩小搜索区间时，上一次迭代得到的分割点可复用为下一次的分割点，因此不必重新计算新的试探点，于是有 \(\mu_{k+1} = \lambda_k\)，于是有 \(\rho^2 = 1-\rho\)，解得 \(\rho = 0.618\)。
对于情形 \(\varphi(\lambda_k) > \varphi(\mu_k)\) 也有相同的结论，此处不再赘述。所以有：
\[\begin{cases} \lambda_k = a_k + 0.382(b_k - a_k) \\ \mu_k = a_k + 0.618(b_k - a_k) \\ \end{cases} \]【算法步骤】
- 第一步：初始区间 \([a_0, b_0]\)，给定 \(\epsilon > 0\)，\(k=0\)，计算初始分割点：
-
第二步：计算 \(\varphi(\lambda_k)\) 和 \(\varphi(\mu_k)\)，
- 若 \(\varphi(\lambda_k) \leq \varphi(\mu_k)\)，说明 \(\alpha^* \in [a_k, \mu_k]\)，跳转第三步
- 若 \(\varphi(\lambda_k) > \varphi(\mu_k)\)，说明 \(\alpha^* \in [\lambda_k, b_k]\)，跳转第四步
-
第三步：若 \(\mu_k - a_k < \epsilon\)，则输出 \(\alpha^* = \lambda_k\)；否则，令 \(a_{k+1} \leftarrow a_k\)，\(b_{k+1} \leftarrow \mu_k\)，\(\mu_{k+1} \leftarrow \lambda_k\)，\(\lambda_{k+1} = a_{k+1} + 0.382(b_{k+1} - a_{k+1})\)，\(k \leftarrow k+1\)，返回第二步
-
第四步：若 \(b_k - \lambda_k < \epsilon\)，则输出 \(\alpha^* = \mu_k\)；否则，令 \(a_{k+1} \leftarrow \lambda_k\)，\(b_{k+1} \leftarrow b_k\)，\(\lambda_{k+1} \leftarrow \mu_k\)，\(\mu_{k+1} = a_{k+1} + 0.618(b_{k+1} - a_{k+1})\)，\(k \leftarrow k+1\)，返回第二步
插值法
三点二次插值法（拉格朗日插值法）
（此处用 \(s\) 代替上文中的 \(\alpha\)）
【算法原理】构造抛物线方程：\(q(s) = a_0 + a_1 s + a_2 s^2\)，将 \(s_0, s_1, s_2\) 三个点代入求解 \(a_0, a_1, a_2\)，解得：
\[\begin{cases} a_1 = ... \\ a_2 = ... \\ \end{cases} \]设 \(\bar{s}\) 为该抛物线的极小值点，则有 \(q'(\bar{s})=0\)，所以有：
\[\bar{s} = -\frac{a_1}{2a_2} \]【算法步骤】
-
第一步：在 \([a,b]\) 中由进退法取三个点：\(s_0, s_1, s_2\)，使得对于 \(\varphi_0 = \varphi(s_0), \varphi_1 = \varphi(s_1), \varphi_2 = \varphi(s_2)\)，有 \(\varphi_0 > \varphi_1 < \varphi_2\)，即“两边高中间低”。
-
第二步：由公式计算 \(\bar{s}\) 和 \(\bar{\varphi}(\bar{s})\)，
- 若 \(\bar{\varphi}(\bar{s}) > \varphi_1\)，转步骤三。
- 若 \(\bar{\varphi}(\bar{s}) \leq \varphi_1\)，转步骤四。
-
第三步：
- 若 \(s_1 > \bar{s}\)，则 \(s_2 \leftarrow s_1\)，\(s_1 \leftarrow \bar{s}\)，\(\varphi_2 \leftarrow \varphi_1\)，\(\varphi_1 \leftarrow \bar{\varphi}\)，转步骤五。
- 若 \(s_1 \leq \bar{s}\)，则 \(s_0 \leftarrow s_1\)，\(s_1 \leftarrow \bar{s}\)，\(\varphi_0 \leftarrow \varphi_1\)，\(\varphi_1 \leftarrow \bar{\varphi}\)，转步骤五。
-
第四步：
- 若 \(s_1 > \bar{s}\)，则 \(s_0 \leftarrow \bar{s}\)，\(\varphi_0 \leftarrow \bar{\varphi}\)，转步骤五。
- 若 \(s_1 \leq \bar{s}\)，则 \(s_2 \leftarrow \bar{s}\)，\(\varphi_2 \leftarrow \bar{\varphi}\)，转步骤五。
-
第五步：若 \(|s_2 - s_0| < \epsilon\)，则输出 \(s^* = s_1\)；否则，转步骤二。