运 筹 学 实 习 报 告
姓 名: xxxxxxxxxx 学 号: xxxxxxxxxxx 专业班级: xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日
题目:用最速下降法求解无约束非线性规划问题
摘要:
无约束最优化问题的求解方法分为解析法和直接法两大类。解析法需要计
算函数的梯度,其中最速下降法就属于解析法中的一种。对于一个无约束非线性规划利用最速下降法求解,首先需要确定其优化方向,此优化方向应该选择为f在当前点处的负梯度方向,利用一维搜索法找出沿此方向上的最小值及其对应点,此后将该点作为新的出发点重复上述过程,直到达到允许的误差为止。本文通过理论的计算方法,进一步分析,最后用c++编程实现求出允许误差内的最优解。此编程可用于计算符合下列形式的函数求最优解过程:
f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中:a[i] (i=0,1,2,3,4,5) 为函数的系数。
本文以“ 李占利 主编,中国矿业大学出版社出版”的《最优化理论与方法》 第五章 “无约束最优化方法,5.1 最速下降法 ”例5—1为实例,首先利用上述迭代的方法,计算出各迭代点的函数值,梯度及其模。然后应用c++语言编程,得到在精度范围内的精确最优解。
*(3)T
xx[0.00823045,0.0329218] C++编程计算的最优解为 : 。
即转化为分数结果为:xx
*(3)
21 。 2434
满足精度要求的模为:
||p(3)||0.0736154
1
10。
关键词:无约束非线性规划 解析法 最速下降法 梯度 模 最优解
一、算法思想
无约束最优化方法中的最速下降法首先需要确定其优化方向,此优化方向应该选择为f在当前点处的负梯度方向,利用一维搜索法找出沿此方向上的最小值及其对应点,此后将该点作为新的出发点重复上述过程,直到达到允许的误差为止。主要依据解无约束非线性规划问题的最速下降法计算步骤进行设计算法。 具体步骤如下:
第1步 选取初始点x,给定终止误差 >0,令k=0;
kkf(xk)f(x) 第2步 计算,若,停止迭代,输出x,否则进行第3
步;
kk
pf(x); 第3步 取
f(xkkpk)minf(xkpk)k0
第4步 进行一维搜索,求k,使得,令
xk1xkkpk
,k=k+1。转第2步。
由以上计算步骤可知,最速下降法迭代终止时,求得的是目标函数驻点的一个近似点。 依据以上步骤就可以用C++编程实现最速下降法求解最优解的算法。
二、算法流程图
三、程序代码
#include #include
double lamda(double x[2],double p[2],double a[2]) { double lam1,lam2; lam1=(pow(a[0],3)*x[0]*x[0]+pow(a[1],3)*x[1]*x[1]); lam2=-(pow(a[0]*x[0],2)+pow(a[1]*x[1],2)); double s;
s=-lam2/(2*lam1); return s; }
void main() {
cout
cout>e; cout>m; cin>>n; x[0]=m; x[1]=n; cout>a[i];
p[0]=(2*a[0]*x[0]+a[2]*x[1]+a[3]); p[1]=(2*a[1]*x[1]+a[2]*x[0]+a[4]); g[0]=-p[0]; g[1]=-p[1]; i=0; cout
while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i
lamd=lamda(x,g,a); x[0]=x[0]+lamd*g[0]; x[1]=x[1]+lamd*g[1];
s=-lam2/(2*lam1); return s; }
void main() {
cout
cout>e; cout>m; cin>>n; x[0]=m; x[1]=n; cout>a[i];
p[0]=(2*a[0]*x[0]+a[2]*x[1]+a[3]); p[1]=(2*a[1]*x[1]+a[2]*x[0]+a[4]); g[0]=-p[0]; g[1]=-p[1]; i=0; cout
while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i
lamd=lamda(x,g,a); x[0]=x[0]+lamd*g[0]; x[1]=x[1]+lamd*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
cout
cout
四、例子与结果
例子为“ 李占利 主编,中国矿业大学出版社出版”的《最优化理论与方法》
第五章 “无约束最优化方法,5.1 最速下降法 ”例5—1。用最速下降法求解
中很明显有:a[0]=2,a[1]=1,a[2]=a[3]=a[4]=a[5]=0;e=0.1;x[0]=x[1]=1;
12
0.1。则体现在程序minf(x)2x12x2,初始迭代点x(0)1,精度为
则程序运行结果为:
12
即在允许的精度范围内minf(x)2x12x2,初始迭代点x(0)1,精度
为0.1。得到在精度范围内的精确最优解为:
*(3)T21*(3)xx[0.008230,40.5032921]8 ,即xx 。
2434
满足精度要求的模为:
||p(3)||0.0736154
1
10。
五、结论与总结
最速下降法为最优化万千方法中的一种,要想更好地利用最优化方法解决我们身边的问题,光靠这一种方法远远不够。因此我必须要好好掌握其他的各种方法。还有通过这次实习让我深深认识到,并不是所有的问题都能够手工完成的,我们平常接触的例题,都非常基础,那完全可以手工计算得到答案,但如果问题比较复杂时,我们是没有办法用手工完成的。所以我们必须借助计算机来解决那些复杂的问题。因此这就要求我们必须要熟练掌握编程技巧,要能够把实际的复杂问题通过编写程序来解决它。还有此次用最速下降法求解最优解的程序,我编的还不够完美,还有很多不足之处,只能用于研究二元函数的最优解问题,不能进行其他的更深入的研究,所以还有很多改进的地方,以后我还要继续努力。 对于编程一定要多练、多动手操作,通过这次实习让我深深地认识到,光靠理论知识是不行的,理论知道再多,如果不动手实践的话照样编不出程序,只有在实践中,在编写程序的过程中我们才能发现自己的不足,才能知道问题出在哪儿。所以无论学习什么编程语言,我今后一定要多动手,今后无论学习什么我都要勤动手,多动手,多写,多练。
六、参考文献
[1]龚尚福,贾澎涛. C/C++语言程序设计 [M].徐州:中国矿业大学出版社,2006.12.
[2]李占利,张卫国. 最优化理论与方法 [M].徐州:中国矿业大学出版社,2012.8. [3]范玉妹,徐尔.数学规划及其应用 [M].北京:冶金工业出版社,2009.9. [4]孙文瑜,徐成贤,朱德通. 最优化方法 [M].北京:高等教育出版社,2004.8.
运 筹 学 实 习 报 告
姓 名: xxxxxxxxxx 学 号: xxxxxxxxxxx 专业班级: xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日
题目:用最速下降法求解无约束非线性规划问题
摘要:
无约束最优化问题的求解方法分为解析法和直接法两大类。解析法需要计
算函数的梯度,其中最速下降法就属于解析法中的一种。对于一个无约束非线性规划利用最速下降法求解,首先需要确定其优化方向,此优化方向应该选择为f在当前点处的负梯度方向,利用一维搜索法找出沿此方向上的最小值及其对应点,此后将该点作为新的出发点重复上述过程,直到达到允许的误差为止。本文通过理论的计算方法,进一步分析,最后用c++编程实现求出允许误差内的最优解。此编程可用于计算符合下列形式的函数求最优解过程:
f(x)=a[0]x1*x1+a[1]x2*x2+a[2]x1*x2+a[3]x1+a[4]x2+a[5]其中:a[i] (i=0,1,2,3,4,5) 为函数的系数。
本文以“ 李占利 主编,中国矿业大学出版社出版”的《最优化理论与方法》 第五章 “无约束最优化方法,5.1 最速下降法 ”例5—1为实例,首先利用上述迭代的方法,计算出各迭代点的函数值,梯度及其模。然后应用c++语言编程,得到在精度范围内的精确最优解。
*(3)T
xx[0.00823045,0.0329218] C++编程计算的最优解为 : 。
即转化为分数结果为:xx
*(3)
21 。 2434
满足精度要求的模为:
||p(3)||0.0736154
1
10。
关键词:无约束非线性规划 解析法 最速下降法 梯度 模 最优解
一、算法思想
无约束最优化方法中的最速下降法首先需要确定其优化方向,此优化方向应该选择为f在当前点处的负梯度方向,利用一维搜索法找出沿此方向上的最小值及其对应点,此后将该点作为新的出发点重复上述过程,直到达到允许的误差为止。主要依据解无约束非线性规划问题的最速下降法计算步骤进行设计算法。 具体步骤如下:
第1步 选取初始点x,给定终止误差 >0,令k=0;
kkf(xk)f(x) 第2步 计算,若,停止迭代,输出x,否则进行第3
步;
kk
pf(x); 第3步 取
f(xkkpk)minf(xkpk)k0
第4步 进行一维搜索,求k,使得,令
xk1xkkpk
,k=k+1。转第2步。
由以上计算步骤可知,最速下降法迭代终止时,求得的是目标函数驻点的一个近似点。 依据以上步骤就可以用C++编程实现最速下降法求解最优解的算法。
二、算法流程图
三、程序代码
#include #include
double lamda(double x[2],double p[2],double a[2]) { double lam1,lam2; lam1=(pow(a[0],3)*x[0]*x[0]+pow(a[1],3)*x[1]*x[1]); lam2=-(pow(a[0]*x[0],2)+pow(a[1]*x[1],2)); double s;
s=-lam2/(2*lam1); return s; }
void main() {
cout
cout>e; cout>m; cin>>n; x[0]=m; x[1]=n; cout>a[i];
p[0]=(2*a[0]*x[0]+a[2]*x[1]+a[3]); p[1]=(2*a[1]*x[1]+a[2]*x[0]+a[4]); g[0]=-p[0]; g[1]=-p[1]; i=0; cout
while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i
lamd=lamda(x,g,a); x[0]=x[0]+lamd*g[0]; x[1]=x[1]+lamd*g[1];
s=-lam2/(2*lam1); return s; }
void main() {
cout
cout>e; cout>m; cin>>n; x[0]=m; x[1]=n; cout>a[i];
p[0]=(2*a[0]*x[0]+a[2]*x[1]+a[3]); p[1]=(2*a[1]*x[1]+a[2]*x[0]+a[4]); g[0]=-p[0]; g[1]=-p[1]; i=0; cout
while(sqrt(g[0]*g[0]+g[1]*g[1])>e&&i
lamd=lamda(x,g,a); x[0]=x[0]+lamd*g[0]; x[1]=x[1]+lamd*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
cout
cout
四、例子与结果
例子为“ 李占利 主编,中国矿业大学出版社出版”的《最优化理论与方法》
第五章 “无约束最优化方法,5.1 最速下降法 ”例5—1。用最速下降法求解
中很明显有:a[0]=2,a[1]=1,a[2]=a[3]=a[4]=a[5]=0;e=0.1;x[0]=x[1]=1;
12
0.1。则体现在程序minf(x)2x12x2,初始迭代点x(0)1,精度为
则程序运行结果为:
12
即在允许的精度范围内minf(x)2x12x2,初始迭代点x(0)1,精度
为0.1。得到在精度范围内的精确最优解为:
*(3)T21*(3)xx[0.008230,40.5032921]8 ,即xx 。
2434
满足精度要求的模为:
||p(3)||0.0736154
1
10。
五、结论与总结
最速下降法为最优化万千方法中的一种,要想更好地利用最优化方法解决我们身边的问题,光靠这一种方法远远不够。因此我必须要好好掌握其他的各种方法。还有通过这次实习让我深深认识到,并不是所有的问题都能够手工完成的,我们平常接触的例题,都非常基础,那完全可以手工计算得到答案,但如果问题比较复杂时,我们是没有办法用手工完成的。所以我们必须借助计算机来解决那些复杂的问题。因此这就要求我们必须要熟练掌握编程技巧,要能够把实际的复杂问题通过编写程序来解决它。还有此次用最速下降法求解最优解的程序,我编的还不够完美,还有很多不足之处,只能用于研究二元函数的最优解问题,不能进行其他的更深入的研究,所以还有很多改进的地方,以后我还要继续努力。 对于编程一定要多练、多动手操作,通过这次实习让我深深地认识到,光靠理论知识是不行的,理论知道再多,如果不动手实践的话照样编不出程序,只有在实践中,在编写程序的过程中我们才能发现自己的不足,才能知道问题出在哪儿。所以无论学习什么编程语言,我今后一定要多动手,今后无论学习什么我都要勤动手,多动手,多写,多练。
六、参考文献
[1]龚尚福,贾澎涛. C/C++语言程序设计 [M].徐州:中国矿业大学出版社,2006.12.
[2]李占利,张卫国. 最优化理论与方法 [M].徐州:中国矿业大学出版社,2012.8. [3]范玉妹,徐尔.数学规划及其应用 [M].北京:冶金工业出版社,2009.9. [4]孙文瑜,徐成贤,朱德通. 最优化方法 [M].北京:高等教育出版社,2004.8.