BFGS和DFP法的最优化问题求解及在MATLAB中的实现

第26卷第5期2012年9月长沙大学学报

JOURNALOFCHANGSHAUNIVERSITYVol．26No．5Sep．2012

BFGS和DFP法的最优化问题求解

及在MATLAB中的实现

*

吴顺秋

（湖南城市学院数学与计算科学学院，湖南益阳413000）

摘

要：对拟Newton方法中的DFP算法和BFGS算法进行了探讨，借助matlab软件中fminsearch和fminunc函数，利用

BFGS方法和DFP方法对非线性无约束优化问题进行了仿真研究，结果表明利用matlab软件解答非线性无约束优化问题获得了好的效果，为数学工作者求解非线性无约束优化问题提供了一种新的方法．

关键词：matlab软件；数学建模；BFGS算法；DFP算法；最优解中图分类号：TB112

文献标识码：A

文章编号：1008－4681（2012）05－0001－03

DFP算法的一般计算步骤如下：

dk=－（Bk）

－1

在当今科学研究、工程设计和经济管理等许多领域中，常常会遇到如何在一切可能的方案中选择最优、最好方案的这类问题，数学上把它称之为最优化问题．如何得到最优方案，自然也就成了科技人员在解决实际问题中特别关心的问特别是现在的高科技人才中，很题．而在大多数人的头脑中，

多人只注意新方法新问题的发明、发现，其实如何对已有的很艰巨的问题方法的优化同样是一个很重要、

［1，2］

gk

xk+1=xk+akdk

Bk+1

T

BkskyTsTk+ykskBkkBksk

=Bk－+1+TT

skykkkskyk

()

ak为步长因子，其中sk=akdk；yk=gk+1－gk，它由具体的线搜索准则确定．

Goldstein－Armijor线搜索下的DFP算法

B1∈Rn*n且对称正定，k=1；步骤1：取x1∈Rn，

步骤2：计算gk=f（xk），如果gk=0，则终止，最优解为xk；如果gk≠0，令dk=－（Bk）

－1

．

在数学上，优化问题就是求解如下形式的最优解：Minimizef（x）Subjectto［C．E．］

［B．C．］

Subjectto引导的部分称为约其中f（x）称为目标函数，

［C．E．］［B．C．］即边界条件，束条件，即条件方程，用来约束自变量的求解域，以vlb≤x≤vub的形式给出．

在优化问题中，根据目标函数、约束函数和变量的不同，可以将其大致分为线性优化、非线性优化、二次优化、多任务目标优化等，本文主要讨论非线性优化问题，这里仅就DFP算法和BFGS算法进行一些探讨．

gk，继续下一步；

步骤3：选取ak满足以下两式

f（xk+akdk）≤f（xk）+μak（gk）Tdkf（xk+akdk）≥f（xk）+δak（gk）Tdk

其中0＜μ＜δ＜1

步骤4：令xk+1=xk+sk=xk+akdk；步骤5：令Bk+1

T

BkskyTk+ykskBk

=Bk－+

sTkyk

(

sTkBksk

·1+T

skyk

)

1

1．1

DFP算法和BFGS算法

DFP算法

无约束优化问题的基本形式为

［3］

yk22

，其中yk=gk+1gk；Tskyk

；

（1）

1．2

步骤6：k=k+1，转至步骤2．BFGS算法

BFGS（Broyden－Fletcher－Gold-在求解无约束问题时，

farb－Shanno）算法是拟Newton算法中最有效的方法之一，Fletcher、Goldfarb和Shanno等四人所提出，它由Broyden、求解前面问题（1）的BFGS算法步骤如下

［5］

Minimizef（x）x∈Rn

其中f（x）：Rn→R称为目标函数．

理论分析和大量数值试验表明，在求解（1）的各种算法中，拟Newton算法是效果最好的一类方法．DFP（Davidon－Fletcher－Powell）算法是最早提出的拟Newton算法，它首先并由Fletcher和Powell修改而成由Davidon给出，

*

［4］

：

．步骤1：选择初始点x1∈Rn，初始对称且正定矩阵B1∈

收稿日期：2012－08－26

作者简介：吴顺秋（1965－），男，湖南益阳人，湖南城市学院数学与计算科学学院副教授．研究方向：应用数学、最优化问

常微分方程．题、

2

Rn*n，计算梯度f（x1），令k=1；

长沙大学学报2012年9月

hessupdate控制，（默认值），当hessupdate=‘bfgs’拟Newton，的BFGS公式；当hessupdate=‘dfp’拟Newton的DFP公式．

x122

［例2］求函数f（x）=e（4x1+2x2+4x1x2+2x2+

步骤2：如果f（xk）=0，则算法终止，否则，令dk

=－Bk－1f（xk）；

步骤3：对函数f（x）在点xk处沿着方向dk进行某种线性搜索获得步长ak，然后令xk+1=xk+akdk．计算f（xk+1）；

步骤4：由下列公式计算Bk+1；Bk+1

BksksTykyTkBkk

=Bk－T+T

skBkskyksk

1）在点［－1，1］附近的局部最小值．

解：MATLAB实现程序及运行结果如下：

f=‘exp（x（1））*（4*x（1）^2+2*x（2）^2+4*x（1）*x（2）+2*x（2）+1）’；

x0=［－1，1］；options=［］

x=fminunc（f，x0，options）；x输出为：

x=0．[1**********]358－1．[**************]］y=options［y输出为：

1．[1**********]846e－010

1］0．5，1］处取得局部最小可知函数在［－1，附近的点［options为优化参数选择控制值点，极小值为1．3e－10．其中，如options（8）为函数值等等．注意，这里用一个详细的字量，

符串表达式表示函数，通常函数可由M文件给出．

［例3］分别用BFGS方法和DFP方法求解如下的Powell奇异函数的最小值点［9］．

f=（x1+x2）x4）

4

2

yk=f（xk+1）－f（xk）．其中sk=xk+1－xk，

步骤5：令k=k+1，转步骤2．

BFGS算法中的矩阵Bk+l满足拟Newton条件yk=Bk+1sk．众所周知，如果Bk是正定的，则dk是f（x）在xk处的一非个下降方向．计算步长ak所使用的线性搜索有精确搜索，Armijo搜索以及满足Goldstein条件的精确的Wolfe型搜索、非精确搜索等．

由于BFGS算法具有快速的收敛性和较好的数值效果

［6］

，它已成为数学家和工程师们解决最优化问题的一类最

受欢迎的方法；BFGS方法已有较完善的局部收敛理论，对其全局收敛性的研究也取得了重要成果，特别是在求解凸函数的极小化问题中，采用精确线性搜索或某些特殊非精确线性BFGS方法具有全局收敛性．搜索，

BFGS算法的核心内容是BFGS校正公式Bk+1，利用这一公式产生Hessian矩阵的近似，避免了直接计算Hessian矩阵的麻烦，因此，这一校正公式现已被广泛应用在多种优化方法中．

+5（x3－x4）

2

+（x2－2x3）

4

+10（x1－

解：可以看出，最小值点即为（0000）点．此例只是为比较各方法的应用，并无大的实际意义．

在matlab里编制的程序并运行结果如下：functionf=pfun（x）

f=（x（1）+x（2））^2+5*（x（3）－x（4））^2+（x（2）－2*x（3））^4+10*（x（1）－x（4））^4

x0=［3，－1，0，1］BFGS法

%采用混合插值法

options（6）=0；Options（7）=0；fminunc（‘pfun’，x0，Options）ans=

0．0027－0．0003－0．0057－0．0057%采用立方插值法

options（6）=0；Options（7）=1；fminunc（‘pfun’，x0，Options）ans=

2非线性无约束优化问题在matlab中的实现

无约束优化问题在matlab中可由三个功能函数实现，即

fminsearch（多变量的函数fminbnd（单变量的最小函数值）、

fminunc（多变量函数最小值时的变量值）．其最小函数值）、

中fminbnd和fminsearch的优化算法简单，处理简单问题方便，但对复杂问题却力不从心；fminunc的算法复杂，可解决且提供了几种可供选择的不同算法．较为复杂的问题，2．1

用fminsearch实现BFGS方法的最优解

332

［例1］用BFGS方法散求2x1+4x1x2－10x1x2+x2的

最小值点．

解：Matlab程序及运行结果如下：

fminsearch（‘2*x（1）^3+4*x（1）*x（2）^3－10x（1）*x（2）+x（2）^2’，［0，0］）

ans=1．00162．2

0．8334

－0．01560．0015－0．0146－0．0146DFP方法

%采用混合插值法

options（6）=1；Options（7）=0；fminunc（‘pfun’，x0，Options）

用fminunc实现BFGS方法和DFP方法的最优解Fminunc算法为无约束优化提供了大型优化和中型优化

［7，8］

算法

，由options中的参数控制；Fminunc算法同时也为中

由options中的参数型优化算法的搜索方向提供了4种算法，

总第109期

ans=

吴顺秋：BFGS和DFP法的最优化问题求解及在MATLAB中的实现

员的负担，提高工作效率，是一个值得推广的方法．

3

0．0214－0．00210．01190．0120%采用立方插值法

options（6）=1；Options（7）=1；fminunc（‘pfun’，x0，Options）ans=

－0．01390．0014－0．0064－0．0064

其中对函数fminunc来说．Options（6）为控制搜索方向取默认值0时，是BFGS方法：取1时为DFP方法．Op-算法，

tionsw（7）为控制插值法，其中取默认值0时是混合插值；取1时为立方插值．

参考文献：

［1］王沫然．MATLAB与科学计算［M］．北京：电子工业出版

2005．社，

［2］濮定国．修改的DFP算法［J］．应用数学学报，1990，（2）：21

－24．

［3］韦增欣，李国胤．在一种新型线搜索下DFP算法的全局收敛性

［J］．广西大学学报（自然科学版），2002，（1）：61－66．

［4］袁功林，韦增欣，鲁习文．一个修改的求解非线性对称方程组的

J］．广西科学，2006，（4）：288－292．高斯－牛顿BFGS方法［

［5］刘陶文．BFGS方法及其在求解约束优化问题中的应用［D］．长

2006．沙：湖南大学博士学位论文，

［6］时平平．关于无约束最优化问题的拟牛顿算法研究［D］．太原：

3结语

在当今社会，优化问题已成为科学研究、工程设计和经

2008．太原科技大学硕士学位论文，

［7］何伟．基于新拟牛顿方程的改进的BFGS方法［D］．南京：南京理

2007．工大学硕士学位论文，

［8］王正林，．北京：电子工业出版刘明．精通MATLAB7［M］

2006．社，

［9］周智峰，张明，周海青．基于matlab的最优化问题求解通用程序

J］．机械传动，2004，（6）：29－32．的实现［

济管理等许多领域中一类重要问题，而许多科技人员往往又本文主要针对非线性优化问题，采用拟只注重寻找新方法，

Newton法中的DFP算法和BFGS算法进行一些探讨；并利用MATLAB语言通过几个算例对其进行了仿真分析，认为BFGS算法是拟Newton算法中的最有效的方法之一；同时认为用MATLAB编写程序来研究优化问题，能大大减轻设计人

（责任编校：晴川）

第26卷第5期2012年9月长沙大学学报

JOURNALOFCHANGSHAUNIVERSITYVol．26No．5Sep．2012

BFGS和DFP法的最优化问题求解

及在MATLAB中的实现

*

吴顺秋

（湖南城市学院数学与计算科学学院，湖南益阳413000）

摘

要：对拟Newton方法中的DFP算法和BFGS算法进行了探讨，借助matlab软件中fminsearch和fminunc函数，利用

BFGS方法和DFP方法对非线性无约束优化问题进行了仿真研究，结果表明利用matlab软件解答非线性无约束优化问题获得了好的效果，为数学工作者求解非线性无约束优化问题提供了一种新的方法．

关键词：matlab软件；数学建模；BFGS算法；DFP算法；最优解中图分类号：TB112

文献标识码：A

文章编号：1008－4681（2012）05－0001－03

DFP算法的一般计算步骤如下：

dk=－（Bk）

－1

在当今科学研究、工程设计和经济管理等许多领域中，常常会遇到如何在一切可能的方案中选择最优、最好方案的这类问题，数学上把它称之为最优化问题．如何得到最优方案，自然也就成了科技人员在解决实际问题中特别关心的问特别是现在的高科技人才中，很题．而在大多数人的头脑中，

多人只注意新方法新问题的发明、发现，其实如何对已有的很艰巨的问题方法的优化同样是一个很重要、

［1，2］

gk

xk+1=xk+akdk

Bk+1

T

BkskyTsTk+ykskBkkBksk

=Bk－+1+TT

skykkkskyk

()

ak为步长因子，其中sk=akdk；yk=gk+1－gk，它由具体的线搜索准则确定．

Goldstein－Armijor线搜索下的DFP算法

B1∈Rn*n且对称正定，k=1；步骤1：取x1∈Rn，

步骤2：计算gk=f（xk），如果gk=0，则终止，最优解为xk；如果gk≠0，令dk=－（Bk）

－1

．

在数学上，优化问题就是求解如下形式的最优解：Minimizef（x）Subjectto［C．E．］

［B．C．］

Subjectto引导的部分称为约其中f（x）称为目标函数，

［C．E．］［B．C．］即边界条件，束条件，即条件方程，用来约束自变量的求解域，以vlb≤x≤vub的形式给出．

在优化问题中，根据目标函数、约束函数和变量的不同，可以将其大致分为线性优化、非线性优化、二次优化、多任务目标优化等，本文主要讨论非线性优化问题，这里仅就DFP算法和BFGS算法进行一些探讨．

gk，继续下一步；

步骤3：选取ak满足以下两式

f（xk+akdk）≤f（xk）+μak（gk）Tdkf（xk+akdk）≥f（xk）+δak（gk）Tdk

其中0＜μ＜δ＜1

步骤4：令xk+1=xk+sk=xk+akdk；步骤5：令Bk+1

T

BkskyTk+ykskBk

=Bk－+

sTkyk

(

sTkBksk

·1+T

skyk

)

1

1．1

DFP算法和BFGS算法

DFP算法

无约束优化问题的基本形式为

［3］

yk22

，其中yk=gk+1gk；Tskyk

；

（1）

1．2

步骤6：k=k+1，转至步骤2．BFGS算法

BFGS（Broyden－Fletcher－Gold-在求解无约束问题时，

farb－Shanno）算法是拟Newton算法中最有效的方法之一，Fletcher、Goldfarb和Shanno等四人所提出，它由Broyden、求解前面问题（1）的BFGS算法步骤如下

［5］

Minimizef（x）x∈Rn

其中f（x）：Rn→R称为目标函数．

理论分析和大量数值试验表明，在求解（1）的各种算法中，拟Newton算法是效果最好的一类方法．DFP（Davidon－Fletcher－Powell）算法是最早提出的拟Newton算法，它首先并由Fletcher和Powell修改而成由Davidon给出，

*

［4］

：

．步骤1：选择初始点x1∈Rn，初始对称且正定矩阵B1∈

收稿日期：2012－08－26

作者简介：吴顺秋（1965－），男，湖南益阳人，湖南城市学院数学与计算科学学院副教授．研究方向：应用数学、最优化问

常微分方程．题、

2

Rn*n，计算梯度f（x1），令k=1；

长沙大学学报2012年9月

hessupdate控制，（默认值），当hessupdate=‘bfgs’拟Newton，的BFGS公式；当hessupdate=‘dfp’拟Newton的DFP公式．

x122

［例2］求函数f（x）=e（4x1+2x2+4x1x2+2x2+

步骤2：如果f（xk）=0，则算法终止，否则，令dk

=－Bk－1f（xk）；

步骤3：对函数f（x）在点xk处沿着方向dk进行某种线性搜索获得步长ak，然后令xk+1=xk+akdk．计算f（xk+1）；

步骤4：由下列公式计算Bk+1；Bk+1

BksksTykyTkBkk

=Bk－T+T

skBkskyksk

1）在点［－1，1］附近的局部最小值．

解：MATLAB实现程序及运行结果如下：

f=‘exp（x（1））*（4*x（1）^2+2*x（2）^2+4*x（1）*x（2）+2*x（2）+1）’；

x0=［－1，1］；options=［］

x=fminunc（f，x0，options）；x输出为：

x=0．[1**********]358－1．[**************]］y=options［y输出为：

1．[1**********]846e－010

1］0．5，1］处取得局部最小可知函数在［－1，附近的点［options为优化参数选择控制值点，极小值为1．3e－10．其中，如options（8）为函数值等等．注意，这里用一个详细的字量，

符串表达式表示函数，通常函数可由M文件给出．

［例3］分别用BFGS方法和DFP方法求解如下的Powell奇异函数的最小值点［9］．

f=（x1+x2）x4）

4

2

yk=f（xk+1）－f（xk）．其中sk=xk+1－xk，

步骤5：令k=k+1，转步骤2．

BFGS算法中的矩阵Bk+l满足拟Newton条件yk=Bk+1sk．众所周知，如果Bk是正定的，则dk是f（x）在xk处的一非个下降方向．计算步长ak所使用的线性搜索有精确搜索，Armijo搜索以及满足Goldstein条件的精确的Wolfe型搜索、非精确搜索等．

由于BFGS算法具有快速的收敛性和较好的数值效果

［6］

，它已成为数学家和工程师们解决最优化问题的一类最

受欢迎的方法；BFGS方法已有较完善的局部收敛理论，对其全局收敛性的研究也取得了重要成果，特别是在求解凸函数的极小化问题中，采用精确线性搜索或某些特殊非精确线性BFGS方法具有全局收敛性．搜索，

BFGS算法的核心内容是BFGS校正公式Bk+1，利用这一公式产生Hessian矩阵的近似，避免了直接计算Hessian矩阵的麻烦，因此，这一校正公式现已被广泛应用在多种优化方法中．

+5（x3－x4）

2

+（x2－2x3）

4

+10（x1－

解：可以看出，最小值点即为（0000）点．此例只是为比较各方法的应用，并无大的实际意义．

在matlab里编制的程序并运行结果如下：functionf=pfun（x）

f=（x（1）+x（2））^2+5*（x（3）－x（4））^2+（x（2）－2*x（3））^4+10*（x（1）－x（4））^4

x0=［3，－1，0，1］BFGS法

%采用混合插值法

options（6）=0；Options（7）=0；fminunc（‘pfun’，x0，Options）ans=

0．0027－0．0003－0．0057－0．0057%采用立方插值法

options（6）=0；Options（7）=1；fminunc（‘pfun’，x0，Options）ans=

2非线性无约束优化问题在matlab中的实现

无约束优化问题在matlab中可由三个功能函数实现，即

fminsearch（多变量的函数fminbnd（单变量的最小函数值）、

fminunc（多变量函数最小值时的变量值）．其最小函数值）、

中fminbnd和fminsearch的优化算法简单，处理简单问题方便，但对复杂问题却力不从心；fminunc的算法复杂，可解决且提供了几种可供选择的不同算法．较为复杂的问题，2．1

用fminsearch实现BFGS方法的最优解

332

［例1］用BFGS方法散求2x1+4x1x2－10x1x2+x2的

最小值点．

解：Matlab程序及运行结果如下：

fminsearch（‘2*x（1）^3+4*x（1）*x（2）^3－10x（1）*x（2）+x（2）^2’，［0，0］）

ans=1．00162．2

0．8334

－0．01560．0015－0．0146－0．0146DFP方法

%采用混合插值法

options（6）=1；Options（7）=0；fminunc（‘pfun’，x0，Options）

用fminunc实现BFGS方法和DFP方法的最优解Fminunc算法为无约束优化提供了大型优化和中型优化

［7，8］

算法

，由options中的参数控制；Fminunc算法同时也为中

由options中的参数型优化算法的搜索方向提供了4种算法，

总第109期

ans=

吴顺秋：BFGS和DFP法的最优化问题求解及在MATLAB中的实现

员的负担，提高工作效率，是一个值得推广的方法．

3

0．0214－0．00210．01190．0120%采用立方插值法

options（6）=1；Options（7）=1；fminunc（‘pfun’，x0，Options）ans=

－0．01390．0014－0．0064－0．0064

其中对函数fminunc来说．Options（6）为控制搜索方向取默认值0时，是BFGS方法：取1时为DFP方法．Op-算法，

tionsw（7）为控制插值法，其中取默认值0时是混合插值；取1时为立方插值．

参考文献：

［1］王沫然．MATLAB与科学计算［M］．北京：电子工业出版

2005．社，

［2］濮定国．修改的DFP算法［J］．应用数学学报，1990，（2）：21

－24．

［3］韦增欣，李国胤．在一种新型线搜索下DFP算法的全局收敛性

［J］．广西大学学报（自然科学版），2002，（1）：61－66．

［4］袁功林，韦增欣，鲁习文．一个修改的求解非线性对称方程组的

J］．广西科学，2006，（4）：288－292．高斯－牛顿BFGS方法［

［5］刘陶文．BFGS方法及其在求解约束优化问题中的应用［D］．长

2006．沙：湖南大学博士学位论文，

［6］时平平．关于无约束最优化问题的拟牛顿算法研究［D］．太原：

3结语

在当今社会，优化问题已成为科学研究、工程设计和经

2008．太原科技大学硕士学位论文，

［7］何伟．基于新拟牛顿方程的改进的BFGS方法［D］．南京：南京理

2007．工大学硕士学位论文，

［8］王正林，．北京：电子工业出版刘明．精通MATLAB7［M］

2006．社，

［9］周智峰，张明，周海青．基于matlab的最优化问题求解通用程序

J］．机械传动，2004，（6）：29－32．的实现［

济管理等许多领域中一类重要问题，而许多科技人员往往又本文主要针对非线性优化问题，采用拟只注重寻找新方法，

Newton法中的DFP算法和BFGS算法进行一些探讨；并利用MATLAB语言通过几个算例对其进行了仿真分析，认为BFGS算法是拟Newton算法中的最有效的方法之一；同时认为用MATLAB编写程序来研究优化问题，能大大减轻设计人

（责任编校：晴川）