最优化大作业

最优化大作业所在院系：电子工程学院学号：02115088姓名:张赛捷第一题问题描述分别用最速下降法和共轭梯度法求优化问题2212112min()242fxxxxxx一、最速下降法1、算法简介在基本迭代公式kkkkptxx1中，每次迭代搜索方向kp取为目标函数)(xf的负梯度方向，即)(kkxfp，而每次迭代的步长kt取为最优步长，由此确定的算法为最速下降法2、迭代步骤给定控制误差0步骤1：取初始点)0(x，令k=0；步骤2：计算)(kp=)()(kxf；步骤3：若)(kp,取)(*kxx，停止计算；否则，转下一步；步骤4：求0k，使得)(min)()()(0)()(kpxfpxfkkkk，转步骤2；3、实验结果初始点为（1,1），运行结果为)9980.1,9941.3(*x。4、总结最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小值点。但从全局来看，由于锯齿现象的影响，即使向着极小点移近不太大的距离，也要经历不小的“弯路”，因此收敛速度大为减慢。二、共轭梯度法1、算法简介在共轭方向法中初始的共轭向量0P恰好取为初始点0X处的负梯度00(X)gf，而以下各共轭方向kP由第k迭代点kX处的负梯度kg与已经得到的共轭向量1kP的线性组合来确定，那么就构成了一种具体的共轭方向法。因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。2、迭代步骤步骤1：选0,0x；步骤2：若)(0xf，)(0xf停止，输出0x；否则转步骤3；步骤3：构造初始搜索方向，)(00xfp，令k=0，转步骤4；步骤4：进行一维搜索，求kt使得)(min)(0kktkkktpxfptxf，令kkkkptxx1，转步骤5；步骤5：)(1kxf，若)(0xf，停止，输出1kx；否则，转步骤6；步骤6：若k+1=n，令kxx0，转步骤3；否则转步骤7；步骤7：构造共轭方向，取221)()(kkkxfxf，令kkkkpxfp)(11，令k=k+1，转步骤4；3、实验结果选取初始点（0,1），得到最优解*(4.0000,2.0000)Tx。，4、总结共轭梯度法是介于最速下降法和牛顿法之间的一个方法，仅仅储存向量，因而储存量小，克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，适合于维数较高的优化的问题。第二题问题描述利用外点法和内点法求解下列约束优化问题001..)1(121)(min21231xxtsxxxf一、外点法1、算法简介根据约束的特点构造某种惩罚函数，并把惩罚函数添加到目标函数上去，从而得到一个增广目标函数，使约束优化问题的求解转化为一系列无约束极小优化问题的求解。2、迭代步骤步骤1：构建函数)()(),(XaMXfMXFkk.步骤2：输入初始点X.步骤3：用最速下降法求)],(min[kMXF得到较优点kX.步骤4：若)(XaMk，则kX就是所求最优点，打印结果。否则转5.步骤5：1kkMM，k=k+1，转3.3、实验结果选取初始点（0，0），迭代后得到最优解Tx)0,9999.0(*。4、结论外点法是通过一系列惩罚因子{M,k0,1,2,...}k，求(X,M)kF的极小点逼近原约束问题的最优点。随着惩罚因子的增大，迫使惩罚项的值逐渐减小，从而使(X,M)kF的极小点*(M)kX沿着某一运动轨迹逐渐接近等式约束面与起作用的不等式约束面上的最优点*X，当kM趋于无穷大时，(X,M)kF的极小点就是原问题的最优点*X。但是kM越大，增广目标函数(X,M)kF的Hesse矩阵的条件数越坏，给无约束问题求解增加越来越多的困难，甚至无法求解。所以，在迭代开始时不得不把kM取小一些，因而增加了运算量。二、内点法1、算法简介内点法将新目标函数Φ(x,r)构筑在可行域D内，随着惩罚因子r(k)的不断递减，生成一系列新目标函数Φ(xk,r(k))，在可行域内逐步迭代，产生的极值点xk*(r(k))序列从可行域内部趋向原目标函数的约束最优点x*。2、迭代步骤构造增广目标函数11(X,)(X)(X)lkkiiFrfrg终止限0。步骤1：选定初始点0XD，初始障碍因子110r，障碍因子的缩小系数1c；1k。步骤2：假设已获迭代点1kX，以1kX为初始点，求解min(X,)kfr，设其最优解为()kXr。步骤3：若11(X())lkiikrgr，则()kXr是最优解，打印(X(),(X()))kkrfr，结束；否则，转步骤4。步骤4：1kkrcr，1kk，转步骤2。3、实验结果选取初始点（2,2），迭代后得到最优解*(1.0000,0.0067)Tx。4、结论内点法的优点在于每次迭代都是可行点，当迭代到一定次数时，尽管可能没有达到约束最优点，但可以被接受为一个较好的近似最优点。然而，内点法要求初始点位于可行域内部，即所有的约束需按严格不等式满足，对于复杂的优化问题，就要采用求可行点的算法。实验心得通过本次大作业，我对最速下降法，共轭梯度法，内点法和外点法有了更深的了解，也对最优化这门课程有了更深的认识。通过matlab程序的实现，让我对每种方法各自的优势与不足有了新的体会。在完成这两道题的过程中，我锻炼了动手能力，提高了分析问题以及解决问题的能力，这些是通过看书难以得到的收获。