最优化大作业.doc

一、最速下降法和共轭梯度法(一) 问题描述分别用最速下降法和共轭梯度法求解以下问题：（2） 问题求解 1、最速下降法（1）基本思想在基本迭代公式中，每次迭代搜索方向取为目标函数的负梯度方向，即，而且每次迭代的步长取为最优步长，由此确定的算法称为最速下降法.（2）算法实现步骤Step1:取初始点，容许误差（精度），令k：=0。Step2:计算Step3:检验，若是，迭代终止，取，否则，转Step4。Step4:求最优步长：（一维搜索）Step5:令，令k：=k+1，转step2。（3）运行结果与分析 取初始点，终止条件为 运行结果： x=4,2,minf(x)=-8 迭代次数:k=432、 共轭梯度法（1）基本思想共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用 已知点处的梯度构造一组共轭方向，并沿这组方向进行搜素，求出目标函数的极小点。根据共轭方向基本性质，这种方法具有二次终止性。（2） 算法实现步骤Step1:给定初始点，及精度；Step2:若，停止，极小值点为，否则转步骤Step3；Step3:取，且置；Step4:用一维搜索法求，使得，令，转步骤Step5；Step5:若，停止，极小值点为，否则转步骤Step6；Step6:若，令，转步骤Step3，否则转步骤Step7；Step7:令，置，转步骤Step4（3）运行结果与分析 取初始点，终止条件为 运行结果： x=4,2,minf(x)=-8 迭代次数:k=2二、外点法和内点法法(一) 问题描述 利用外点法和内点法求解下列优化问题（二）问题求解 1、外点法 （1）基本原理考虑不等式约束优化设计时：对构造一般形式的外点惩罚函数为： （2）算法实现步骤1.给定初始点，初始惩罚因子，维数n迭代精度和递增系数；2.构造外点惩罚函数；3.选用无约束优化方法来求解惩罚函数极小点，即，4.检验是否满足迭代终止条件或若满足转6，若不满足转5；5.令，转2；6.输出最优解，迭代终止。（3）参数设置与运行结果 取初始点，初始惩罚因子， 终止条件为 运行结果： x=1,0,minf(x)=0.6667 迭代次数:k=62、内点法（1）基本原理内点法将新目标函数( x , r ) 构筑在可行域 D 内，随着惩罚因子 r(k) 的不断递减，生成一系列新目标函数 (xk ,r(k)，在可行域内逐步迭代，产生的极值点 xk*(r(k) 序列从可行域内部趋向原目标函数的约束最优点 x* 。构造该增广目标函数为（2）算法实现步骤1选取合适的初始点 x(0) ，以及 r(0)、c、计算精度 1、2令 k=0；构造惩罚（新目标）函数；3调用无约束优化方法，求新目标函数的最优解 xk* 和 (xk , r(k) ) ；4判断是否收敛：运用终止准则若均满足，停止迭代，有约束优化问题的最优点为 x* = xk*；若有一个准则不满足，则令 k=k+1,并转入第 3 步，继续计算。（3）参数设置与运行结果 取初始点 终止条件为运行结果： x=1,0,minf(x)=0.666603三、方法总结与心得 1、最速下降法：最速下降法收敛速度比较慢，迭代次数多，而且对初始点的要求不高。对于问题一，取初始点时，其迭代次数为43，取初始点时，其迭代次数为52，两者均能收敛到极小点4,2。终止条件的设置不同会影响结果的精度，当终止条件为，极小点4.0000,2.0000，但当时，极小点为3.9990,1.9995,迭代次数31，经过多次的初始点以及终止条件的尝试发现，该方法对初始点的要求不高，即使从一个不好的初始点出发，往往也能收敛到局部极小点。当用最速下降法寻找极小点时，在开头几步，目标函数下降较快，但在接近极小点时，收敛速度就不理想了。 2、共轭梯度法：共轭梯度法是介于最速下降和牛顿法之间的算法，克服了最速下降法的收敛速度慢的缺点，又避免了牛顿法的大计算量。在问题一中，不论我如何改动初始值，其迭代次数均为k=2，说明该方法具有二次终止性，再一次验证了课堂上的理论知识。刚开始在代码中不小心少打了一个负号，把初始搜索方向错误设置成，迭代次数变成了46次，这与理论知识不符合，于是在检查中发现了这个错误，所以初始搜索方向必须取最速下降方向，即，如此才证实了该方法具有二次终止性。3、 外点法：在问题二中，经过一系列的初始点设置的尝试，发现外点法的初始点,可以在可行域内也可以在可行域外任意选取，最终都会运行出结果1,0，这个特点很方便于实际运算，并且通过尝试发现，外点法构造的惩罚函数的取值要合理，太小的话收敛会比较慢，太大的话Hesse矩阵的条件数越坏，给无约束问题求解带来很大的问题，很可能无法求解。 4、 内点法：要求初始点应在可行域内，在问题二中，当我设置初始点即时运行界面出现出错提示，当初始点即时，可运行出极小点1,0,。在一维搜