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