本文基本上是老师的讲义, 少部分为自己理解或修改.

首先回忆最优化问题的形式.

\begin{equation*} \min_{x \in \R^n} f(x),\quad \st x \in X.\end{equation*}

考虑最简单的情况: $n = 1$, 此时考虑的函数为 $f : \R \to \R$, $X$ 可以是 $(-\infty, a]$, $[a, b]$, $[b, +\infty)$, 也可以是这些区间的并集. 为方便起见, 先考虑无约束的一维最优化问题:
\begin{equation}\label{equ:notResOneOpt}
\min_{x \in \R} f(x).
\end{equation}

• 它是高维优化问题的基础.
• 一般只考虑非线性的 $f$, 线性的情况是平凡的.
• 假设 $f \in C^1$, 若 $x^* \in \R$ 是问题 \eqref{equ:notResOneOpt} 的解, 则有 $f’(x^*) = 0$, 于是我们获得了一个必要条件
  \begin{equation}\label{equ:fpxEqu0}
  f’(x) = 0.
  \end{equation}

Newton 法

例 $x^2 = 2$, 希望求出正根. 观察函数图像可知正根大于 $1$ 小于 $2$. 我们取初始的 $x = 1$.

1. $x = 1 + \ep$, $0 < \ep < 1$, 有 $(1 + \ep)^2 = 2$, 展开得 $1 + 2\ep + \ep^2 = 2$ 忽略二次项, 解得 $\ep \approx \dfrac{1}{2}$, 得到 $x \approx 1.5$.

2. $x = 1.5 + \ep$, $0 < \ep < 1$, 有 $(1.5 + \ep)^2 = 2$, 展开得 $2.25 + 3\ep + \ep^2 = 2$ 忽略二次项, 解得 $\ep \approx -\dfrac{1}{12}$, 得到 $x \approx 1.416$.

3. $x = 1.5 - \dfrac{1}{12} + \ep$, $\cdots$

Newton 法的思想

先猜测一个初值, 然后 $x \approx x_k + \ep$, 前面做的实际上是进行了一个二阶的 Taylor 展开

\begin{equation*} P(x_k + \ep) = 0 \Rightarrow P(x_k) + \ep P'(x_k) + O(\ep^2).\end{equation*}

由于 $\ep$ 是无穷小量, 可以把 $O(\ep^2)$ 近似为 $0$, 得到一个线性方程, 求解得到

\begin{equation*} \ep\approx\dfrac{P(x_k)}{P'(x_k)},\end{equation*}

于是得到迭代公式

\begin{equation*} x_{k + 1} = x_k - \dfrac{P(x_k)}{P'(x_k)}.\end{equation*}

有了 Newton 法的思想后, 可以直接应用到 \eqref{equ:fpxEqu0}, 只需要把 $P(x)$ 替换成 $f’(x)$.

算法, 可靠性及有效性

算法 2.1 (一维问题 Newton 法)

Step 1. 给定 $\ep > 0$ 作为精度要求 (终止条件). 取 $k = 0$ 及 $x_0$.

Step 2. 计算 $f’(x_k)$ 及 $f^{\prime\prime}(x_k)$.

Step 3. $x_{k + 1} = x_k - \dfrac{f’(x_k)}{f^{\prime\prime}(x_k)}$.

Step 4. 若 $\lrv{f’(x_{k + 1})} < \ep$ 则停止, 输出 $x^* = x_{k + 1}$.

否则, 取 $x_k = x_{k + 1}$, $k = k + 1$, 进入 Step 2.

需要对这个算法给出相应的数学分析.

• 可靠性: 是否 $x_k \to x^*$, $k \to \infty$?

• 有效性: $\lrv{x_k - x^*}$ 收敛到 $0$ 的速度 (作为 $k$ 的函数)?

定理 2.1 设 $f \in C^2$, $f’(x^*) = 0$, $f^{\prime\prime}(x^*) \neq 0$. $\lrb{x_k}$ 是算法 2.1 产生的序列, 则当 $x_0$ 充分靠近 $x^*$ 时, 有

• $\displaystyle\lim_{k \to \infty} x_k = x^*$;

• $\displaystyle\lim_{k \to \infty} \dfrac{\lrv{x_{k + 1} - x^*}}{\lrv{x_k - x^*}} = 0$;

• 特别地, 若 $f \in C^3$, 则 $\lrv{x_{k + 1} - x^*} = O\left(\lrv{x_k - x^*}^2\right)$.

证明

\begin{align*}
x_{k + 1} - x^* &= x_k - \dfrac{f’(x_k)}{f^{\prime\prime}(x_k)} - x^*\\
&= x_k - x^* - \dfrac{f’(x_k)}{f^{\prime\prime}(x_k)}\\
&= x_k - x^* - \dfrac{\displaystyle\int_{x^*}^{x_k} f^{\prime\prime}(x)\di x}{f^{\prime\prime}(x_k)}\\
&= \dfrac{1}{f^{\prime\prime}(x_k)}\left( \int_{x^*}^{x_k} \left( f^{\prime\prime}(x_k) - f^{\prime\prime}(x) \right) \di x\right),
\end{align*}

因为 $f \in C^2$ 且 $f^{\prime\prime}(x^*) \neq 0$, 所以存在 $\de > 0$, $x, y \in (x^* - \de, x^* + \de)$ 时, 有

\begin{equation*} \lrv{f^{\prime\prime}(x) - f^{\prime\prime}(y)} \leqslant \dfrac{1}{2}\lrv{f^{\prime\prime}(x)},\end{equation*}

进而

\begin{equation*} \lrv{x_{k + 1} - x^*} \leqslant \dfrac{1}{2}\lrv{x_{k} - x^*},\end{equation*}

第一个结论得证.$\square$

习题 2.1 证明定理 2.1 的后两个结论.

证明 由 Taylor 公式可得

\begin{equation*} 0 = f'(x^*) = f'(x_k) + f^{\prime\prime}(x_k)(x^* - x_k) + o(\lrv{x^* - x_k}),\end{equation*}

于是

\begin{equation*} x_{k + 1} - x^* = x_k - \dfrac{f'(x_k)}{f^{\prime\prime}(x_k)} - x^* = -\dfrac{f'(x_k) + f^{\prime\prime}(x_k)(x^* - x_k)}{f^{\prime\prime}(x_k)} = o(\lrv{x^* - x_k}).\end{equation*}

由 Taylor 公式可得

\begin{equation*} 0 = f'(x^*) = f'(x_k) + f^{\prime\prime}(x_k)(x^* - x_k) + \dfrac{1}{2}f^{\prime\prime\prime}(x_k)(x^* - x_k)^2 + o(\lrv{x^* - x_k}^2),\end{equation*}

于是

\begin{equation*} 0 = \dfrac{f'(x_k)}{f^{\prime\prime}(x_k)} + x^* - x_k + \dfrac{f^{\prime\prime\prime}(x_k)}{2f^{\prime\prime}(x_k)}(x^* - x_k)^2 + o(\lrv{x^* - x_k}^2),\end{equation*}

进而

\begin{equation*} \dfrac{x_{k + 1} - x^*}{\left(x^* - x_k\right)^2} = \dfrac{f^{\prime\prime\prime}(x_k)}{2f^{\prime\prime}(x_k)} + o(1) = O(1),\end{equation*}

故 $\lrv{x_{k + 1} - x^*} = O\left(\lrv{x_k - x^*}^2\right)$.$\square$

定义 2.1 记 $e_k = \lrvv{x_k - x^*}$, 取

\begin{equation*} Q_p := \limsup_{k\to\infty} \dfrac{e_{k + 1}}{e_{k}^p},\quad p > 0.\end{equation*}

• 若 $0 < Q_1 < 1$, 则称 $x_k$ 是线性收敛的.

• 若 $Q_1 = 0$, 则称 $x_k$ 是超线性收敛的.

• 若 $p > 1$ 且 $0 < Q_p < \infty$, 则称 $x_k$ 是 $p$ 阶收敛的.

• Newton 法是超线性收敛的. 若 $f \in C^3$, 则 Newton 法是二阶收敛的.

习题 2.2 假定 $\lrvv{x_0 - x^*} = 3 \times 10^{-3}$, 设两个算法收敛速度分别为

\begin{equation*} \dfrac{\lrvv{x_{k + 1} - x^*}}{\lrvv{x_{k} - x^*}} = \dfrac{1}{2},\quad \dfrac{\lrvv{x_{k + 1} - x^*}}{\lrvv{x_{k} - x^*}^2} = \dfrac{1}{2},\end{equation*}

若需要达到 $\lrvv{x_{k} - x^*} \leqslant 10^{-9}$, 则两个算法分别需要多少次迭代?

解 对于第一种算法有

\begin{equation*} \dfrac{1}{2^k} = \dfrac{\lrvv{x_{k} - x^*}}{\lrvv{x_{0} - x^*}} \leqslant \dfrac{10^{-9}}{3 \times 10^{-3}},\end{equation*}

解得 $k \geqslant \log_2 3 \times 10^6 \approx 21.5165$, 至少 $22$ 次迭代.

对于第二种算法有
\begin{align*}
\lrvv{x_{1} - x^*} &= \dfrac{1}{2}\lrvv{x_{0} - x^*}^{2} = 4.5 \times 10^{-6} > 10^{-9},\\
\lrvv{x_{2} - x^*} &= \dfrac{1}{2}\lrvv{x_{1} - x^*}^{2} = 1.0125 \times 10^{-11} < 10^{-9},
\end{align*}

所以至少 $2$ 次迭代.$\square$

割线法

割线法的思想和 Newton 法非常相似, 它甚至可以看成是 Newton 法的一种近似. Newton 法的核心是迭代公式

\begin{equation*} x_{k + 1} = x_k - \dfrac{f'(x_k)}{f^{\prime\prime}(x_k)},\end{equation*}

但实际计算中由于 $f$ 的光滑性或者计算复杂度的问题, 我们经常希望避免二阶导数的计算.

想法: 用差商来近似 (替代) 求导运算, 即

\begin{equation*} f^{\prime\prime}(x_k) \approx \dfrac{f'(x_k) - f'(x_{k - 1})}{x_k - x_{k - 1}},\end{equation*}

代入 Newton 法中, 得到

\begin{equation*} x_{k + 1} = x_k - \dfrac{f'(x_k)}{\dfrac{f'(x_k) - f'(x_{k - 1})}{x_k - x_{k - 1}}}.\end{equation*}

算法 2.2 (一维优化问题割线法)

Step 1. 给定 $\ep > 0$, 初始值 $x_0$, $x_1$, 令 $k = 1$, 计算 $f’(x_{k - 1})$.

Step 2. 计算 $f’(x_k)$.

Step 3. 若 $\lrv{f’(x_k)} < \ep$ 则停止, 输出 $x^* = x_k$, 否则计算

\begin{equation*} x_{k + 1} = x_k - \dfrac{f'(x_k)(x_k - x_{k - 1})}{f'(x_k) - f'(x_{k - 1})},\end{equation*}

令 $k = k + 1$, 进入 Step 2.

下面通过数学分析来看割线法的可靠性与有效性.

定理 2.2 设 $f \in C^3$, $f’(x^*) = 0$, $f^{\prime\prime}(x^*) \neq 0$, 则当 $x_1$, $x_2$ 充分靠近 $x^*$ 时, 算法 2.2 产生的序列 $\lrb{x_k}$ 满足

\begin{equation*} \lim_{k \to \infty} \dfrac{\lrvv{x_{k + 1} - x^*}}{\lrvv{x_{k + 1} - x^*}^\tau} = \lrvv{\dfrac{f^{\prime\prime\prime}(x^*)}{2f^{\prime\prime}(x^*)}}^\frac{1}{\tau},\quad \text{其中}~\tau = \dfrac{\sqrt{5} + 1}{2} < 2.\end{equation*}

证明 (这个证明我感觉有问题, 主要是 Peano 余项那部分估计) 作差
\begin{align}
x_{k + 1} - x^* &= x_k - \dfrac{f’(x_k)(x_k - x_{k - 1})}{f’(x_k) - f’(x_{k - 1})} - x^*\nonumber\\
&= \dfrac{1}{f’(x_k) - f’(x_{k - 1})}\left( f’(x_k)(x_{k - 1} - x^*) - f’(x_{k - 1})(x_{k} - x^*) \right),\label{equ:xkp1xs}
\end{align}

由 $f \in C^3$, 利用带 Peano 余项的 Taylor 展开
\begin{align*}
f’(x_k) &= f’(x^*) + f^{\prime\prime}(x^*)(x_k - x^*) + \dfrac{1}{2}f^{\prime\prime\prime}(x^*)(x_k - x^*)^2 + o\left( \lrv{x_k - x^*}^2 \right),\\
f’(x_{k - 1}) &= f’(x^*) + f^{\prime\prime}(x^*)(x_{k - 1} - x^*) + \dfrac{1}{2}f^{\prime\prime\prime}(x^*)(x_{k - 1} - x^*)^2 + o\left( \lrv{x_{k - 1} - x^*}^2 \right),
\end{align*}

代回 \eqref{equ:xkp1xs} 式得 (第一项由于 $f’(x^*) = 0$ 消失, 第二项由于抵消消失)
\begin{align}
x_{k + 1} - x^* =& \dfrac{1}{f’(x_k) - f’(x_{k - 1})} \left( \dfrac{f^{\prime\prime\prime}(x^*)}{2}(x_k - x^*)(x_{k - 1} - x^*)(x_k - x_{k - 1}) \right)\nonumber\\
&+ \dfrac{1}{f’(x_k) - f’(x_{k - 1})} \left( (x_{k - 1} - x^*) o\left( \lrv{x_k - x^*}^2 \right)\right.\nonumber\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad -\left. (x_k - x^*) o\left( \lrv{x_{k - 1} - x^*}^2 \right) \right)\nonumber\\
=&: T_1 + T_2\quad (\text{两项分别记为}~T_1~\text{与}~T_2).\label{equ:T1T2}
\end{align}

对于 $T_1$, 由中值定理可得

\begin{equation*} f'(x_k) - f'(x_{k - 1}) = \left( f^{\prime\prime}(x^*) + o(1) \right)(x_k - x_{k - 1}),\end{equation*}

代入可得

\begin{equation*} T_1 = \dfrac{f^{\prime\prime\prime}(x^*)}{2}(x_k - x^*)(x_{k - 1} - x^*)\dfrac{1}{f^{\prime\prime}(x^*) + o(1)}.\end{equation*}

由

\begin{equation*} \dfrac{1}{f^{\prime\prime}(x^*)} - \dfrac{1}{f^{\prime\prime}(x^*) + o(1)} = \dfrac{o(1)}{f^{\prime\prime}(x^*)\left( f^{\prime\prime}(x^*) + o(1) \right)}\end{equation*}

有

\begin{equation*} T_1 = \dfrac{f^{\prime\prime\prime}(x^*)}{2f^{\prime\prime}(x^*)}(x_k - x^*)(x_{k - 1} - x^*) + o\left( \lrv{x_k - x^*}\lrv{x_{k - 1} - x^*} \right).\end{equation*}

对于 $T_2$, 记 $e_k = x_k - x^*$, $r_k = r(e_k)$ 为 Peano 余项, 它是 $e_k$ 的函数, 有
\begin{equation}\label{equ:rxx2}
\displaystyle\lim_{x \to 0}\dfrac{r(x)}{x^2} = 0,
\end{equation}

及
\begin{align*}
T_2 &= \dfrac{1}{f’(x_k) - f’(x_{k - 1})}\left( e_{k - 1}r_k - e_kr_{k - 1} \right)\\
&= \dfrac{1}{f^{\prime\prime}(\tilde{x})(x_k - x_{k - 1})} e_{k - 1}e_k\left( \dfrac{r_k}{e_k} - \dfrac{r_{k - 1}}{e_{k - 1}} \right)\quad \text{其中}~\tilde{x} \in (x_{k - 1}, x_k)\\
&= \dfrac{1}{f^{\prime\prime}(\tilde{x})}\dfrac{e_{k - 1}e_k}{e_k - e_{k - 1}}\left( \dfrac{r_k}{e_k} - \dfrac{r_{k - 1}}{e_{k - 1}} \right).
\end{align*}

记 $g(x) = \dfrac{r(x)}{x}$, 由 \eqref{equ:rxx2} 式可得 $\displaystyle\lim_{x \to 0} g’(x) = 0$, 于是
\begin{align*}
\lim_{k \to \infty}\dfrac{T_2}{e_ke_{k - 1}} &= \lim_{k \to \infty} \dfrac{1}{f^{\prime\prime}(\tilde{x})} \dfrac{1}{e_k - e_{k - 1}}\left( \dfrac{r_k}{e_k} - \dfrac{r_{k - 1}}{e_{k - 1}} \right)\\
&= \lim_{k \to \infty} \dfrac{1}{f^{\prime\prime}(\tilde{x})} \dfrac{1}{e_k - e_{k - 1}} g’(\tilde{e})\left( e_k - e_{k - 1}\right)\quad \text{其中}~\tilde{e} \in (e_{k - 1}, e_k)\\
& = 0.
\end{align*}

故 $T_2 = o(e_k e_{k - 1})$. 由 \eqref{equ:T1T2} 式结合 $T_1$ 与 $T_2$ 的估计可得

\begin{equation*} x_{k + 1} - x^* = \dfrac{f^{\prime\prime\prime}(x^*)}{2f^{\prime\prime}(x^*)}(x_k - x^*)(x_{k - 1} - x^*) + o\left( \lrv{x_k - x^*}\lrv{x_{k - 1} - x^*} \right),\end{equation*}

所以 $x_k \to x^*$, $k \to \infty$, 进而使用以下引理即可证得定理结论.$\square$

引理 2.1 设 $e_k > 0$ 且 $\displaystyle\lim_{k \to \infty} e_k = 0$, 若 $e_{k + 1} = \beta_k e_k e_{k - 1}$, 其中 $\beta_k \to \beta^* > 0$, 则

\begin{equation*} \lim_{k \to \infty} \dfrac{e_{k + 1}}{e_k^\tau} = \left(\beta^* \right)^\frac{1}{\tau},\quad \tau = \dfrac{\sqrt{5} + 1}{2}.\end{equation*}

习题 2.3 证明上述引理. 提示: $\ln e_{k + 1} = \ln e_k + \ln e_{k - 1} + \ln \beta_k$, 利用 $\tau^2 = \tau + 1$, 有

\begin{equation*} \ln e_{k + 1} - \tau \ln e_k = -\dfrac{1}{\tau} \left( \ln e_k - \tau \ln e_{k - 1} \right) + \ln \beta_k.\end{equation*}

证明 利用提示内容, 有

\begin{equation*} \ln e_{k + 1} - \tau \ln e_k - \dfrac{1}{\tau}\ln\ba_k = -\dfrac{1}{\tau} \left( \ln e_k - \tau \ln e_{k - 1} - \dfrac{1}{\tau}\ln\ba_{k - 1} \right) + \dfrac{\ln \beta_k - \ln \ba_{k - 1}}{\tau^2}.\end{equation*}

令

\begin{equation*} a_k = \ln e_{k + 1} - \tau \ln e_k - \dfrac{1}{\tau}\ln\ba_k,\quad b_{k - 1} = \dfrac{\ln \beta_{k} - \ln \ba_{k - 1}}{\tau^2},\end{equation*}

有
\begin{align*}
a_k &= -\dfrac{1}{\tau}a_{k - 1} + b_{k - 1}\\
&= -\dfrac{1}{\tau}\left( -\dfrac{1}{\tau}a_{k - 2} + b_{k - 2} \right) + b_{k - 1}\\
&=\dfrac{a_1}{(-\tau)^{k - 1}} + \left( b_{k - 1} - \dfrac{1}{\tau}b_{k - 2} + \dfrac{1}{\tau^2}b_{k - 3} + \cdots + \dfrac{1}{(-\tau)^{k - 2}}b_{1} \right)\\
&=: x_{k - 1} + y_{k - 1}.
\end{align*}

由 $\displaystyle\lim_{k \to \infty} b_k = 0$, 对于任意 $\ep > 0$, 存在 $N \in \N$, $n > N$ 时, $\lrv{b_k} < \ep$. 令 $M = \lrb{\lrv{b_1}, \lrv{b_2}, \cdots, \lrv{b_N}}$, 有
\begin{align*}
\lrv{y_{k - 1}} &= \lrv{b_{k - 1} - \dfrac{1}{\tau}b_{k - 2} + \cdots + \dfrac{1}{(-\tau)^{k - 1 - N}}b_N + \cdots + \dfrac{1}{(-\tau)^{k - 2}}b_{1}}\\
&\leqslant \left( 1 + \dfrac{1}{\tau} + \cdots + \dfrac{1}{\tau^{k - 1 - N}} \right)\ep + \left( \dfrac{1}{\tau^{k - N}} + \cdots + \dfrac{1}{\tau^{k - 2}} \right) M\\
&< \left( \sum_{i = 0}^{\infty} \dfrac{1}{\tau^i} \right)\ep + \left( \sum_{i = k - N}^{\infty} \dfrac{1}{\tau^i} \right)M\\
&= \dfrac{1}{1 + \tau}\ep + \left( \sum_{i = k - N}^{\infty} \dfrac{1}{\tau^i} \right)M,
\end{align*}

令 $k \to \infty$, 有

\begin{equation*} \lim_{k \to \infty} \lrv{y_{k - 1}} < \dfrac{1}{1 + \tau}\ep,\end{equation*}

由 $\ep$ 的任意性知 $\displaystyle\lim_{k \to \infty} y_{k - 1} = 0$. 显然有 $\displaystyle\lim_{k \to \infty} x_{k - 1} = 0$, 因此 $\displaystyle\lim_{k \to \infty} a_{k} = 0$, 进而有

\begin{equation*} \lim_{k \to \infty} \ln e_{k + 1} - \tau \ln e_k = \lim_{k \to \infty} \dfrac{1}{\tau}\ln\ba_k = \dfrac{1}{\tau} \ln \ba^*,\end{equation*}

所以
\begin{align*}
\lim_{k \to \infty} \dfrac{e_{k + 1}}{e_k^\tau} = \left(\beta^* \right)^\frac{1}{\tau}.\tag*{$\square$}
\end{align*}

两种方法统一的刻画

前面两种方法都可以用以下的方式刻画.

考虑 \eqref{equ:fpxEqu0} 式, 要得到 $x^*$, 从 $x_k$ 出发, 构造一个线性函数 $\eta_k(x)$ 逼近 $f’(x)$, 然后求解 $\eta_k(x_{k + 1}) = 0$, 得到近似值 $x^* = x_{k + 1}$.

回到 \eqref{equ:notResOneOpt} 式上, 同样地从 $x_k$ 出发, 构造一个二次函数 $\p_k(x)$ 逼近 $f(x)$, 然后求解 $\displaystyle\min_{x \in \R} \p_k(x)$ 的极小 $x_{k + 1}$, 得到近似值 $x^* = x_{k + 1}$.

前面所述的两种方法构造的二次函数为
\begin{equation}\label{equ:pkx}
\p_k(x) = f(x_k) + f’(x_k)(x - x_k) + \dfrac{1}{2} c_k(x - x_k)^2,
\end{equation}

满足条件

\begin{equation*} \p_k(x_k) = f(x_k),\quad \p'_k(x_k) = f'(x_k),\end{equation*}

要求出 $c_k$ 还需要增加条件.

对于 Newton 方法, 增加的条件为 $\p_k^{\prime\prime}(x_k) = f^{\prime\prime}(x_k)$, 解得 $c_k = f^{\prime\prime}(x_k)$, 进而 $x_{k + 1} = x_k - \dfrac{f’(x_k)}{f^{\prime\prime}(x_k)}$.

对于割线法, 增加的条件为 $\p’_k(x_{k - 1}) = f’(x_{k - 1})$, 解得 $c_k = \dfrac{f’(x_k) - f’(x_{k - 1})}{x_k - x_{k - 1}}$, 进而 $x_{k + 1} = x_k - \dfrac{f’(x_k)(x_k - x_{k - 1})}{f’(x_k) - f’(x_{k - 1})}$.

习题 2.4 若增加的条件为 $\p_k(x_{k - 1}) = f(x_{k - 1})$, 计算 $c_k$, 并进一步写出算法的迭代公式.

将 $\p_k(x_{k - 1}) = f(x_{k - 1})$ 代入 \eqref{equ:pkx} 式, 解得

\begin{equation*} c_k = \dfrac{2\left( f(x_{k - 1}) - f(x_k) -f'(x_k)(x_{k - 1} - x_k)\right)}{(x_{k - 1} - x_k)^2}.\end{equation*}

$\p_k(x)$ 的极小值点满足

\begin{equation*} x - x_k = -\dfrac{f'(x_k)} {c_k},\end{equation*}

故迭代公式为
\begin{align*}
x_{k + 1} = x_k - \dfrac{f’(x_k)(x_{k - 1} - x_k)^2}{2\left( f(x_{k - 1}) - f(x_k) -f’(x_k)(x_{k - 1} - x_k)\right)}.\tag*{$\square$}
\end{align*}

程序 1 求解 $\displaystyle\min_{x \in \R} -x\e^{-x}$, 已知 $x^* = 1$, 编制 Newton 法和割线法的程序来求解并进行比较, 初值选取为:

• Newton 法: $x_0 = 0$;
• 割线法: $x_0 = 0$, $x_1 = 0.5$.

解 取 $\ep = 2^{-52}$ (即 MATLAB 的浮点相对精度), 代码如下.

clear, clc, close all;
syms x
f(x) = -x .* exp(-x);
x0 = 0;
x1 = 0.5;
varepsilon = eps;
df = diff(f);
ddf = diff(df);
%% Newton 法

x = x0;

while true
    xk = x(end);
    x = [x; double(xk - df(xk) ./ ddf(xk))];
    if abs(df(x(end))) < varepsilon
        break;
    end
end
%% 割线法

y = [x0; x1];

while true
    xk = y(end);
    dfxk = df(xk);
    if abs(dfxk) < varepsilon
        break;
    end
    y = [y; double(xk - dfxk .* (xk - y(end - 1)) ./ (dfxk - df(y(end - 1))))];
end
%% 比较

figure;
plot(0 : (size(x, 1) - 1), abs(1 - x), 0 : (size(y, 1) - 1), abs(1 - y)), ...
    xlabel('迭代次数', 'FontName', '微软雅黑'), ...
    ylabel('误差', 'FontName', '微软雅黑'), ...
    legend('Newton 法', '割线法', 'FontName', '微软雅黑');
format long;
disp(x);
disp(x - 1);
disp(abs(x(2 : end) - 1) ./ abs(x(1 : (end - 1)) - 1) .^ 2);
disp(y);
disp(y - 1);
disp(abs(y(2 : end) - 1) ./ abs(y(1 : (end - 1)) - 1) .^ ((sqrt(5) + 1) ./ 2));

运行结果如下. 注意到 Newton 法的 $\dfrac{\lrv{x_k - x^*}}{\lrv{x_{k - 1} - x^*}^2}$ 与割线法的 $\dfrac{\lrv{x_k - x^*}}{\lrv{x_{k - 1} - x^*}^\tau}$ 都趋近于 $\lrv{\dfrac{f^{\prime\prime\prime}(x^*)}{2f^{\prime\prime}(x^*)}} = 1$.

Newton 法

$x_k$	$x_k - x^*$	$\dfrac{\lrv{x_k - x^*}}{\lrv{x_{k - 1} - x^*}^2}$
$0$	$-1.000000000000000$
$0.500000000000000$	$-0.500000000000000$	$0.500000000000000$
$0.833333333333333$	$-0.166666666666667$	$0.666666666666667$
$0.976190476190476$	$-0.023809523809524$	$0.857142857142858$
$0.999446290143965$	$-0.000553709856035$	$0.976744186046483$
$0.999999693575066$	$-0.000000306424934$	$0.999446596698782$
$0.999999999999906$	$-0.000000000000094$	$1.000304885275709$
$1.000000000000000$	$0$	$0$

割线法

$x_k$	$x_k - x^*$	$\dfrac{\lrv{x_k - x^*}}{\lrv{x_{k - 1} - x^*}^\tau}$
$0$	$-1.000000000000000$
$0.500000000000000$	$-0.500000000000000$	$0.500000000000000$
$0.717633299196792$	$-0.282366700803208$	$0.866742802928595$
$0.898802528965495$	$-0.101197471034505$	$0.783018667120379$
$0.976078343656424$	$-0.023921656343576$	$0.973779328626748$
$0.997722783634153$	$-0.002277216365847$	$0.956258176135382$
$0.999946231646904$	$-0.000053768353096$	$1.014697058670582$
$0.999999877700416$	$-0.000000122299584$	$0.989869260031477$
$0.999999999993424$	$-0.000000000006576$	$1.006279510682946$
$1.000000000000000$	$0$	$0$

抛物线法

若 $\p_k(x) = ax^2 + bx + c$ 满足

\begin{equation}\begin{cases}\begin{aligned}
\p_k(x_k) &= f(x_k),\\
\p_k(x_{k - 1}) &= f(x_{k - 1}),\\
\p_k(x_{k - 2}) &= f(x_{k - 2}),
\end{aligned}\end{cases}\label{equ:kk-1k-2}\end{equation}

则可以求出 $x_{k + 1} = \underset{x \in \R}{\mathrm{argmin}} \p_k(x)$ 来逼近 $x^*$.

为了求解 \eqref{equ:kk-1k-2} 式, 可以利用 Lagrange 插值公式, 有

\begin{align*}
\p_k(x) &= f(x_{k - 2}) \dfrac{(x - x_{k - 1})(x - x_k)}{(x_{k - 2} - x_{k - 1})(x_{k - 2} - x_k)}\\
&\quad + f(x_{k - 1}) \dfrac{(x - x_{k - 2})(x - x_k)}{(x_{k - 1} - x_{k - 2})(x_{k - 1} - x_k)}\\
&\quad + f(x_{k}) \dfrac{(x - x_{k - 1})(x - x_{k - 2})}{(x_{k} - x_{k - 1})(x_{k} - x_{k - 2})}
\end{align*}

习题 2.5 写出抛物线法的迭代公式, 进一步写出相应的算法. 注意:

• 每个迭代步只需算一次函数值;
• 如何选点进入新的迭代.

解 Lagrange 插值得到的公式为
\begin{align*}
\p_k(x) &= \dfrac{f(x_{k - 2})(x_k - x_{k - 1}) + f(x_{k - 1})(x_{k - 2} - x_k) + f(x_{k})(x_{k - 1} - x_{k - 2})}{(x_{k - 2} - x_{k - 1})(x_{k - 1} - x_k)(x_k - x_{k - 2})} x^2\\
&\quad + \dfrac{f(x_{k - 2})(x_{k - 1}^2 - x_k^2) + f(x_{k - 1})(x_k^2 - x_{k - 2}^2) + f(x_{k})(x_{k - 2}^2 - x_{k - 1}^2)}{(x_{k - 2} - x_{k - 1})(x_{k - 1} - x_k)(x_k - x_{k - 2})} x + c,
\end{align*}
最小值点即迭代公式为
\begin{equation}\label{equ:xkp1}
x_{k + 1} = \dfrac{f(x_{k - 2})(x_{k - 1}^2 - x_k^2) + f(x_{k - 1})(x_k^2 - x_{k - 2}^2) + f(x_{k})(x_{k - 2}^2 - x_{k - 1}^2)}{2(f(x_{k - 2})(x_{k - 1} - x_k) + f(x_{k - 1})(x_k - x_{k - 2}) + f(x_{k})(x_{k - 2} - x_{k - 1}))}.
\end{equation}
具体算法如下.

Step 1. 给定 $\ep > 0$, 初始值 $x_0 < x_1 < x_2$, 使得 $f(x_1) < f(x_0)$, $f(x_1) < f(x_2)$ (可用进退法确定: 给定 $x_0$, 步长 $h$, $\lambda = 1$, 若 $f(x_0) > f(x_1)$, 则 $x_2 = x_1 + \lambda h$, 不断扩大 $\lambda$ 使得 $f(x_2) > f(x_1)$, 若 $f(x_0) \leqslant f(x_1)$, 则 $x_2 = x_1 - \lambda h$, 不断扩大 $\lambda$ 使得 $f(x_2) > f(x_0)$).

Step 2. 若 $\lrv{x_2 - x_0} < \ep$, 则停止, 输出 $x^* = x_1$, 否则进入 Step 3.

Step 3. 利用 \eqref{equ:xkp1} 式计算 $x_3$, 若 $f(x_3) < f(x_1)$, 则进入 Step 4, 否则进入 Step 5.

Step 4. 若 $x_3 < x_1$, 则令 $x_2 = x_1$, 否则令 $x_0 = x_1$. 然后令 $x_1 = x_3$, 进入 Step 2.

Step 5. 若 $x_3 < x_1$ 则令 $x_0 = x_3$, 否则令 $x_2 = x_3$. 然后进入 Step 2.$\square$

二分法

要求解 $f’(x^*) = 0$, 可以通过迭代试探点来分割并缩小搜索区间, 目标:

• 极小点始终在搜索区间内;
• 区间缩小的速率尽可能快.

定理 2.3 (根存在定理) 若 $f’(a)f’(b) < 0$, 则 $f’(x) = 0$ 在 $(a, b)$ 内一定存在根.

根据定理 2.3, 选取区间的办法如下.

• 若 $f’(a)f’(c) < 0$, 则选取 $[a’, b’] = [a, c]$.
• 若 $f’(b)f’(c) < 0$, 则选取 $[a’, b’] = [c, b]$.

考虑最坏的情况, 有

\begin{equation*} \min\dfrac{\lrv{a' - b'}}{\lrv{a - b}} = \min_{c \in (a, b)}\dfrac{\max \lrb{\lrv{a - c}, \lrv{b - c}}}{\lrv{a - b}} = \dfrac{1}{2},\end{equation*}

即选取 $c = \dfrac{1}{2}(a + b)$ 可使收敛速度最快, 此时每次区间缩小到原来的 $\dfrac{1}{2}$, 为线性收敛的算法.

练习 写出二分法的算法.

Fibonacci 法

首先定义一个区间上的单峰函数.

定义 2.2 (单峰函数) $f \in C([a, b])$, 若 $x^* \in [a, b]$ 使得 $f$ 在 $[a, x^*]$ 上严格单调下降, 在 $[x^*, b]$ 上严格单调上升, 则称 $f$ 是 $[a, b]$ 上的单峰函数.

有如下性质.

1. $x^*$ 是 $f$ 在 $[a, b]$ 上的极小值点.

2. • 若 $a’ \in [a, x^*]$, 则 $f$ 在 $[a’, b]$ 上是单峰函数;

   • 若 $b’ \in [x^*, b]$, 则 $f$ 在 $[a, b’]$ 上是单峰函数.

3. 设 $x_1, x_2 \in [a, b]$, $x_1 < x_2$.

   • 若 $f(x_1) < f(x_2)$, 则 $x^* \in [a, x_2]$.

   • 若 $f(x_1) > f(x_2)$, 则 $x^* \in [x_1, b]$.

   • 若 $f(x_1) < f(x_2)$, 则 $x^* \in [x_1, x_2]$.

利用性质 3, 可以将 $[a, b]$ 缩小为 $[a’, b’]$:

\begin{equation*} [a', b'] = \left\{\begin{array}{ll} [a, x_2], & \text{若}~f(x_1) < f(x_2),\\ [x_1, b], & \text{若}~f(x_1) > f(x_2),\\ [x_1, x_2], & \text{若}~f(x_1) = f(x_2). \end{array}\right.\end{equation*}

如何寻找试探点 $x_1$, $x_2$, 使得 $\dfrac{\lrv{a’ - b’}}{\lrv{a - b}}$ 尽可能地小?

(后面再补)

习题 2.6 写出完整的 Fibonacci 算法. 提示:

• 由 $\ep$ 来决定迭代次数 $k$;
• 每一步只计算一次函数值.

解

Step 1. 给定 $[a, b]$ 和 $\ep > 0$, 求得 $k$ 及数列 $\lrb{F_i}_{i = 1}^k$ 使得 $F_k \geqslant \dfrac{b - a}{\ep} > F_{k - 1}$.

令

\begin{equation*} x_1 = a + \dfrac{F_{k - 2}}{F_k}(b - a),\quad x_2 = a + \dfrac{F_{k - 1}}{F_k}(b - a),\quad n = 1,\quad f_1 = f(x_1),\quad f_2 = f(x_2).\end{equation*}

Step 2. 若 $f_1 < f_2$, 进入 Step 3. 若 $f_1 \geqslant f_2$, 进入 Step 4.

Step 3. 令

\begin{equation*} b = x_2,\quad x_2 = x_1,\quad x_1 = a + \dfrac{F_{k - 2 - n}}{F_{k - n}}(b - a),\quad f_2 = f_1,\quad f_1 = f(x_1),\end{equation*}

若 $n = k - 2$ 则停止, 最小值位于 $[a, b]$, 否则 $n = n + 1$, 进入 Step 2.

Step 4. 令

\begin{equation*} a = x_1,\quad x_1 = x_2,\quad x_2 = a + \dfrac{F_{k - 1 - n}}{F_{k - n}}(b - a),\quad f_1 = f_2,\quad f_2 = f(x_2),\end{equation*}

若 $n = k - 2$ 则停止, 最小值位于 $[a, b]$, 否则 $n = n + 1$, 进入 Step 2.$\square$

• 优点: 收敛快.

• 缺点: 不灵活, 当精度要求改变时, 需要重新开始算法.

为了克服该缺点, 在 Fibonacci 法的基础上改进出黄金分割法.

黄金分割法

目标: 每一步区间缩小的比例相同.

(后面再补)

经过 $k$ 步以后 $\a \geqslant \dfrac{1}{F_{k + 1}} \geqslant \a^{k + 1}$, 所以只需要多迭代一步, 算法精度就可以超过 Fibonacci 法, 同时算法更灵活.

习题 2.7 证明 $\a^k \geqslant \dfrac{1}{F_{k + 1}} \geqslant \a^{k + 1}$. 提示: 利用 Fibonacci 数列的通项公式.

证明 首先求出 Fibonacci 数列的通项公式. 设 $r$, $s$ 满足

\begin{equation*} F_k - rF_{k - 1} = s(F_{k - 1} - rF_{k - 2}),\end{equation*}

则 $r + s = 1$, $rs = -1$, 解得

\begin{equation*} s = \dfrac{1 + \sqrt{5}}{2},\quad r = \dfrac{1 - \sqrt{5}}{2}.\end{equation*}

$k \geqslant 2$ 时, 有

\begin{equation*} F_k - rF_{k - 1} = s^{k - 1}(F_{1} - rF_{0}) = s^{k - 1} = s^k,\end{equation*}

进而
\begin{align*}
F_k &= rF_{k - 1} + s^k\\
&= s^k + rs^{k - 1} + r^2F_{k - 2}\\
&= \sum_{i = 0}^k s^{k - i}r^i\\
&= \dfrac{s^{k + 1} - r^{k + 1}}{s - r}\\
&= \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1 + \sqrt{5}}{2}\right)^{k + 1} - \left(\dfrac{1 - \sqrt{5}}{2}\right)^{k + 1}\right)\\
&= \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1}{\a}\right)^{k + 1} - \left(-\a\right)^{k + 1}\right),
\end{align*}

代入 $k = 0, 1$ 均成立. 于是
\begin{align*}
&\a^k \geqslant \dfrac{1}{F_{k + 1}} \geqslant \a^{k + 1}\\
\Longleftrightarrow\quad & \a^{-k} \leqslant \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1}{\a}\right)^{k + 2} - \left(-\a\right)^{k + 2}\right) \leqslant \a^{-k - 1}\\
\Longleftrightarrow\quad & \sqrt{5}\a^2 \leqslant 1 - (-\a^2)^{k + 2} \leqslant \sqrt{5} \a,
\end{align*}

上述不等式中只有中间部分是与 $k$ 有关的, 两边都是常数, 故只需分析中间部分的极值. $k$ 为偶数时, $k = 0$ 时取得最小值, 有 $1 - \a^4 = \sqrt{5}\a^2$, 中间部分随 $k$ 的增大而增大, $k \to \infty$ 时, 有 $1 \leqslant \sqrt{5}\a$. $k$ 为奇数时, $k = 1$ 时取得最大值, 有 $1 + \a^6 \leqslant 1.0558 \leqslant 1.3819 \leqslant \sqrt{5}\a$, 中间部分随 $k$ 的增大而减小, $k \to \infty$ 时, 有 $1 \geqslant \sqrt{5}\a^2$.$\square$

练习: 写出黄金分割法的完整算法.

线搜索

---