最优化方法课程实验报告

《最优化方法及其应用》课程实验报告项目名称：最优化方法课程实验学生姓名：学生学号：指导教师：完成日期：2014-01-04项目一一维搜索算法（一）[实验目的]编写加步探索法、对分法、Newton法的程序。[实验准备]1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤；2．掌握对分法的思想及迭代步骤；3．掌握Newton法的思想及迭代步骤。[实验内容及步骤]编程解决以下问题：1．用加步探索法确定一维最优化问题的搜索区间，要求选取．加步探索法算法的计算步骤：(1)选取初始点，计算．给出初始步长，加步系数，令。(2)比较目标函数值．令kkkhtt1，计算)(11kkt，若kk1，转(3)，否则转(4)。(3)加大探索步长．令，同时，令，转(2)。(4)反向探索．若，转换探索方向，令，转（2）。否则，停止迭代，令。加步探索法算法的计算框图12)(min30tttt2,1,000ht])0[)(0[max00ttt，或，)(00t00h10kkkhh1,ktt,1kktt1kk0k,kkhh1ktt11min{}max{}kkattbtt，，，程序清单加步探索法算法程序见附录1实验结果运行结果为：2．用对分法求解，已知初始单谷区间，要求按精度，分别计算．对分法迭代的计算步骤：(1)确定初始搜索区间],[ba，要求。(2)计算],[ba的中点)(21bac．(3)若0)(c，则ca，转(4)；若0)(c，则ct*，转(5)；若0)(c，则cb，转(4)．(4)若||ba，则)(21*bat，转(5)；否则转(2)．(5)打印*t，结束对分法的计算框图)2()(minttt]5,3[],[ba3.0001.0'()0'()0ab，程序清单对分法程序见附录2实验结果运行结果为：3．用Newton法求解，已知初始单谷区间，要求精度．Newton法的计算步骤(1)确定初始搜索区间],[ba，要求(2)选定0t(3)计算(4)若||0tt，则tt0，转（3）；否则转（5）．(5)打印，结束．Newton法的计算框图12)(min3ttt]1,0[],[ba01.0'()0'()0ab，000'()/()tttt()tt，程序清单Newton法程序见附录3实验结果运行结果为：项目二一维搜索算法（二）[实验目的]编写黄金分割法、抛物线插值法的程序。[实验准备]1．掌握黄金分割法的思想及迭代步骤；2．掌握抛物线插值法的思想及迭代步骤。[实验内容及步骤]编程解决以下问题：1．用黄金分割法求解，已知初始单谷区间，要求精度．)2()(minttt]5,3[],[ba001.0黄金分割法迭代步骤：(1)确定)(t的初始搜索区间][ba，．(2)计算)(382.02abat(3)计算)(618.01abat(4)若||21tt，则打印221*ttt，结束；否则转(5)．(5)判别是否满足21：若满足，则置12122，，ttta然后转(3)；否则，置)()(22221211tabttttb，，，，然后转(4)．黄金分割法的计算框图：程序清单黄金分割法程序见附录4实验结果运行结果为：2．用抛物线插值法求解，已知初始单谷区间．抛物线插值法的计算步骤：（1）)()(0tt，所以相对0t来说t是好点，故划掉区间],[20tt，保留],[01tt为新区间，故置)()(0202tttt，，)()(00tttt，，1t保持不变；（2）)()(0tt，所以相对t来说0t是好点，故划掉区间],[1tt，保留],[2tt为新区间，故置)()(11tttt，，0t与2t保持不变；程序清单抛物线插值法程序见附录5实验结果运行结果为：项目三常用无约束最优化方法（一）[实验目的]3728)(min23xxxxf001.0]20[][，，，ba编写最速下降法、Newton法（修正Newton法）的程序。[实验准备]1．掌握最速下降法的思想及迭代步骤。2．掌握Newton法的思想及迭代步骤；3．掌握修正Newton法的思想及迭代步骤。[实验内容及步骤]编程解决以下问题：1．用最速下降法求．最速下降法计算步骤（1）0,0)(,)0(kX令精度容许误差取初始点（2）)()()(kkXfp计算（3）0)()(4,,?否则转取若是迭代终止检验kkXXp（4）))(()(min:)()()()(0一维搜索求最优步长kkkkkkpXfpXf0)()()1(2,1:,转令令kkpXXkkkk最速下降法的计算框图程序清单最速下降法程序见附录6实验结果运行结果为：22120min()25[22]0.01TfXxxX，，，2．用Newton法求，初始点．Newton法的计算步骤（1）给定初始点(0)x，及精度0，令0k；（2）若()()kfX，停止，极小点为()kx，否则转步骤（3）；（3）计算12()()kfX，令1()()()()()kkksHXfX；令(1)()()kkkxxs，1kk，转步骤（2）。程序清单Newton法程序见附录7实验结果运行结果为：3．用修正Newton求22121212min()60104fXxxxxxx0[00]0.01TX，，，初始点．修正Newton的计算步骤（1）给定初始点(0)x，及精度0，令0k；（2）若()()kfX，停止，极小点为()kx，否则转步骤（3）；（3）计算12()()kfX，令1()()()()()kkksHXfX；（4）用一维搜索法求，使得()()()()()0()min()kkkkkfXSfXS，令(1)()()()kkkkXXS，1kk，转步骤（2）。程序清单修正Newton程序见附录8实验结果运行结果为：项目四常用无约束最优化方法（二）实验目的编写共轭梯度法、变尺度法（DFP法和BFGS法）程序。221212min()4(1)2(1)10fXxxxx0[00]0.01TX，，实验准备1．掌握共轭方向法的思路及迭代过程；2．掌握共轭梯度法的思想及迭代步骤；3．掌握DFP法和BFGS法的思想及迭代步骤。实验内容及步骤编程解决以下问题：1．用共轭梯度法求得，取初始点，．共轭梯度法算法步骤（1）给定初始点(0)x，及精度0；（2）若(0)()fx，停止，极小值点为(0)x，否则转步骤（3）；（3）取(0)(0)()pfx，且置0k；（4）用一维搜索法求kt，使得()()()()0()minkkkkktfxtpfxtp，令，(1)()()kkkkxxtp，转步骤5；（5）若(1)()kfx，停止，极小值点为(1)kx，否则转步骤（6）；（6）若1kn，令(0)()nxx，转步骤（3），否则转步骤（7）；（7）令(1)(1)()()kkkkpfxp，2(1)2()()()kkkfxfx，置1kk，转步骤（4）。程序清单共轭梯度法程序见附录9实验结果运行结果为：)4min(2221xxTX]11[0，01.02．用共轭梯度法求，自定初始点，．程序清单共轭梯度法程序见附录9实验结果运行结果为：3．用DFP法求，初始点．DFP法的具体迭代步骤如下：（1）给定初始点，迭代精度，维数n（2）置0→k，单位矩阵I→，计算。（3）计算搜索方向（4）进行一维搜索求，使221212min()2fXxxxx01.02212min()4(5)(6)fXxx01.0]98[0，，TX得迭代新点（5）检验是否满足迭代终止条件‖‖≤？若满足，停止迭代，输出最优解,；否则进行下一步。（6）检查迭代次数，若k=n，则置，转向步骤(2)；若kn，则进行下一步。（7）计算：。然后，置k+1→k，转向步骤（3）。DFP法的计算框图程序清单DFP法程序见附录10实验结果运行结果为：项目五常用约束最优化方法[实验目的]编写外点罚函数法、外点罚函数法的程序。[实验准备]1．掌握外点罚函数法的思想及迭代步骤；2．掌握内点罚函数法的思想及迭代步骤。[实验内容及步骤]编程解决以下问题：1．用外点罚函数法编程计算精度．外点法的计算步骤：（1）给定初始点x(0)，初始罚因子)1(，放大系数c1；允许误差e0,设置k=1；（2）以x(k-1)作为搜索初始点，求解无约束规划问题)()(minxPxf，令x(k)为所求极小点。（3）当exPk)()(，则停止计算，得到点x(k)；否则，令)()1(kkc，返回（2）执行。程序清单外点罚函数法程序见附录11实验结果实验结果为，，，01)(0ln)(..)(min2112121xxXhxXgtsxxXf510运行结果为：2．用内点罚函数法编程计算初始点取为，初始障碍因子取，缩小系数取．内点罚步骤：（1）给定初始内点Sx)0(，允许误差e0，障碍参数)1(，缩小系数)1,0(b，置k=1；（2）以)1(kx为初始点，求解下列规划问题：SxtsxBxfk..)()(min)(，令)(kx为所求极小点（3）如果exBkk)()()(，则停止计算，得到结果)(kx，（4）否则令)()1(kkb，置k=k+1，返回（2）。内点罚计算框图．，，001..)1(31min21231xxtsxxTX]43[0，101u1.0c程序清单内点罚函数法程序见附录12实验结果运行结果为：附录1#includeiostream.h#includeLIMITS.H#defineMAX20480doublefun(doublex){returnx*x*x-2*x+1;}doubleMax_Num(doublea,doubleb){if(ab)returna;elsereturnb;}doubleMin_Num(doublea,doubleb){if(ab)returna;elsereturnb;}voidStepAdding_Search(double&a,double&b){doublet[MAX]={0};doubleh[MAX]={0};doublef[MAX]={0};doubleresult=0;doublep=2;t[0]=0;h[0]=1;f[0]=fun(t[0]);for(intk=0;kMAX-1;k++){t[k+1]=t[k]+h[k];f[k+1]=fun(t[k+1]);if(f[k+1]f[k]){h[k+1]=p*h[k];result=t[k];t[k]=t[k+1];f[k]=f[k+1];}elseif(k==0){h[k]=-h[k];result=t[k+1];}else{a=Min_Num(result,t[k+1]);b=Max_Num(result,t[k+1]);}}}intmain(){doublea=0.0;doubleb=0.0;StepAdding_Search(a,b);cout该问题的根的搜索空间是:[a,b]\n;return0;}附录2#includeiostream.h#includemath.h#defineeps0.001doublefun(doublex){returnx*x+2*x;}doublediff_fun(doublex){return2*x+2;}doubledichotomy(doublea,