数 学 规 划 课 程 设 计
题目：用最速下降法求解无约束非线性规划问题姓名：学号：成绩：
2011年6月
用最速下降法求解无约束非线性规划问题
摘要：无约束非线性规划问题是一类重要的数学规划问题。文主要研究了用最速下降法也就是梯度法对无约束非线性规划问题进行求解。对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。本文最后利用c++语言编程得到满足允许误差内的最优解。
本文主要对一个无约束非线性规划问题的实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。然后应用c++语言编程，得到精确地最优解，需迭代六次才使得??0.01，得到的最优解为
)p(6)x(6?(0.0016257T，7,0?.0.007270660016。2 577)
关键词：最速下降法 无约束非线性规划 最优解
1
一、问题重述
2用最速下降法求解无约束非线性规划问题：min(x12?2x2)，设初始点取为
x(0)?(4,4)T,迭代到满足允许误差?=0.01为止的精确解。
二、问题分析
2.1 无约束非线性问题的最优条件
该问题是一个无约束非线性规划问题，利用最少下降法求解该问题，无约束非线性规划问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此有以下几个定理。
定理1 设f：Rn?R1在点x?Rn处可微，若存在p?Rn，使?f(x)Tp?0，则向量p是f在点x处的下降方向。
定理2设f：Rn?R1在点x?Rn处可微，若x?是无约束问题的局部最优解，则?f(x?)?0
有数学分析中我们已经知道，使?f(x)?0的点x为函数f的驻点或平稳点。函数f的一个驻点可以是极小值点；也可以是极大值点；甚至也可能既不是极小值点也不是极大值点，因此称它为函数f的鞍点，以上定理告诉我们，x?是无约束问题的局部最优解的必要条件是：x?是其目标函数f的驻点。
定理3 设f：Rn?R1在点x?Rn处的Hesse矩阵?2f(x?)存在，若
?f(x?)?0，并且?2f(x?)正定，则
x?是无约束非线性问题的严格局部最优解。
一般而言，无约束非线性问题的目标函数的驻点不一定是无约束非线性问题的最优解，但对于其目标函数是凸函数的无约束凸规划，下面定理证明了它的目标函数的驻点就是它的整体最优解。
定理4设f：Rn?R1，x??Rn，f是Rn上的可微凸函数。若有?f(x?)?0，则x?是无约束问题的整体最优解。 2.2最速下降法的基本思想
2
最速下降法又称为梯度法，是1847年由著名数学家Cauchy给出的，他是解析法中最古老的一种，其他解析方法或是他的变形，或是他的启发得到的，因此它是最优化方法的基础。
设无约束非线性规划问题中的目标函数f：Rn?R1在点x?Rn处可微。最速下降法的基本思想是：从当前点xk出发，取函数f(x)在点xk处下降最快的方向作为我们收索方向pk，由
f(x)的
Taylor展示知
f(xk)?f(xk??pk)????f(xk)Tpk?0(?pk)，略去?的高阶无穷小项不计，可
见取pk???f(xk)时，函数值下降的最多 ，于是，我们可以够造出最速下降法的迭代步骤。
2.3无约束非线性规划问题的迭代步骤
解无约束非线性规划问题的最速下降法计算步骤
第1步 选取初始点x0，给定终止误差 ?>0，令k=0；
第2步 计算?f(xk)，若?f(xk)??，停止迭代，输出xk，否则进行第3步；
第3步 取pk???f(xk)；
第4步 进行一维搜索，求?k，使得f(xk??kpk)?minf(xk??pk)，令
k?0xk?1?xk??kpk，k=k+1。转第2步。
由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。
三、问题求解
3.1对原无约束非线性规划迭代 首先进行第一次迭代
p(0)?2x1?T ???f(x)???|?(?8,?16)T?(4,4)?4x2?(0)f(x(0)??p(0))?f((4,4)T??(?8,?16)T)?f(4?8?,4?16?)T?(4?8?)2?2(4?16?)2
3
df??16(4?8?)?64(4?16?) d?df5?0，即?16(4?8?)?64(4?16?)=0，解得：?(0)??0.2778 令d?18则
所以，x(1)?x(0)??(0)p(0)?(4,4)T?0.2778(?8,?16)T?(1.7776,?0.4448)T
?2x1?T此时，p???f(x)????|(1.7776,?0.4448)T?(?3.5552,1.7792)
?4x2?(1)(1)又因为 p(1)?(?3.5552)2?(1.7792)2?3.9755?0.01 则进行第二次迭代
f(x(1)??p(1))?(1.7776?3.5552?)2?2(?0.4448?1.7792?)2
df??7.1104(1.7776?3.5552?)?7.1168(?0.4448?1.7792?) d?df?0，代入即可解得：?(1)?0.4167 令d?则
所以
x(2)?x(1)??(1)p(1)?(1.7776,?0.44448)T?0.4167(?3.5552,1.7792)T?(0.2962,0.2966)T?2x?此时，p(2)???f(x(2))???1?|(0.2962,0.2966)T?(?0.5924,?1.1864)T
?4x2?又因为 p(2)?(?0.5924)2?(?1.1864)2?1.3261?0.01 则进行第三次迭代
f(x(2)??p(2))?(0.2962?0.5924?)2?2(0.2966?1.1864?)2
df??1.1848(0.2962?0.5924?)?4.7456(0.2966?1.1864?) d?df?0，代入即可解得：?(2)?0.2777 令d?则
所以
x(3)?x(2)??(2)p(2)?(0.2962,0.2966)T?0.2777(?0.5924,?1.1864)T?(0.1317,?0.0329)T此时，p(3)?2x1?T???f(x)????|(0.1317,?0.0329)T?(?0.2634,0.1316)
?4x2?(3)又因为 p(3)?(?0.2634)2?(0.1316)2?0.2944?0.01 则进行第四次迭代
4
