首页 > 代码库 > 工程优化方法中的“最速下降法”和“DFP拟牛顿法”的 C 语言实现
工程优化方法中的“最速下降法”和“DFP拟牛顿法”的 C 语言实现
这个小程序是研一上学期的“工程优化”课程的大作业。其实这题本可以用 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算法都比最速下降法结果精确;