• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

工程优化方法中的“最速下降法”和“DFP拟牛顿法”的C语言实现 ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

这个小程序是研一上学期的“工程优化”课程的大作业。其实这题本可以用 MATLAB 实现,但是我为了锻炼自己薄弱的编码能力,改为用 C 语言实现。这样,就得自己实现矩阵的运算(加减乘除、求逆、拷贝);难点是求偏导,通过查资料,发现可以通过导数定义,即取极限的方法,来逐步逼近求得梯度;另外,没法做到输入任意公式,只能将公式硬编码为函数,而求导函数需要传入公式,就直接传入函数指针了。思考、编码、调试、测试共耗费两周左右时间,完成于 2013/01/10。虽然为了认真做这个大作业而耽误了期末考试的复习,但我不后悔做出的选择,因为我学到了我觉得真正有用的东西。

源码托管在 Github 上:点此打开链接

以下为完整的作业报告:

一、题目

用最速下降法和DFP拟牛顿法求解以下函数的最小值点以及最小值:

1.1 ,其中,

1.2 ,其中,

二、算法

2.1最速下降法(steepest descent method)

算法步骤:

(1)取初始点,精度,令

(2)计算,若,则停,;否则转(3);

(3)一维搜索:

,转(2)。

2.2拟牛顿法(DFP)

算法步骤:

(1)取初始点,允许误差

(2)求,若,令,算法停止;否则转(3);

(3)令

(4)令

(5)求,令

(6)求,若,令,算法停止;否则转(6);

(7)若,则令,转(3);

否则令

计算

,转(4)。

2.3成功—失败法(用于一维搜索)

算法步骤:

(1)取初始点,初始步长和精度,计算

(2)计算

(3)若(搜索成功),令

(搜索失败),若,令,停止迭代;

否者,令,转(2);

三、语言及算法实现说明

3.1算法实现语言及平台:

C语言+VC6.0(Debug模式)。

3.2几个部分的思考:

(1)由于实现实时输入函数多项式比较困难,本程序将函数多项式写成模块,存入程序文件中,由于程序使用函数指针,故可以陆续添加函数多项式而不必修改核心算法的代码;

(2)由于函数不同,取值范围不同,则算法需要不同的精度和步长,才能求得精确的结果,故本程序提供接口让用户指定;

(3)为了实现实时输入变量维度,本程序使用动态内存分配,建立多维数组,模拟矩阵,用于存储多维变量;

3.3算法实现的重难点分析:

(1)偏导数的求解:本程序使用偏导数的定义,即极限方法,求解指定点的函数值;

(2)DFP算法中的计算:本程序用多维数组来模拟矩阵进行运算。

四、程序中的主要模块说明(完整程序及注释见附录)

4.1待求解的两个函数:

其中vars为多维变量,n代表维度,这两个模块返回函数在指定点的值。

/* 求函数1在指定点的值 */

double fun1(double **vars, int n);

/* 求函数2在指定点的值 */

double fun2(double **vars, int n);

4.2利用偏导的定义求某个点的偏导数:

其中f为指定函数,vars为多维变量,grads为梯度,n为维度,prec为用户指定的精度;该模块求出函数的偏导存入矩阵grads中。

/* 用极限方法求指定点的偏导/梯度 */

void differ(double (*f)(double **vars, int n), double **vars, double **grads, int n, double prec);

4.3成功—失败法,用于一维搜索:

其中f代表指定函数,vars为多维变量,d为二维搜索的方向,n为维度,prec为用户指定的进度,h为用户指定的步长;

该模块将搜索到的所对应的多维变量存入矩阵vars。

/* 成功失败法,用于一维搜索 */

void suc_fail(double (*f)(double **vars, int n), double **vars, double **d, int n, double prec, double h);

4.4两个核心算法:

其中fun为待解函数的标号,n为维度,prec为用户指定的精度,h为用户指定的用于一维搜索的步长;

这里这两个模块求出指定函数的最小值点和最小值并输出。

/* 最速下降法(Speedest Descent Method)*/

void SD(int fun, int n, double prec, double h);

/* DFP拟牛顿法 */

void DFP(int fun, int n, double prec, double h);

五、程序使用说明

本程序将最速下降法和DFP法整合在一起,精度、步长、维度可由用户指定:

(1)选择方法(只输入序号,‘0’退出);

(2)选择函数(只输入序号);

(3)输入精度值();

(4)输入一维搜索的步长;

(5)输入变量维度;

(6)输入变量的每个分量;

回车后程序开始使用指定方法对指定函数进行计算,计算过程中输出迭代次数;

最后输出结果:最小值点和最小值。

如下图所示(下一页):

六、运行结果及分析

6.1精度选择:

(1)如下用最速下降法求函数1,精度取,步长取1,初值取(5,5,5),求解时陷入了无限迭代:

……

(2)对于(1)的输入,仅修改精度为,仅迭代3次就求出了结果,且达到很高的精度,变量的三个分量和最优值都约等于0:

6.1.1小结

当精度值选择太小,虽然可能得到更精确的结果,但会陷入死循环。当精度要求放松了一点,反而快速求出了精确结果,可见精度要选着适当,不可太大,也不可太小。以下试验就选择为精度值。

6.2一维搜索的步长选择:

(1)如下用最速下降法求函数1,精度取,步长取0.1,初值取(3,3,3),迭代3次求出结果,但是误差很大:

(2)针对(1),仅将步长改为0.5,迭代4次求出结果,精度很高:

(4)如下用最速下降法求函数2,精度取,步长取0.5,

初值取(300,300,300),迭代9次求出结果,但是误差很大:

(5)针对(4),仅将步长改为30,迭代17次求出结果,虽然结果与理想值0还是有一些误差,但比(4)的结果精确了很多:

6.2.1小结

一维搜索的步长也要选择适当,否者求出的结果误差很大。从以上对比可以看出,步长的选取要根据自变量的取值进行相应的调整:函数F1的,变量取3,步长h取0.5时误差较小;函数F2的,变量取300,步长h取30时误差较小,步长h取值为变量x取值的10%左右时误差较小。

6.3比较最速下降法和DFP法:

6.3.1求解函数F1:精度取,步长取0.5,变量分别取(-5,-5,-5)、(5,5,5)

(1) 最速下降法

(2) DFP

6.3.2求解函数F2:精度取,步长取50,变量取(500,500,500)

(1)最速下降法

(2)DFP

6.3.3小结

由以上两组对比可看出:

(1) 对于函数F1和F2,DFP算法都比最速下降法迭代次数多;

(2) 对于函数F1和F2,DFP算法都比最速下降法结果精确;


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C语言·FJ的字符串发布时间:2022-07-14
下一篇:
[三边定位]C#演示程序发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap