无约束规划方法迭代法的基本步骤下降算法类拟牛顿算法共轭方向算法类1/68
1/68 无约束规划方法 ◼ 迭代法的基本步骤 ◼ 下降算法类 ◼ 拟牛顿算法 ◼ 共轭方向算法类
一、迭代法的基本结构给定初始估计x,第k次迭代的基本结构为：p,（1）确定一个搜索方向(2）不确定步长αk使得维搜索问题f(xk +αph)<f(xk)(3) 置 x+1 =x* +αpk采用不同方法构造p和不同方法寻找α就对应不同算法。2/68
2/68 一、迭代法的基本结构 采用不同方法构造 和不同方法寻找 就对应不同算法。 k k p k k k 1 k x x p + （3）置 = + 给定初始估计 第k次迭代的基本结构为： 1 x , , k （1）确定一个搜索方向 p （2）确定步长 使得 ( ) ( ) k k k k f x p f x + k 一维搜索问题
（梯度法）二、最速下降法函数值增加最快的方向迭代公式：Vf(xk)xk+1 = xk +αkp如何选择下降方向？下降方向1、最速下降法（梯度法）-Vf(xk函数值下降最快的方向 搜索方向 dk=-Vf(x)(②)搜索步长：α取最优步长,即满足f(x* +αrp*)= min f(xk +α p) 。3/68
3/68 迭代公式： k k k k x = x + p +1 如何选择下降方向？ 函数值下降最快的方向 函数值增加最快的方向 下降方向 ( ) k f x ( ) k − f x k x 二、最速下降法（梯度法） 1、最速下降法（梯度法） 1 ( ) k k （）搜索方向 d = −f x 。 （）搜索步长 取最优步长 即满足 ( ) min ( ) 2 : , k k k k k k f x p f x p + = +
2、最速下降法算法步骤给定初始点x'ER",允许误差ε>0,令k=1(②)计算搜索方向 p=-V f(x);(3)若LpkⅡ≤ε,则停止计算,x为所求极值点;否则，求最优步长α，使得f(x* +αrp*) = min f(x* +α p*)。Q() 令 xk+1 = xk +αpk,令k:= k+1,转2。4/68
4/68 （1）给定初始点 x 1 R n ,允许误差 0, 令k = 1。 2 ( ); k k （）计算搜索方向 p = − f x 否则，求最优步长 ，使得 （）若 则停止计算， 为所求极值点； k k k p x 3 || || , f (x k k p k ) min f (x k p k )。 + = + （4）令 x k+1 = x k +k p k ,令k := k + 1,转2。 2、最速下降法算法步骤
例1 用最速下降法求解：min f(x)=x +3x2初始 x'=(2,1),求迭代一次后的选代点 x2。解: ： Vf(x)=(2x1,6x2)T. p'=-Vf(x)=(-4,-6).:: xl +αp'=(2-4α,1-6α).令 (α)= f(x' +αp)=(2-4α) +3(1-6α),求解min p(α)132令 (α) = -8(2 - 4α)-36(1-6α)= 0 =→αi62(36,-8) x = x' +αp =(31'31)5/68
5/68 2 2 1 2 1 : min ( ) 3 , (2,1) , T f x x x x = + = 用最速下降法求解 初始 求迭代一次后的迭代点 x 2 。 解： ( ) ( 2 ,6 ) , 1 2 T f x = x x 1 1 ( ) ( 4, 6) . T = − = − − p f x 1 1 (2 4 ,1 6 ) . T + = − − x p 1 1 2 2 令 ( ) ( ) (2 4 ) 3(1 6 ) = + = − + − f x p ， 求解 min ( ) 令 '( ) 8(2 4 ) 36(1 6 ) 0 = − − − − = 1 13 62 = 例１ T 2 1 1 1 36 8 , . 31 31 x x p − = + =