总述

处理类似于点、线、多面体这样的几何对象

最近对问题

给定平面上的n个点中，距离最近的两个点

• 点数量n不大3时，可以通过蛮力算法求解的
• 假设集合中每个点均不相同、点按其x坐标升序排列
• 另外使用算法得到点按照y坐标升序排列的列表Q

蛮力算法

算法

1
2
3
4
5
6
7
8
9

BruteForceClosestPoints(p)
	// 蛮力算法求平面中距离最近的点
	// 输入：n个点的列表p；p_i = (x_i, y_i)
	// 输出：两个最近点的距离
	d = \infty
	for i = 1 to n -1 do
		for j = i+1 to n do
			d = min(d, sqrt((x_i - x_j)^2 + (y_i - y_j)^2))
	return d

改进

• 忽略平方根函数，只比较平方

分治法

• 在点集在x轴方向中位数m作垂线，将点集分成大小为 $\lceiling n/2 \rceiling, \lfloor n/2 \rfloor$两个子集 $P_l, P_r$，然后递归求解子问题$P_l, P_r$得到最近点问题解

• 定义$d=min{d_l, d_r}$

  • d不一定是所有点对最小距离
  • 最小距离点对可能分别位于分界线两侧，在合并子问题的 解时需要考虑

• 只需要考虑关于m对称的2d垂直带中的点，记S为来自Q、位于 分隔带中的点列表

  • S同样升序排列
  • 扫描S，遇到距离更近的点对时更新最小距离$d_{min}=d$
  • 对于S中点P，只需考虑在其后、y坐标差小于$d_min$ 的矩形范围内点（因为S有序，P前的点已经考虑过）
  • 该矩形范围内点数目不超过6个（包括P），所以考虑下个点 前，至多考虑5个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

EfficientClosestPair(P, Q)
	// 分治法解决最近点问题
	// 输入：P存储平面上n个点，按x轴坐标升序排列
			Q存储和P相同的n个点，按y坐标升序排列
	/// 输出：最近点直接欧几里得距离
	if n <= 3
		return 蛮力法最小距离
	else
		将P前ceiling(n/2)个点复制到P_l
		将Q相应的ceiling(n/2)点复制到Q_l
		将P余下floor(n/2)个点复制到P_r
		将Q余下floor(n/2)个点复制到Q_r

		d_l = EfficientClosestPair(P_l, Q_l)
		d_r = EfficientClosestPair(P_r, Q_r)
		d = min{d_l, d_r}

		m = P[ceiling(n/2) - 1].x
		将Q中所有|x-m|<d的点复制到数组S[0..num-1]

		dminsq = d^2
		for i=0 to num-2 do
			k = i+1
			while k <= num-1 and (S[k].y - S[i].y)^2 < dminsq
				dminsq = min((S[k].x - S[i].x)^2 + (S[k].y - S[i].y)^2, dminsq)
				k = k+1
	return sqrt(dminsq)

算法特点

• 算法时间效率

  • 将问题划分为规模相同子问题、合并子问题解，算法都只 需要线性时间
  • 运行时间递推式$T(n) = 2T(n/2) + f(n)$，其中 $f(n) \in \Theta(n)$，则$T(n) \in \Theta(nlogn)$
  • 已经证明在对算法可以执行的操作没有特殊假设情况下， 这是可能得到的最好效率

应用

• 聚类分析

凸包问题

寻找能把给定集合中所有点都包含在里面的最小凸多边形

• 设集合S中点按照x坐标升序排列，存储在列表P中 （x坐标相同，按y坐标升序）

蛮力算法

算法

• 对于n个点集中两个点$p_i$、$p_j$，当且仅当集合中其他点 都位于穿过这两点的直线同侧时，其连线是该集合凸包边界 一部分
• 检验每对点，满足条件的点即构成凸包边界

特点

• 算法时间效率为$O(n^3)$

快包算法（分治法）

算法

• $p_1、$p_n$显然是凸包顶点，且$\overrightarrow{p_1p_n}$ 将点集分为左右两部分$S_1$、$S_2$

  • 其上的点不是凸包顶点，之后不必考虑
  • S的凸包也被划分为upper hull、lower hull，可以使用 相同的方法构造

• 若$S1$为空，则上包就是线段$p_1p_n$；否则寻找距离 $p_1p_n$最大点$p{max}$，若有多个，则选择使得夹角 $\angle p_{max}p_1p_n$最大点

  • $p_max$是上包顶点
  • 包含在$\triangle p1p{max}p_2$中的点不是上包顶点， 之后不必考虑
  • 不存在同时位于$\overrightarrow{p1p{max}}$、 $\overrightarrow{p_{max}p_n}$左侧的点

• 对$\overrightarrow{p1p{max}}$及其左侧点构成的集合 $S{1,1}$、$\overrightarrow{p{max}pn}$及其左侧的点构成 集合$S{1,2}$，重复以上即可继续得到上包顶点

• 类似的可以对$S_2$寻找下包顶点

向量左侧、距离计算参考线代

算法特点

快包和快排很类似

• 最差效率$\Theta(n)$，平均效率好得多
• 也一般会把问题平均的分成两个较小子问题，提高效率
• 对于均匀分布在某些凸区域（园、矩形）的点，快包平均效率 可以达到线性

应用

• 计算机动画中使用凸包替换物体本身，加快碰撞检测速度
• 车辆路径规划
• 地理信息系统中根据卫星图像计算accessibility map
• 数理统计中用于进行异常值检测
• 计算点集直径的高效算法中需要用到

欧几里得最小生成树问题

给定平面上n个点，构造顶点为这n个点的总长度最小的树

参考

二维散点

Convex Hull

凸包：包含点集S的最小凸集合

• 离散点集：包含所有点的最小凸多边形
• 最小：凸包一定是所有包含S的凸集合的子集
• 凸包能方便地提供目标形状或给定数据集地一个近似

Extreme Point

极点：对于任何以集合中点为端点的线段，不是线段中点的点

• 极点有一些特性是凸集中其他点不具备的性质

  • 单纯形法：如果存在极值，则一定可以在极点处取到
  • 找到极点、极点排序方向即可解决凸包问题

• 举例

  • 三角形中3个顶点
  • 圆周上所有点

共轭方向

• 设G为$n * n$阶正定对称矩阵，若$d^{(1)}, d^{(2)}$满足

  $$(d^{(1)})^T G d^{(2)} = 0$$

  则称$d^{(1)}, d^{(2)}$关于G共轭

• 类似正交方向，若$d^{(1)},\cdots,d^{(k)}(k \leq n)$关于 G两两共轭，则称其为G的k个共轭方向

• 特别的，$G=I$时，共轭方向就是正交方向

定理1

• 设目标函数为 $$f(w) = \frac 1 2 w^T w + r^T w + \sigma$$ $q^{(1)}, \cdots, q^{(k)}$是$k, k \leq n$个非零正交方向 ，从任意初始点$w^{(1)}$出发，依次沿着以上正交方向做 精确一维搜索，得到$w^{(1)}, \cdots, w^{(k+1)}$， 则$w^{(k+1)}$是$f(w)$在线性流形 $$\bar W_k = \{w = w^{(1)} + \sum_{i=1}^k \alpha_i q^{(i)} | -\infty < \alpha_i < +\infty \}$$ 上的唯一极小点，特别的k=n时，$w^{(n+1)}$是$f(w)$在整个 空间上的唯一极小点

• $\bar W_k$上的存在唯一极小点$\hat w^{(k)}$，在所有方向 都是极小点，所以有

  $$<\triangledown f(\hat w^{(k)}), q^{(i)}> = 0, i=1,2,..$$

• 将$\hat w^{(k)}$由正交方向表示带入梯度，求出系数表达式

• 解精确搜索步长，得到$w^{(k+1)}$系数表达式

扩展子空间定理

• 设目标函数为 $$f(w) = \frac 1 2 x^T G x + r^T x + \sigma$$ $d^{(1)}, \cdots, d^{(k)}$是$k, k \leq n$个非零正交方向 ，从任意初始点$x^{(1)}$出发，依次沿着以上正交方向做 精确一维搜索，得到$x^{(1)}, \cdots, x^{(k+1)}$， 则$x^{(k+1)}$是$f(x)$在线性流形 $$\bar x_k = \{x = x^{(1)} + \sum_{i=1}^k \alpha_i d^{(i)} | -\infty < \alpha_i < +\infty \}$$ 上的唯一极小点，特别的k=n时，$x^{(n+1)}$是$f(x)$在整个 空间上的唯一极小点

• 引进变换$w = \sqrt G x$即可证

• 在以上假设下，有 $$<\triangledown f(x^{(k+1)}), d^{(i)}> = 0, i=1,2...$$

Conjugate Gradient Method

共轭梯度法

对正定二次函数函数

• 任取初始点$x^{(1)}$，若$\triangledown f(x^{(1)}) = 0$， 停止计算，得到极小点$x^{(1)}$，否则取

  $$d^{(1)} = -\triangledown f(x^{(1)})$$

• 沿着$d^{(1)}$方向进行精确一维搜索得到$x^{(2)}$，若 $\triangledown f(x^{(2)}) \neq 0$，令

  $$d^{(2)} = -\triangledown f(x^{(2)}) + \beta_1^{(2)} d^{(1)}$$

  且满足$(d^{(1)})^T G d^{(2)} = 0$，即二者共轭，可得

  $$\beta_1^{(2)} = \frac {(d^{(1)})^T G \triangledown f(x^{(2)})} {((d^{(1)})^T G d^{(1)})}$$
  • 这里$d^{(2)}$方向的构造方式是为类似构造后面$d^{(k)}$ ，得到能方便表示的系数
  • 类似于将向量组$\triangledown f(x^{(i)})$正交化

• 如此重复搜索，若$\triangledown f^(x^{i)}) \neq 0$，构造 $x^{(k)}$处搜索方向$d^{(k)}$如下

  $$\begin{align*} 0 & = (d^{(i)})^T G d^{(k)} \\ & = -(d^{(i)})T G \triangledown f(x^{(k)}) + \sum_{j=1}^{k-1} \beta_j^{(k)} (d^{(i)})^T G d^{(j)} \\ & = -(d^{(i)})^T G \triangledown f(x^{(k)}) + \beta_i^{(k)} (d^{(i)})^T G d^{(i)} \end{align*}$$

  可得

  $$\beta_i^{(k)} = \frac {(d^{(i)})^T G \triangledown f(x^{(k)})} {(d^{(i)})^T G d^{(i)}}$$

  此时$d^{(k)}$与前k-1个方向均关于G共轭，此k个方向是G的k个 共轭方向，由扩展空间子定理，$x^{(k+1)}$是整个空间上极小

计算公式简化

期望简化$d^{(k)}$的计算公式

• 由扩展子空间定理推论有 $\triangledown f(x^{(k)})^T d^{(i)} = 0, i=1,2…,k-1$ 结合以上$d^{(k)}$的构造公式，有

  $$\begin{align*} & \triangledown f(x^{(k)})^T \triangledown f(x^{(i)}) \\ = & \triangledown f(x^{(k)})^T ( -d^{(i)} + \beta_1^{(i)} d^{(1)} + \cdots + \beta_{i-1}^{(i)} d^{(i-1)} ) \\ = & 0, i=1,2,...,k-1 \end{align*}$$

• 则有

  $$\begin{align*} (d^{(i)})^T G \triangledown f(x^{(k)}) & = \triangledown f(x^{(k)})^T G d^{(i)} \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T G (x^{(i+1)} - x^{(i)}) \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T (\triangledown f(x^{(i+1)}) - \triangledown f(x^{(i)})) \\ & = 0, i=1,2,\cdots,k-2 \end{align*}$$

  • $d^{(k)} = \frac 1 {\alpha_i} x^{(i+1)} - x^{(i)}$

• 所以上述$d^{(k)}$构造公式可以简化为

  $$d^{(k)} = -\triangledown f(x^{(k)}) + \beta_{k-1} d^{(k-1)}$$

• 类似以上推导有

  $$\begin{align*} (d^{(k-1)})^T G \triangledown f(x^{(k)}) & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)})) \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T \triangledown f(x^{(k)}) \\ \end{align*}$$ $$\begin{align*} (d^{(k-1)})^T G d^{(k-1)} & = \frac 1 {\alpha_i} (d^{(k-1)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)})) \\ & = -\frac 1 {\alpha_i} (d^{(k-1)})^T \triangledown f(x^{(x-1)}) \\ & = -\frac 1 {\alpha_i} (\triangledown f(x^{(k-1)}) - \beta_{k-2}d^{(k-2)})^T \triangledown f(x^{(x-1)}) \\ & = -\frac 1 {\alpha_i} \triangledown f(x^{(k-1)})^T \triangledown f(x^{(k-1)}) \end{align*}$$

  最终的得到简化后系数$\beta_{k-1}, k>1$的PRP公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))} {\triangledown f(x^{(k-1)})^T \triangledown f(x^{(k-1)})}$$

  或FR公式

  $$\beta_{k-1} = \frac {\|\triangledown f(x^{(k)})\|^2} {\|\triangledown f(x^{(k-1)}) \|^2}$$

• 以上推导虽然是根据正定二次函数得出的推导，但是仍适用于 一般可微函数

• $\beta _ {k-1}$给出两种计算方式，应该是考虑到目标函数 可能不是标准正定二次函数、一维搜索数值计算不精确性

• 将$\beta _ {k-1}$分子、分母推导到不同程度可以得到其他 公式

• Growder-Wolfe公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))} {(d^{(k-1)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))}$$

• Dixon公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T \triangledown f(x^{(k)})} {(d^{(k-1)})^T \triangledown f(x^{(k-1)})}$$

FR/PRP算法

1. 初始点$x^{(1)}$、精度要求$\epsilon$，置k=1

2. 若$|\triangledown f(x^{(k)}) | \leq \epsilon$，停止 计算，得到解$x^{(k)}$，否则置

   $$d^{(k)} = -\triangledown f(x^{(k)}) + \beta_{k-1}d^{(k-1)}$$

   其中$\beta_{k-1}=0, k=1$，或由上述公式计算

3. 一维搜索，求解一维问题

   $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} - \alpha d^{(k)})$$

   得$\alpha_k$，置$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$

4. 置k=k+1，转2

• 实际计算中，n步重新开始的FR算法优于原始FR算法
• PRP算法中 $\triangledown f(x^{(k)}) \approx \triangledown f(x^{(k-1)})$ 时，有$\beta_{k-1} \approx 0$，即 $d^{(k)} \approx -\triangledown f(x^{(k)})$，自动重新开始
• 试验表明，对大型问题，PRP算法优于FR算法

共轭方向下降性

• 设$f(x)$具有连续一阶偏导，假设一维搜索是精确的，使用共轭 梯度法求解无约束问题，若$\triangledown f(x^{(k)}) \neq 0$ 则搜索方向$d^{(k)}$是$x^{(k)}$处的下降方向

• 将$d^{(k)}$导入即可

算法二次终止性

• 若一维搜索是精确的，则共轭梯度法具有二次终止性

• 对正定二次函数，共轭梯度法至多n步终止，否则

  • 目标函数不是正定二次函数
  • 或目标函数没有进入正定二次函数区域，

• 此时共轭没有意义，搜索方向应该重新开始，即令

  $$d^{(k)} = -\triangledown f(x^{(k)})$$

  即算法每n次重新开始一次，称为n步重新开始策略

综述

一维搜索/线搜索：单变量函数最优化，即求一维问题

最优解的$\alpha_k$的数值方法

• exact line search：精确一维搜索，求得最优步长 $\alpha_k$使得目标函数沿着$d^{(k)}$方向达到极小，即

• inexact line search：非精确一维搜索，求得$\alpha_k$ 使得

  $$\begin{align*} f(x^{(k)} + \alpha_k d^{(k)}) & < f(x^{(k)}) \\ \phi(\alpha_k) & < \phi(0) \end{align*}$$

一维搜索基本结构

• 确定搜索区间
• 用某种方法缩小搜索区间
• 得到所需解

搜索区间

• 搜索区间：设$\alpha^{ }$是$\phi(\alpha)$极小点，若存在 闭区间$[a, b]$使得$\alpha^{ } \in [a, b]$，则称 $[a, b]$是$phi(\alpha)$的搜索区间

确定搜索区间的进退法

1. 取初始步长$\alpha$，置初始值

   $$\mu_3 = 0, \phi_3 = \phi(\mu_3), k = 0$$

2. 置

   $$\mu = \mu_3 + \alpha, \phi = \phi(\mu), k = k+1$$

3. 若$\phi < \phi_3$，置

   $$\mu_2 = \mu_3, \phi_2 = \phi_3 \\ \mu_3 = \mu, \phi_3 = \phi \\ \alpha = 2\alpha, k = k+1$$

4. 若k =1，置

   $$\mu_2 = mu, \phi_2 = \phi, \alpha = -\alpha$$

   转2，否则置

   $$\mu_1 = \mu_2, \phi_1 = \phi_2 \\ \mu_2 = \mu_3, \phi_2 = \phi_3 \\ \mu_3 = \mu, \phi_3 = \phi$$

   并令$a=min{\mu_1,\mu_3}, b=max{\mu_1,\mu_3}$，停止搜索

• 通常认为目标函数此算法得到搜索区间就是单峰函数

试探法

• 在搜索区间内选择两个点，计算目标函数值
  • 需要获得两个点取值才能判断极值点的所属区间
• 去掉函数值较大者至离其较近端点段

0.618法

1. 置初始搜索区间$[a, b]$，置精度要求$\epsilon$，计算左右 试探点

   $$\begin{align*} a_l & = a + (1 - \tau)(b - a) \\ a_r & = a + \tau(b - a) \end{align*}$$

   其中$\tau = \frac {\sqrt 5 - 1} 2$，及相应函数值

   $$\begin{align*} \phi_l & = \phi(a_l) \\ \phi_r & = \phi(a_r) \end{align*}$$

2. 若$\phi_l<\phi_r$，置

   $$b= a_r, a_r = a_l, \phi_l = \phi_l$$

   并计算

   $$a_l = a + (1 - \tau)(b - a), \phi_l = \phi(a_l)$$

   否则置

   $$a = a_l, a_l = a_r, \phi_l = \phi_r$$

   并计算

   $$a_r = a + \tau(b - a), \phi_r = \phi(a_r)$$

3. 若$|b - a| \geq \epsilon$

   • 若$\phi_l < \phi_r$，置$\mu = a_l$
   • 否则置$\mu = \alpha_r$ 得到问题解$\mu$，否则转2

• 0.618法除第一次外，每次只需要计算一个新试探点、一个新 函数值，大大提高了算法效率
• 收敛速率线性，收敛比为$\tau = \frac {\sqrt 5 - 1} 2$常数

Fibonacci方法

1. 置初始搜索区间$[a, b]$，置精度要求$\epsilon$，选取分离 间隔$\sigma < \epsilon$，求最小正整数n，使得 $F_n > \frac {b - a} \epsilon$，计算左右试探点

   $\begin{align} al & = a + \frac {F{n-2}} {Fn} (b - a)\ a_r & = a + \frac {F{n-1}} {F_n} (b - a) \end{align}

2. 置n=n-1

3. 若$\phi_l < \phi_r$，置

   $$b = a_r, a_r = a_l , \phi_r = \phi_l$$

   • 若n>2，计算

     $$\begin{align*} a_l & = a + \frac {F_{n-2}} {F_n} (b - a) \\ \phi_r & = \phi(a_l) \end{align*}$$

   • 否则计算

     $$\begin{align*} a_l & = a_r - \sigma \\ \phi_l & = \phi(a_l) \end{align*}$$

4. 若$\phi_l \geq \phi_r$，置

   $$a = a_l, a_l = a_r , \phi_l = \phi_r$$

   • 若n>2，计算

     $$\begin{align*} a_l & = a + \frac {F_{n-1}} {F_n} (b - a) \\ \phi_r & = \phi(a_r) \end{align*}$$

   • 否则计算

     $$\begin{align*} a_r & = a_l + \sigma \\ \phi_r & = \phi(a_r) \end{align*}$$

5. 若n=1

   • 若$\phi_l < \phi_r$，置$\mu = a_r$
   • 否则置$\mu = a_r$

   得到极小点$\mu$，停止计算，否则转2

• Finonacci方法是选取实验点的最佳策略，即在实验点个数相同 情况下，最终的极小区间最小的策略

• Finonacci法最优性质可通过设最终区间长度为1，递推使得原始 估计区间最大的取实验点方式，得出

插值法

• 利用搜索区间上某点的信息构造插值多项式（通常不超过3次） $\hat \phi(\alpha)$
• 逐步用$\hat \phi(\alpha)$的极小点逼近$\phi(\alpha)$ 极小点$\alpha^{*}$

• $\phi^{ * }$解析性质比较好时，插值法较试探法效果好

三点二次插值法

思想

以过三个点$(\mu_1,\phi_1), (\mu_2,\phi_2), (\mu_3,\phi_3)$ 的二次插值函数逼近目标函数

• 求导，得到$\hat \phi(\alpha)$的极小点

  $$\mu = \frac {2[\phi_1(\mu_2-\mu_3) + \phi_2(\mu_3-\mu_1) + \phi_3(\mu_1 - \mu_2)]} {[\phi_1 (\mu_2^2-\mu_3^2) + \phi_2(\mu_3^2-\mu_1^2) + \phi_3(\mu_1^2 - \mu_2^2)]}$$

• 若插值结果不理想，继续构造插值函数求极小点近似值

算法

1. 取初始点$\mu_1<\mu_2<\mu_3$，计算$\phi_i=\phi(\mu_i)$， 且满足$\phi_1 > \phi_2, \phi_3 > \phi_2$，置精度要求 $\epsilon$

2. 计算

   $$A = 2[\phi_1(\mu_2 - \mu_3) + \phi_2(\mu_3 - \mu_1) + \phi_3(\mu_1 - \mu_2)]$$
   • 若A=0，置$\mu = \mu_2, \phi = \phi_2$，停止计算， 输出$\mu, \phi$

3. 计算

   $$\mu = [\phi_1 (\mu_2^2 - \mu_3^2) + \phi_2(\mu_3^2 - \mu_1^2) + \phi_3(\mu_1^2 - \mu_2^2)] / A$$
   • 若$\mu<\mu_1 或 \mu>\mu_3,\mu \notin (\mu_1,\mu_3)$ ，停止计算，输出$\mu, \phi$

4. 计算$\phi = \phi(\mu)$，若$|\mu - \mu_2| < \epsilon$， 停止计算，得到极小点$\mu$

5. 若$\mu \in (\mu_2, \mu_3)$

   • 若$\phi < \phi_2$，置 $$\mu_1=\mu_2, \phi_1=\phi_2, \mu_2=\mu, \phi_2=\phi$$
   • 否则置 $$\mu_3 = \mu, \phi_3 = \phi$$

   否则

   • 若$\phi < \phi_2$，置

     $$\mu_3=\mu_2, \phi_3=\phi_2, \mu_2=\mu, \phi_2=\phi$$

   • 否则置

     $$\mu_1 = \mu, \phi_1 = \phi$$

6. 转2

两点二次插值法

思想

以$\phi(\alpha)$在两点处$\mu_1, \mu_2$函数值 $\phi_1=\phi(\mu_1)$、一点处导数值 $\phi_1^{‘}=\phi^{‘}(\mu_1) < 0$构造二次函数逼近原函数

• 为保证$[\mu_1, \mu_2]$中极小点，须有 $\phi_2 > \phi_1 + \phi_1^{‘}(\mu_2 - \mu_1)$

• 求解，得到$\hat \phi (\mu)$极小值为

  $$\mu = \mu_1 - \frac {\phi_1^{'}(\mu_2 - \mu_1)^2} {2[\phi_2 - \phi_1 - \phi_1^{'}(\mu_2 - \mu_1)]}$$

• 若插值不理想，继续构造插值函数求极小点的近似值

算法

1. 初始点$\mu_1$、初始步长$d$、步长缩减因子$\rho$、精度要求 $\epsilon$，计算

   $$\phi_1 = \phi(\mu_1), \phi_2 = \phi_(\mu_2)$$

2. 若$\phi_1^{‘} < 0$，置$d = |d|$，否则置$d = -|d|$

3. 计算

   $$\mu_2 = \mu_1 + d, \phi_2 = \phi(\mu_2)$$

4. 若$\phi_2 \leq \phi_1 + \phi_1^{‘}(\mu_2 - \mu_1)$，置 $d = 2d$，转3

5. 计算

   $$\mu = \mu_1 - \frac {\phi_1^{'}(\mu_2 - \mu_1)^2} {2[\phi_2 - \phi_1 - \phi_1^{'}(\mu_2 - \mu_1)]} \\ \phi = \phi(\mu), \phi^{'} = \phi^{'}(\mu)$$

6. 若$|phi^{‘}| \leq \epsilon$，停止计算，得到极小点$\mu$， 否则置

   $$\mu_1 = \mu, \phi_1 = \phi, \phi_1^{'} = \phi^{'}, \alpha = \rho \alpha$$

• 其中通常取$d = 1, \rho = 0.1$

两点三次插值法

原理

以两点$\mu_1, \mu_2$处函数值$\phi_i = \phi(\mu_i)$和其导数值 $\phi_i^{‘} = \phi^{‘}(\mu_i)$，由Himiter插值公式可以构造 三次插值多项式$\hat \phi(\alpha)$

• 求导置0，得到$\hat \phi(\alpha)$极小点

  $$\begin{align*} \mu & = \mu_1 + (\mu_2 - \mu_1)(1 - \frac {\phi_2^{'} + w + z} {\phi_2^{'} - \phi_1^{'} + 2w}) \\ z & = \frac {3(\phi_2 - \phi_1)} {\mu_2 - \mu_1} - \phi_1^{'} - \phi_2^{'} \\ w & = sign(\mu_2 - \mu_1) \sqrt {z^2 - \phi_1^{'} \phi_2^{'}} \end{align*}$$

算法

1. 初始值$\mu_1$、初始步长$d$、步长缩减因子$\rho$、精度要求 $\epsilon$，计算

   $$\phi_1 = \phi(\mu_1), \phi_1^{'} = \phi^{'}(\mu_1)$$

2. 若$\phi_1^{‘} > 0$，置$d = -|d|$，否则置$d = |d|$

3. 置$\mu_2 = \mu_1 + \alpha$，计算

   $$\phi_2 = \phi(\mu_2), \phi_2^{'} = \phi^{'}(\mu_2)$$

4. 若$\phi_1^{‘} \phi_2{‘} > 0$，置

   $$d = 2d, \mu_1 = \mu_2, \phi_1 = \phi_2, \phi_1^{'} = \phi_2^{'}$$

   转3

5. 计算

   $$\begin{align*} \mu & = \mu_1 + (\mu_2 - \mu_1)(1 - \frac {\phi_2^{'} + w + z} {\phi_2^{'} - \phi_1^{'} + 2w}) \\ z & = \frac {3(\phi_2 - \phi_1)} {\mu_2 - \mu_1} - \phi_1^{'} - \phi_2^{'} \\ w & = sign(\mu_2 - \mu_1) \sqrt {z^2 - \phi_1^{'} \phi_2^{'}} \\ \phi & = \phi(\mu) \\ \phi^{'} = \phi^{'}(\mu) \end{align*}$$

6. 若$|\phi^{‘}| < \epsilon$，停止计算，得到极小点$\mu$， 否则置

   $$d = \rho d, \mu_1 = \mu, \phi_1 = \phi, \phi_1^{'} = \phi^{'}$$

   转2

• 通常取$d = 1, \rho = 0.1$

非精确一维搜索

• 对无约束问题整体而言，又是不要求得到极小点，只需要一定 下降量，缩短一维搜索时间，使整体效果最好

• 求满足$\phi(\mu) < \phi(0)$、大小合适的$\mu$

  • $\mu$过大容易不稳定
  • $\mu$过小速度慢

GoldStein方法

原理

• 预先指定精度要求$0< \beta_1 < \beta_2 < 1$

• 以以下不等式限定步长

  $$\begin{align*} \phi(\mu) & \leq \phi(0) + \mu\beta_1 \phi^{'}(0) \\ \phi(\mu) & \geq \phi(0) + \mu\beta_2 \phi^{'}(0) \end{align*}$$

算法

1. 初始试探点$\mu$，置$\mu{min} = 0, \mu{max} = \infty$， 置精度要求$0 < \beta_1 < \beta_2 < 1$

2. 对$\phi(mu)$

   • 若$\phi(\mu) > \phi(0) + \beta1 \phi^{‘}(0) \mu$， 置$\mu{max} = \mu$

   • 否则若$\phi(\mu) > \phi(0) + \beta_2 \phi^{‘}(0)\mu$ ，则停止计算，得到非精确最优解$\mu$

   • 否则置$\mu_{min} = \mu$

3. 若$\mu{max} < \infty$，置 $\mu = \frac 1 2 (\mu{min} + \mu{max})$，否则置 $\mu = 2 \mu{min}$

4. 转2

Armijo方法

Armijo方法是Goldstein方法的变形

• 预先取$M > 1, 0 < \beta_1 < 1$

• 选取$\mu$使得其满足以下，而$M\mu$不满足

  $$\phi(\mu) \leq \phi(0) + \mu \beta_1 \phi^{'}(0)$$

• M通常取2至10

Wolfe-Powell方法

• 预先指定参数$0 < \beta_1 < \beta_2 <1$

• 选取$\mu$满足

  $$\begin{align*} \phi(\mu) & \leq \phi(0) + \mu \beta_1 \phi^{'}(0) \\ \phi^{'}(\mu) & \geq \beta_2 \phi^{'}(0) \end{align*}$$

• 能保证可接受解中包含最优解，而Goldstein方法不能保证