最速下降法的特 最速下降法是一个求解极值问题的古老算法 早在1947年就已由柯西( Cauchy)提出 直观、简单 要计算函数的梯度,故属于解析法,即间接求解法 采用了函数的负梯度方向作为下一步的搜索方向,所以收敛速度 较慢,越是接近极值点收敛越慢,这是它的主要缺点 应用最速下降法可以使目标函数在开头几步下降很快,所以它可 与其他无约束优化方法配合使用 些更有效的方法都是在对它改进后,或在它的启发下获得的, 因此最速下降法仍是许多有约束和无约束优化方法的基础。 2021/2/20
2021/2/20 11 最速下降法的特点 • 最速下降法是一个求解极值问题的古老算法 – 早在1947年就已由柯西(Cauchy)提出 – 直观、简单 • 要计算函数的梯度，故属于解析法，即间接求解法 • 采用了函数的负梯度方向作为下一步的搜索方向，所以收敛速度 较慢，越是接近极值点收敛越慢，这是它的主要缺点 • 应用最速下降法可以使目标函数在开头几步下降很快，所以它可 与其他无约束优化方法配合使用 • 一些更有效的方法都是在对它改进后，或在它的启发下获得的， 因此最速下降法仍是许多有约束和无约束优化方法的基础
3.牛顿型方法 维搜索的牛顿方法的迭代公式 x k+1 x f(xk)k=0,1,2L fI(xk 对于多元函数x),设x为其极小点x*附近的一个近似点,在x处 进行泰勒展开,保留到二次项 (x)?j(x) f(xr)+[ f(xk](x xk)+5(x-xx)? 2f(xk)(x xk) 极值必要条件 ?j(xk+1)0 f(xk) (xk)(x )=0 xk+1=xk-[蜒f(xk)f(xk)〓次收 2021/2/20 12
2021/2/20 12 3. 牛顿型方法 • 一维搜索的牛顿方法的迭代公式 • 对于多元函数f(x)，设xk为其极小点x*附近的一个近似点，在xk处 进行泰勒展开，保留到二次项 ( ) ( ) 1 0,1, 2, k k k k f x x x k f x + ¢ = - = ⅱ L ( ) ( ) ( ) [ ( )] ( ) ( ) ( )( ) T 1 T 2 2 k k k k k k f x x f x f x x x x x f x x x ? + ? + - ? j 极值必要条件 ( ) ? j xk + 1 0 ( ) ( )( ) 2 ? ? = f x f x x x k k k k + 1 0 [ ( )] ( ) 1 2 x x f x f x k k k k 1 - + = - 蜒 二次收敛
牛顿法例题 用牛顿法求f(x1x2)x12+25x2的极小值 取初始点为x0=[2,2 f(x0) 0 0 0 50 50 代入牛顿法迭代公式 0 0-[蜒f(x0)]f(x) 2021/2/20 13
2021/2/20 13 牛顿法例题 • 用牛顿法求f(x1,x2)=x1 2+25x2 2的极小值 取初始点为x 0=[2,2]T ( ) 0 1 0 2 2 4 50 100 x x f x x 轾 轾 ? = 犏 犏 犏 犏 臌 臌 ( ) 2 0 2 0 0 50 f x 轾 ? 犏犏臌 [ ( )] 1 2 0 1 0 2 1 0 50 f x - 轾犏 ? 犏犏犏犏臌 代入牛顿法迭代公式 [ ( )] ( ) 1 1 0 2 0 0 1 2 4 0 0 2 2 100 1 0 0 50 x x f x f x - 轾 轾 轾 犏 轾 = - 蜒 = - = 犏 犏 犏 犏 犏 犏 犏 犏 臌 臌 犏 臌 犏臌
阻尼牛顿法 从牛顿法迭代公式的推演中可以看到,迭代点 的位置是按照极值条件确定的,其中并未含有 沿下降方向搜寻的概念 对于非二次函数,如果采用上述牛顿迭代公式, 有时会使函数值上升,即出现f(xk+)>f(xk)的现 象 需对上述牛顿法进行改进,引入数学规划法的 搜索概念,提出所谓“阻尼牛顿法 2021/2/20
2021/2/20 14 阻尼牛顿法 • 从牛顿法迭代公式的推演中可以看到，迭代点 的位置是按照极值条件确定的，其中并未含有 沿下降方向搜寻的概念 • 对于非二次函数，如果采用上述牛顿迭代公式， 有时会使函数值上升，即出现f(xk+1)>f(xk )的现 象 • 需对上述牛顿法进行改进，引入数学规划法的 搜索概念，提出所谓“阻尼牛顿法