转载请注明出处:http://www.codelast.com/

共轭方向法是介于最速下降法牛顿法之间的一种存在——它的收敛速度(二阶收敛)比最速下降法(线性收敛)快,同时它的计算量又比牛顿法要小,因此它的存在是有意义的。

需要注意,共轭方向法可以不使用目标函数的一阶导数信息(当然也可以使用)。所以,如果目标函数的一阶导数不容易求的话,共轭方向法可能就可以派上用场了。
共轭方向法的显著特征就是:两次搜索方向之间是有关联的,这种关联就是“共轭”。
文章来源:http://www.codelast.com/
『1』向量共轭
先解释一下向量共轭的含义,你就明白共轭方向法的两次搜索方向之间的“共轭”是怎么回事了。
G 为对称正定矩阵,若 d_m^TG{d_n} = 0,\;\;m \ne n ,则称 {d_m}{d_n} 为“G共轭”,共轭方向是“互不相关”的方向。

『2』特性
当目标函数是二次函数 f(x) = \frac{1}{2}{x^T}Gx + {b^T}x + c 时,共轭方向法最多经过N步(N为向量维数)迭代,就可以到达极小值点——这种特性叫作二次收敛性Quadratic Convergence)。
假设沿着一系列的共轭方向做迭代(寻找极小值点),这些共轭方向组成的集合叫作共轭方向集,则沿共轭方向集的每个方向顺序做line search的时候,在每个方向上都不需要做重复搜索——在任何一个方向上的移动,都不会影响到在另一个方向上已经找到的极小值。
上面这段描述是什么意思呢?我们先不讨论这些共轭方向是怎么计算出来的,拿一个在水平面上走路的例子来做比喻:你在水平方向A上走了10米,然后再沿着与水平方向垂直的另一个方向B上又走了10米,那么,你在方向A上走动的时候,在方向B上的坐标是不变的;你在方向B上走动的时候,在方向A上的坐标也是不变的。因此,把方向A和方向B看作两个共轭方向,那么,你在这两个共轭方向中的任何一个方向上移动,都不会影响到另一个方向上已经走到的坐标(把它想像成在这个方向上的极小值)。
文章来源:http://www.codelast.com/
但是世界哪有那么美好?目标函数不是二次函数的时候多得去了!这个时候,共轭方向法不就废了吗?非也非也。
理论与实践证明,将二次收敛算法用于非二次的目标函数,也有很好的效果。但是,这个时候,就不能保证N步迭代到达极小值点了。大家需要记住的是,很多函数都可以用二次函数很好地近似,这种近似在工程上是很重要。
有人一定会问,哪些函数可以用二次函数很好地近似呢?请原谅我没在书中看到这个总结,你只能自己去挖掘了。

『3』理论基础
共轭方向法有一个重要的理论基础,它是一个神奇的定理,有了它,可以推导出很多结论(共轭梯度法的理论推导就信赖于此)。
这里只把结论写上来,证明较长,不是本文关注的所以就不写了:
在精确line search的情况下,当前迭代点的梯度 g 与前面所有的搜索方向 d 直交:
g_{i + 1}^T{d_j} = 0,\;\;j = 0,1, \cdots ,i

这个结论在很多专业书中,都用了晦涩的描述来显示出教科书般的“高端、大气、上档次”,我看完之后只有一个感觉:看你们这些牛人写的书压力好大啊!
上面的红字,是我认为可以精简成“人话”之后的描述,也许它不严谨,也许它有漏洞,但是它大概说的就是这么回事,简单不就是美吗?
下面稍微解释一下定理中的一些概念:

为什么 g_{i + 1}^T{d_j} = 0 表明两个向量“直交”?从两个向量的夹角的数学定义:
vector angle
我们可知, g_{i + 1}^T{d_j} 为0时,整个式子为零,从而 \theta = \frac{\pi }{2} ,也就是说两个向量的夹角是 \frac{\pi }{2} ,所以它们当然是“直交”的。
g_{i + 1}^T{d_j} = 0 这个式子中,当 g 的下标是 {i + 1} 时, d 的下标可以是 0,1,\cdots ,i ,例如, g_3^T{d_0} = 0,\;\;g_3^T{d_1} = 0,\;\;g_3^T{d_2} = 0 ,这表明,当前迭代点的梯度 {g_3} 与前面所有的搜索方向( {d_0},{d_1},{d_2} )直交。

文章来源:http://www.codelast.com/
现在我把某书中一段和上面的理论等价的描述摘录下来,让大家看看它描述得是不是很晦涩:
共轭方向法在迭代过程中的每一个迭代点 {x_{i + 1}} 都是目标函数 f(x){x_0} 和方向 {d_0},{d_1}, \cdots ,{d_i} 所张成的线性流形

conjugate direction basic theory

中的极小点。

其实这个晦涩的描述,是line search基础定理——梯度与方向的点积为零——的另一种表述。例如,我们拿一个特例来说:
迭代点 {x_2} (此时 i = 1 )是目标函数 f(x) 和方向 {d_0},{d_1} 所张成的线性流形 \left\{ {\left. x \right|x = {x_0} + {\alpha _0}{d_0} + {\alpha _1}{d_1}} \right\} 的极小值点。
{x_0} + {\alpha _0}{d_0} + {\alpha _1}{d_1} = {x_1} + {\alpha _1}{d_1} = {x_2} ,所以这就说明了 {x_1} 是在 {{d_0}} 方向上line search得到的极小值点, {x_2} 是在 {{d_1}} 方向上line search得到的极小值点。所以由基础定理可知,当前迭代点的梯度与前面所有方向的点积为零。

自己慢慢体会...
文章来源:http://www.codelast.com/
『4』基本流程
下面来看看,共轭方向法在迭代过程中是怎么做的。
假设迭代已经进行到了第 k 步,那么,下一步怎么走?

  • 确定一个搜索方向要满足: {g_{k + 1}}^T{d_{k + 1}} < 0 ——这是为了满足目标函数值下降的条件(下降是最优化的目标),并且 d_{k + 1}^TG{d_i} = 0,\;\;i = 1,2, \cdots ,k ——这是为了满足搜索方向之间的“共轭”条件。
  • 检验迭代终止条件,若未终止,则用line search求 f({x_k} + {\alpha _k}{d_k}) = \mathop {\min }\limits_{\alpha \ge 0} f({x_k} + \alpha {d_k}) ——在每一个搜索方向上,我们都要找到极小值点。
  • {x_{k + 1}} = {x_k} + {\alpha _k}{d_k} ,继续迭代

大家注意到,上面说确定一个搜索方向,要满足“共轭”的条件,问题是,共轭方向是如何获取的?光有愿望可不行啊。
文章来源:http://www.codelast.com/
『5』创造共轭方向
这里的关键是,如何构造出一个方向的集合,其N个方向线性无关、两两共轭?
有一个经典的方案就是Powell共轭方向集方法
Powell是谁?

M.J.D. POWELL,剑桥大学退休教授,世界著名的最优化专家。他是袁亚湘的导师(袁亚湘,中国科学院数学与系统科学研究院研究员、博士生导师,美国数学学会首届会士(2012年),中国科学院院士)。

Powell方法是一种不需要求目标函数导数的方法(zero-order method)。有一篇英文文章里说,如果你只需要知道一种zero-order method如何编程实现的话,那么一定是选Powell方法,可见Powell方法是有其重要地位的。
关于Powell方法,可以参考一下这篇文章,本文不详述。
文章来源:http://www.codelast.com/
『6』Powell方法的问题及改进
Powell方法产生的共轭方向集可能会变得线性相关,这会导致最终我们求得的,是N维空间的一个子空间内的极小值,而不是整体的极小值,所以,人们对Powell方法研究出了一些改进方案,例如:

  • N轮迭代后,方向集重置为基向量;
  • Brent(就是Brent's method的作者)提出,N轮迭代后,可以将方向集重置为任意正交矩阵(见下面的说明)的列向量;
  • 放弃目标函数下降最大的方向,用一些好的方向代替N个必须共轭的方向;
  • ...

PS:什么是正交矩阵
一个实数正交矩阵是方块矩阵Q,它的转置矩阵是它的逆矩阵: {Q^T}Q = Q{Q^T} = E ,其中, E 为单位矩阵:
unit matrix

[原创] 再谈 共轭方向法/Conjugate Direction Method In Optimization

One thought on “[原创] 再谈 共轭方向法/Conjugate Direction Method In Optimization

  • 2014 年 07 月 20 日 at 08:09
    Permalink

    "所以由基础定理可知,当前迭代点的梯度与前面所有方向的点积为零"还是没有明白,求指点

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注