无约束最优化幻灯片.ppt

《无约束最优化幻灯片.ppt》由会员分享，可在线阅读，更多相关《无约束最优化幻灯片.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、无约束最优化第1页，共18页，编辑于2022年，星期六 二、二、局部解的局部解的最优性条件最优性条件定理定理4 41 1（一阶必要条件一阶必要条件）设）设 具有连续的一阶偏具有连续的一阶偏导数，若导数，若 是无约束问题的局部解，则是无约束问题的局部解，则定理定理4 42 2（二阶必要条件二阶必要条件）设）设 具有连续的具有连续的二阶偏导数，若二阶偏导数，若 是无约束问题的局部解，则是无约束问题的局部解，则 半正定。半正定。第2页，共18页，编辑于2022年，星期六定理定理4 43 3（二阶充分条件二阶充分条件）设）设 具有连续的具有连续的二阶偏导数，若在二阶偏导数，若在 处满足：处满足：正定，

2、正定，则则 是无约束问题的严格局部解。是无约束问题的严格局部解。定义定义2 2 设设G G是是 阶正定对称矩阵，称函数阶正定对称矩阵，称函数 为正定二次函数。为正定二次函数。第3页，共18页，编辑于2022年，星期六例例1 1 证明：若目标函数为正定二次函数，则相应的证明：若目标函数为正定二次函数，则相应的无约束问题有严格局部解，且此局部解也是全局解。无约束问题有严格局部解，且此局部解也是全局解。定理定理4 44 4 设设 是连续可微的凸函数，则是连续可微的凸函数，则 是无约束是无约束问题的全局解的充要条件是问题的全局解的充要条件是第4页，共18页，编辑于2022年，星期六 三、三、最速下降法

3、最速下降法思路：从某一点出发，以最快的速度到达最小点，思路：从某一点出发，以最快的速度到达最小点，什么方向是函数下降最快的方向呢？什么方向是函数下降最快的方向呢？负梯度方向。负梯度方向。步长：沿负梯度方向走多远？步长：沿负梯度方向走多远？当前点当前点 ，计算负梯度，计算负梯度 ，最优，最优步长步长第5页，共18页，编辑于2022年，星期六算法算法4.1 4.1 最速下降法最速下降法（1 1）取初始点）取初始点 ，令，令（2 2）若）若 ，停止，否则，停止，否则 （3 3）一维搜索，求解问题）一维搜索，求解问题得得 令令（4 4）令）令 转（转（2 2）.第6页，共18页，编辑于2022年，星期

4、六例例2 2 用最速下降法求解无约束问题：用最速下降法求解无约束问题：取初始点取初始点数值实验数值实验（1 1）a=b=1;a=b=1;(2)a=99,b=1.(2)a=99,b=1.第7页，共18页，编辑于2022年，星期六 最速下降算法分析最速下降算法分析定理定理4 45 5 若一维搜索是精确的，则最速下降法若一维搜索是精确的，则最速下降法产生的相邻两次搜索方向是相互正交的，即产生的相邻两次搜索方向是相互正交的，即结论：结论：锯齿形，收敛慢。锯齿形，收敛慢。停机条件：停机条件：不合理。不合理。合理停机条件：合理停机条件：第8页，共18页，编辑于2022年，星期六解：解：第9页，共18页，编

5、辑于2022年，星期六第10页，共18页，编辑于2022年，星期六四、四、算法的收敛性算法的收敛性算法强收敛：迭代点列算法强收敛：迭代点列 或子列满足或子列满足 弱收敛：弱收敛：的任一个聚点是稳定点，的任一个聚点是稳定点，或者或者局部收敛，全局收敛局部收敛，全局收敛第11页，共18页，编辑于2022年，星期六收敛速度收敛速度迭代点列迭代点列 满足满足 若若则（则（1）则称则称 线性收敛；线性收敛；（2）则称则称 次线性收敛；次线性收敛；（3）则称则称 超线性收敛。超线性收敛。若若 则称则称 为为 阶收敛。阶收敛。第12页，共18页，编辑于2022年，星期六算法的二次终止性算法的二次终止性定义定

6、义3 3 若某个算法对于任意的正定二次函数，从任意的若某个算法对于任意的正定二次函数，从任意的初始点出发，都能经有限步迭代达到其极小点，则称该初始点出发，都能经有限步迭代达到其极小点，则称该算法具有二次终止性。算法具有二次终止性。第13页，共18页，编辑于2022年，星期六 算法及相关概念算法及相关概念1.一般迭代算法一般迭代算法集合集合S上的迭代算法上的迭代算法A：（1）初始点）初始点；（2）按照某种规则）按照某种规则A产生下一个迭代点产生下一个迭代点。（i）如果点列）如果点列收敛于最优解收敛于最优解，则称算法，则称算法A收敛。收敛。（ii）如果）如果，则称算法，则称算法A为为下降迭代算法。

7、下降迭代算法。.第14页，共18页，编辑于2022年，星期六 极小点的判定条件极小点的判定条件（1）必要条件：）必要条件：（2）充分条件：）充分条件：第15页，共18页，编辑于2022年，星期六2.下降迭代算法步骤下降迭代算法步骤（1）给出初始点）给出初始点，令，令；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向；（3）按照某种规则确定搜索步长）按照某种规则确定搜索步长，使得，使得；（4）令）令，；（5）判断）判断是否满足停止条件。是则停止，否则转第是否满足停止条件。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：称称。为最优步长，且有为最优步长，且有第16页，共18页，编辑于2022年，星期六 终止条件终止条件2.4.1.3.5.最可靠法则最可靠法则：第17页，共18页，编辑于2022年，星期六 收敛速度收敛速度则称则称 的收敛阶为的收敛阶为 。设算法设算法A所得的点列为所得的点列为，如果，如果第18页，共18页，编辑于2022年，星期六