下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 第1-6节

第1-6节.ppt

第1-6节

zzdxwg
2010-11-20 0人阅读 举报 0 0 暂无简介

简介:本文档为《第1-6节ppt》,可适用于高等教育领域

运筹学(下)运筹学(下)运筹学的研究内容运筹学的研究内容数学规划论:()线性规划(linearprogramming):线性规划问题的建模相对简单有通用算法和计算机软件是运筹学应用最广泛的一个分支()整数规划(integerprogramming):如线性规划中的决策变量要求为整数这类模型的研究构成整数规划分支()目标规划(goalprogramming):解决多目标决策问题。()非线性规划(nonlinearprogramming):如线性规划中的目标函数或约束条件不全是线性的这类模型的研究构成非线性规划分支()动态规划(dynamicprogramming):研究多阶段决策过程最优化的运筹学分支。图论(graphtheory)图论研究由节点和边所组成图形的数学理论和方法。网络分析(networkanalysis)网络分析研究具体网络对象(如铁路网、电力网、通信网)。图论是网络分析的基础。排队论(queuingtheory):研究生产和生活中存在的有形和无形的排队和拥挤现象。存储论(inventorytheory):研究最优存储策略的理论和方法。对策论(gametheory):研究对抗局势问题。系统中参与对抗的各方成为局中人他们各自按照有利于自己的方式活动但又无法精确预测其他局中人的行为。对策论为局中人提供一套定量化和程序化的选择策略的理论和方法。决策论(decisiontheory):随着科学技术的发展要求科学决策取代经验决策。决策论就是研究科学地决策方法。形成问题、提出方案、效果度量、综合评价一直到最优方案的选取。启发式智能优化方法方法不追求严格最优具有启发式思路并借助来自生物学、物理学和其他学科的思想来解决问题。遗传算法(GA)模拟退伙算法(SA)神经网络(NN)模糊逻辑(FL)进化计算(EC)禁忌算法(TS)运筹学应用的工具运筹学应用的工具主要是数学和电子计算机。参考书目参考书目运筹学《运筹学》教材编写组编清华大学出版社运筹学教程胡运权主编清华大学出版社现代优化计算方法邢文训、谢金星编著清华大学出版社非数值并行算法模拟退火算法康立山等著科学出版社非数值并行算法遗传算法康立山等著科学出版社遗传算法的数学基础张文修等编著西安交通大学出版社进化计算王正志等著国防科技大学出版社第一章无约束非线性规划问题第一章无约束非线性规划问题在生产管理和经营活动中经常提出以下两类问题:如何利用有限的人力、物力、财力等资源安排生产使产值最大或利润最高。对给定的任务如何统筹安排以便用最少的人力、物力、财力等资源消耗去完成任务。在生产管理和经营活动中经常提出以下两类问题:如何利用有限的人力、物力、财力等资源安排生产使产值最大或利润最高。对给定的任务如何统筹安排以便用最少的人力、物力、财力等资源消耗去完成任务。对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究构成了运筹学的一个重要分支数学规划论。对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究构成了运筹学的一个重要分支数学规划论。数学规划论数学规划论线性规划(LinearProgramming,LP)非线性规划(NonlinearProgramming,NLP)自年丹捷格(GBDantzig)提出线性规划问题的求解方法单纯形法之后使得线性规划在理论上趋向成熟并在管理决策、经济计划、交通运输业、最优化设计等领域发挥了重要作用。线性规划已成为现代科学管理的重要手段之一。自年丹捷格(GBDantzig)提出线性规划问题的求解方法单纯形法之后使得线性规划在理论上趋向成熟并在管理决策、经济计划、交通运输业、最优化设计等领域发挥了重要作用。线性规划已成为现代科学管理的重要手段之一。在科学管理和其他领域对一些实际问题所建立的数学模型其目标函数和约束条件都是自变量的一次函数即可以归结为线性规划问题。在科学管理和其他领域对一些实际问题所建立的数学模型其目标函数和约束条件都是自变量的一次函数即可以归结为线性规划问题。线性规划问题的特征线性规划属于一类优化问题它们的共同特征为:每个问题都用一组决策变量(x,x,…,xn)表示某一方案。这组决策变量的值代表一个具体方案这些变量一般取值都是非负的。存在一定的约束条件这些约束条件可以用一组线性等式或线性不等式来表示。都有一个要求表达的目标它可用决策变量的线性函数来表示(称为目标函数)按问题的不同要求目标函数实现最大化或最小化。线性规划问题的数学模型满足以上三个条件的数学模型称为线性规划的数学模型:目标函数max(min)z=cxcx…cnxn约束条件axax…anxn≤(=,≥)baxax…anxn≤(=,≥)b…………amxamx…amnxn≤(=,≥)bmx,x,…,xn≥maxz=xx是线性规划maxz=xx不是线性规划不是线性规划但很多实际问题所建立的数学模型其目标函数和约束条件都很难表达为自变量的线性函数。即目标函数和约束条件中含有非线性函数称这种数学规划问题为非线性规划问题。但很多实际问题所建立的数学模型其目标函数和约束条件都很难表达为自变量的线性函数。即目标函数和约束条件中含有非线性函数称这种数学规划问题为非线性规划问题。非线性规划是世纪年代开始形成的一门新兴学科。年HW库恩和AW塔克发表的关于最优性条件(后来称为库恩-塔克条件)的论文是非线性规划正式诞生的一个重要标志。非线性规划是世纪年代开始形成的一门新兴学科。年HW库恩和AW塔克发表的关于最优性条件(后来称为库恩-塔克条件)的论文是非线性规划正式诞生的一个重要标志。年代末到年代末出现了许多解非线性规划问题的有效的算法年代又得到进一步的发展。非线性规划问题在近几十年来得到了长驱发展在管理科学、系统控制、最优设计等许多领域得到越来越广泛的应用。年代末到年代末出现了许多解非线性规划问题的有效的算法年代又得到进一步的发展。非线性规划问题在近几十年来得到了长驱发展在管理科学、系统控制、最优设计等许多领域得到越来越广泛的应用。由于非线性规划问题中其目标函数或约束条件含有非线性函数故求解非线性规划问题要比求解线性规划问题困难得多。由于非线性规划问题中其目标函数或约束条件含有非线性函数故求解非线性规划问题要比求解线性规划问题困难得多。非线性规划问题非线性规划问题线性规划问题单纯形法等通用方法没有适用于各种问题的一般算法第一节基本概念第二节非线性规划的图解法第三节极值问题第四节凸函数和凹函数第五节凸规划第六节跌代算法第七节一维搜索第八节无约束非线性规划问题的解法梯度法第九节无约束非线性规划问题的解法共轭梯度法第十节无约束非线性规划问题的解法牛顿法第十一节无约束非线性规划问题的解法变尺度法第一节基本概念第二节非线性规划的图解法第三节极值问题第四节凸函数和凹函数第五节凸规划第六节跌代算法第七节一维搜索第八节无约束非线性规划问题的解法梯度法第九节无约束非线性规划问题的解法共轭梯度法第十节无约束非线性规划问题的解法牛顿法第十一节无约束非线性规划问题的解法变尺度法第一节基本概念第一节基本概念一、问题的提出例某工厂生产I、II两种产品。已知生产一件产品I所需原材料为吨生产一件产品II所需原材料为(x)吨。工厂共有吨原材料。又知道每生产一件产品I可获得元每生产一件产品II可获得元问应如何制定生产计划才能够使得盈利做大?解:生产计划就是要确定生产产品I和II各多少件。故问题的决策变量为需要生产产品I的数量、生产产品II的数量。设需要生产产品I的数量:x设需要生产产品II的数量:x对生产计划(即产品I和II的生产数量)造成影响的制约因素有一个为:原材料数限制:x(x)x≤问题的目标是使得创造的利润达到最大用z表示所创造的利润值则可表示为:maxz=xx综上所述建立问题的数学模型为:目标函数:maxz=xx约束条件:二、非线性规划问题的特征每个问题都用一组决策变量(x,x,…,xn)表示某一方案。这组决策变量的值代表一个具体方案。存在一定的约束条件这些约束条件可以用一组等式或不等式来表示(不一定是线性的)。都有一个要求表达的目标它可用决策变量的函数来表示(称为目标函数不一定是线性的)按问题的不同要求目标函数实现最大化或最小化。三、非线性规划问题的数学模型目标函数等式约束条件不等式约束条件故非线性规划模型也可表述为如下形式:因等式约束可表示为不等式情况:第二节非线性规划的图解法第二节非线性规划的图解法对于两个变量的非线性规划问题可以用图解法来求解。步骤如下:在直角坐标系中画出由所有约束条件所组成的公共取值范围。画出目标函数在直角坐标系中所代表的曲线并变动直到要离开图中可行域(公共取值范围)为止停止变动。定义:位于同一条目标函数所代表的曲线上的点具有相同的目标函数值因而称它为“等值线”。求出目标函数曲线同可行域相交的边界点坐标值。该边界值即为问题的最优解并代入目标函数求出问题的最优解。注意:线性规划问题的最优解一定可以在其可行域的顶点上达到非线性规划问题的最优解则可能在其可行域中的任意一点达到。例:解:()绘制公共取值范围:xx=:直线xx=xxxx=()绘制等值线并变动。Qxxxx=(x)(x)=z()求出交点坐标Q(,)。()最优解为:x=x=。最优值为:z=例:解:()绘制公共取值范围:xx=:直线xx=的左下方。xxxx=()绘制等值线并变动。xxxx=(x)(x)=zQ()求出交点坐标Q(,)。()最优解为:x=x=。最优值为:z=例:解:()绘制公共取值范围:xxxx≥()绘制等值线并变动。xxxx≥(,)Q()求出交点坐标Q(,)。()最优解为:x=x=。最优值为:f(X*)=第三节极值问题第三节极值问题线性规划的目标函数为线性函数可行域为凸集因而求出的最优解就是整个可行域的全局最优解。非线性规划则不然当非线性规划的目标函数是非线性函数时求出的某个解虽然是一部分可行域上的极值点但却并不一定是整个可行域上的全局最优解。目标函数为线性函数目标函数为非线性函数局部最优就是全局最优局部最优点不是全局最优点设f(X)为定义在n维欧氏空间En的某一区域R上的n元实数其中X=(x,x,…,xn)T。对于X*∈R如果存在某个ε>使所有与X*的距离小于ε的X∈R(即X∈R且‖XX*‖<ε)均满足不等式f(X)≥f(X*)则称X*为f(X)在R上的局部极小点(或相对极小点)f(X)为局部极小值。一、局部极值X*Xn维实数空间上的区域R‖XX*‖<ε如果f(X)≥f(X*)称X*为f(X)在R上的局部极小点(或相对极小点)设f(X)为定义在n维欧氏空间En的某一区域R上的n元实数其中X=(x,x,…,xn)T。对于X*∈R如果存在某个ε>使所有与X*的距离小于ε的X∈R(即X∈R且‖XX*‖<ε)均满足不等式f(X)>f(X*)则称X*为f(X)在R上的严格局部极小点(或严格相对极小点)f(X)为严格局部极小值。X*Xn维实数空间上的区域R‖XX*‖<ε如果f(X)>f(X*)称X*为f(X)在R上的严格局部极小点(或严格相对极小点)设f(X)为定义在n维欧氏空间En的某一区域R上的n元实数其中X=(x,x,…,xn)T。对于X*∈R对于所有X∈R均满足不等式f(X)≥f(X*)则称X*为f(X)在R上的全局极小点f(X)为全局极小值。二、全局极值X*Xn维实数空间上的区域R如果f(X)≥f(X*)称X*为f(X)在R上的全局极小点设f(X)为定义在n维欧氏空间En的某一区域R上的n元实数其中X=(x,x,…,xn)T。对于X*∈R对于所有X∈R均满足不等式f(X)>f(X*)则称X*为f(X)在R上的严格全局极小点f(X)为严格全局极小值。X*Xn维实数空间上的区域R如果f(X)>f(X*)称X*为f(X)在R上的严格全局极小点三、极值点存在的条件极值点存在的必要条件R是n维欧氏空间En上的某一开集f(X)在R上有一阶连续偏导数且在点X*∈R取得局部极值则必有或X*∈R为极值点▽f(X*)=必要条件f(X)在X*处的梯度已知X*=(X,X)=(,)为函数的极小值点。称为f(X)在点X’处的梯度。▽f(X’)的方向为f(X)的等值面(等值线)在点X’处的法线方向沿这个方向函数值增加最快。xx(,)处的法线方向。c梯度计算f(X)=(x)(x)在点处的梯度的方向为等值线(x)(x)=c在点f(X)在极值点X*处的梯度为f(X)在处梯度f(X)在处梯度故不是极值点。极值点存在的充分条件R是n维欧氏空间En上的某一开集f(X)在R上有二阶连续偏导数存在点X*∈R若▽f(X*)=且对于任何非零向量Z∈En有则X*为f(X)的严格局部极小点。此处H(X*)为f(X)在点X*处的海赛(Hesse)矩阵:X*为极小值点▽f(X*)=且充分条件f(X)的海赛矩阵H(X)在X*处正定证明X*=(X,X)=(,)为函数的极小值点。因为海赛矩阵在X*处正定故根据充分条件可知X*=(,)为极值点。二次型的二次齐次多项式称为n元二次型简称二次型。四、二次型的相关知识二次型的矩阵表示二次型可写成当i≠j时aij=aji=xixj项系数的一半aii是xi项的系数。将二次型写成矩阵形式。正定二次型设二次型f(x,x,…,xn)=xTAx如果对任意的x=x,x,…,xnT≠恒有f=xTAx>则称f为正定二次型称对称矩阵A是正定的。f=xTAx≥则称f为半正定二次型称对称矩阵A是半正定的。f=xTAx<则称f为负定二次型称对称矩阵A是负定的。f=xTAx≤则称f为半负定二次型称对称矩阵A是半负定的。正定二次型的判断对称矩阵A为正定的充分必要条件是:A的各阶主子式都为正。对称矩阵A为半正定的充分必要条件是:A的各阶主子式都为正和。对称阵A为负定的充分必要条件是:A的奇数阶主子式为负而偶数阶主子式为正。对称阵A为半负定的充分必要条件是:A的奇数阶主子式为负和而偶数阶主子式为正和。判断将二次型的正定性。A为正定矩阵对应的二次型f为正定二次型。第四节凸函数和凹函数第四节凸函数和凹函数一、凸集的定义凸集、凸函数、凸函数极值的性质是研究非线性规划问题所不可缺少的内容。设K是n维欧氏空间的一个点集若存在任意两点X()∈KX()∈K的连线上的一切点:则称K为凸集。注:X()X()Xαα实心圆、实心球体、实心立方体等都是凸集。凸集没有凹入部分其内部没有空间。两个凸集的交集是凸集。二、凸函数的定义设f(X)为定义在n维欧氏空间En中某个凸集R上的函数若对于任何实数α(<α<)以及R中的任意两点X()和X()恒有:称f(X)为定义在R上的凸函数。设f(X)为定义在n维欧氏空间En中某个凸集R上的函数若对于任何实数α(<α<)以及R中的任意两点X()和X()恒有:称f(X)为定义在R上的严格凸函数。xf(x)x()x()αx()(α)x()凸函数凸函数的定义说明:凸函数上两点间的线性插值不低于这个函数的值。xf(x)x()x()凸函数三、凹函数的定义设f(X)为定义在n维欧氏空间En中某个凸集R上的函数若对于任何实数α(<α<)以及R中的任意两点X()和X()恒有:称f(X)为定义在R上的凹函数。设f(X)为定义在n维欧氏空间En中某个凸集R上的函数若对于任何实数α(<α<)以及R中的任意两点X()和X()恒有:称f(X)为定义在R上的严格凹函数。xf(x)x()x()αx()(α)x()凹函数凹函数的定义说明:凹函数上两点间的线性插值不高于这个函数的值。xf(x)x()x()凸函数xf(x)x()x()非凸非凹函数四、凸函数的性质性质设f(X)为定义在凸集R上的凸函数则对任意实数β≥函数βf(X)也是定义在R上的凸函数。性质设f(X)和f(X)为定义在凸集R上的两个凸函数则其和f(X)=f(X)f(X)仍为定义在R上的凸函数。推论有限个凸函数的非负线性组合βf(X)βf(X)…βmfm(X)βi≥仍为凸函数。五、凹函数的性质性质设f(X)为凹函数则对任意实数β≥函数βf(X)也是凹函数。性质设f(X)和f(X)为两个凹函数则其和f(X)=f(X)f(X)仍为凹函数。推论有限个凹函数的非负线性组合βf(X)βf(X)…βmfm(X)βi≥仍为凹函数。例:证明为凹函数。证明:先证明为凹函数。利用定义任意指定两点a和a证明下式成立即可。上式显然成立。同理可证明也为凹函数。由性质可知f(X)为凹函数。证毕。六、函数凸性的判断判定定理定义。判定定理(一阶条件)设R为n维欧氏空间En上的凸集f(X)在R上具有一阶连续偏导数则f(X)为R上的凸函数的充要条件是:对任意两个不同点X()∈R和X()∈R恒有证明:①必要性f(X)为凸函数设f(X)为R上的凸函数则对任何α(<α<)有②充分性f(X)为凸函数设X()∈R和X()∈R因为X()∈R和X∈R则有则X()和X()连线上的点X∈R因为X()∈R和X∈R则有{{}}f(X)为凸函数一阶条件:凸函数上函数的值高于基于某点导数的线性近似。xf(x)X()凸函数X基于X()判定定理的引申(一阶条件)设R为n维欧氏空间En上的凸集f(X)在R上具有一阶连续偏导数则f(X)为R上的凹函数的充要条件是:对任意两个不同点X()∈R和X()∈R恒有例:证明为凹函数。证明:任选取X()=(a,b)X()=(a,b)即证明上式显然成立证毕。判定定理(二阶条件)设R为n维欧氏空间En上的凸集f(X)在R上具有二阶连续偏导数则f(X)为R上的凸函数的充要条件是:f(X)的海赛矩阵H(X)在R上处处半正定。判定定理的引申(二阶条件)设R为n维欧氏空间En上的凸集f(X)在R上具有二阶连续偏导数则f(X)为R上的凹函数的充要条件是:f(X)的海赛矩阵H(X)在R上处处半负定。例:证明为凹函数。证明:写出f(X)的海赛矩阵如下海赛矩阵处处负定故f(X)为严格凹函数。凸函数凹函数严格凸函数严格凹函数一阶条件凸函数凹函数严格凸函数严格凹函数f(X)的海赛矩阵H(X)在R上处处半负定f(X)的海赛矩阵H(X)在R上处处负定f(X)的海赛矩阵H(X)在R上处处半正定f(X)的海赛矩阵H(X)在R上处处正定二阶条件六、凸函数的极值一般函数:局部极值≠全局极值。凸函数:局部极值=全局极值定理设f(X)为定义在凸集R上的凸函数则它的任一极小点就是它在R上全局极小点而且它的极小点形成了一个凸集。证明:X*是R中的局部极小点Y是R中的任一点。对于充分小的λ存在:f((λ)X*λY)≥f(X*)X*RY因为f(X)是凸函数故(λ)f(X*)λf(Y)≥f((λ)X*λY)(λ)f(X*)λf(Y)≥f(X*)f(Y)≥f(X*)f((λ)X*λY)≥f(X*)(λ)f(X*)λf(Y)≥f((λ)X*λY)即X*也是R中的全局极小点证毕。定理设f(X)是定义在凸集R上的可微凸函数若存在点X*∈R有▽f(X)(XX*)≥则X*是f(X)在R上的全局极小点。证明:因为f(X)是凸函数由一阶条件可知f(X)≥f(X*)▽f(X*)(XX*)又因为▽f(X*)(XX*)≥故:f(X)≥f(X*)即X*为全局极小点。第五节凸规划第五节凸规划满足所有约束约束的解称为可行解。所有可行解得集合称为可行域。某个可行解使目标函数最小称它为最优解。或称这样的非线性规划为凸规划。凸函数凹函数凸规划是一类比较简单又具有重要意义的非线性规划。凸规划的特点:凸规划的可行域为凸集。凸规划的局部最优解就是全局最优解。如凸规划的目标函数为严格凸函数其最优解唯一。线性函数即可视为凸函数又可视为凹函数故线性规划也属于凸规划。例:试分析下列非线性规划。解:利用二阶条件来判断f(X)和g(x)是否为凸函数g(x)为线性函数。海赛矩阵处处正定故f(X)为严格凸函数。f(X)的海赛矩阵为:g(X)的海赛矩阵为:海赛矩阵半负定故f(X)为凹函数(非严格凹函数)。xxxx≥(,)Q最优值为:f(X*)=根据凸规划的定义可知该非线性规划为凸规划。因为该问题只有两个变量故可用图解法求解。作业判断下列非线性规划是否为凸规划。海赛矩阵处处正定故f(X)为严格凸函数。解:f(X)的海赛矩阵为:g(X)的海赛矩阵为:g(X)的海赛矩阵半正定故g(X)为凸函数(非严格凸函数)故问题不是一个凸规划。g(X)的海赛矩阵为:作业判断下列非线性规划是否为凸规划。解:模型变为标准形式。f(X)的海赛矩阵为:f(X)为凸函数。g(X)的海赛矩阵为:g(X)的海赛矩阵半正定故g(X)为凸函数(非严格凸函数)故问题不是一个凸规划。g(X)的海赛矩阵为:第六节跌代算法第六节跌代算法无约束可微函数f(X)的最优解求解方法:令该函数f(X)的梯度=求出驻点。利用充分条件(该函数f(X)的海赛矩阵在驻点处正定)进行判断。该方法的问题:对于n元函数f(X)▽f(X)=往往是一个非线性方程组从而无法求出驻点。如函数f(X)不可微不能使用上述方法。给定一个初始估计X()。按某种算法找到比X()更好的解X()。按某种算法找到比X()更好的解X()。如此循环…。若这个问题有最优解经过多次跌代X(k)将无限接近该最优解其接近程度视跌代次数而定即一、跌代法的思路设拟建工厂有n个配送中心、仓库或原材料供应点。已知:(xi,yi):各配送中心、仓库或原材料供应点的坐标其中i=,,…,n。hi:工厂到i处(配送中心、仓库或原材料供应点)的每单位货物单位距离所需的运输费用又称运输费率。wi:工厂与i处间的物流量。现在欲求此工厂的位置(x,y)使从工厂到各处的总运输费用为最小。设di为工厂到i处的直线运输距离ci为工厂到i处的运输费用H为工厂到各处的总运输费用。但从目标函数形式可以看出目标函数为关于x和y的连续函数又无任何约束其极值点必然位于驻点可考虑求该函数的驻点的方法求出问题的最优解。该问题的目标函数为关于x和y的二元非线性函数无约束条件属于无约束非线性规划问题。问题:根据函数求极值的原理对H分别关于x和y求偏导令偏导数为可得:因为hi、wi和xi均为已知数只须用它们将x表示出来即可。因为hi、wi和xi均为已知数只须用它们将y表示出来即可。造成无法直接写出x和y表达式的根本原因在于di为未知变量其中含有x和y。如果di为已知数的话则x和y的表达式很容易写出。令为已知数则利用上述公式可求得:又因为将x和y代入可得出新的di:为已知数利用公式可求得:又因为将x和y代入可得出新的di:()()()算法步骤()给出厂址的初始位置(xk,yk)()利用式()计算出总运输费用Hk()将(xk,yk)代入式()计算dik()将dik代入式()计算出改进位置(xk,yk)()将(xk,yk)代入式()计算出Hk()将Hk和Hk进行比较:如果Hk<Hk将(xk,yk)代入式()计算出改进位置(xk,yk)如果Hk≥Hk说明位置(xk,yk)便是最优解。一般将重心位置作为初始厂址位置该重心位置距离各客户的距离相等即例:已知拟建工厂有个原材料供应地供应地坐标、原材料供应量和运输费率如下表所示求总运费最佳的厂址。解:()()由于计算机只能进行有限次跌代一般很难得到精确的最优解X()当满足所要求的精度时即可停止跌代。二、跌代法存在的问题选定某一初始点X()并令k=确定搜索方向P(k)从X(k)出发沿搜索方向P(k)求步长λk以产生下一个跌代点X(k):X(k)=X(k)λkP(k)检查得到的新点X(k)是否为极小点或近似极小点。若是停止跌否则令k=k转步骤()继续跌代。三、跌代法的步骤X*P(k)X(k)X(k)P(k)λk搜索方向步长等值线搜索方向P(k)的确定是最为关键的一步确定搜索方向的方法有多种。步长λk的确定也有多种方法:令步长λk等于某一常数任意选取步长λk基于搜索方向确定使目标函数下降最多的最佳步长λk。(该方法称为一维搜索或线搜索)四、搜索方向和步长的确定五、一维搜索(线搜索)一维搜索要求沿射线X(k)=X(k)λkP(k)搜索使目标函数f(X)极小:一维搜索性质:在搜索方向上所得到的最优点处的梯度和该搜索方向正交。X*P(k)X(k)X(k)P(k)λk等值线▽f(X(k))定理:设目标函数f(X)具有一阶连续偏导数X(k)=X(k)λkP(k)按下述规则产生则有证明:若λ为极小点则f(X(k)λP(k))关于λ下的一阶导数为(极值点存在的必要条件)。证毕。六、算法收敛速度的判别一个好的算法不仅要求能够收敛到最优解还要求具有较快的收敛速度。如上式成立则称算法收敛的阶为α或α阶收敛。当α=时称二阶收敛<α<时称超线性收敛当α=且<β<时称线性收敛或一阶收敛。二阶收敛最快其次超线性收敛线性收敛最慢。七、算法的终止准则真正的最优解事先并不知道故常常根据相继两次跌代结果设计终止计算准则:根据相继两次跌代的绝对误差。根据相继两次跌代的相对误差。根据目标函数梯度的模足够小。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/164

第1-6节

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利