最优化大作业

最优化大作业

所在院系： 电子工程学院 学 号： 02115090 学生姓名: 徐晓雅 任课老师： 马文萍

一．分别用最速下降法和共轭梯度法求解优化问题

minf(x)x12x24x12x1x2

⒈最速下降法 ⑴基本原理

22 在基本迭代公式xk1xktkpk中，每次迭代搜索方向pk取为目标函数f(x)的

负梯度方向，即pkf(xk)，而每次迭代的步长tk取为最优步长，由此确定的算法为最速下降法 ⑵迭代步骤

Step1：x(0)，0，令k=0;

Step2: p(k)=f(x(k));

Step3: p(k),停止，取x*x(k)；否则，转下一步；

Step4：求k0，使得f(x(k)kp(k))minf(x(k)p(k))，转step2；

0⑶运行结果

初始点为（1,1）终止条件为0.000001 运行结果为x*(4,2) f*8迭代次数k为45次 ⑷总结

最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小值点，但它有一个严重缺点就是收敛速度慢。

2.共轭梯度法 ⑴基本原理

如果在共轭方向法中初始的共轭向量p0恰好取为初始点x0处的负梯度而以下共轭方向pk由第k迭代点xk处的负梯度f(xk)与已经得p0f(x0)，

到的共轭向量pk1的线性组合来确定，这就构成了一种具体的共轭方向法，因为每个共轭向量都是依赖于迭代点处的负梯度构造出来的，所以称为共轭梯度法 ⑵迭代步骤

Step1：选x0,0；

Step2：若f(x0)，f(x0)停止，输出x0；否则转step3； Step3：构造初始搜索方向，p0f(x0)，令k=0，转step4；

f(xktpk)，令 Step4：进行一维搜索，求tk使得f(xktkpk)mint0xk1xktkpk，转step5；

Step5：f(xk1)，若f(x0)，停止，输出xk1；否则，转step6； Step6：若k+1=n，令x0xk，转step3；否则转step7； Step7：构造共轭方向，取kk=k+1，转step4； ⑶运行结果 ⑷总结

f(xk1)f(xk)22，令pk1f(xk1)kpk，令

共轭梯度法是介于最速下降法和牛顿法之间的一个方法，仅需利用一阶导数

信息，克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

二．利用外点法和内点法求解下列约束优化问题

13minf(x)(x1)x2112s.t.x110 

x201.外点法 ⑴基本原理

外点法常采用如下形式的函数：gi(x)min0,gi(x)2由此，外点法所构造

的相应的增广目标函数为Tx;Mkf(x)Mkgi(x)式中，惩罚因子Mk是一

i1m个递增的正值数列。

罚函数中gi(x)min0,gi(x)20当gi(x)0g(x)gi(x) i22gi(x)当gi(x)02由此可见，当迭代点x位于可行域内满足约束条件时，惩罚项为零，新目标函数就是原目标函数，等价于求原目标函数f(x)在己满足全部约束条件下的极小；而当点x位于可行域外不满足约束条件时，罚函数Mkgi(x)为正值，惩

i1m罚函数的值较原目标函数的值增大了，这就构成对不满足约束条件时的一种“惩

罚”。则需要加大惩罚因子，随着罚因子的逐次调整增大，最优点点列从可行域的外部一步一步地接近可行域，所得的最优点列逼近原问题的约束最优点x。这样，将原约束最优化问题转换成为序列无约束最优化问题。外点法就是因从可行域的外部逼近最优解而得名。 ⑵迭代步骤

Step1：x0Rn,M0,0,k1；

m Step2：minT(x;M)minf(x)Mgi(x)T(x*;M)；

i1 Step3：若存在j(1jn)使gj(xk)，则令M=10M,k=k+1,转step3；否则，停止，x*xk. ⑶运行结果

初始点为（0,0）终止条件为0.00001 2 运行结果为x*(1,0) f*0.667

3

⑷总结

外点法的优点是等式约束和非凸规划均适用，x0任取，不要求x0R,计算

简单；缺点是在R外f(x)性质复杂或者没有意义，方法失效。

2.内点法

⑴基本原理

首先在D的边界设置一道障碍，当从可行域D中的某点x0出发进行迭代时，每当迭代点靠近D的边界时，便被此边界上的障碍阻挡碰回，即当迭代点靠近D的边界时，离边界越近函数值增加越大，特别当迭代点到达边界时，函数值变为无穷大，由此可知不可能在靠近D的边界上取得最优解，只能在远离D的边界内找到最优解，这种方法即为内点法。 ⑵迭代步骤

Step1：取误差0；

Step2：求一内点x0R0，令k=1；

k0kx;I(x;),xR Step3：以xk1R0为初始点，求min； kk0xR Step4：若满足判别准则，停，得xk，否则取k1k（比如c=10),令k=k+1，

c转step3； ⑶运行结果 ⑷总结

内点法只适用于解不等式约束优化问题。由于内点法需要在可行域内部进行搜索，所以初始点必须在可行域内部选取可行点。内点法的突出优点在于每个迭代点都是可行点。因此，当迭代达到一定阶段时，尽管尚没有达到最优点，但也可以被接受为一个较好的近似解。

三．学习体会

通过本次课程大作业，我对最速下降法，共轭梯度法，内点法和外点法有了更深的了解，也对最优化这门课程有了更进一步的认识。通过运用matlab编程，不仅完成了此次的作业，更锻炼了动手能力，分析问题以及解决问题的能力。发现我们在很多时候，都没有好好地把知识学扎实，特别是细节知识方面更是模棱两可，当实际编程时就会出现各种各样的问题，所以书本的内容一定要仔细弄懂。