无约束最优化(二) 共轭方向法与共轭梯度法
之前文章 最速下降法、Newton法、修正Newton法 介绍的最速下降法存在锯齿现象，Newton法需要计算目标函数的二阶导数。接下来介绍的 共轭方向法 是介于最速下降法和Newton法之间的一种方法，它克服了最速下降法的锯齿现象，从而提高了收敛速度；它的迭代公式也比较简单，不必计算目标函数的二阶导数，与Newton法相比，减少了计算量和存储量。它是比较实用而有效的最优化方法。
我们先将其在正定二次函数 上研究，然后再把算法用到更一般的目标函数上。首先考虑二维的情形。
任选初始点 ，沿它的某个下降方向，例如向量 的方向，作直线搜索，如上图所示。由下面这个定理：
定理 ：设目标函数 具有一阶连续偏导数，若 ,则 。
知 。如果按照最速下降法选择的就是负梯度方向为搜索方向(也就是 方向)，那么将要发生锯齿现象。于是一个设想是，干脆选择下一个迭代的搜索方向 就从 直指极小点 ，也就是找到上图所示的 方向。
因为 从 直指极小点 ,所以 可以表示为：
其中 是最优步长因子。显然，当 时， 。到这里，我们还有一个已知条件没用，就是目标函数为二次正定，所以我们对目标函数求导，得到：
因为 是极小点，所以有:
将 带入上述方程式，有：
上式两边同时左乘 ，并注意到 和 ，得到 。这就是为使 直指极小点 ， 所必须满足的条件。并且我们将两个向量 和 称为 共轭向量 或称 和 是 共轭方向 。
由上面共轭梯度法那张图可以设：
上式两边同时左乘 ,得：
由此解出：
代回 得：
从而求到了 的方向。
归纳一下，对于正定二元二次函数，从任意初始点 出发，沿任意下降方向 做直线搜索得到 再从 出发，沿 的共轭方向 作直线搜索，所得到的 必是极小点 。到目前为止的共轭梯度法依旧是假设了目标函数是二次正定矩阵。
上面的结果可以推广到 维空间中，即在 维空间中，可以找出 个互相共轭的方向，对于 元正定二次函数从任意初始点出发，顺次沿着这 个共轭方向最多作 次直线搜索，就可以求到目标函数的极小点。
对于 元正定二次目标函数，如果从任意初始点出发经过 有限次迭代 就能够求到极小点，那么称这种算法具有 二次终止性 。例如，Newton法对于二次函数只须经过一次迭代就可以求到极小点，因此是二次终止的；而最速下降法就不具有二次终止性。共轭方向法（如共轭梯度法、拟Newton法等）也是二次终止的。
一般说来，具有二次终止性的算法，在用于一般函数时，收敛速度是较快的。
定义：设 是 对称正定矩阵。若 维向量空间中的非零向量 满足 ， 则称 是 共轭向量或称向量 是 共轭的（简称共轭）。
当 (单位矩阵)时 变为 ， 。即向量 互相正交 。由此看到，“正交”是“共轭”的一种特殊情形，或说，“共轭”是“正交”的推广。
下面介绍几个定理：
定理 ：若非零向量 是 共轭的，则线性无关。
推论 ：在 维向量空间中， 非零的共轭向量的个数不超过 。
定义 设 是 中的线性无关向量， 。那么形式为：
的向量构成的集合，记为 。称为由点 和向量 所生成的 线性流形 。
共轭方向法的理论基础是下面的定理。
定理 假设
(1) Q为 对称正定矩阵;
(2) 非零向量 是 共轭向量;
(3) 对二次目标函数 顺次进行 次直线搜索:
其中 是任意选定的初始点，则有：
i) ， ;
ii) 是二次函数 在线性流形 上的极小点。
这个定理看来较繁，但可借用直观的几何图形来帮助理解。 ， 的情形为例，如图示。
和 是Q共轭向量，张成了二维空间 ，这是过坐标原点的一个平面。 现在，过点 沿 方向作直线搜索得到 ，再过点 沿 方向作直线搜索得到 过点 由向量 和 张成的平面就是线性流形 。它是 的平行平面。
定理的论断是，最后一个迭代点 处的梯度 必与 和 垂直。并且 是三元二次目标函数 在线性流形 (即过 由 和 张成的平面)上的极小点。
共轭方向法算法的大体流程 就是：选定初始点 和下降方向向量 ，做直线搜索 。提供的梯度方向 使得 ， 。提供共轭方向的方法有多种。不同的提供方法将对应不同的共轭方法。每种方法也因产生共轭方向的特点而得名。
那么这里做直线搜索 中的 是如何确定的呢？这里我们先回顾一下在最速下降法中是如何计算这个 的。最速下降法：
依据定理 设目标函数 具有一阶连续偏导数，若 ,则 。，我们可以得到 。由此有：
由此，可求解出 :
这里还可以采用另外一种种方式计算 ，下面对另外一种方式进行公式推导：
由 ，用 左乘上式两边，然后再同时加上 ，利用 能够得到：
左乘 有
由此解出：
在最速下降法中 ，在共轭方向法中 。
在共轭方向法中，如果初始共轭向量 恰好取为初始点 处的负梯度 ，而其余共轭向量 由第 个迭代点 处的负梯度 与已经得到的共轭向量 的线性组合来确定，那么这个共轭方向法就称为 共轭梯度法 。
针对目标函数是正定二次函数来讨论：
(1) 第一个迭代点的获得 ：
选定初始点 ，设 (否则迭代终止)，因此 。取 ，（以下用 表示 ）从 出发沿 方向做直线搜索，得到第1个迭代点 ，其中 可由下式确定：
显然
(2) 第二个迭代点的获得 ：
设 ，因此 。由 知 与 线性无关。取 其中 是使 与 共轭的待定系数，令：
由此解出
并代回确定 ，并获得第2个迭代点。
由公式 可以求得 ，带入公式 可进一步优化得到：
(3) 第三个迭代点的获得 ：
设 ，因此 。由 知 与 线性无关。取 其中 是使 与 共轭的待定系数，令：
由此解出
并代回确定 ，并获得第3个迭代点。
其中
上述过程仅表明 与 ， 与 共轭，现在问， 与 也共轭吗？
(4) 第 个迭代点的获得 ：
由 知 与 线性无关。取 其中 是使 与 共轭的待定系数，令：
由此解出
并代回确定 ，并获得第k+1个迭代点。
其中
以上就是共轭梯度法得核心内容。
为使共轭梯度算法也适用于非二次函数，需要消去算法中的 对于正定二次函数，有 代入到 中，得：
此式中已不再出现矩阵 ，将 两端转置运算，并同时右乘 得：
将共轭方向法中的定理带入得到 ，由直线搜索的性质有 ，带入上式有 。此外：
带入 ，得到：
此式称为Fletcher－Reeves公式(1964年)。
相关参考：
原始牛顿法和阻尼牛顿法的区别
牛顿法二次收敛的特性，而对初始点的选取并没有苛刻的要求。这类方法的主要缺点计算复杂，工作量大，要求计算机存储量大。共轭方向 共轭方向主要是针对二次函数的，但也可以用于一般非二次函数。共轭方向法是二次 收敛的；
优化方法的理论体系
(二)多维无约束优化方法。主要有:1)负梯度方向法及基于盲人探路思想的折线负梯度方向法。2)多维二阶近似式方向法及其近似算法。3)坐标系拟均匀变换法,也称为坐标变换法,包括局部坐标系的建立。4)获得共轭方向的方法,主要有定义法、...
数学建模——常考优化类模型总结
接下来，我们转向非线性规划的领域，这里不仅有非线性函数的挑战，还有下山单纯形法（无导数需求）和改进BFGS（依赖一阶导数）等方法的精彩表演。这些算法如同登山者，能在复杂地形中寻找到最优路径。其他算法，如共轭方向法、...
优化方法的理论体系 有哪些方面
(二)多维无约束优化方法。主要有:1)负梯度方向法及基于盲人探路思想的折线负梯度方向法。2)多维二阶近似式方向法及其近似算法。3)坐标系拟均匀变换法,也称为坐标变换法,包括局部坐标系的建立。4)获得共轭方向的方法,主要有定义法、...
优化方法的理论体系
2.(二)多维无约束优化方法。主要有:1)负梯度方向法及基于盲人探路思想的折线负梯度方向法。2)多维二阶近似式方向法及其近似算法。3)坐标系拟均匀变换法,也称为坐标变换法,包括局部坐标系的建立。4)获得共轭方向的方法,主要有定义法...
《最优化方法》复习题
5、叙述常用优化算法的迭代公式．（1）0.618法的迭代公式：（2）Fibonacci法的迭代公式：．（3）Newton一维搜索法的迭代公式：．（4）推导最速下降法用于问题的迭代公式：（5）Newton法的迭代公式：．（6）共轭方向法用于...
cos(z的共轭)是否等于cos(z)的共轭
cos（z的共轭）等于cos(z)的共轭。由cos(z)=(e^z+e^-z)\/2 将z写成a+bi的实部加虚部的形式 两向量间的一种特殊关系。设A为n×n对称正定矩阵，向量p，p∈R。若满足条件(p)Ap=0，则称p和p关于A是共轭方向，...
高等数学中有哪些最优化算法?
牛顿法（Newton's Method）：牛顿法是一种基于二阶导数的最优化算法。它利用目标函数的一阶和二阶导数信息，通过迭代逼近最优解。牛顿法收敛速度快，但计算复杂度较高。共轭梯度法（Conjugate Gradient Method）：共轭梯度法...
什么是共轭向量
共轭向量就是两个向量大小相同，方向相反。在平面直角坐标系中，分别取与x轴、y轴方向相同的两个单位向量i，j作为一组基底。a为平面直角坐标系内的任意向量，以坐标原点O为起点P为终点作向量a。由平面向量基本定理可知，有...
讨论鲍威尔式2的几何意义
鲍威尔法，严格来说是鲍威尔共轭方向法，是迈克尔JD鲍威尔提出的一种求解函数局部最小值的算法。该函数不能是可微分的，并且不会导出衍生函数。该函数必须是固定数量的实值输入的实值函数。通过传入一组初始搜索向量，通常会...
相关评论
13180966602： 一.无约束最优化方法1.梯度法(最速下降法)2.牛顿法(基本牛顿法、阻尼牛顿法)3.变尺度法(拟牛顿法)4.共轭梯度法5.鲍威尔法(基本鲍威尔法、修正鲍威尔法) 二.约束最优化方法1.可行方向法2.惩罚函数法(外点法、内点法、混合法)3.乘子法(等式约束问题乘子法、不等式约束问题乘子法)4.序列二次规划法5.多目标最优化法(主要目标法、线性加权法、理想点法、目标逼近法、最大最小法) 三.智能最优化方法1.遗传算法2.神经网络算法(人工神经元与神经网络模型、BP网络、径向基RBF网络、Hopfield网络)
13180966602： 1 无约束非线性最优化问题常用算法:梯度法(最速下降法)、共轭梯度法、变尺度法和步长加速法.其中,前三个要用到函数的一阶导数或二阶导数,适用于函数表达式导数存在且求导简单的情况,而步长加速法则相反,适用于函数表达示复杂,甚至无解析表达式,或导数不存在情况.2 约束非线性最优化问题常用算法:按照是否化成无约束问题可分为 可行方向法、制约函数法(外点法和内点法),其中内点法适用于目标函数在可行域外性质复杂情况,外点法则相反.后者根据罚函数或障碍函数的构造不同,又有不同的变形.
13180966602： 原发布者:蔡珍 共轭方向法和共轭梯度法问题1:如何建立有效的算法?从二次模型到一般模型.问题2:什么样的算法有效呢?二次终止性.简介共轭方向法和共轭梯度法共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导...
13180966602： 鲍威尔法一种有效的共轭梯度方向法,可以在有限步内找到二次函数的极小点的简便方法.鲍威尔法是鲍威尔于1964年提出的,以后又经过他本人的改进.对于非二次函数只要具有连续的二阶导数,用这种方法也是有效的. 鲍威尔算法:在每一轮迭代中总是有一个始点(第一轮的始点是任选的初始点)和n个线形独立的搜索方向.从初始点出发顺次沿n个方向作一维搜索得到终点.由始点和终点决定了一个新的搜索方向.判断原向量是否需要用新的搜索方向替换.如需替换,还要进一步判断原向量组中那个向量最坏,然后再用新产生的向量替换这个最坏的向量,以保证逐次生成共轭方向.
