13 使用导数的最优化方法_882602461.ppt

《13 使用导数的最优化方法_882602461.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章使用导数的最优化方法----研究无约束问题最优化方法精确一维搜索的一个重要性质：定理：最速下降法最速下降方向取搜索方向:步骤:例:第一次迭代解:第二次迭代例:最速下降法的收敛性定理：二次函数情形最速下降法表示为Kantorovich不等式定理（最速下降法—二次情形）定理：条件数非二次情形结论：在相继两次迭代中,梯度方向互相正交.牛顿法基本思想:用一个二次函数去近似目标函数f(x),然后精确地求出这个二次函数的极小点.----一维搜索函数逼近法中的牛顿法的推广.牛顿方向定理：步骤:用Newton法求

2、解无约束问题会出现以下情形：（1）收敛到极小点。（2）收敛到鞍点。（3）Hesse矩阵不可逆，无法迭代下去。优点:（1）Newton法产生的点列{x(k)}若收敛，则收敛速度快---具有至少二阶收敛速率。(2)Newton法具有二次终止性。缺点:（1）可能会出现在某步迭代时，目标函数值上升.（2）当初始点远离极小点时，牛顿法产生的点列可能不收敛，或者收敛到鞍点，或者Hesse矩阵不可逆，无法计算.（3）需要计算Hesse矩阵的逆矩阵，计算量大.步骤:阻尼牛顿法用阻尼牛顿法求解下列问题:步骤:修正牛顿法共

3、轭方向法共轭方向定义：例：定理1证明：定理2：证明：定理3：定理（扩张子空间定理,expandingsubspacetheorem）共轭方向法步骤（适用于正定二次函数）从任意点出发，依次沿某组共轭方向进行一维搜索求解非线性规划问题的方法。结论：证明：共轭方向法步骤（适用于正定二次函数）共轭方向法步骤（适用于正定二次函数）例：共轭梯度法(ConjugateGradientMethod)(FR法)记号：在共轭梯度法中，初始点处的搜索方向取为该点的负梯度方向，即取而以下各共轭方向d(k)由第k次迭代点x(k)

4、处的负梯度-gk与已经得到的共轭向量d(k-1)的线性组合来确定。以此类推，得定理:步骤(FR共轭梯度法）例:例:用于一般函数的共轭梯度法与原方法的主要区别：迭代的延续方法：步骤(FR共轭梯度法）变尺度法(VariableMetricMethod)拟牛顿法(Quasi-NewtonMethod)这是一种求解无约束极值问题的有效算法，由于它既避免了计算二阶导数、矩阵及其求逆过程，又比最速下降法的收敛速度快，特别是对高维问题具有显著的优越性，所以，它被公认为求解无约束极值问题最有效的算法之一。牛顿法的缺点:

5、（1）可能会出现在某步迭代时，目标函数值上升.（2）当初始点远离极小点时，牛顿法产生的点列可能不收敛，或者收敛到鞍点，或者Hesse矩阵不可逆，无法计算.（3）需要计算Hesse矩阵，计算量大.基本原理：阻尼牛顿法:拟牛顿条件拟牛顿法步骤秩1校正一般策略：校正矩阵拟牛顿法步骤DFP算法(变尺度法)定义：DFP公式DFP法计算步骤:例:用DFP方法求解下列问题：第一次迭代第二次迭代例:用共轭梯度法求解下列问题：第一次迭代第二次迭代DFP算法(变尺度法)定理：推论：定理：信赖域方法基本思想：在当前迭代点的某

6、个邻域内（通称取为以当前迭代点为中心的球域，称为信赖域），根据已知的有关优化问题的信息，确定一个模型函数来近似原来的目标函数；然后，在该领域内极小化模型函数确定可能的改进点；最后，根据一定标准决定是否接受这个可能的改进点。基本原理子问题信赖域半径的确定通过比较迭代过程中模型函数和目标函数的下降量,确定下一个迭代过程的信赖域半径.步骤：子问题的精确求解法必要性证明充分性证明第一次迭代:第二次迭代:第三次迭代: