《无约束最优化问题的一般结构.ppt》由会员分享,可在线阅读,更多相关《无约束最优化问题的一般结构.ppt(22页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、无约束最优化问题的一般结构现在学习的是第1页,共22页4.1 无约束问题的最优性条件一元函数的最优性条件无约束问题局部最优解的必要条件无约束问题局部最优解的充分条件无约束凸规划问题最优解的充要条件例子现在学习的是第2页,共22页一元函数的最优性条件()若()为的局部极小点,则若则为的严格局部极小点;若()为的局部极小点,则:现在学习的是第3页,共22页一阶导数为0,非极值点充分条件的一个例子:f(x)=x3,f(0)=0,f(0)=0现在学习的是第4页,共22页无约束问题局部最优解的必要条件定理1:若为的局部极小点,且在内一阶连续可导,则注:(1)仅仅是必要条件,而非充分条件(2)满足的点称为
2、驻点驻点分为:极小点,极大点,鞍点现在学习的是第5页,共22页无约束问题局部最优解的必要条件(续)定理2:若为的局部极小点,且在内二阶连续可导,则半正定现在学习的是第6页,共22页无约束问题局部最优解的充分条件定理3:若在内二阶连续可导,且正定,则为严格局部极小点注:如果负定,则为严格局部极大点现在学习的是第7页,共22页无约束凸规划问题最优解的充要条件定理4:设在上是凸函数且有一阶连续偏导数,则为的全局极小点的充要条件是现在学习的是第8页,共22页例1:利用极值条件解下列问题:解:令即:得到驻点:现在学习的是第9页,共22页函数的海赛阵:由此,在点处的海赛阵依次为:现在学习的是第10页,共2
3、2页由于矩阵不定,则不是极小点负定,则不是极小点,实际上它是极大点正定,则是局部极小点现在学习的是第11页,共22页4.2 无约束问题的最速下降算法现在学习的是第12页,共22页问题提出问题:在点处,沿什么方向下降最快?分析:考查:显然当时,取极小值因此:结论:负梯度方向使下降最快,亦即最速下降方向现在学习的是第13页,共22页最速下降法算法Step1:给出Step2:计算如果停Step3:计算下降方向Step4:计算步长因子Step5:令转步.现在学习的是第14页,共22页现在学习的是第15页,共22页4.3 算法的收敛性收敛含义实用收敛准则(停机准则)收敛速度算法的二次终止性最速下降算法的
4、收敛性现在学习的是第16页,共22页收敛含义现在学习的是第17页,共22页实用收敛准则现在学习的是第18页,共22页收敛速度现在学习的是第19页,共22页算法的二次终止性定义:若某个算法对于任意的正定二次函数,从任意初始点出发,都能经过有限步迭代达到极小点,则称该算法具有二次终止性。原因:正定二次函数具有某些好的性质,一个好的算法应该能在有限步内达到其极小点对于一个一般的目标函数,若在其极小点处的Hesse矩阵正定,则目标函数在该极小点附近于一个正定二次函数相似,因此对于正定二次函数好的算法,对一般目标函数也会有好的性质。现在学习的是第20页,共22页最速下降算法的收敛性定理1:设在上存在且一致连续,则最速下降法产生的序列满足或者对某个有或者定理2:二次连续可微,其中是个正常数,对任何给定的初始点最速下降算法或有限终止,或者设且或者现在学习的是第21页,共22页最速下降法优点(1)程序设计简单,计算量小,存储量小,对初始点没有特别要求(2)有着很好的整体收敛性,即使对一般的目标函数,它也整体收敛现在学习的是第22页,共22页