共轭方向法是介于最速下降法和牛顿法之间的一种存在——它的收敛速度(二阶收敛)比最速下降法(线性收敛)快,同时它的计算量又比牛顿法要小,因此它的存在是有意义的。
需要注意,共轭方向法可以不使用目标函数的一阶导数信息(当然也可以使用)。所以,如果目标函数的一阶导数不容易求的话,共轭方向法可能就可以派上用场了。
共轭方向法的显著特征就是:两次搜索方向之间是有关联的,这种关联就是“共轭”。
文章来源:http://www.codelast.com/
『1』向量共轭
先解释一下向量共轭的含义,你就明白共轭方向法的两次搜索方向之间的“共轭”是怎么回事了。
设 为对称正定矩阵,若
,则称
和
为“G共轭”,共轭方向是“互不相关”的方向。
『2』特性
当目标函数是二次函数 时,共轭方向法最多经过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_{i + 1}^T{d_j} = 0](https://www.codelast.com/wp-content/plugins/latex/cache/tex_8d872f432d24ebbba8149cc6b8513904.gif)
![vector angle](http://www.codelast.com/wp-content/uploads/ckfinder/images/vector_angle.png)
![g_{i + 1}^T{d_j}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_83ac542f846e9dcc6aea6534e5303b66.gif)
![\theta = \frac{\pi }{2}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_f898dd39bd002624d891bc76fb86aa9f.gif)
![\frac{\pi }{2}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_e26d35e05970ddca7d236176d1db4d6d.gif)
![g_{i + 1}^T{d_j} = 0](https://www.codelast.com/wp-content/plugins/latex/cache/tex_8d872f432d24ebbba8149cc6b8513904.gif)
![g](https://www.codelast.com/wp-content/plugins/latex/cache/tex_b2f5ff47436671b6e533d8dc3614845d.gif)
![{i + 1}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_14b8b90a04464597e4e220394a9e1416.gif)
![d](https://www.codelast.com/wp-content/plugins/latex/cache/tex_8277e0910d750195b448797616e091ad.gif)
![0,1,\cdots ,i](https://www.codelast.com/wp-content/plugins/latex/cache/tex_9b99ea6244b508fa66267b802a9accf5.gif)
![g_3^T{d_0} = 0,\;\;g_3^T{d_1} = 0,\;\;g_3^T{d_2} = 0](https://www.codelast.com/wp-content/plugins/latex/cache/tex_2e6140194834b2ff066e6b6bc5bafd46.gif)
![{g_3}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_d0720487a8b5bdbea3c08f5a9b9d3fef.gif)
![{d_0},{d_1},{d_2}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_808b726a7c1125dc98c805fd9e6951a2.gif)
文章来源:http://www.codelast.com/
现在我把某书中一段和上面的理论等价的描述摘录下来,让大家看看它描述得是不是很晦涩:
共轭方向法在迭代过程中的每一个迭代点 都是目标函数
在
和方向
所张成的线性流形
![conjugate direction basic theory](http://www.codelast.com/wp-content/uploads/ckfinder/images/conjugate_direction_basic_theory.png)
中的极小点。
![{x_2}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_c1015f14836165504ccbb2a42b2c150b.gif)
![i = 1](https://www.codelast.com/wp-content/plugins/latex/cache/tex_5905475576a21ecdafdaab879ff45aff.gif)
![f(x)](https://www.codelast.com/wp-content/plugins/latex/cache/tex_50bbd36e1fd2333108437a2ca378be62.gif)
![{d_0},{d_1}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_f4aba82441fb27b51c794c3f12805550.gif)
![\left\{ {\left. x \right|x = {x_0} + {\alpha _0}{d_0} + {\alpha _1}{d_1}} \right\}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_567c97afc470e145244da0863bc2784a.gif)
![{x_0} + {\alpha _0}{d_0} + {\alpha _1}{d_1} = {x_1} + {\alpha _1}{d_1} = {x_2}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_af41c8e502055b5419bf4c6ea8922fa9.gif)
![{x_1}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_802914d74c5ec475b03d8e01114b4af4.gif)
![{{d_0}}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_8fec6c6a71936f2a9cd2d11877a06b26.gif)
![{x_2}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_c1015f14836165504ccbb2a42b2c150b.gif)
![{{d_1}}](https://www.codelast.com/wp-content/plugins/latex/cache/tex_17fbe469667bc25c9dd11284cd8a5b48.gif)
自己慢慢体会...
文章来源:http://www.codelast.com/
『4』基本流程
下面来看看,共轭方向法在迭代过程中是怎么做的。
假设迭代已经进行到了第 步,那么,下一步怎么走?
-
确定一个搜索方向要满足:
——这是为了满足目标函数值下降的条件(下降是最优化的目标),并且
——这是为了满足搜索方向之间的“共轭”条件。
-
检验迭代终止条件,若未终止,则用line search求
——在每一个搜索方向上,我们都要找到极小值点。
-
,继续迭代
大家注意到,上面说确定一个搜索方向,要满足“共轭”的条件,问题是,共轭方向是如何获取的?光有愿望可不行啊。
文章来源: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,它的转置矩阵是它的逆矩阵: ,其中,
为单位矩阵:
文章来源:https://www.codelast.com/
➤➤ 版权声明 ➤➤
转载需注明出处:codelast.com
感谢关注我的微信公众号(微信扫一扫):
共轭梯度迭代中的N怎么证明比最速下降的少呢?
"所以由基础定理可知,当前迭代点的梯度与前面所有方向的点积为零"还是没有明白,求指点