首页 > 代码库 > 工程优化方法中的“最速下降法”和“DFP拟牛顿法”的 C 语言实现

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

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

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

一、题目

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

1.1 clip_image002,其中,clip_image004clip_image006clip_image008

1.2 clip_image010,其中,clip_image012clip_image013clip_image014

二、算法

2.1最速下降法(steepest descent method)

算法步骤:

(1)取初始点clip_image016clip_image018,精度clip_image020,令clip_image022

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

(3)一维搜索:clip_image030

clip_image032,转(2)。

2.2拟牛顿法(DFP)

算法步骤:

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

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

(3)令clip_image043

(4)令clip_image045

(5)求clip_image047clip_image049,令clip_image051

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

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

否则令clip_image065clip_image067

计算clip_image069

clip_image071,转(4)。

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

算法步骤:

(1)取初始点clip_image016[1]clip_image073,初始步长clip_image075和精度clip_image020[1],计算clip_image077

(2)计算clip_image079

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

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

否者,令clip_image091,转(2);

三、语言及算法实现说明

3.1算法实现语言及平台:

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

3.2几个部分的思考:

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

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

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

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

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

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

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

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为用户指定的步长;

该模块将搜索到的clip_image095所对应的多维变量存入矩阵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)输入精度值(clip_image097);

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

(5)输入变量维度;

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

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

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

如下图所示(下一页):

clip_image099clip_image101

clip_image103

六、运行结果及分析

6.1精度选择:

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

clip_image107 clip_image109……

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

clip_image113clip_image115

6.1.1小结

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

6.2一维搜索的步长选择:

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

clip_image119clip_image121

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

clip_image123clip_image125

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

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

clip_image127clip_image129

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

clip_image131clip_image133

6.2.1小结

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

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

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

(1) 最速下降法

clip_image135clip_image137

clip_image139clip_image141

(2) DFP

clip_image143clip_image145

clip_image147clip_image149

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

(1)最速下降法

clip_image151clip_image153

(2)DFP

clip_image155clip_image157

6.3.3小结

由以上两组对比可看出:

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

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