
最速下降法课件.ppt
38页Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,,,*,,,,,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,,,*,4.1,非线性规划数学模型,4.2,凸函数和凸规划,4.3,一维搜索,4.4,无约束优化问题的解法,,第四章 无约束最优化问题,,4.1 非线性规划数学模型第四章 无约束最优化问题,第四节 无约束优化问题的解法,最速下降法,Newton,法,拟,Newton,法,共轭梯度法,,,第四章 无约束最优化问题,,第四节 无约束优化问题的解法最速下降法第四章 无约束最优化问,,一,.,最速下降法,收敛性问题的基本概念,最速下降法的迭代原理,最速下降法的迭代步骤,最速下降法的举例,最速下降法的收敛结论,,,,无约束问题,4-4,一.最速下降法收敛性问题的基本概念无约束问题4-4,,1.,收敛性问题的基本概念,定义,4-9,若序列 ,对于 ,存在正整数,当 时,有 ,即,则称 收敛于 ,记为,,无约束问题,4-4,1.收敛性问题的基本概念定义4-9若序列 ,对于,,,定义,4-10,1.,收敛性问题的基本概念,若 收敛于 ,且满足,则,p,称为 收敛于 的阶。
当,p,= 1,时,称为,一阶收敛,;,当,p,= 2,时,称为,二阶收敛,;,当 时,称为,超线性收敛,;,,无约束问题,4-4,定义4-101.收敛性问题的基本概念若 收敛于,当 时,,当,p,= 2,,时, 同阶无穷小,若 收敛于 ,且满足,则,p,称为 收敛于 的阶1.,收敛性问题的基本概念,定义,4-10,,无约束问题,4-4,当 时, 当 p = 2 时,,当 时,,当,p,= 1,,时, 同阶无穷小,若 收敛于 ,且满足,则,p,称为 收敛于 的阶1.,收敛性问题的基本概念,定义,4-10,,无约束问题,4-4,当 时, 当 p = 1 时,,,,定义,4-10,1.,收敛性问题的基本概念,若 收敛于 ,且满足,则,p,称为 收敛于 的阶当,p,= 1,时,称为,一阶收敛,;,当,p,= 2,时,称为,二阶收敛,;,当 时,称为,超线性收敛,;,,无约束问题,4-4,最速下降法,Newton,法,拟,Newton,法,定义4-101.收敛性问题的基本概念若 收敛于,,定义,4-12,,若某算法对于任意正定二次目标函数,,,从任意初始点出发,,,都能经过,有限次迭代,达到其极小点,,,则该算法称为具有,二次终止性,的算法或二次收敛算法,.,1.,收敛性问题的基本概念,结论:,当,Q,为正定阵时,称,f,(,X,),为正定二次函数。
正定二次函数 有唯一,全局极小点:,,无约束问题,4-4,定义4-12 若某算法对于任意正定二次目标函数,从任意初,,一,.,最速下降法,收敛性问题的基本概念,最速下降法的迭代原理,最速下降法的迭代步骤,最速下降法的举例,最速下降法的收敛结论,,,,,无约束问题,4-4,一.最速下降法收敛性问题的基本概念无约束问题4-4,是,X,(,k,),处函数值下降最快的方向当 时,,p,(,k,),是,f,(,X,),在,X,(,k,),处的,下降方向,函数,f,(,X,),在,X,(,k,),处的负梯度方向,梯度的性质:,2.,迭代原理,证明:,结论:,一元函数泰勒公式:,,无约束问题,4-4,是X(k)处函数值下降最快的方向当,,2.,迭代原理,,,,最优步长,,无约束问题,4-4,2.迭代原理最优步长无约束问题4-4,,,,最速下降法迭代原理:,,一维搜索找极小点 :,1),确定,[0 , 1],,精度,0.1,2),用,0.618,法得到,,,,0,4,0.5,3,1,84,,无约束问题,4-4,最速下降法迭代原理:一维搜索找极小点 :1)确定[0,,,,最速下降法迭代原理:,,,,无约束问题,4-4,最速下降法迭代原理: 无约束问题4-4,,,,,,2.,迭代原理,最优步长,最优步长,,无约束问题,4-4,2.迭代原理最优步长最优步长无约束问题4-4,,,,,,线性收敛,2.,迭代原理,最优步长,最优步长,得到一个点列:,可以证明:,,无约束问题,4-4,线性收敛2.迭代原理最优步长最优步长得到一个点列:可以证明:,,2.,迭代原理,证明:,,无约束问题,4-4,2.迭代原理证明:无约束问题4-4,,一,.,最速下降法,收敛性问题的基本概念,最速下降法的迭代原理,最速下降法的迭代步骤,最速下降法的举例,最速下降法的收敛结论,,,,,,无约束问题,4-4,一.最速下降法收敛性问题的基本概念无约束问题4-4,,无约束问题,4-4,,3.,迭代步骤,无约束问题4-43.迭代步骤,,3.,迭代步骤,注释:,(,一阶必要条件,),1,0,停机准则:,设 连续,(,即,f,(,X,),连续可微,),,无约束问题,4-4,3.迭代步骤注释:(一阶必要条件)10 停机准则:设,,注释:,,,,3.,迭代步骤,一维搜索最优解的梯度 与搜索方向,正交,2,0,结论:,证明:,,无约束问题,4-4,注释:3.迭代步骤一维搜索最优解的梯度,,注释:,最速下降法的任何两个相邻搜索方向,正交,(,垂直,),,,,3.,迭代步骤,3,0,结论:,,无约束问题,4-4,注释:最速下降法的任何两个相邻搜索方向正交(垂直)3.迭代步,,注释:,3.,迭代步骤,4,0,将一维搜索用于正定二次函数:,则可以得到 的表达式:,,无约束问题,4-4,注释:3.迭代步骤40 将一维搜索用于正定二次函数:则可以得,,证明:,3.,迭代步骤,4,0,将一维搜索用于正定二次函数:,则可以得到 的表达式:,注释:,该公式具有普遍性,,无约束问题,4-4,证明:3.迭代步骤40 将一维搜索用于正定二次函数:则可以得,,注释:,3.,迭代步骤,4,0,将一维搜索用于正定二次函数:,则可以得到 的表达式:,,无约束问题,4-4,注释:3.迭代步骤40 将一维搜索用于正定二次函数:则可以得,,注释:,3.,迭代步骤,5,0,将最速下降法用于正定二次函数:,则可以得到 的表达式:,,无约束问题,4-4,注释:3.迭代步骤50 将最速下降法用于正定二次函数:则可以,,注释:,3.,迭代步骤,5,0,最速下降法,,Newton,法,拟,Newton,法,共轭梯度法的区别,就是,搜索方向,p,(,k,),取得不同。
无约束问题,4-4,注释:3.迭代步骤50 最速下降法,Newton法,拟New,,一,.,最速下降法,收敛性问题的基本概念,最速下降法的迭代原理,最速下降法的迭代步骤,最速下降法的举例,最速下降法的收敛结论,,,,,,,无约束问题,4-4,一.最速下降法收敛性问题的基本概念无约束问题4-4,,4.,举例,例,4-10,解:,用最速下降法求 的极小点,,迭代两次无约束问题,4-4,4.举例例4-10解:用最速下降法求,,4.,举例,例,4-10,解:,用最速下降法求 的极小点,,迭代两次无约束问题,4-4,4.举例例4-10解:用最速下降法求,,解:,1,,无约束问题,4-4,解:1无约束问题4-4,,解:,1,,无约束问题,4-4,解:1无约束问题4-4,,解:,2,,无约束问题,4-4,解:2无约束问题4-4,,解:,3,(太大)继续迭代最速下降法收敛速度很慢注释:,,无约束问题,4-4,解:3(太大)继续迭代最速下降法收敛速度很慢注释:无约束,,例,4-10,注释:,本例的计算结果如图,4,-14(,P,156,).,迭代点在向极小点靠近的过程中形成一条锯齿折线,,,这种现象称为,锯齿现象,.,这是由于最速下降法的,任何两个相邻搜索方向正交,.,因此,,,从直观上可以看到,,,在远离极小点的地方,,,每次迭代可使目标函数值有较大的下降,,,但,越接近极小点,,,由于锯齿现象,,,函数值下降速度显著变慢,.,优点:,计算简单,,,存储量小,.,缺点:,由于锯齿现象,,,迭代后期收敛速度变慢,.,4.,举例,用最速下降法求 的极小点,,迭代两次。
无约束问题,4-4,例4-10注释: 本例的计算结果如图4-14(P156,,一,.,最速下降法,收敛性问题的基本概念,最速下降法的迭代原理,最速下降法的迭代步骤,最速下降法的举例,最速下降法的收敛结论,,,,,,,,无约束问题,4-4,一.最速下降法收敛性问题的基本概念无约束问题4-4,,5.,最速下降法的收敛结论,线性收敛,最速下降法所产生的迭代点列,是 的局部最优解,,无约束问题,4-4,5.最速下降法的收敛结论线性收敛最速下降法所产生的迭代点列是,,一,.,最速下降法,收敛性问题的基本概念,最速下降法的迭代原理,最速下降法的迭代步骤,最速下降法的举例,最速下降法的收敛结论,,,,,,,,作业:,P245 14,作业:,P155 14,一.最速下降法收敛性问题的基本概念作业:P245 14作业,。












