em算法及其改进 ppt课件.ppt

em算法及其改进EM算法及其改进(二)第一部分:EM变尺度加速算法下降迭代算法求解非线性最优化问题最常用算法基本步骤:step1:选取初始数据,选取初始点,令k=0step2:构造搜索方向,按照一定规则,构造f在点处的下降方向(对于无约束最优化问题)或可行方向(对有约束问题)作为搜索方向。下降迭代算法step3:确定搜索步长。确定以为起点沿搜索方向的适当步长,使目标函数值有某种意义的下降,通常是使step4:求出新迭代点,令step5:检验终止条件,判定是否满足终止条件,若满足,则停止迭代输出近似最优解;否则,令k:=k+1,:其中称为牛顿方向,它是第k+1次迭代的搜索方向,:其中,为黑塞矩阵。牛顿法的优缺点优点:对正定二次函数,迭代一次就可以得到极小点。如果正定且初始点选取合适,算法很快收敛。缺点:要求函数二阶可微收敛性与初始点的选取依赖很大每次都需要计算黑塞矩阵,计算了大每次都需要解方程组方程组有时奇异或是病态的,无法确定是不是下降方向。变尺度算法拟牛顿法是一种逼近牛顿法的方法,它在每次迭代的搜索方向满足,其中是一近似的矩阵,如果正定,拟牛顿法也称变尺度法。它的基本思想是利用梯度差及步长构造矩阵满足拟牛顿方程(变尺度方程)。变尺度法不必计算二阶导数。