非线性共轭梯度法

最速下降法 and 共轭梯度法

分类： matlab 2011-04-17 17:02 961人阅读 评论(2) 收藏 举报

算法出版优化

注明：程序中调用的函数jintuifa.m golddiv.m我在之前的笔记中已贴出

最速下降法

%最速下降法求解f = 1/2*x1*x1+9/2*x2*x2的最小值，起始点为x0=[9 1]

%算法根据最优化方法（天津大学出版社）97页算法3.2.1编写

%v1.0 author: liuxi BIT

%format long

syms x1 x2 alpha;

f = 1/2*x1*x1+9/2*x2*x2;%要最小化的函数

df=jacobian(f,[x1 x2]);%函数f的偏导

epsilon=1e-6;%0.000001k=0;

x0=[9 1];%起始点

xk=x0;

gk=subs(df,[x1 x2],xk);%起始点的梯度

gk=double(gk);

while(norm(gk)>epsilon)%迭代终止条件||gk||<=epsilon

pk=-gk;%负梯度方向

f_alpha=subs(f,[x1 x2],xk+alpha*pk);%关于alpha的函数

[left right] = jintuifa(f_alpha,alpha);%进退法求下单峰区间

[best_alpha best_f_alpha]=golddiv(f_alpha,alpha,left,right);%黄金分割法求最优步长

xk=xk+best_alpha*pk;

k=k+1;

gk=subs(df,[x1 x2],xk);

gk=double(gk);

end

best_x=xk;%最优点

best_fx=subs(f,[x1 x2],best_x);%最优值

共轭梯度法 %共轭梯度法求解f = 3/2*x1*x1+1/2*x2*x2-x1*x2-2*x1的最小值，起始点为x0=[0 0]

２００８年６月　第２２卷第２期总７２期　北京联合大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｂｅｉｊｉｎｇ　Ｕｎｉｏｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅｓ）　Ｊｕｎ．２００８　Ｖｏ１．２２　Ｎｏ．２　Ｓｕｍ　Ｎｏ．７２　

无约束非线性规划的共轭梯度法研究综述　

张　静　

（１．北京联合大学基础部，北京　１００１０１；２．首都师范大学数学科学学院，北京　１０００３７）　

［摘　要］　共轭梯度法是５０多年来算法研究的热点课题，它最初是基于求解对称正定线性方程　

组提出的，随后推广到求解非线性无约束优化问题。现在，它已经成为数值最优化领域的一类重　

要方法，具有所需存储量小、局部和全局收敛性好的特性。综述了求解无约束非线性规划问题的　

共轭梯度法，总结了它近年来的研究状况，展望了未来的发展趋势。　

［关键词】　共轭梯度法；无约束优化；非线性规划；算法；迭代　

［中图分类号］０　２２１．２　［文献标识码］　Ａ　［文章编号］　１００５．０３１０（２００８）０２－００７２—０５　

Ａ　Ｓｕｍｍａｒｉｚｅｒ　ｏｆ　Ｃｏｎｊｕｇａｔｅ　Ｇｒａｄｉｅｎｔ　Ｍｅｔｈｏｄｓ　ｆｏｒ　Ｓｏｌｖｉｎｇ　

Ｕｎｃｏｎｓｔｒａｉｎｅｄ　Ｎｏｎｌｉｎｅａｒ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｐｒｏｂｌｅｍ　

ＺＨＡＮＧ　Ｊｉｎｇ　・　（１、Ｂａｓｉｃ　Ｃｏｕｒｓｅｓ　Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｂｅｉｊｉｎｇ　Ｕｎｉｏｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１００１０１，Ｃｈｉｎａ；　２．Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃａｌ　Ｓｃｉｅｎｃｅｓ，Ｃａｐｉｔａｌ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００３７，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｏｎｊｕｇａｔｅ　ｇｒａｄｉｅｎｔ　ｍｅｔｈｏｄ　ｈａｓ　ｂｅｅｎ　ｔｈｅ　ｓｕｂｊｅｃｔ　ｏｆ　ｈｏｔ　ｒｅｓｅａｒｃｈ　ｆｏｒ　ｍｏｒｅ　ｔｈａｎ　５０　ｙｅａｒｓ．Ｉｔ　ｓｔａｒｔｅｄ　ｏｕｔ　ａｓ　

第３９卷第２期　玉林师范学院学报（自然科学）　２０　１　８正　ＪＯＵＲＮＡＬ　ＯＦ　ＹＵＬＩＮ　ＮＯＲＭＡＬ　ＵＮＩＶＥＲＳＩＴＹ　Ｖ０１．３９　Ｎｏ．２　（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　非线性极大极小问题一个修正ＦＲ共轭梯度法　口靳文慧’，刘美杏　（１玉林师范学院教务处，广西玉林５３７０００；　２玉林师范学院数学与统计学院／广西高校复杂系统优化与大数据处理重点实验室，广西玉林５３７０００）　［摘要］基于指数光滑化函数，提出了一个求解非线性极大极小问题修正ＦＲ共轭梯度算法．在　每一次迭代中，通过Ａｒｍｊ　ｏ非精确线搜产生步长，利用几何减小策略调整指数光滑化函数中的罚参　数．在适当的假设条件下，新算法具有全局收敛性．　［关键词］非线性极大极小问题；指数光滑化函数；修正ＦＲ共轭梯度法；全局收敛性　［中图分类号］０２２１．２　［文献标识码］Ａ　［文章编号］１００４—４６７１（２０１８）０２—００１４—０５　文考虑求解如下非线性极大极小问题：　ｍｉｎ　ｆ（　）：＝ｍａｘ｛　（　），ｉ∈，），　（１）　其中，＝（１，２，…，ｍ　（　）（ｉ∈Ｉ）是定义在　上的光滑实值函数．　许多决策、金融、工程管理、经济问题都可描述为极大极小问题．然而，其非光滑性使之不能被已有　的光滑优化算法直接求解，故其理论与数值方法的研究较光滑优化困难．但是，通过构造含有参数的指数　型光滑化函数　（亦称熵函数　），如　。ｇ　ｉ＝１唧（　＝　（　）＋／ｚｌ。ｇ∑ｅｘｐ　ｌ　（２）　由０≤／（ｘ，／ｚ）一／（　）￣＜／ｚｌｏｇｍ，故当　一０　时，有／’（ｘ，Ｉｘ）一　（　）．利用一个简单易行的光滑化函数逼　近原问题的目标函数，通过求解序列光滑优化问题去逼近原问题的稳定点，并系统地论证光滑化方法的　收敛性及与原问题的等价性，如文［４—７］．此类算法随着参数　的减小，函数厂（　，　）的计算量较大及数　值试验中可能出现病态．为此，文［４］提出了自适应的精确参数调整策略：当迭代点远离稳定点时，将　参数　控制得较大；当迭代点逼近稳定点时，让参数　减小．文［５］分析了此类算法仅具有次线性收敛性　和计算复杂性，并给出了两种新的参数肛调整策略．　众所周知，共轭梯度法是求解无约束优化问题ｍｉｎ｛．厂（　）Ｉｘ∈Ｒ　卜一类非常有效的方法．共轭梯度法的　关键技术之一为共轭参数　的构造．诸多学者对共轭梯度法进行深入的研究，并且已获得一些收敛性和数　值效果都较为理想的方法　”　．文献［１０］对ＦＲ公式　进行了改进，得到了一个新共轭梯度法：　ｆ　ｏ；　ｄ　＝＝｛——　！　．：—　—　—ｉ　｛　＋　ｏ　ＦＲｄ　一　，ｋ≥ｌ，　（３）　Ｉ　＿ｌ　ｇｋ一１ｌｒ　ｌｌ～ｌＩ２　其中ｇ　（　），卢　＝　Ｌ　，并证明由新公式产生的搜索方向不依赖任何线搜索准则都是一个充分下　［收稿日期］２０１８—０２—２６　［基金项目］广西自然科学基金项目（２０１５ＧＸＮＳＦＢＡ１３９００１）；广西高校科研项目（ＫＹ２０１５ＹＢ２４２）　［作者简介］靳文慧（１９８４～），女，蒙古族，助教，研究方向：非线性极大极小优化问题．

共轭梯度法

对于任意形式的目标函数()fX，在极值点*X附近展开成泰勒级数，且取前三项，有

****2**1()...2TTfXfXfXXXXXfXXX

因在极值点*X处*0fX，而2**()fXHX为()fX在*X的二阶偏导数矩阵，即Hessian矩阵，故

****1().().2TfXfXXXHXXX

对于二次函数来说，若令

2*2*2*221122,,fXfXfXabcxxxx

则

**1(),abHXfXdbc而—常数

则，得到

11221212121122*1**112*2**12**112**1222****11122-1()+--2---1=+--2--1-2---2xxabfXdxxxxbcxxaxxbxxdxxxxbxxcxxdaxxbxxxxcxx

由上式可知，当12*1**2xxXXxx时，得到目标函数的极小值*1()fXfXd，当22(),,...fXdd时，则有等值线族。

令2()fXd，代入上式，则有

112222****2111221()-2---2fXddaxxbxxxxcxx

所以目标函数()fX在*X点附近的等值线方程为

112222****1122-2---0axxbxxxxcxxd

式中，122()ddd常数。由极小值点存在的充分必要条件为二阶导数行列式小于零，即

20bac

在解析几何中已经证明，当20bac时为椭圆，所以二元函数的等值线在极值点附近是近似的同心椭圆族。