10 拟牛顿法.ppt

《10 拟牛顿法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§4.6拟牛顿法牛顿法收敛很快，但需要计算Hesse矩阵，而此矩阵可能非正定，可能导致搜索方向不是下降方向。基本思想：用不包含二阶导数的矩阵近似Hesse矩阵的逆。拟牛顿条件秩1校正DFP(Davidon-Fletcher-Powell)算法：秩2校正BFGS(Broyden-Fletcher-Goldfarb-Shanno)公式及Broyden族校正矩阵秩1校正秩为1注释在一定条件下，收敛且具有二次终止性。无法保证Hk的正定性；即使能，也有可能导致△Hk无界。DFP算法秩为2计算步骤：否是否是重置DFP法具有二次终止性！搜索方向为下降方向共轭DFP法具有二次终止性！BFGS公式BFGS修正

2、公式DFP公式Sherman-Morrison公式经验表明，比DFP公式好。Broyden族Broyden族的所有成员均满足拟牛顿条件。特点不必计算Hesse矩阵。当Hk>0时，算法产生的方向均为下降方向，具有二次终止性。存储量较大。拟牛顿法是无约束最优化方法中最有效的一类算法。作业P21826§5约束优化数学模型一阶最优性条件(必要;充分)不等式约束问题一般约束问题二阶最优性条件(必要;充分)RPPPP起作用约束下降方向:局部概念定理可行方向:局部概念定理可行下降方向反证法不等式约束问题的一阶最优性条件可微互补松弛条件对于凸规划，有下面的一阶充分条件：一般约束问题的一阶最优性条件互补松弛条

3、件对于凸规划，有下面的一阶充分条件：凹函数线性函数凸函数图解：11F(x)(1,1)(2,1)fg1g2几点说明(1)、对于凸规划，K－T条件是充分必要条件。(2)、关于“起作用约束在x*点梯度线性无关”说明x20g1x1x*=(1,0)minf(x)=-x1g1(x)=(1-x1)3-x20g2(x)=x10g3(x)=x20起作用约束为g1,g3，而f(x*)=-10g1(x*)=0-1g3(x*)=01g1g3与线性相关fg1g3,显然不能由线性表示∴x*不满足K－T条件(3)、用K－T条件解minf(x)=(x-3)20x5设K－T点为x*，f(x)

4、=2(x-3)g1(x)=1g2(x)=-1解：写出标准形minf(x)=(x-3)2g1(x)=x0g2(x)=5-x0K－T条件2(x*-3)-w1+w2=0w1x*=0w2(5-x*)=0w10,w20分别考虑：①w10,w20：无解②w10,w2=0：x*=0,w1=-6，不是K－T点③w1=0,w20：x*=5,w2=-4，不是K－T点④w1=0,w2=0：x*=3,f(x*)=0∵凸规划∴x*=3是最小点作业P3192.(1),(3)3.