第二节无约束极值问题 minf(x) ★一般模型: 其中X∈R ★求解((X)可微):应用极值条件求解,往往得到一个非线 性的方程组,求解十分困难。因此,求解无约束问题一般 采用迭代法,称为下降类算法
第二节 无约束极值问题 ★一般模型： min ( ) n f X 其中X R ★求解（f(X)可微）：应用极值条件求解，往往得到一个非线 性的方程组，求解十分困难。因此，求 解无约束问题一般 采用迭代法，称为下降类算法
下降类算法的基本步骤与算法收敛性 1基本思想 基本思想是使f(X)逐步下降,逐 渐趋近其最小值。迭代方式是从 个初始点X出发,选取某一搜 索方向P,沿该方向搜索到下 个点若达到与最优解误差的 精度要求,则停止,否则再沿该 点的某一方向P搜索下一个点X2 这一过程如图所示:
一、下降类算法的基本步骤与算法收敛性 1.基本思想 0 0 1 1 2 f X( ) X P X P X 基本思想是使 逐步下降，逐 渐趋近其最小值。迭代方式是从 一个初始点 出发，选取某一搜 索方向 ，沿该方向搜索到下一 个点 。若达到与最优解误差的 精度要求，则停止，否则再沿该 点的某一方向 搜索下一个点 。 这一过程如图所示： P0 P1 P2 X0 X1 X3 X2
2基本步骤 (1)选取初始点X,令k=0确定精度E>0 (2)对于点X,计算Vf(X)若‖Vf(XA)kE,则停止, 得到近似最优解X,否则转(3) (3)从出发,确定搜索方向P; (4)沿方向搜索,即由X=X+P确定搜索步长 得到下一个点X=X+2P,令k=k+转(2) 注:不同的搜索方向,就形成了不同的算法,不 同的算法所产生的点列收敛于最优解的速度 也不一样
2.基本步骤 0 (1) 选取初始点 ，令 确定精度 ； X k : 0, 0 = ( ), ( ) , 3 k k k k X f X f X X 对于点 ，计算 若 则停止, 得到近似最优解 ，否则转（ ）； (2) 从 出发，确定搜索方向 ； X P k k (3) 1 , , : 1, 2) k k k k k k k k P X X P X X P k k + + + = + 沿 方向搜索，即由 ＝ 确定搜索步长 得到下一个点 ＝ 令 转( 。 (4) 注：不同的搜索方向，就形成了不同的算法，不 同的算法所产生的点列收敛于最优解的速度 也不一样
3收敛性 衡量标准:1immk B k→∞ ①a=1,0<B<1,则称{X}是线性收敛的 ②a=1B=0,则称{X}是超线性收敛的; ③a=2,0≤B<+0,则称{X}是二阶收敛的 二阶收敛>超线性收敛>线性收敛
3.收敛性 衡量标准： * 1 * lim k k k X X X X + → − = − 1,0 1, { } ① = 则称 是线性收敛的； Xk 1, 0, { } ② = = 则称 是超线性收敛的； Xk 2,0 , { } ③ = + 则称 是二阶收敛的。 Xk 二阶收敛>超线性收敛>线性收敛
二、一维搜索 精确搜索:通过求极值minf(X+P)2 得到最佳步长 维搜索 分数法 求上面极值 近似搜索{0.168法 的近似值得 其他方法(导数信息)到近似最佳 步长
二、一维搜索 : 精确搜索： 一维搜索 分数法 近似搜索 0.168法 其他方法（导数信息） 0 min ( ), k k k f X P 通过求极值 + 得到最佳步长 k 求上面极值 的近似值得 到近似最佳 步长