无约束最优化精品文稿.ppt

无约束最优化第1 页，本讲稿共18 页 二、局部解的最优性条件定理41（一阶必要条件）设 具有连续的一阶偏导数，若 是无约束问题的局部解，则定理42（二阶必要条件）设 具有连续的二阶偏导数，若 是无约束问题的局部解，则 半正定。第2 页，本讲稿共18 页定理43（二阶充分条件）设 具有连续的二阶偏导数，若在 处满足：正定，则 是无约束问题的严格局部解。定义2 设G是 阶正定对称矩阵，称函数 为正定二次函数。第3 页，本讲稿共18 页例1 证明：若目标函数为正定二次函数，则相应的无约束问题有严格局部解，且此局部解也是全局解。定理44 设 是连续可微的凸函数，则 是无约束问题的全局解的充要条件是第4 页，本讲稿共18 页 三、最速下降法思路：从某一点出发，以最快的速度到达最小点，什么方向是函数下降最快的方向呢？负梯度方向。步长：沿负梯度方向走多远？当前点，计算负梯度，最优步长第5 页，本讲稿共18 页算法4.1 最速下降法（1）取初始点，令（2）若，停止，否则（3）一维搜索，求解问题得 令（4）令 转（2）.第6 页，本讲稿共18 页例2 用最速下降法求解无约束问题：取初始点数值实验（1）a=b=1;(2)a=99,b=1.第7 页，本讲稿共18 页 最速下降算法分析定理45 若一维搜索是精确的，则最速下降法产生的相邻两次搜索方向是相互正交的，即结论：锯齿形，收敛慢。停机条件：不合理。合理停机条件：第8 页，本讲稿共18 页解：第9 页，本讲稿共18 页第10 页，本讲稿共18 页四、算法的收敛性算法强收敛：迭代点列 或子列满足 弱收敛：的任一个聚点是稳定点，或者局部收敛，全局收敛第1 1 页，本讲稿共18 页收敛速度迭代点列 满足 若则（1）则称 线性收敛；（2）则称 次线性收敛；（3）则称 超线性收敛。若 则称 为 阶收敛。第12 页，本讲稿共18 页算法的二次终止性定义3 若某个算法对于任意的正定二次函数，从任意的初始点出发，都能经有限步迭代达到其极小点，则称该算法具有二次终止性。第13 页，本讲稿共18 页 算法及相关概念1.一般迭代算法集合S上的迭代算法A：（1）初始点；（2）按照某种规则A产生下一个迭代点。（i）如果点列收敛于最优解，则称算法A收敛。（ii）如果，则称算法A为下降迭代算法。.第14 页，本讲稿共18 页 极小点的判定条件（1）必要条件：（2）充分条件：第15 页，本讲稿共18 页2.下降迭代算法步骤（1）给出初始点，令；（2）按照某种规则确定下降搜索方向；（3）按照某种规则确定搜索步长，使得；（4）令，；（5）判断 是否满足停止条件。是则停止，否则转第2步。搜索步长确定方法：称。为最优步长，且有第16 页，本讲稿共18 页 终止条件2.4.1.3.5.最可靠法则：第17 页，本讲稿共18 页 收敛速度则称 的收敛阶为。设算法A所得的点列为，如果第18 页，本讲稿共18 页