优化算法-梯度下降法

山东经济学院 计算机科学与技术学院 刘兆广 1 梯度下降法 山东经济学院 计算机科学与技术学院 刘兆广 2 梯度下降法又称最速下降法。函数 J(a)在某点 ak的梯度 是一个向量，其方向是 J(a)增长最快的方向。显 然，负梯度方向是 J(a)减少最快的方向。 在梯度下降法中，求某函数极大值时，沿着梯度方向走， 可以最快达到极大点；反之，沿着负梯度方向走，则最 快地达到极小点。 ()kJa 山东经济学院 计算机科学与技术学院 刘兆广 3 ()Ja a ka ()Ja ()Ja 山东经济学院 计算机科学与技术学院 刘兆广 4 求函数 J(a)极小值的问题，可以选择任意初始点 a0,从 a0 出发沿着负梯度方向走，可使得 J(a)下降最快。 s(0)：点 a0的搜索方向。 ( 0 ) 0()s J a 山东经济学院 计算机科学与技术学院 刘兆广 5 对于任意点 ak，可以定义 ak点的负梯度搜索方向的单位 向量为 : 从 ak点出发，沿着 方向走一步，步长为 ,得到新 点 ak+1,表示为： () () () k k k Jas Ja ()ks k ()1 kk k ka a s 山东经济学院 计算机科学与技术学院 刘兆广 6 ()Ja aka ()Ja ()Ja k 1ka 山东经济学院 计算机科学与技术学院 刘兆广 7 因此，在新点 ak+1，函数 J(a)的函数值为： 所有的 ak组成一个序列，该序列由迭代算法生成 a0, a1, a2, . , ak, ak+1, . 该序列在一定条件下收敛于使得 J(a)最小的解 a* 迭代算法公式： ()1 ( ) ( )kk k kJ a J a s ()1 kk k ka a s 山东经济学院 计算机科学与技术学院 刘兆广 8 迭代算法公式： 关键问题：如何设计步 长 如果选得太小，则算法收敛慢，如果选得太大， 可能会 导致发散。 ()1 kk k ka a s k 山东经济学院 计算机科学与技术学院 刘兆广 9 梯度法的迭代过程： 1)选取初始点 a0，给定允许误差 0,0,并令 k=0。 2)计算负梯度 及其单位向量 。 3)检查是否满足条件 ，若满足则转 8，否则继续。 4)计算最佳步长 。 5)令： 6)计算并检验另一判据： ，满足转 8， 否则继续。 7)令 k=k+1,转 2。 8)输出结果，结束。 () ()k ks J a *k ()ks ()ks * ( )1 kk k ka a s 1( ) ( )kkJ a J a