非线性最优化.pptx
《非线性最优化.pptx》由会员分享,可在线阅读,更多相关《非线性最优化.pptx(147页珍藏版)》请在咨信网上搜索。
1、 非线性最优化 非线性最优化的基本概念非线性最优化的基本概念 一维搜索一维搜索 无约束极值问题的解法无约束极值问题的解法 最优性条件最优性条件 有约束极值问题的解法有约束极值问题的解法 二次规划二次规划 可行方向法可行方向法 制约函数法制约函数法 第一节 基本概念1.1 非线性问题的提出非线性问题的提出 例例1 某公司经营两种设备,第一种设备售价某公司经营两种设备,第一种设备售价30元,第二种设备售价元,第二种设备售价450元。根据统计,售出一件第元。根据统计,售出一件第一种设备所需要的营业时间平均是一种设备所需要的营业时间平均是0.5小时,第二种小时,第二种设备是设备是(2+0.25 x2
2、)小时小时,其中其中x2是第二种设备的售出是第二种设备的售出数量。已知该公司在这段时间内的总营业时间为数量。已知该公司在这段时间内的总营业时间为800小时,试决定使其营业额最大的营业计划小时,试决定使其营业额最大的营业计划.分析:设该公司经营第一种设备分析:设该公司经营第一种设备x1件件,第二种设备第二种设备 x2 件,其营业额为件,其营业额为f(X),依题意列出问题的数学模型:,依题意列出问题的数学模型:maxf(X)=30 x1+450 x2 s.t.0.5 x1+(2+0.25 x2)x2 800 x1 0,0,x2 0 0 例例1 1的目标函数为自变量的线性函数,但的目标函数为自变量的
3、线性函数,但其第一个约束条件却是自变量的二次函数,其第一个约束条件却是自变量的二次函数,因而它是非线性规划问题。因而它是非线性规划问题。若规划问题的若规划问题的目标函数目标函数及及约束函数约束函数中中至少至少有一个有一个是非线性函数是非线性函数,则称这种规划为非线性则称这种规划为非线性规划。规划。非线性规划的数学模型非线性规划的数学模型 非线性规划的数学模非线性规划的数学模型常表示成以下形式型常表示成以下形式 Minf(X)hi(X)=0 i=1,2,m gj(X)0 j=1,2,l非线性规划的数学模型非线性规划的数学模型可以写成以下形式可以写成以下形式 Minf(X)gj(X)0 j=1,2
4、,ln注注1.min-f(X)=-maxf(x);n注注2.gj(X)0-gj(X)0;n注注3.hi(X)=0hi(X)0,-hi(X)0.1.2 极值问题极值问题 设设f(X)为定义在为定义在n维欧氏空间维欧氏空间 En 的某一区的某一区域域S上的上的n元实函数,其中元实函数,其中X=(x1,x2 xn)T T .局部极小点局部极小点(值值):对于对于 X*S S,如果存在,如果存在某某0,0,使所有与使所有与X*的距离小于的距离小于的的X XS,S,均均满足不等式满足不等式f(X)f(f(X)f(X*),),则称则称X*为为f(X)在在S上的局部极小点上的局部极小点,f(f(X*)为局部
5、极小值。为局部极小值。严格局部极小点严格局部极小点(值值):对于所有对于所有XX*且且与与X*的距离小于的距离小于的的X XS,f(X)f(S,f(X)f(X*),),则称则称X*为为f(X)在在S上的严格局部极小点,上的严格局部极小点,f(f(X*)为为严格严格局部极小值。局部极小值。全局极小点全局极小点(值值):对于所有的对于所有的X X S S,都,都有有f(X)f(f(X)f(X*),),则称则称X*为为f(X)在在S上的全局上的全局极小点,极小点,f(f(X*)为全局极小值。为全局极小值。严格全局极小点严格全局极小点(值值):对于所有对于所有X XS且且XX*,都有都有f(X)f(f
6、(X)f(X*),),则称则称X*为为f(X)在在R上的严格全局极小点,上的严格全局极小点,f(f(X*)为严格全局极为严格全局极小值。小值。将上述不等式反向,即可以得到相应的将上述不等式反向,即可以得到相应的极大点和极大值的定义。极大点和极大值的定义。极值点存在的必要条件和充分条件极值点存在的必要条件和充分条件 定理定理1(必要条件必要条件)设设S是是n维欧氏空间维欧氏空间E En n 上上的某一开集,的某一开集,f(X)在在S上有一阶连续偏导数,上有一阶连续偏导数,且在点且在点X*S取得局部极值,则必有取得局部极值,则必有 或或 其中其中 为函数为函数f(X)在点在点X*处的梯度处的梯度。
7、定理定理2(充分条件充分条件)设设S是是n维欧氏空间维欧氏空间E En n 上上的某一开集,的某一开集,f(X)在在S上具有二阶连续偏导数,上具有二阶连续偏导数,X*S S,若,若f(X*)=0,且对任何非零向量且对任何非零向量ZEn有有 ZTH(X*)Z0 (1.4)则则X*为为f(X)的严格局部极小点的严格局部极小点.此处此处H(X*)为为f(X)在点在点X*处的海赛处的海赛(Hesse)矩阵矩阵.1.3 凸函数和凹函数凸函数和凹函数 凸函数凸函数:设设f(X)是定义在是定义在n维欧氏空间维欧氏空间E En n 中某个中某个凸集凸集S上的函数上的函数,若对任何实数若对任何实数a(0a 1)
8、以及以及S中的中的任意两点任意两点X(1)和和X(2),恒有恒有 f(aX(1)+(1-a)X(2)af(X(1)+(1-a)f(X(2)(1.5)则称则称f(X)为定义在为定义在S上的凸函数上的凸函数.严格凸函数严格凸函数:若对每一个若对每一个a(0a1)以及以及S中的中的任意两点任意两点X(1)和和X(2),X(1)X(2),恒有,恒有 f(aX(1)+(1-a)X(2)0,0,使得对任意使得对任意XXN N N N(X X X X*),),),),恒有恒有恒有恒有f(X)f(X)f(X)f(X)f(f(f(f(X X X X*).).).).令令令令y y y y是是是是S中中任一点,则
9、对充分小的任一点,则对充分小的(0,1)(0,1),有有 y+(1-y+(1-y+(1-y+(1-)X X X X*N N N N(X X X X*),),),),从而从而 f(f(y+(1-y+(1-y+(1-y+(1-)X X X X*)f(f(f(f(X X X X*)(1)(1)(1)(1)由于由于f f为凸函数为凸函数,有有 f(f(y)+(1-y)+(1-)f(X)f(X*)f(f(y+(1-y+(1-)X X*)(2)(2)由由(1)(1)、(2)(2),得到,得到 f(y)f(y)f(f(X X*).).所以所以X X*为全局最小点为全局最小点.记记a:=a:=minf=f(m
10、inf=f(X X*),),则则S上的极小点的集合上的极小点的集合 S Sa a=X|XR,f(X)X|XR,f(X)aa.由性质由性质3 3知知,S Sa a是是凸凸集集.用反证法证明定理用反证法证明定理6:设设X X X X*S是一个局部极小点是一个局部极小点,则存在则存在0,0,使得对使得对任意任意XSXSN N N N(X X X X*),),),),恒有恒有恒有恒有 f(X)f(X)f(X)f(X)f(f(f(f(X X X X*).).).).假设假设假设假设X X X X*非全局最小非全局最小非全局最小非全局最小,则存在则存在则存在则存在X X X X S,S,使得使得f(f(X
11、 X X X*)f()f(X X X X).).由由S S的凸性的凸性,对任意对任意0,1,0,1,X X X X+(1-+(1-+(1-+(1-)X X X X*S,S,由由X X*X X X X,取取(0,1).(0,1).因为因为因为因为11时时,可使可使 X X X X+(1-+(1-+(1-+(1-)X X X X*SSN N N N(X X X X*).).).).又由又由f f凸凸,有有 f(f(X X X X+(1-+(1-+(1-+(1-)X X X X*)f(f(X X X X)+(1-)+(1-)+(1-)+(1-)f(X)f(X)f(X)f(X*)f(f(X X X X
12、*)+(1-)+(1-)+(1-)+(1-)f(X)f(X)f(X)f(X*)=f(X =f(X =f(X =f(X*)此与此与此与此与X X X X*局部极小矛盾局部极小矛盾局部极小矛盾局部极小矛盾.所以所以所以所以X X X X*为全局最小点为全局最小点为全局最小点为全局最小点.定理定理7 设设f(X)是定义在凸集是定义在凸集S上的可微凸上的可微凸函数函数,若存在点若存在点X X*S,使得所有的使得所有的XS有有 f(Xf(X*)T T(X-X(X-X*)00则则X X*是是f(X)f(X)在在S S上的最小点上的最小点(全局极小点全局极小点).).证证 由定理由定理3,3,对任意对任意X
13、 XS有有 f(X)f(Xf(X*)+)+f(Xf(X*)T T(X-X(X-X*)f(Xf(X*),),证毕证毕.注注1:1:若若f(f(X X*)=0,=0,则则f(f(X X*)T T(X-XX-X*)0.0.注注2:2:最小点未必唯一最小点未必唯一,但凸集上严格凸函但凸集上严格凸函数的最小点唯一数的最小点唯一.注注3:3:对凹函数也有上述类似的结果对凹函数也有上述类似的结果.注注2:2:最小点未必唯一最小点未必唯一,但凸集上严格凸函但凸集上严格凸函数的最小点唯一数的最小点唯一.事实上事实上,设有两个最小点设有两个最小点X XY,Y,令令 Z=Z=X+(1-)Y,(0,1),X+(1-)
14、Y,(0,1),则则 f(Z)f(Z)f(X)+(1-)f(Y)f(X)+(1-)f(Y)f(X)+f(X)+(1-)f(X)=f(X),(1-)f(X)=f(X),矛盾矛盾.例例4 求函数求函数f(x x1 1,x x2 2,x,x3 3)=x x1 1+2x x3 3+x2x3-x x1 12 2-x x2 22 2 x x3 32 2 的极值的极值.非线性规划的数学模型非线性规划的数学模型 Minf(X)(1.1)hi(X)=0 i=1,2,m (1.2)gj(X)0 j=1,2,l (1.3)满足约束条件满足约束条件(1.2)和和(1.3)的点称为的点称为可行点可行点(可行解可行解),
15、所有可行点的集合称为所有可行点的集合称为可行域可行域.若某个可行解使目标函数若某个可行解使目标函数(1.1)最小,就称最小,就称它为它为最优解最优解.1.4 凸规划凸规划n考虑非线性规划考虑非线性规划 MinxS f(X)S=X|gj(X)0,j=1,2,l假定其中假定其中f(X)为凸函数为凸函数,g gj j(X)(j=1,2,l)为凹为凹函数函数.这样的非线性规划称为这样的非线性规划称为凸规划凸规划.凸规划具有如下性质凸规划具有如下性质:1)凸规划的可行域为凸集凸规划的可行域为凸集;2)凸规划的局部最优解为全局最优解凸规划的局部最优解为全局最优解;3)凸规划的最优解集为凸集凸规划的最优解集
16、为凸集;4)f(X)为严格凸函数时为严格凸函数时,凸规划的最优解唯一凸规划的最优解唯一.n例例5.5.求解非线性规划求解非线性规划迭代法基本思想迭代法基本思想:为了求函数为了求函数f(X)的最优解的最优解,首先给定一个首先给定一个初始估计初始估计X X(0)(0),然后按某种然后按某种算法算法找出比找出比X X(0)(0)更好更好的解的解X X(1)(1)(对极小化问题对极小化问题,f(f(X X(1)(1)f(X)f(Xf(X(0)(0),),再按此种规则找出再按此种规则找出比比X X(1)(1)更好的解更好的解X X(2)(2),.如此即可得到一个解的如此即可得到一个解的序列序列X X(k
17、)(k).若这个解序列有极限若这个解序列有极限X X*,即即limlimkkXX(k)(k)-X-X*=0,=0,则称它则称它收敛收敛于于X X*.若这算法是有效的若这算法是有效的,那么它所产生的解的那么它所产生的解的序列将收敛于该问题的最优解序列将收敛于该问题的最优解.1.5 下降迭代算法下降迭代算法 若由某算法所产生的解的序列若由某算法所产生的解的序列X(k)使使目标函数值目标函数值f(X(k))逐步减小逐步减小,就称这算法为就称这算法为下降算法下降算法.假定已迭代到点假定已迭代到点X X(k)(k),若从若从X X(k)(k)出发沿任出发沿任何方向移动都不能使目标函数下降何方向移动都不能
18、使目标函数下降,则则X X(k)(k)是是局部极小点局部极小点,迭代停止迭代停止.若从若从X X(k)(k)出发至少存出发至少存在一个方向可使目标函数值有所下降在一个方向可使目标函数值有所下降,则可则可选能使目标函数值下降的某方向选能使目标函数值下降的某方向P P(k)(k),沿这,沿这方向迈进适当的一步方向迈进适当的一步,得到下一个迭代点得到下一个迭代点X X(k+1)(k+1),并使并使 f(f(X X(k+1)(k+1)f()f(X X(k)(k).).这相当于在射线这相当于在射线X=X=X X(k)(k)+PP(k)(k)上选定新点上选定新点 X X(k+1)(k+1)=X X(k)(
19、k)+k kP P(k)(k)X X(k+1)(k+1)=X X(k)(k)+k kP P(k)(k)其中其中P P(k)(k)称为称为搜索方向搜索方向;k k称为称为步长步长或或步长因子步长因子.下降迭代法的步骤下降迭代法的步骤:(1)(1).选定某一初始点选定某一初始点X X(0)(0),并令并令k:=0.k:=0.(2).(2).确定搜索方向确定搜索方向P P(k)(k).(3).从从X(k)出发,沿方向出发,沿方向P(k)求步长求步长k,以产生下一个迭代点以产生下一个迭代点X(k+1).(4).检查得到的新点检查得到的新点X(k+1)是否为极小点是否为极小点或近似极小点或近似极小点.若
20、是,则停止迭代若是,则停止迭代.否则,令否则,令k:=k+1,转回,转回(2)继续进行迭代继续进行迭代.在下降迭代步骤中在下降迭代步骤中,关键是关键是选取搜索方向选取搜索方向P P(k)(k)和和确定步长确定步长k.确定步长确定步长k k的常用方法:的常用方法:(1)令令k等于某一常数等于某一常数.(2)只要能使目标函数值下降只要能使目标函数值下降,可选取任意可选取任意k k.(3)沿射线沿射线X=X(k)+P(k)求目标函数求目标函数f(X)的极小的极小:k k:()=Minf(X X(k)(k)+PP(k)(k)称这一过程为称这一过程为(最优最优)一维搜索一维搜索或线搜索或线搜索,以此以此
21、确定的步长为确定的步长为最佳步长最佳步长.一维搜索在搜索方向上所得最优点处的一维搜索在搜索方向上所得最优点处的梯度和该搜索方向正交梯度和该搜索方向正交.定理定理8 设目标函数设目标函数f(X)C(1),X X(k+1)(k+1)按下按下述规则产生述规则产生k:Minf(X(k)+P(k)X(k+1)=X(k)+kP(k)则有则有 f(X(k+1)TP(k)=0.证证 设设()=f(X()=f(X(k)(k)+PP(k)(k),),则由则由 ()=()=f(Xf(X(k)(k)+PP(k)(k)T T P P(k)(k)=0=0 得得 =k k f(Xf(X(k)(k)+k kP P(k)(k)
22、T T P P(k)(k)=f(Xf(X(k+1)(k+1)T TP P(k)(k)=0=0 n迭代计算法的收敛速度迭代计算法的收敛速度 设序列设序列x(k)收敛于收敛于x*,若存在与若存在与k无关的数无关的数,0+和和1,使得使得 X(k+1)-X*X(k)-X*,kk0则称则称x(k)收敛的阶为收敛的阶为,或或x(k)阶收敛阶收敛.当当=2时,称为二阶收敛时,称为二阶收敛,也称也称x(k)具有具有二阶敛速;当二阶敛速;当12时,称为超线性收敛;时,称为超线性收敛;当当=1,01时时,称为线性收敛或一阶收敛称为线性收敛或一阶收敛.n常用的收敛的准则有以下几种常用的收敛的准则有以下几种:(1)
23、.根据相继两次迭代的根据相继两次迭代的绝对误差绝对误差 X X(k+1)(k+1)-X X(k)(k)|f(|f(X X(k+1)(k+1)-f()-f(X X(k)(k)|)|(2).(2).根据相继两次迭代的根据相继两次迭代的相对误差相对误差 X X(k+1)(k+1)-X X(k)(k)/X X(k)(k)|f(|f(X X(k+1)(k+1)-f()-f(X X(k)(k)|/|f()|/|f(X X(k)(k)|)|这时要求分母不接近于零这时要求分母不接近于零.(3).根据目标函数梯度的模足够小根据目标函数梯度的模足够小 f(Xf(X(k k))其中其中是事先给定的足够小的正数是事先
24、给定的足够小的正数.n下单峰概念下单峰概念 设设f:RR,a,b为为R的区间的区间.若存在点若存在点x*a,b,使得,使得f(x)在在a,x*上严格单减,在上严格单减,在x*,b上严格单增,则称上严格单增,则称a,b是是f(x)的下单峰的下单峰区间,区间,f(x)是是a,b上的下单峰函数上的下单峰函数.n定理定理9 f(x)是是a,b上的下单峰函数上的下单峰函数,对任意对任意的的x1,x2a,b,x1x2,那么那么(1).若若f(x1)f(x2),则则x1,b是是f(x)的下单峰区间的下单峰区间;(2).若若f(x1)f(x2),则,则a,x2是是f(x)的下单峰区间的下单峰区间.第二节第二节
25、 一维搜索一维搜索2.1 Fibonacci法(分数法)Fibonacci Fibonacci使用使用对称搜索对称搜索的方法的方法,逐步缩短逐步缩短所考察的区间所考察的区间,它能以尽量少的函数求值次数它能以尽量少的函数求值次数,达到预定的某一缩短率达到预定的某一缩短率.2.2 0.618法法(黄金分割法黄金分割法)若用不变的区间缩短率若用不变的区间缩短率0.618,代替分数代替分数法每法每次不同的缩短率次不同的缩短率,就得到了黄金分割法就得到了黄金分割法.0.618.0.618法是一种法是一种等速对称等速对称进行试探的方法进行试探的方法,每次的试每次的试点均取在区间长度的点均取在区间长度的0.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 非线性 优化
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。