运筹学10使用导数的最优化方法.pdf

最优化理论与算法 §10，使用导数的最优化方法 TP SHUAI 1 第十章使用导数的最优化方法 最速下降法 牛顿法 共轭梯度法 拟牛顿法 信赖域法 TP SHUAI 2 10.1最速下降法 10.1最速下降法 考虑无约束问题 min f (x), x Rn (10.1.1) 其中f (x)具有一阶连续偏导数。 在处理这类问题时，一般策略是，希望从某一点出发，选择 一个目标函数值下降最快的方向，沿此方向搜索以期尽快达 到极小点，基于这一思想，Cauchy于1847年提出了最速下降 法。这是无约束最优化中最简单的方法。 TP SHUAI 3 10.1最速下降法－1 函数f (x)在点x处沿方向d 的变化率可用方向导数表 示，当函数可微时有，方向导数 Df (x, d ) f (x)T d (1.2) 求函数f(x)在点x处下降最快的方向,归结为求 min f (x)T d s.t d 1 (1.3) 由Schwartz不等式, T f (x ) d  f (x ) d  f (x ) T  f (x ) d  f (x ) (1.4) TP SHUAI 4 10.1最速下降法－2 由上式知.当 f (x ) d  (1.5) f (x ) 时等号成立.故在点x 处沿(1.5)所定义的方向变化 率最小,即负梯度方向为最速下降方向. 注意:在不同的尺度下最速下降方向是不同的. TP SHUAI 5 10.1最速下降法－3 最速下降算法 最速下降算法的迭代公式为 x (k 1) x (k )  d (k ) (1.6) k 其中d (k )是从x(k ) 出发的搜索方向,此处取在点x(k )的最速下降 方向,即 d (k ) f (x(k ) ). 是从x(k )出发沿方向d ( k )进行一维搜索的步长,即满足 k f (x(k ) d (k ) )  f (x( k ) d ( k ) ) (1.7) k min 0 TP SHUAI 6 10.1最速下降法－4 算法描述 Step1,给定初始点x(k ) En ,允许误差 0,置k 1 Step2, 计算搜索方向d (k ) f (x(k ) ) Step3, 若 d