18.2.4 数值搜索程序

使用非线性优化程序, 通过综合几种类型的优化问题的计算成本, 可以找到能接受的近似解. 它们是基于函数值的比较原理.

18.2.4.1 一维搜索

几种优化方法都含有寻找实函数 $f\left(x\right)$ 在 $\left[a,b\right]$ 上的极小值这样的子问题. 通常只需找出极小点 $x^{\ast }$ 的近似 $\overline{x}$ 就够了.

1. 问题的提法

函数 $f\left(x\right),x\in \mathbb{R}$ 称作在区间 $\left[a,b\right]$ 上是单峰的,是指其在每个闭子区间 $J\subseteq$ $\left[a,b\right]$ 上正好有一个局部极小点. 设 $f$ 是 $\left[a,b\right]$ 上的单峰函数,而 $x^{\ast }$ 是其全局极小点. 那么应该找到一个 $\left[c,d\right]\subseteq \left[a,b\right]$ 使得 $x^{\ast }\in \left[c,d\right]$ ,并且 $d-c<\epsilon ,\epsilon >0$ .

2. 一致搜索

选择一正整数 $n$ 使得 $\delta =\frac{b-a}{n+1}<\frac{\epsilon }{2}$ ,并计算函数值 $f\left(x^k\right),x^k=a+k\delta (k=$ $1,\cdots ,n)$ . 如果 $f\left(x\right)$ 是这些函数值中的最小值,则极小点 $x^{\ast }$ 就在区间 $\left[x-\delta ,x+\delta \right]$ 上. 对于给定的精度, 可以估计出所需函数值的数目:

$$\begin{array}{}\text{(18.67)}& n>\frac{2\left(b-a\right)}{\epsilon }-1.\end{array}$$

3. 黄金分割法、斐波那契法

区间 $\left[a,b\right]=\left[a_1,b_1\right]$ 将被逐步缩小使得新的子区间始终包含极小点 $x^{\ast }$ . 按如下方式确定区间 $\left[a_1,b_1\right]$ 中点 ${\lambda }_1,{\mu }_1$ :

$$\begin{array}{}\text{(18.68a)}& {\lambda }_1=a_1+\left(1-\tau \right)\left(b_1-a_1\right),{\mu }_1=a_1+\tau \left(b_1-a_1\right),\end{array}$$

其中

$$\begin{array}{}\text{(18.68b)}& \tau =\frac{1}{2}\left(\sqrt{5}-1\right)\approx 0.618.\end{array}$$

这对应于黄金分割. 接着我们区分两种情形:

a) 如果 $f\left({\lambda }_1\right)<f\left({\mu }_1\right)$ ,则作替换 $a_2=a_1,b_2={\mu }_1$ 和 ${\mu }_2={\lambda }_1$ .(18.69a)

b) 如果 $f\left({\lambda }_1\right)\ge f\left({\mu }_1\right)$ ,则作替换 $a_2={\lambda }_1,b_2=b_1$ 和 ${\lambda }_2={\mu }_1$ .(18.69b)如果 $b_2-a_2\ge \epsilon$ ,则在区间 $\left[a_2,b_2\right]$ 基础上重复此一程序,这里从第 1 步已经知道了一个值,即在情形 $\mathrm{a}$ ) 下是 $f\left({\lambda }_2\right)$ ,而在情形 $\mathrm{b}$ ) 下是 $f\left({\mu }_2\right)$ . 为了确定包含极小点的区间 $\left[a_n,b_n\right]$ ,需要一起计算 $n$ 个函数值. 根据要求

$$\begin{array}{}\text{(18.70)}& \epsilon >b_n-a_n={\tau }^{n-1}\left(b_1-a_1\right),\end{array}$$

就可以估计出必要的步数 $n$ .

使用黄金分割方法, 与斐波那契方法相比, 至多多一个函数值要确定. 在斐波那契法中, 不再是根据黄金分割法细分区间, 而是根据斐波那契数细分区间 (参见第 501 页 5.4.1.5 以及第 1178 页 17.3.2.4, 4.).

18.2.4.2 在 $n$ 维欧几里得向量空间中的极小搜索

问题 $f\left(\underset{―}{x}\right)=min!,\underset{―}{x}\in \mathbb{R}$ 的极小点的近似搜索可以化成求解一列一维优化问题:

**a) $\underset{―}{\mathbf{x}}\ast \ast ={\underset{―}{\mathbf{x}}}^1,k=1$ ,其中 ${\underset{―}{\mathbf{x}}}^1$ 是 ${\underset{―}{\mathbf{x}}}^{\ast }$ 的适当的初始近似.(18.71a)

b) 对于 $r=1,\cdots ,n$ ,求解一维问题:

$$\begin{array}{}\text{(18.71b)}& \phi \left({\alpha }_r\right)=f\left(x_1^{k+1},\cdots ,x_{r-1}^{k+1},x_r^k+{\alpha }_r,x_{r+1}^k,\cdots ,x_n^k\right)=min!,{\alpha }_r\in \mathbb{R}.\end{array}$$

如果 ${\overline{\alpha }}_r$ 是第 $r$ 个一维问题的精确或近似极小点,则作替换 $x_r^{k+1}=x_r^k+{\overline{\alpha }}_r$ .

c) 如果两个相邻的近似彼此非常接近, 即在某种向量范数下有

$$\begin{array}{}\text{(18.71c)}& \Vert \begin{array}{c}{\underset{―}{\mathbf{x}}}^{k+1}-{\underset{―}{\mathbf{x}}}^k\end{array}\Vert <{\epsilon }_1,\text{ 或 }\left|f\left({\underset{―}{\mathbf{x}}}^{k+1}\right)-f\left({\underset{―}{\mathbf{x}}}^k\right)\right|<{\epsilon }_2,\end{array}$$

那么 ${\underset{―}{x}}^{k+1}$ 是 ${\underset{―}{x}}^{\ast }$ 的一近似. 否则的话,由 $k+1$ 代替 $k$ 重复步骤 b). b) 中的一维问题可以利用 18.2.4.1 中给出的方法求解.