即使目标函数\(f(x)\)是一元函数， 求最小值点也经常需要使用数值迭代方法。 另外，在多元目标函数优化中， 一般每次迭代从上一步的\(\boldsymbol x^{(t)}\)先确定一个下降方向\(\boldsymbol d^{(t)}\), 然后对派生出的一元函数\(h(\alpha) = f(\boldsymbol x^{(t)} + \alpha \boldsymbol d^{(t)})\), \(\alpha \geq 0\)求最小值点得到下降的步长\(\alpha_t\)， 并令\(\boldsymbol x^{(t+1)} = \boldsymbol x^{(t)} + \alpha_t \boldsymbol d^{(t)}\)， 求步长的过程称为一维搜索， 搜索可以是求一元函数\(h(\alpha)\)的精确最小值点， 也可以求一个使得目标函数下降足够多的\(\alpha\)作为步长。 对于多元目标函数\(f(\boldsymbol x)\)， \(\boldsymbol x \in \mathbb R^d\), 有一种优化方法是先沿\(x_1\)坐标轴方向搜索， 再沿\(x_2\)坐标轴方向搜索， 直到沿\(x_d\)坐标轴方向搜索后再重复地从\(x_1\)坐标轴方向开始， 这种方法叫做坐标循环下降法。

一元函数的求根问题和优化问题使用的算法类似， 下面讨论一元函数的优化和求根问题。 在R语言中，uniroot()函数可以用来进行一元函数求根， polyroot()可以求多项式的所有复根， optimize()可以进行一元函数优化。

优化问题与求根问题密切相关， 很多优化问题会归结为一个求根问题。 对一元目标函数\(f(x)\)， 若\(f(x)\)连续可微， 极值点一定是\(f'(x)=0\)的根。 二分法是实际数值计算中一元函数求根使用最多的方法， 这种方法简单而又有比较高的收敛速度。

设函数\(f(x)\)在闭区间\([a,b]\)连续， 且\(f(a) f(b) \leq 0\)， 由中间值定理，至少有一个点\(x^* \in [a,b]\)使得\(f(x^*) = 0\)。 如果\(f(x)\)在\([a,b]\)上还是严格单调函数则解\(x^*\)存在唯一。

二分法求根用区间\([a,b]\)中点\(c\)处函数值\(f(c)\)的正负号来判断根在区间中点的左边还是右边， 显然，如果\(f(c)\)与\(f(a)\)异号，则\([a,c]\)中有根； 如果\(f(c)\)与\(f(b)\)异号，则\([c,b]\)中有根。 根据这样的想法，可以迭代地每次用区间的左半部分或右半部分代替原来的含根区间， 逐步缩小含根的区间。 设求根的绝对误差限规定为\(\epsilon\)。算法如下:

设真实根为\(x^*\)，第\(k\)步的区间中点为\(x^{(k)}\)， 则 \[\begin{align*} |x^{(k)} - x^*| \leq (b-a) \left(\frac12 \right)^k , \end{align*}\] 二分法具有线性收敛速度。

如果\(f(x)\)是\([a, \infty)\)区间上的严格单调的连续函数, 且\(\lim_{x\to\infty} f(x)\)与\(f(a)\)反号， 则\(f(x)\)在\([a, \infty)\)上存在唯一的根， 这时需要先找到闭区间\([a,b]\)使得\(f(a)\)与\(f(b)\)反号， 二分法算法需要略作调整:

其它的情况，比如\(f(x)\)定义在\((-\infty, \infty)\), \((a, b)\)的情况可类似处理， 都需要先找到使得区间端点函数值符号相反的闭区间。

例36.1 设某种建筑钢梁的强度\(X\)服从正态\(\text{N}(\mu, \sigma^2)\)分布， \(\mu, \sigma^2\)未知， 根据设计要求，当\(X>L\)(\(L\)已知)时钢梁的强度才达到要求， 称\(L\)为强度的下规范限， 称强度达到要求的概率\(R = P(X > L)\)为单侧性能可靠度, 在可靠性评估中需要在给了总体\(X\)的一组样本\(X_1, X_2, \dots, X_n\) 以后求可靠度\(R\)的\(1-\alpha\)置信下限(\(0 \alpha\)约束下求\(K\)的下确界， 等价于在固定\(u\)的情况下对关于\(K\)严格单调增的连续函数 \(f(K) \stackrel{\triangle}{=} G(u,K) - \alpha\)求根， 易见根存在唯一， 只要用二分法求根即可。 需要先求得包含根的闭区间。

※※※※※

设目标函数\(f(x)\)有连续二阶导数， 求最小值点可以通过求解\(f'(x)=0\)的根实现。 记\(g(x) = f'(x)\)。 设\(x^*\)是\(f(x)\)的一个最小值点， 则\(g(x^*) = 0\)， 设\(x_0\)是\(x^*\)附近的一个点。 在\(x_0\)附近对\(g(x)\)作一阶泰勒近似得 \[\begin{align*} g(x) \approx g(x_0) + g'(x_0) (x - x_0), \end{align*}\] 令\(g(x)=0\)，得\(x\)近似为 \[\begin{align*} x_1 = x_0 - \frac{g(x_0)}{g'(x_0)}, \end{align*}\] 写成迭代公式，即 \[\begin{align} x_{t+1} = x_t - \frac{g(x_t)}{g'(x_t)}, \ t=0,1,2,\dots \tag{36.1} \end{align}\] 或 \[\begin{align} x_{t+1} = x_t - \frac{f'(x_t)}{f''(x_t)}, \ t=0,1,2,\dots \tag{36.2} \end{align}\]

如果\(g'(x)\)在\(x^*\)的一个邻域\([x^*-\delta, x^*+\delta]\)内都为正， 初值\(x_0 \in [x^*-\delta, x^*+\delta]\), 则牛顿法产生的迭代数列\(\{ x_t \}\)收敛到\(x^*\)。 如果初值接近于最小值点并且目标函数满足一定正则性条件， 牛顿法有二阶收敛速度。 但是，如果迭代过程中遇到\(g'(x)\)接近于零的点， 下一个迭代点可能会被抛到远离根\(x^*\)的地方， 造成不收敛。 另外，牛顿法迭代的停止法则， 可以取为\(|x_{t+1}-x_t| < \epsilon_x\)或\(|g(x_t)| < \epsilon_g\), \(\epsilon_x\)和\(\epsilon_g\)是预定的精度值。 在实际数值计算中， 函数\(g(x)\)和\(g'(x)\)只有一定的计算精度， 所以算法中对\(\epsilon_x\)和\(\epsilon_g\)的选取并不是越小越好， 一般够用就可以了， 取\(\epsilon\)太小有可能导致算法在\(x^*\)附近反复跳跃而不能满足收敛法则。 判断算法收敛， 可以使用绝对变化量也可以使用相对变化量。 实际算法经常使用\(U^{1/4}\)作为相对变化量的界限， 其中\(U\)是双精度值的机器单位。 为了保险起见， 还应该设置一个迭代最大次数， 迭代超过最大次数时宣告算法失败。

牛顿法是方程求根方法, 也可以通过求\(f(x)\)的导数\(g(x)\)的根来求最小值点。 这里给出牛顿法的一个几何解释。 设\(x_t\)是根\(x^*\)附近的一个点， 从曲线\(g(x)\)上的点\((x_t, g(x_t))\)作切线(见图36.1)， 切线方程为 \[\begin{align*} y = g(x_t) + g'(x_t) (x - x_t), \end{align*}\] 用切线在\(x_t\)附近作为曲线\(g(x)\)的近似， 把求\(g(x)=0\)的根近似地变成求切线与\(x\)轴交点的问题，令 \[\begin{align*} 0 = g(x_t) + g'(x_t) (x - x_t), \end{align*}\] 则交点\(x\)的值就是公式(36.1)的下一个迭代值\(x_{t+1}\)。

图36.1: 用牛顿法解一元非线性方程

例36.2 对函数\(f(x)=\frac14 x^4 - \frac18 x\)，求\(\mathop{\text{argmin}}_{x \geq 0} f(x)\)。

令\(g(x) = f'(x) = x^3 - \frac18\)， 显然\(g(x)=0\)在\(x\geq 0\)有唯一的根\(x^*=\frac12\)。 取\(x_0=2\)，用(36.1)进行迭代的过程如图36.1。 迭代的前几个近似值为\(x_1=1.3438\), \(x_2=0.9189\), \(x_3=0.6619\)。 从图中可以看出， 牛顿法当\(g(x)\)斜率大且形状接近直线时收敛最快。

用R的uniroot()求解：

结果：

※※※※※

如果待求根的函数\(g(x)\)的导数\(g'(x)\)没有表达式或很难推导， 也可以用数值微分方法计算\(g'(x)\)。 另一种方法是用函数图像上连接两次迭代的两个点\((x_{t-1}, g(x_{t-1}))\)和\((x_{t}, g(x_{t}))\) 的连线斜率代替公式(36.1)中的\(g'(x_t)\)， 公式变成 \[\begin{align} x_{t+1} = x_t - \frac{x_t - x_{t-1}}{g(x_t) - g(x_{t-1})} g(x_t), \tag{36.3} \end{align}\] 这种方法称为割线法， 适当正则条件下具有超线性收敛速度但比牛顿法差一些。 割线法简单易行， 但是和牛顿法一样，遇到\(g'(x)\)接近于零的点会使得近似点被抛离真值\(x^*\)。 有一些方法结合割线法与二分法的优点， 具有超线性收敛速度而且保证根总在迭代的区间内， 参见 Monahan (2001) §8.3。

一维搜索一般需要先确定包含极小值点的区间, 方程求根时可能也需要确定根所在的区间。

对一元连续函数\(f(x)\)， 若存在\(A < x^* < B\)使得\(f(x)\)在\((A, x^*]\)单调下降， 在\([x^*, B)\)单调上升， 则称\(f(x)\)在\((A, B)\)是单谷的。 这时， 若存在\(A < a < c < b < B\)使得\(f(c) < f(a)\), \(f(c) < f(b)\)， 则\(x^*\)必在\((a, b)\)中。这是因为如果\(x^* \leq a\)， 则\(a, c, b\)三个点在单调上升分支， 必有\(f(a) \leq f(c) \leq f(b)\)， 如果\(x^* \geq b\)则\(a, c, b\)三个点在单调下降分支， 必有\(f(a) \geq f(c) \geq f(b)\)， 都会导致矛盾。

设定义于\((-\infty, \infty)\)或\((0,\infty)\)的连续目标函数\(f(x)\)存在局部极小值点\(x^*\), 且设\(f(x)\)在\(x^*\)的一个邻域内是单谷的, 则只要能找到三个点\(af(x_1)\)， 则最小值点可能在\(x_1\)右侧， 向右侧搜索找到一个函数值超过\(f(x_1)\)的点\(x_2\)， 这时最小值点应该在\((x_0, x_2)\)内部； 如果\(f(x_0) < f(x_1)\)， 则最小值点可能在\(x_0\)左侧， 向左侧搜索(参考图36.2)。

如果函数\(f(x)\)的定义域为\(x \in (0, \infty)\)，以上的算法应取初值\(x_0>0\)， 如果出现向左搜索，可取迭代公式为\(x_{k+1} = \frac{1}{\gamma} x_k\)。

如果目标函数\(f(x)\)连续可导， 则求最小值点所在区间也可以通过求\(a0\)来解决。 可取初值\(x_0\)，如果\(f'(x_0)0\)，则向左搜索找到\(a