最优化马昌凤第五章作业

求解无约束最优化问题的非单调MFR,MPRP方法
李湘;曾金平
【期刊名称】《应用数学》
【年(卷),期】2008(0)S1
【摘要】本文在求解无约束最优化问题的MFR共轭梯度法和MPRP共轭梯度法中引入两种非单调线性搜索技术.我们证明在适当条件下采用非单调线性搜索的MFR算法和MPRP算法具有全局收敛性.数值结果表明非单调线性搜索具有优越性.
【总页数】6页(P6-11)
【关键词】MFR方法;MPRP方法;非单调线性搜索;全局收敛性
【作者】李湘;曾金平
【作者单位】湖南大学数学与计量经济学院;东莞理工学院软件学院
【正文语种】中文
【中图分类】O224
【相关文献】
1.求解无约束最优化非单调自确定信赖域算法 [J], 刘宁;马昌凤
2.求解非线性无约束优化问题的一种非单调信赖域方法 [J], 孙刘平
3.非单调信赖域方法求解无约束非光滑优化问题 [J], 高雷阜;于冬梅
4.求解无约束优化问题的非单调自适应信赖域方法 [J], 徐明明
5.求解无约束优化问题的非单调自适应信赖域方法 [J], 徐明明
因版权原因，仅展示原文概要，查看原文内容请购买。

最优化方法及其Matlab程序设计习题作业暨实验报告学院：数学与信息科学学院班级：12级信计一班姓名：李明学号：1201214049第三章 最速下降法和牛顿法一、上机问题与求解过程1、用最速下降法求212221216423),(x x x x x x f --+=的极小值。

解：仿照书上编写最速下降法程序如下：function [x,val,k]=grad(fun,gfun,x0) %功能：用最速下降法求解无约束化问题：min f(x) %输入：x0是初始点，fun,gfun 分别是目标函数和梯度 %输出：x,val 分别是近似嘴有点和最优值，k 是迭代次数 maxk=5000;rho=0.5;sigma=0.4;%一开始选择时选择的rho 和sibma 选择的数据不够合理，此处我参照书上的数据编写数据 k=0;epsilon=1e-5; while (k<maxk)g=feval(gfun,x0); %计算梯度 d=-g;%计算搜索方向if (norm(d)<epsilon),break ;end m=0;mk=0; while (m<20)%Armijo 搜索if (feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d) mk=m;break ;%直接利用Armijo 搜索公式,一开始的时候没有记住公式编写出现错误 end m=m+1; endx0=x0+rho^mk*d; k=k+1; end x=x0;val=feval(fun,x0) %求得每一个的函数值然后仿照书上建立两个目标函数和梯度的M 文件：function f=fun(x)f=3*x(1)^2+2*x(2)^2-4*x(1)-6*x(2); function g=gfun(x) g=[6*x(1)-4,4*x(2)-6]';选取初始点为']0,0[，调用函数程序，得出最小极值点为']500.1,6667.0[，极小值为8333.5-，在界面框中输入的程序如下：[x,val,k]=grad('fun','gfun',x0) val = -5.8333 x =0.6667 1.5000 val =-5.8333 k = 10从结果可以看出迭代次数为10次，如果选取不同的初值点则迭代次数不一样，但是极小值相同。

[课时作业]1．某学生检查了1 000个处于有丝分裂期的细胞，其中有692个处于前期，105个处于中期，35个处于后期，168个处于末期。

据此可判断洋葱根尖有丝分裂()A．细胞周期中各期相对持续时间关系是前期>末期>中期>后期B．进行得比较旺盛C．细胞周期中分裂期持续的时间比分裂间期要短D．分裂期中前期持续的时间短解析：选A。

由处于不同时期的细胞个数可推知相应时期在一个细胞周期中所占的时间长短，处于某时期的细胞个数越多，说明该时期在一个细胞周期中所占时间越长。

根据细胞分裂各时期时间持续长短无法判断洋葱根尖有丝分裂进行得是否旺盛。

据题中数据，也无法比较分裂间期与分裂期持续时间的长短。

2．用光学显微镜观察有丝分裂过程，如果仅从细胞分裂周期来看，图中植物作为实验材料最适合的是()解析：选D。

用显微镜观察有丝分裂过程，主要观察分裂期的细胞，因此应选择细胞周期短(分裂旺盛)且分裂期相对较长的作实验材料。

3．菠菜根的分生区细胞不断分裂使根向远处生长，在分裂过程中不会出现的是() A．细胞分裂间期，中心体的两个中心粒各自产生一个新的中心粒B．细胞分裂中期，染色体形态较固定、数目较清晰C．细胞分裂前期，核膜和核仁逐渐消失D．细胞分裂末期，高尔基体参与细胞壁的形成解析：选A。

菠菜是高等植物，细胞内没有中心体，纺锤体是由植物细胞两极发出纺锤丝所形成的。

4．在“观察植物细胞有丝分裂”实验中，三位实验人员制作洋葱根尖装片的操作步骤(“＋”表示操作，“—”表示未操作)如下表所示：实验人员操作取材解离漂洗染色制片甲根尖1～3 mm处－＋＋＋续实验操作人员取材解离漂洗染色制片乙根尖1～3 mm处＋－＋＋丙根尖5～7 mm处＋＋＋＋A．细胞重叠、染色体着色很浅不清楚、细胞分散染色体清楚B．细胞分散但看不到染色体、染色体着色清楚、细胞分散染色体清楚C．细胞重叠、染色体着色很浅不清楚、细胞着色清楚但看不到染色体D．染色体着色很浅不清楚、细胞分散染色体清楚、细胞分散染色体清楚解析：选C。

[键入公司名称]一题目要求：1.分别用①牛顿法和②变尺度法求解优化问题min f(x)=x^2-2*x*y+4*y^2+x-3*y2.利用①外点法和②内点法解下列约束问题 min f(x)=(x-3)^3+(y-2)^2 s.t. h(x)=x1+x2-4≤0二基本思想牛顿法：应用基本迭代公式X k+1=X k +t k P k 中，每轮迭代在迭代的起始点X K 处用一个适当的二次函数来近似该点处的目标函数，由此用点X K 指向近似二次函数极小点的方向来构造搜索方向Pk. 设()f x 是二次可微实函数，n k x R ∈，Hesse 矩阵()2k f x ∇正定。

在k x 附近用二次Taylor 展开近似f ，()()()()()()212TTk T k k k k f x s q s f x s f x s s f x s +≈=+∇+∇ k s x x =-，()()k q s 为()f x 的二次近似。

将上式右边极小化，便得： ()()121k k k k x x f x f x -+⎡⎤=-∇∇⎣⎦，这就是牛顿法的迭代公式。

在这个公式里，步长因子1k α=。

令()()2,k k k k G f x g f x =∇=∇，则上式也可写成：11k k k k x x G g -+=-显然，牛顿法也可以看成在椭球范数kG⋅下的最速下降法。

事实上，对于()()T k k k f x s f x g s +≈+，k s 是极小化问题minn Tk s R g ss∈的解。

该极小化问题依赖于所取的范数，当采取2l 范数时，k k s g =-，所得方法为最速下降法。

当采用椭球范数kG⋅时，1k k k s G g -=-，所得方法即为牛顿法。

对于正定二次函数，牛顿法一步即可达到最优解。

而对于非二次函数，牛顿法并不能保证有限次迭代求得最优解，但由于目标函数在极小点附近近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般是快的。

最优化方法及其Matlab程序设计习题作业暨实验报告学院：数学与信息科学学院班级：12级信计一班姓名：李明学号：1201214049第二章 线搜索技术一、上机问题与求解过程 1、用0.618法求解 .1)(min 2--=x x x f 初始区间]1,1[-，区间精度为50.=0δ. 解：当初始时不限制近似迭代函数值得大小，编写程序运行结果为：从结果可以看出迭代次数为9次，极小点为5016.0，极小点的函数值为2500.1-。

根据人工手算，极小值点应该为500.0，所以在设计程序的时候添加函数值误差范围，并取范围为10101-⨯。

编写的设计函数程序并调试改正如下：function [s,fs,k,G,FX,E]=gold(f,a,b,H,F) %输入：% f:目标函数，a ：搜索区间左侧端点；b:搜索区间右侧端点； % H ：搜索区间允许范围；F ：搜索区间函数值允许范围； %输出：% s:近似极小值点：fa ：近似极小点数值；k:迭代次数：% FX ：近似迭代函数值；E=[h,fh]，h 为近似区间误差，fh 为函数值误差 t=(sqrt(5)-1)/2;h=b-a; p=a+(1-t)*h;q=a+t*h;fa=feval(f,a);fb=feval(f,b); fp=feval(f,p);fq=feval(f,q); k=1;G(k,:)=[a,p,q,b];%初始时错误语句：G(1,:)=[a,p,q,b]; %初始调试的时候没有注意到后面需要开辟k 行空间 FX(k,:)=[fa,fp,fq,fb];while (abs(fa-fb)>F) ((b-a)>H) if (fp<fq)b=q;fb=fq;q=p;fq=fp;h=b-a;p=a+(1-t)*h;fp=feval(f,p); %初始时错误语句：b=q;fb=fq;h=b-a;q=a+t*h;fq=feval(f,q); %初始调试的时候对0.618方法没有充分理解所以出现错误 elsea=p;fa=fp;p=q;fp=fq;h=b-a;q=a+t*h;fq=feval(f,q);%初始时错误语句：a=p;fa=fp;h=b-a;p=a+(1-t)*h;fp=feval(f,p); %初始调试的时候对0.618方法没有充分理解所以出现错误 end极小点(s) 迭代次数搜索区间误差 函数值误差 0.501690.04260.0006k=k+1;G(k,:)=[a,p,q,b];%初始时错误语句：G(1,:)=[a,p,q,b]; %初始调试的时候没有注意到前面已经开辟k 行空间 FX(k,:)=[fa,fp,fq,fb]; end if (fp<fq) s=p;fs=fp; elses=q;fs=fq; endh=b-a;fh=abs(fb-fa);%选取试探点最小的数值为近似点，并且计算出以上为搜索区间的的最后误差以及函数值误差 E=[h,fh];在命令窗口内输入如下命令：[s,fs,k,G,FX,E]=gold(inline('s^2-s-1'),-1,1,0.05,1e-10) 回车之后得到如下数据结果：附：在窗口中输出的结果如下>> [s,fs,k,G,FX,E]=gold(inline('s^2-s-1'),-1,1,0.05,1e-10) s = 0.5000 fs = -1.2500 k = 24 G =-1.0000 -0.2361 0.2361 1.0000 -0.2361 0.2361 0.5279 1.0000 0.2361 0.5279 0.7082 1.0000极小点 极小点数值 迭代次数 搜索区间误差 函数值误差 0.500-1.250024410321.0-⨯0000.00.2361 0.4164 0.5279 0.70820.4164 0.5279 0.5967 0.70820.4164 0.4853 0.5279 0.59670.4164 0.4590 0.4853 0.52790.4590 0.4853 0.5016 0.52790.4853 0.5016 0.5116 0.52790.4853 0.4953 0.5016 0.51160.4953 0.5016 0.5054 0.51160.4953 0.4992 0.5016 0.50540.4953 0.4977 0.4992 0.50160.4977 0.4992 0.5001 0.50160.4992 0.5001 0.5006 0.50160.4992 0.4997 0.5001 0.50060.4997 0.5001 0.5003 0.50060.4997 0.5000 0.5001 0.50030.4997 0.4999 0.5000 0.50010.4999 0.5000 0.5000 0.50010.5000 0.5000 0.5000 0.50010.5000 0.5000 0.5000 0.50000.5000 0.5000 0.5000 0.50000.5000 0.5000 0.5000 0.5000 FX =1.0000 -0.7082 -1.1803 -1.0000 -0.7082 -1.1803 -1.2492 -1.0000 -1.1803 -1.2492 -1.2067 -1.0000 -1.1803 -1.2430 -1.2492 -1.2067 -1.2430 -1.2492 -1.2406 -1.2067 -1.2430 -1.2498 -1.2492 -1.2406 -1.2430 -1.2483 -1.2498 -1.2492 -1.2483 -1.2498 -1.2500 -1.2492 -1.2498 -1.2500 -1.2499 -1.2492 -1.2498 -1.2500 -1.2500 -1.2499 -1.2500 -1.2500 -1.2500 -1.2499 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.2500 -1.25001.0e-04*0.3121 0.00002、用0.618法求解.12)(min 3+-=x x x f的近似最优解，初始搜索区间为]3,0[，区间精度为50.=1δ. 解：当初始时不限制近似迭代函数值得大小，编写程序运行结果为：从结果可以看出迭代次数为8次，极小点为8115.0，极小点的函数值为0886.0-。

第五章 拟牛顿法§5.1 拟牛顿法牛顿法具有收敛速度快的优点，但需要计算Hesse 矩阵的逆，计算量大。

本章介绍的拟牛顿法将用较简单的方式得到Hesse 矩阵或其逆的近似，一方面计算量不大，另一方面具有较快的收敛速度，这类算法是无约束最优化问题最重要的求解方法。

一、拟牛顿条件设()f x 在nR 上二次可微，为了获得Hesse 矩阵2()()G x f x =∇在1k x +处的近似，先研究如下问题。

考虑()f x 在1k x +附近的二次近似：1111111)()()()2()(TT k k k k k k g x x G x f x f x x x x +++++++-+--≈. 两边求导，有 111()()k k k g x g G x x +++≈+- 令k x x =，有 111()k k k k k g g G x x +++≈+- 再令 1k k k s x x +≈-，1k k k y g g +≈-则有 1k k k y G s +≈ 或 11kkk G y s -+≈.因此，我们要求构造出的Hesse 矩阵的近似1k B +或Hesse 矩阵逆的近似1k H +应分别满足：1k k k B s y += 或 1k kk H y s += （5.1）它们均称之为拟牛顿条件。

二、一般拟牛顿算法1） 给出初始点0x R ∈，0H I =，0ε>，:0k =.2） 若k g ε≤，停止；否则，计算k k k d H g =-（拟牛顿方向）.3） 沿方向k d 进行线性搜索，0k α>（可以是精确，也可非精确）.令1k k k k x x d α+=+. 4） 校正k H 产生1k H +，使拟牛顿条件满足. 5） :1k k =+， 转2）拟牛顿法较之牛顿法有下述优点： 1） 仅需梯度（牛顿法需Hesse 矩阵）；2） k H 保持正定，因而方向具有下降性质（而牛顿法中k G 可能不定）； 3） 每次迭代需2()O n 次运算，而牛顿法需3()O n 次运算。

非线性规划的罚函数算法摘要：最优化理论和方法是一门十分活跃的学科，罚函数法是将约束问题无约束化的一种主要方法。

本文简要介绍了最优化问题的优化算法，主要介绍了非线性规划的罚函数算法的基本理论和相应的发展过程。

关键词：最优化理论；非线性规划；惩罚函数法1 前言最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一门独立的学科还是在上世纪40年代末．Dantzing在1947年提出求解一般线性规划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技术的巨大发展，至今短短的几十年，它得到了迅猛的发展．现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等方面得到了广泛的应用，成为一门十分活跃的学科．约束非线性规划问题广泛见于工程、国防、经济等许多重要领域．求解约束非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法．罚函数方法通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时，求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为精确罚函数，否则称为序列罚函数．针对传统罚函数的定义而言，若罚函数是简单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不光滑的；若罚函数是精确的、光滑的，则它一定是复杂的．因此我们的工作是对传统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结果．我们把这类罚函数称为简单光滑乘子精确罚函数．所谓简单的，即罚函数中包含原问题中的目标函数和约束函数而不包含它们的梯度，若罚函数中包含有原问题中目标函数和约束函数的梯度，则称为是复杂的．2求解最优化问题的介绍和方法分类2.1最优化问题及分类优化技术是一种以数学为基础的，用于求解各种工程问题优化解的应用技术，作为一个重要的科学分支一直受到人们的广泛注视，并在诸多工程领域得到迅速的推广和应用，如系统控制、人工智能、模式识别、生产调度、计算机工程等等。