用最速下降法求解无约束非线性规划问题

用最速下降法求解无约束非线性规划问题

摘要：无约束非线性规划问题是一类重要的数学规划问题。文主要研究了用最速下降法也就是梯度法对无约束非线性规划问题进行求解。对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。本文最后利用c++语言编程得到满足允许误差内的最优解。

本文主要对一个无约束非线性规划问题的实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。然后应用c++语言编程，得到精确地最优解，需迭代六次才使得0.0，得到的最优解为

x(6)(0.00162577,0.00162577)T，p(6)0.00727066。

关键词：最速下降法 无约束非线性规划 最优解

一、问题重述

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最速下降法的基本思想

最速下降法又称为梯度法，是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0

xk1xkkpk，k=k+1。转第2步。

由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。

三、问题求解

3.1对原无约束非线性规划迭代

首先进行第一次迭代

2x1T

p(0)f(x(0))|(4,4)T(8,16)

4x2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

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 此时，p

(1)

2x1T

f(x)|(1.7776,0.4448)T(3.5552,1.7792)

4x2

(1)

又因为

p(1)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

2x1T

此时，p(2)f(x(2))|(0.2962,0.2966)T(0.5924,1.1864)

4x2

又因为

p(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

2x1T

此时，p(3)f(x(3))|(0.1317,0.0329)T(0.2634,0.1316)

4x2

又因为

p(3)0.29440.01 则进行第四次迭代

f(x(3)p(3))(0.13170.2634)22(0.03290.1316)2

df

0.5268(0.13170.2634)0.5264(0.03290.1316) ddf令0，代入即可解得：(3)0.4168 d

则

所以

x(4)x(3)(3)p(3)(0.1317,0.0329)T0.4168(0.2634,0.1316)T(0.0225,0.0219)T

2x1T

此时，p(4)f(x(4))|(0.0225,0.0219)T(0.045,0.0878)

4x2

又因为

p(4)0.09860.01

以上仍然没有达到要求，即还需继续迭代，直到满足p(k)0.01为止。

3.2对原无约束非线性规划进行c++语言编程求解

就这样无限的迭代下去，直到p(k)0.01为止，为此，我们可以用c++语言编程得到，其算法设计如下图（图3-1）

图（3-1）

利用c++语言编程（源代码如下）：

#include #include

double lambda(double x[2],double p[2],double a[2]) {

double lam1,lam2;

lam1=4*(pow(a[0],3)*x[0]*x[0]+pow(a[1],3)*x[1]*x[1]); lam2=-4*(pow(a[0]*x[0],2)+pow(a[1]*x[1],2)); double s; s=-lam2/(2*lam1);

return s; }

void main() {

double lamb,x[2],a[2],p[2],g[2],e=0.01,y; int i=0; x[0]=4.0; x[1]=4.0;

cout>a[i]; p[0]=2*a[0]*x[0]; p[1]=2*a[1]*x[1]; g[0]=-p[0]; g[1]=-p[1];

i=0; //开始迭代将次数赋值为0 cout

while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i

lamb=lambda(x,g,a); x[0]=x[0]+lamb*g[0];

x[1]=x[1]+lamb*g[1]; p[0]=2*a[0]*x[0]; p[1]=2*a[1]*x[1]; g[0]=-p[0]; g[1]=-p[1]; i++;

//cout("di %d ci mo=%f x1=%f\tx2=%f\tbuchang a=%f\n",++i,sqrt(g[0]*g[0]+g[1]*g[1]),x[0],x[1],a); cout

y=a[0]*x[0]*x[0]+a[1]*x[1]*x[1]; cout

x[1],x[2]："

的

值

的模

"

"

3.3结果分析

运行即可得到如下结果：

由以上结果可以得出：要想使得p(k)0.01，则需要迭代6次，此时，

(6)T

0.00727066。 x(6)(0.00162577,0.00162577)，p

四.算例与结果

2

min(x122x2)

运行结果：

五．总结：

接触最速下降法是在学习运筹学时，它是一种重要的无约束最优化方法 。为

了用C 语言实现最速下降法，重温了C 语言，上网查阅了相关资料,完成该次的课程设计报告，详细阐释了最速下降法的基本原理，迭代步骤以及算法的实现，对最速下降法做了较为深入的研究。通过这次设计，我重新学习了以前遗忘的知识，加深了记忆和理解。真正做到了理论和实践相结合，锻炼了自己分析，处理实际问题的能力，也认识到了自己的不足。本次设计过程中总结到的经验和教训将指导我未来的工作和学习，我会更加努力，取得更大的成绩。

参考文献

[1]范玉妹，徐尔.数学规划及其应用 [M].北京：冶金工业出版社，2009.9. [2]倪勤. 最优化方法与程序设计 [M].北京：科学出版社，2009.6.

[3]孙文瑜，徐成贤，朱德通. 最优化方法 [M].北京：高等教育出版社，2004.8. [4]徐宝文. C++程序设计语言 [M].北京：机械工业出版社，2009.8.

[5]冉崇善. C++程序设计语言设计教程 [M].北京：机械工业出版社，2009.12.

[6]张建勋，纪纲. C程序设计语言设计教程 [M].北京：清华大学出版社，2008.2. [7]李占利 最优化理论与方法 中国矿业大学出版社 2012.

用最速下降法求解无约束非线性规划问题

摘要：无约束非线性规划问题是一类重要的数学规划问题。文主要研究了用最速下降法也就是梯度法对无约束非线性规划问题进行求解。对于一个无约束非线性规划利用最速下降法求解，首先需要确定其优化方向，此优化方向应该选择为f在当前点处的负梯度方向，利用一维搜索法找出沿此方向上的最小值及其对应点，此后将该点作为新的出发点重复上述过程，直到达到允许的误差为止。本文最后利用c++语言编程得到满足允许误差内的最优解。

本文主要对一个无约束非线性规划问题的实例，首先利用上述迭代的方法，计算出各迭代点的函数值，梯度及其模。然后应用c++语言编程，得到精确地最优解，需迭代六次才使得0.0，得到的最优解为

x(6)(0.00162577,0.00162577)T，p(6)0.00727066。

关键词：最速下降法 无约束非线性规划 最优解

一、问题重述

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最速下降法的基本思想

最速下降法又称为梯度法，是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0

xk1xkkpk，k=k+1。转第2步。

由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。

三、问题求解

3.1对原无约束非线性规划迭代

首先进行第一次迭代

2x1T

p(0)f(x(0))|(4,4)T(8,16)

4x2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

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 此时，p

(1)

2x1T

f(x)|(1.7776,0.4448)T(3.5552,1.7792)

4x2

(1)

又因为

p(1)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

2x1T

此时，p(2)f(x(2))|(0.2962,0.2966)T(0.5924,1.1864)

4x2

又因为

p(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

2x1T

此时，p(3)f(x(3))|(0.1317,0.0329)T(0.2634,0.1316)

4x2

又因为

p(3)0.29440.01 则进行第四次迭代

f(x(3)p(3))(0.13170.2634)22(0.03290.1316)2

df

0.5268(0.13170.2634)0.5264(0.03290.1316) ddf令0，代入即可解得：(3)0.4168 d

则

所以

x(4)x(3)(3)p(3)(0.1317,0.0329)T0.4168(0.2634,0.1316)T(0.0225,0.0219)T

2x1T

此时，p(4)f(x(4))|(0.0225,0.0219)T(0.045,0.0878)

4x2

又因为

p(4)0.09860.01

以上仍然没有达到要求，即还需继续迭代，直到满足p(k)0.01为止。

3.2对原无约束非线性规划进行c++语言编程求解

就这样无限的迭代下去，直到p(k)0.01为止，为此，我们可以用c++语言编程得到，其算法设计如下图（图3-1）

图（3-1）

利用c++语言编程（源代码如下）：

#include #include

double lambda(double x[2],double p[2],double a[2]) {

double lam1,lam2;

lam1=4*(pow(a[0],3)*x[0]*x[0]+pow(a[1],3)*x[1]*x[1]); lam2=-4*(pow(a[0]*x[0],2)+pow(a[1]*x[1],2)); double s; s=-lam2/(2*lam1);

return s; }

void main() {

double lamb,x[2],a[2],p[2],g[2],e=0.01,y; int i=0; x[0]=4.0; x[1]=4.0;

cout>a[i]; p[0]=2*a[0]*x[0]; p[1]=2*a[1]*x[1]; g[0]=-p[0]; g[1]=-p[1];

i=0; //开始迭代将次数赋值为0 cout

while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i

lamb=lambda(x,g,a); x[0]=x[0]+lamb*g[0];

x[1]=x[1]+lamb*g[1]; p[0]=2*a[0]*x[0]; p[1]=2*a[1]*x[1]; g[0]=-p[0]; g[1]=-p[1]; i++;

//cout("di %d ci mo=%f x1=%f\tx2=%f\tbuchang a=%f\n",++i,sqrt(g[0]*g[0]+g[1]*g[1]),x[0],x[1],a); cout

y=a[0]*x[0]*x[0]+a[1]*x[1]*x[1]; cout

x[1],x[2]："

的

值

的模

"

"

3.3结果分析

运行即可得到如下结果：

由以上结果可以得出：要想使得p(k)0.01，则需要迭代6次，此时，

(6)T

0.00727066。 x(6)(0.00162577,0.00162577)，p

四.算例与结果

2

min(x122x2)

运行结果：

五．总结：

接触最速下降法是在学习运筹学时，它是一种重要的无约束最优化方法 。为

了用C 语言实现最速下降法，重温了C 语言，上网查阅了相关资料,完成该次的课程设计报告，详细阐释了最速下降法的基本原理，迭代步骤以及算法的实现，对最速下降法做了较为深入的研究。通过这次设计，我重新学习了以前遗忘的知识，加深了记忆和理解。真正做到了理论和实践相结合，锻炼了自己分析，处理实际问题的能力，也认识到了自己的不足。本次设计过程中总结到的经验和教训将指导我未来的工作和学习，我会更加努力，取得更大的成绩。

参考文献

[1]范玉妹，徐尔.数学规划及其应用 [M].北京：冶金工业出版社，2009.9. [2]倪勤. 最优化方法与程序设计 [M].北京：科学出版社，2009.6.

[3]孙文瑜，徐成贤，朱德通. 最优化方法 [M].北京：高等教育出版社，2004.8. [4]徐宝文. C++程序设计语言 [M].北京：机械工业出版社，2009.8.

[5]冉崇善. C++程序设计语言设计教程 [M].北京：机械工业出版社，2009.12.

[6]张建勋，纪纲. C程序设计语言设计教程 [M].北京：清华大学出版社，2008.2. [7]李占利 最优化理论与方法 中国矿业大学出版社 2012.