最优化设计程序设计

《最优化设计程序设计》由会员分享，可在线阅读，更多相关《最优化设计程序设计（17页珍藏版）》请在金锄头文库上搜索。

1、 最优化方法 实验报告 学生姓名：学生姓名： 魏魏 峰峰 学学 号：号： 201318050224 班班 级：级： 数学与数学与应用数学应用数学 131802 完成时间：完成时间： 2016 年年 6 月月 20 日日 最优化方法上机实验报告 1 一、一、实验题目实验题目 共轭梯度法求解方程及方程组 二、二、实验目的实验目的 1.进一步熟悉理解掌握共轭梯度法解法思路，提高 matlab 编程能力 2.学习并撑握共轭梯度法的原理、方法及应用，并了解不同无约束优化方法的区别、优缺点及特殊要求。 3.熟悉使用共轭梯度法求解无约束非线性规划问题的原理； 4.在掌握原理的基础上熟练运用此方法解决问题；

2、5.解决问题的同时分析问题，力求达到理论与实践的相统一； 三、实验原理、基本理论三、实验原理、基本理论 共轭梯度法为求解线性方程组而提出。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。 共轭梯度法的基本思想是把共轭性与最速下降方法相结合， 利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。 无约束最优化方法的核心问题是选择搜索方向.在本次实验中,我们运用基于共轭方向的一种算

3、法共轭梯度法 目前已研究出很多种无约束优化方法， 它们的主要不同点在于构造搜索方向上的差别。 （1）间接法要使用导数，如梯度法、 （阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方最优化方法上机实验报告 2 法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中每一个共

4、轭向量都是依赖于迭代点处的负梯度而构造出来。 共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵的作用仅仅是用来由已知向量 P 产生向量 W=AP，这不仅可充分利用的稀疏性，而且对某些提供矩阵较为困难而由已知向量 P 产生向量 W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像 SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 考虑线性方程组 Axb 的求解问题，其中 A 是给定的 n 阶对称正定矩阵，b 是给定的 n 维向量，x是待求解的 n 维向量.为此,定义二次泛函 ( )2TTxx Axb

5、x. 定理 1 :设 A 对称正定,求方程组Axb的解，等价于求二次泛函( )x的极小值点. 定理 1 表明，求解线性方程组问题就转化为求二次泛函( )x的极小值点问题.求解二次函数极小值问题， 通常好像盲人下山那样， 先给定一个初始向量0x，确定一个下山方向0p，沿着经过点0x而方向为0p的直线00xxp找一个点 1000xxp， 使得对所有实数有 00000xpxp， 1(0,1,2,)kkk kskxx最优化方法上机实验报告 3 即在这条直线上1x使( )x达到极小.然后从1x出发，再确定一个下山的方向1p，沿着直 线11xxp再跨出一步，即找到1使得 x在2111xxp达到极小： 11

6、111xpxp. 重复此步骤，得到一串 012, 和 012,pp p ， 称kp为搜索方向，k为步长.一般情况下，先在kx点找下山方向kp，再在直线kkxxp上确定步长k使 ,kkkkkxpxp 最后求出1kkkkxxp.然而对不同的搜索方向和步长，得到各种不同的算法. 由此，先考虑如何确定k.设从kx出发，已经选定下山方向kp.令 kkfxp 2TT kkkkkkxpA xpbxp 22TT kkkkkp Apr px， 其中kkrbAp.由一元函数极值存在的必要条件有 220TT kkkkfp Apr p 所确定的即为所求步长k，即 T kk kT kkr p p Ap. 步长确定后，即

7、可算出 1kkkkxxp. 此时，只要0T kkr p ，就有 1kkkkkkxxxpx 最优化方法上机实验报告 4 2220T kkTT kkkk kkT kkr pp Apr pp Ap 即1kkxx. 再考虑如何确定下山方向kp.易知负梯度方向是( )x减小最快的方向，但简单分析就会发现负梯度方向只是局部最佳的下山方向，而从整体来看并非最佳.故采用新的方法寻求更好的下山方向共轭梯度法. 下面给出共轭梯度法的具体计算过程: 给定初始向量0x，第一步仍选用负梯度方向为下山方向，即00pr，于是有 00 0100010 00,TTr rxxp rbAxp Ap. 对以后各步，例如第 k+1 步

8、（k1）,下山方向不再取kr，而是在过点由向量kr和1kp所张成的二维平面 21 |, ,kkkx xxrpR 内找出使函数下降最快的方向作为新的下山方向kp.考虑在2上的限制： 1,()kkkxrp 11()()T kkkkkkxrpA xrp 12()T kkkbxrp. 计算关于, 的偏导得： 11112,2,TTT kkkkkkTT kkkkr Arr Apr rr AppAp 其中最后一式用到了10T kkr p，这可由kr的定义直接验证.令 0 ， 即知在2内有唯一的极小值点 最优化方法上机实验报告 5 001kkkxxrp， 其中0和0满足 00101011, 0.TTT kkk

9、kkk TT kkkkr Arr Apr r r AppAp 由于0kr 必有00，所以可取 0 1 001kkkkpxxrp 作为新的下山方向.显然，这是在平面2内可得的最佳下山方向.令0 1 0k，则可得 1 1 11.T kk kT kkr Ap pAp 注：这样确定的kp满足10T kkp Ap，即kp与1kp是相互共轭的. 总结上面的讨论，可得如下的计算公式： T kk kT kkr p p Ap ， 1kkkkxxp， 11kkrbAx， 1T kk kT kkrAp p Ap ， 11kkkkprp. 在实际计算中，常将上述公式进一步简化，从而得到一个形式上更为简单而且对称的计算

10、公式.首先来简化1kr的计算公式： 11()kkkkkkkkrbAxbA xprAp. 因为kAp在计算k是已经求出，所以计算1kr时可以不必将1kx代入方程计算，而是从递推关系1kkkrbAp得到. 再来简化k和k的计算公式.此处需要用到关系式 最优化方法上机实验报告 6 1110,TTT kkkkkkr rr prp 1,2,k . 从而可导出 1111,TT kkk krrr ， 111TTT kkkkkkk kkp Apprrp r 1111TT kkkkkk kkrrpr r. 由此可得 ,T kk kT kkr r p Ap， 11.T kk kT kkrr r r. 程序框图如下

11、所示：程序框图如下所示： 最优化方法上机实验报告 7 四、实验内容：四、实验内容： （1）问题描述）问题描述 用共轭梯度法求二次函数 22 1212112( ,)242f x xxxxx x的极小点及极小值。 （2 2）计算求解）计算求解 解：已知初始点1,1T 迭代精度 0.001 1）第一次沿负梯度方向搜寻 计算初始点处的梯度： 为一维搜索最佳步长，应满足 得： 2）第二次迭代 代入目标函数 0120212244()422xxfxxxx0100 00 01414 1212 xxd1002()min()min(40203)ff xxd00.2512 0.5x11()2fx21200()50.

12、2520()ff xx110 02()1.5f dxd22( )(22 )2(0.5 1.5 ) 2(22 )(0.5 1.5 )4(22 )( )f x 最优化方法上机实验报告 8 由 得 从而有： 因 收敛。 （3）程序）程序 运行：运行：打开 matlab,确定 conjugate_grad_2d.m 文件夹为当前目录。在命令窗中输入：f=conjugate_grad_2d(1,1,0.001)，选择不同的初始点坐标0,0,0,1,1,0,和迭代精度 0.01，0.0001,进行运行时，需要多次调用 conjugate_grad_2d 函数。 程序及说明：程序及说明： function

13、f=conjugate_grad_2d(x0,t) %用共轭梯度法求已知函数 f(x1,x2)=x12+2*x22-4*x1-2*x1*x2 的极值点 %已知初始点坐标：x0 %已知收敛精度：t %求得已知函数的极值：f x=x0; syms xi yi a; %定义自变量，步长为符号变量 f=xi2+2*yi2-4*xi-2*xi*yi; %创建符号表达式 f fx=diff(f,xi); %求表达式 f 对 xi 的一阶求导 fy=diff(f,yi); %求表达式 f 对 yi 的一阶求导 fx=subs(fx,xi,yi,x0); %代入初始点坐标计算对 xi 的一阶求导实值 fy=s

14、ubs(fy,xi,yi,x0); %代入初始点坐标计算对 yi 的一阶求导实值 fi=fx,fy; %初始点梯度向量 count=0; %搜索次数初始为 0 while double(sqrt(fx2+fy2)t %搜索精度不满足已知条件 s=-fi; %第一次搜索的方向为负梯度方向 if countToo many input arguments。查阅了些书籍，上网求助，最后查明原因是自定义的 M 文件名称与Matlab 内部函数名相似， 导致无法运行。 浪费了大量的时间与精力， 庆幸的是，经过自己的努力， 纠正错误， 按时完成了作业。 我相信在以后学习工作中 Matlab会提供更大的帮助。 最优化方法上机实验报告 11 一、一、 实验名称实验名称 外点罚函数法 二、二、 实验目的实验目的 1.在本次实验中，我们采用外点罚函数法，通过这次实验，我们要熟练掌握它的原理：它对违反约束的点在目标函数中