规划数学 无约束问题求解

规划数学无约束问题求解第一页，共三十三页，编辑于2023年，星期五共轭梯度法（1学时）步长加速法（1学时）第8讲无约束极值问题算法（2）重点：共轭梯度法、模式搜索法。难点：共轭方向的构造。基本要求：理解共轭方向的定义及性质，掌握共轭梯度法的搜索方向的构造过程，计算步骤，了解共轭梯度法的优缺点；了解模式搜索法的基本思想和计算步骤。第二页，共三十三页，编辑于2023年，星期五首先考虑二次函数的无约束极小问题共轭梯度法令将(1)化为显然，（3）式经n次一维搜索可得最优解为对角阵第三页，共三十三页，编辑于2023年，星期五1定义：设为n阶正定阵，若n维方向满足（一）共轭方向则称是共轭的。2性质：设为n阶正定阵，若是共轭的，则必线性无关第四页，共三十三页，编辑于2023年，星期五1共轭梯度法思想：

将共轭性与最速下降方法结合，利用已知点处的梯度构造一组共轭方向，并沿此组方向进行搜索，求出极小点。适用范围：凸函数（二）共轭梯度法2FR共轭梯度法考虑问题：其中：为对称正定阵第五页，共三十三页，编辑于2023年，星期五

（1）算法步骤：步骤1任选初始点令步骤2若，则停止；否则转下一步令其中：步骤5置k=k+1返回步骤2步骤3步骤4第六页，共三十三页，编辑于2023年，星期五定理设向量为共轭，则从点出发，相继以为搜索方向的下述算法：经n次一维搜索收敛于问题（I）的极小点

FR共轭梯度法的理论推导*问题(I)第七页，共三十三页，编辑于2023年，星期五证明：由式(1)得

则有由于一维搜索时为最佳步长，故第八页，共三十三页，编辑于2023年，星期五即：第九页，共三十三页，编辑于2023年，星期五2FR公式推导第十页，共三十三页，编辑于2023年，星期五证明(1)式：由于一维搜索时为最佳步长，故第十一页，共三十三页，编辑于2023年，星期五证明(2)式：(i)第十二页，共三十三页，编辑于2023年，星期五第十三页，共三十三页，编辑于2023年，星期五(ii)设k=m-1时(2)式成立，(iii)k=m第十四页，共三十三页，编辑于2023年，星期五T第十五页，共三十三页，编辑于2023年，星期五用FR共轭梯度法求解

（2）算法举例解：第一次迭代第二次迭代共轭搜索方向：第十六页，共三十三页，编辑于2023年，星期五例2用共轭梯度法求解下列问题：第一次迭代第十七页，共三十三页，编辑于2023年，星期五第二次迭代第十八页，共三十三页，编辑于2023年，星期五非二次型的共轭梯度法设为某一严格凸函数，具有二阶连续偏导用二阶泰勒展开近似表示迭代公式：第十九页，共三十三页，编辑于2023年，星期五（三）共轭梯度法的优缺点优点（1）程序简单，占内存少；（2）收敛速度较快，介于梯度法和牛顿法之间。缺点（1）当较小时计算可能带来较大的舍入误差，甚至引起不稳定；（2）不进行“n步重新开始”一直作下去，收敛很慢，甚至不收敛。适用场合各种问题，对于高维问题效果尤佳。第二十页，共三十三页，编辑于2023年，星期五模式搜索法（步长加速法）探测移动：依次沿n个坐标轴进行，用于确定新的基点和有利于函数值下降的方向。模式移动：沿相邻两个基点连线方向进行，试图使函数值更快减少。（一）模式搜索法的思路第二十一页，共三十三页，编辑于2023年，星期五第二十二页，共三十三页，编辑于2023年，星期五探测性搜索：第二十三页，共三十三页，编辑于2023年，星期五第二十四页，共三十三页，编辑于2023年，星期五模式搜索第二十五页，共三十三页，编辑于2023年，星期五（二）模式搜索法的迭代步骤第二十六页，共三十三页，编辑于2023年，星期五第二十七页，共三十三页，编辑于2023年，星期五例3用步长加速法求解下列问题：第二十八页，共三十三页，编辑于2023年，星期五第二十九页，共三十三页，编辑于2023年，星期五第三十页，共三十三页，编辑于2023年，星期五第三十一页，共三十三页，编辑于2023年，星期五第三十二页，共三十三页，编辑于2023年，星期五优点(1)编制程序比较简单(2)对函数的要求宽松,不需函数