《工程优化第4章-3重点.》由会员分享，可在线阅读，更多相关《工程优化第4章-3重点.（45页珍藏版）》请在金锄头文库上搜索。
1、最优性条件 最速下降法 牛顿法及其阻尼牛顿法 共轭方向法 共轭梯度法 变尺度法（DFP算法和BFGS算法）,第4章 无约束最优化方法,无约束最优化问题：,设 是对称正定矩阵， 如果 则称向 量p 和q是A共轭的(或称为A正交)。,如果对有限个向量 ，有,共轭方向法-共轭方向及其性质,若 则p与q是正交的。,定义1,定义2,则称这个向量组是A-共轭 (或A正交)向量组，也称它们是一组A共轭方向。,共轭是正交的推广,共轭向量组是正交向量组的推广。,性质2 若Rn中的非零向量p1,p2, pm是A共轭向量组，则这m 个向量是线性无关的。,性质3 在n维空间中互相共轭的非零向量的个数不超过n。,性质4
2、 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设n维非零 向量组p1, p2, pn是A共轭向量组，从任意点x1出发，依 次以p1, p2, pn 为搜索方向进行精确一维搜索，则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交； (2) 最多n次迭代必达到二次函数f(x)的极小点。,性质1 在n维空间中与n个线性无关的向量都正交的一定是零向 量。,共轭方向法-共轭方向的性质,性质4 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设n维非零向量组p1, p2, pn是A共轭向量组，从任意点x1出发，相继以p1, p2, pn 为搜索
3、方向进行精确一 维搜索，则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交； (2) 最多n次迭代必达到二次函数f(x)的极小点。,共轭方向法-共轭方向的性质,定义：一个算法若能在有限步内求得正定二次函数的极 小点，则称该算法具有二次收敛性(又称二次终止性)。,由性质4可知，若能找到一组A共轭向量p1, p2, pn 则前面提到的结合最速下降法和Newton法优点的算法就找到了，就是共轭方向法，,在下降迭代法中，若取下降方向是共轭方向，所得到的方法我们称为共轭方向法。,怎么选取共轭方向？,这个算法具有二次收敛性。,共轭方向的生成与共轭梯度法,共轭方向的选取有很大任意性，而
4、一组不同的共轭方向 就对应着不同的共轭方向法。 作为一种迭代算法，我们自然希望共轭方向能在迭代过 程中逐次生成。,下面先以正定二次函数为例，介绍一种生成共轭方向的方 法，再将这种方法推广到非二次函数上。 这种方法中每一个共轭向量都是依赖于迭代点处的负梯度， 因此称为共轭梯度法，它是共轭方向法中的一种。,令,(2) 若 ，停止， 成的正交锥中找一个向量 ，即令 使得 与 共轭，即,由,共轭梯度法,(1) 从任取初始点x1 出发，沿负梯度方向进行精确一维搜索:,可得,否则在 和 张,(5) 若 ，停止， 成的正交锥中找一个向量 ，即令 使得 与 共轭，即,由,共轭梯度法,(3) 在x2 处沿 p2
5、 方向进行精确一维搜索，,可得,(4) 以此类推，,否则在 和 张,共轭梯度法,这样便构造了一组向量,实际上，这组向量 是一个A共轭向量组。,相邻两个向量是共轭的,共轭梯度法,定理1：设向量组 是由上述方法产生的向量 组，向量组 是由各点的梯度生成的 向量组， ( ) 则 (1) 是正交向量组； (2) 是A共轭向量组。,共轭梯度法,定理1：设向量组 是由上述方法产生的向量组，向量组 是由各点的梯度生成的向量组， ( ) 则 (1) 是正交向量组； (2) 是A共轭向量组。,证明：归纳法：,由 的构造过程知，,是A共轭的，即,结论(2)成立；,利用精确一维搜索的性质知，,而,故,结论(1)成立
6、。,由假设可知，要证明 时结论成立，只需证明,(a) 证明,所以,结论(a)成立，进而结论(1)成立。,与,正交，,与,A共轭。,与,正交;,是A共轭向量组，,利用性质4(1)可知，,性质4 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设n维非零向量组p1, p2, pn是A 共轭向量组，从任意点x1出发，相继以p1, p2, pn 为搜索方向进行精确一维搜索，则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交；,因为,(b) 证明,结论(b)成立，进而结论(2)成立。,与,是A共轭的;,由 的构造过程知，,与,是A共轭的;,下证,与,是A共轭的;,
7、共轭梯度法,定理1：设向量组 是由上述方法产生的向量组， 向量组 是由各点的梯度生成的向量组， ( ) 则 (1) 是正交向量组； (2) 是A共轭向量组。,注：为保证方向的共轭性，初始方向取负梯度方向。,共轭梯度法,性质4 设n元函数f(x)=1/2xTAx+bTx+c, A=AT正定，又设n维非零 向量组p1, p2, pn是A共轭向量组，从任意点x1出发，相 继以p1, p2, pn 为搜索方向进行精确一维搜索，则 (1) f(xk+1)与p1, p2, pk (k=1,2,n)正交； (2) 最多n次迭代必达到正定二次函数f(x)的极小点。,是一个A共轭向量组,每一个搜索方向都依赖迭代
8、点处的负梯度，对应的算法称为共轭梯度法。,共轭梯度法,存在问题：计算量、存储量都很大,针对 f(x)=1/2xTAx+bTx+c, A=AT正定，最多n次迭代达到极 小点找到了一组共轭方向：,针对一般的函数，将这组方向进行推广：,直接对(*)式推广：,在正定二次函数 的前提下，将 变形,怎么解决呢？,能否将 中的A去掉？,定理2：设 ，向量组 是由上述方法构造的A共轭向量组， ，利用前面 所得的公式，得到几个等价的计算公式：,共轭梯度法,利用定理1，可知 是正交向量组，因此(2)中 ; 并且 .,共轭梯度法,对于正定二次函数，上面得到的5个计算公式是等价的； 这5种共轭梯度法也是完全等价的；,
9、SW共轭梯度法,DM共轭梯度法,FR共轭梯度法,PPR共轭梯度法,介绍FR共轭梯度法,Daniel共轭梯度法,简洁，用的最多,更好用,对于非二次函数，产生的搜索方向不再相同， 利用公式(2)-(5), (1)中含有Hesse矩阵，通常不用,步骤1. 选定初始点 。,步骤2. 如果 ，算法停止， ，否则转步骤3。,步骤4. 精确一维搜索找最佳步长 ，令,FR共轭梯度法的计算步骤,步骤3. 取,步骤5. 如果 ，算法停止， 否则,步骤6. 如果k=n, 令 k=1 ，转步骤4; 否则转步骤7。,步骤7. 计算 转步骤4。,转步骤6。,步骤4. 精确一维搜索找最佳步长 ，令,FR共轭梯度法的计算步骤
10、,步骤5. 如果 ，算法停止， ，否则转步骤6。,步骤6. 如果k=n, 令 算法停止,k=1 ，转步骤4; 否则转步骤7。,步骤7. 计算 转步骤4。,误差可能会使n步迭代得不到正定二次函数的极小点。 Rn中共轭方向最多有n个，n步后构造的搜索方向不再是共轭 的， 会降低收敛速度，,步骤6：重新开始技术：xn+1作为新的x1,FR共轭梯度法,，已知初始点(1,1)T,例题 用FR共轭梯度法求下列问题的极值,解： 1）第一次迭代：沿负梯度方向搜寻 计算初始点处的梯度,迭代精度 。,FR共轭梯度法,精确一维搜索求最佳步长，,令,FR共轭梯度法,得,不满足精度，继续迭代：,2）第二次迭代：,FR共
11、轭梯度法,精确一维搜索求最佳步长，,因,得到最优解:,FR共轭梯度法,令,得,共轭梯度法对正定二次函数，具有二次收敛性； 对非二次函数，由于目标函数的Hesse矩阵不再是常数矩 阵，因而产生的方向不再是共轭方向； 共轭梯度法在一定条件下也是收敛的，且收敛速度通常优 于最速下降法，具有较高的求解效率。,FR共轭梯度法,设 f (x)存在连续一阶偏导数，且函数为凸函数，且水平集 有界，则由共轭梯度法得到的点列 有如下 性质： (1) 为严格单调下降序列，且 存在； (2) 的任意聚点 都是 f (x)的最优解。,FR共轭梯度法,共轭梯度法在无约束优化方法中占有重要的地位，是目 前最常用的方法之一。
12、,收敛性定理：,(1) 对凸函数全局收敛（下降算法）； (2) 计算公式简单，不用求Hesse矩阵或者逆矩阵，计算量 小，存储量小，每步迭代只需存储若干向量，适用于大 规模问题； (3) 具有二次收敛性； (对于正定二次函数，至多n次迭代可达最优解）,共轭梯度法的特点,(4) Crowder和Wolfe证明，共轭梯度法的收敛速率不坏 于最速下降法。 如果初始方向不用负梯度方向，则其收敛速率是线 性收敛的； (5) 共轭梯度法是目前求解无约束优化问题最常用的方 法之一。,共轭梯度法的特点,注：不同的k公式，对于正定二次函数是等价的， 对非正定二次函数，有不同的效果，经验上PPR 效果 较好。,作
13、业： P 100 4.9, 4.10, 4.12, 4.13, 4.14, 4.17-4.19,Newton法和阻尼Newton法具有收敛速度快的优点，但 需要计算Hesse矩阵的逆， 计算量大，存储量也很大。,变尺度法-一类特殊的拟Newton法,为减少计算量，用一个n阶对称正定矩阵Hk近似代替Hesse 矩阵的逆 ，即 ，从而搜索方 向是 ，由此搜索方向产生的方法称为变尺度法， Hk称为尺度矩阵，这是一种拟Newton法，被认为是无约束优 化问题中最有效的方法之一。,所谓拟Newton法是指由Newton法的思想出发产生的一类方法。,变尺度法-一类特殊的拟Newton法,变尺度法的计算步骤
14、 步骤1. 任取初始点x1,初始尺度矩阵H1,令k=1. 步骤2. 计算 步骤3. 利用精确一维搜索找最佳步长 ， 步骤4. 令 ，转步骤2。,其中 称为修正矩阵。 不同的修正矩阵，对应着不同的变尺度法。,变尺度法的算法框架,构造 Hk的原则,变尺度法的关键在于如何构造Hk，为了使算法有 较快的收敛速度，需要满足以下几个原则： 拟牛顿性质， 二次收敛性， 稳定性。,变尺度法-一类特殊的拟Newton法,构造 Hk的原则,拟牛顿性质,在 点处对函数 作二阶 Tayloy展开：,变尺度法-一类特殊的拟Newton法,略去高阶项,在xk+1 附近，函数两端求导，得,令 可得,记,变尺度法-一类特殊的拟Newton法,Hesse矩阵 对称正定，又有,变尺度法-一类特殊的拟Newt
