《13 使用导数的最优化方法_882602461》由会员分享，可在线阅读，更多相关《13 使用导数的最优化方法_882602461（102页珍藏版）》请在金锄头文库上搜索。
1、第十章 使用导数的最优化方法,-研究无约束问题最优化方法,精确一维搜索的一个重要性质：,定理：,最速下降法,最速下降方向,取搜索方向:,步骤:,例:,第一次迭代,解:,第二次迭代,例:,最速下降法的收敛性,定理：,二次函数情形,最速下降法表示为,Kantorovich不等式,定理（最速下降法二次情形）,定理：,条件数,非二次情形,结论：在相继两次迭代中,梯度方向互相正交.,牛顿法,基本思想:用一个二次函数去近似目标函数f(x),然后精确地求出这个二次函数的极小点.-一维搜索函数逼近法中的牛顿法的推广.,牛顿方向,定理：,步骤:,用Newton法求解无约束问题会出现以下情形：,（1）收敛到极小点
2、。,（2）收敛到鞍点。,（3）Hesse矩阵不可逆，无法迭代下去。,优点:（1）Newton法产生的点列x(k)若收 敛，则收敛速度快-具有至少二阶收敛速率。,(2) Newton法具有二次终止性。,缺点:,（1）可能会出现在某步迭代时，目标函数值上升. （2）当初始点远离极小点时，牛顿法产生的点列可能不收敛，或者收敛到鞍点，或者Hesse矩阵不可逆，无法计算. （3）需要计算Hesse矩阵的逆矩阵，计算量大.,步骤:,阻尼牛顿法,用阻尼牛顿法求解下列问题:,步骤:,修正牛顿法,共轭方向法,共轭方向,定义：,例：,定理1,证明：,定理2：,证明：,定理3：,定理（扩张子空间定理,expandi
3、ng subspace theorem）,共轭方向法,步骤（适用于正定二次函数）,从任意点出发，依次沿某组共轭方向进行一维搜索求解非线性规划问题的方法。,结论：,证明：,共轭方向法,步骤（适用于正定二次函数）,共轭方向法,步骤（适用于正定二次函数）,例：,共轭梯度法(Conjugate Gradient Method)(FR法),记号：,在共轭梯度法中，初始点处的搜索方向取 为该点的负梯度方向，即取,而以下各共轭方向d(k)由第k次迭代点x(k)处的负梯 度-gk与已经得到的共轭向量d(k-1)的线性组合来确定。,以此类推，得,定理:,步骤(FR共轭梯度法）,例:,例:,用于一般函数的共轭梯度
4、法,与原方法的主要区别：,迭代的延续方法：,步骤(FR共轭梯度法）,变尺度法(Variable Metric Method) 拟牛顿法(Quasi-Newton Method),这是一种求解无约束极值问题的有效算法， 由于它既避免了计算二阶导数、矩阵及其求逆 过程，又比最速下降法的收敛速度快，特别是 对高维问题具有显著的优越性，所以，它被 公认为求解无约束极值问题最有效的算法之一。,牛顿法的缺点:,（1）可能会出现在某步迭代时，目标函数值上升. （2）当初始点远离极小点时，牛顿法产生的点列可能不收敛，或者收敛到鞍点，或者Hesse矩阵不可逆，无法计算. （3）需要计算Hesse矩阵，计算量大.
5、,基本原理：,阻尼牛顿法:,拟牛顿条件,拟牛顿法步骤,秩1校正,一般策略：,校正矩阵,拟牛顿法步骤,DFP算法(变尺度法),定义：,DFP公式,DFP法计算步骤:,例: 用DFP方法求解下列问题：,第 一 次 迭 代,第二次迭代,例: 用共轭梯度法求解下列问题：,第 一 次 迭 代,第二次迭代,DFP算法(变尺度法),定理：,推论：,定理：,信赖域方法,基本思想：在当前迭代点的某个邻域内（通称取 为以当前迭代点为中心的球域，称为信赖域）， 根据已知的有关优化问题的信息，确定一个模型 函数来近似原来的目标函数；然后，在该领域内 极小化模型函数确定可能的改进点；最后，根据 一定标准决定是否接受这个可能的改进点。,基本原理,子问题,信赖域半径的确定,通过比较迭代过程中模型函数和目标函数的下 降量,确定下一个迭代过程的信赖域半径.,步骤：,子问题的精确求解法,必要性证明,充分性证明,第一次迭代:,第二次迭代:,第三次迭代:,
