最优化问题第三章 例题101124.docVIP

1. 最速下降法 最速下降法的迭代公式 ， k=1,2,… 最速下降法的锯齿现象 例3.1 用最速下降法求解无约束极小化问题 . 取. 迭代二次. 解 , 第一次迭代 ，取. 设 ， 有 令 , 得,. 因，所以不是极小点. 继续迭代. 第二次迭代 取，设 ， 有 令 得(不合题意，舍去),.因故是驻点. 又因正定，故是严格局部极小点. □ 通过本题可以了解，(1)对于有些无约束极小化问题，最速下降法对于某些初始点可以在有限步迭代终止，即可以在有限次迭代后求到极小点；(2)非正定二次函数的步长因子没有显示计算公式. 例3.2(P152 例3.1) 通过本题了解，(1)最速下降法使相邻迭代点的梯度正交；(2)正定二次函数的步长因子有显示计算公式；(3)对于某些初始点未能象例3.1在两步内迭代终止，但初始点如果选在坐标轴上，则迭代一步终止. 2. Newton法 Newton迭代公式 , k=1,2,… Newton法是二次收敛算法. n对于正定二次目标函数，Newton迭代一步即可求到极小点；对于非正定二次目标函数，Newton 法一般不会一步迭代终止. 例3.3 用Newton 法求解无约束极小化问题 . 取. 解 正定, 因目标函数是严格二次凸函数，所以即是最优解. □ 例3.4　用Newton 法求解无约束极小化问题 . 取. 迭代一次. 试判断迭代点是否为最优点，若不是最优点，则判断其是否为下降点. 解 , 因，故不是最优点，但是函数值下降点. □ 3.共轭梯度法 共轭梯度法迭代公式 , k=1,2,… ， . 共轭梯度法是二次收敛算法. 对于n元正定二次目标函数，共轭梯度法至多n次迭代即可求到极小点；对于n元非二次目标函数，共轭梯度法一般不会在有限步迭代终止. 例3.5 用F-R共轭梯度法求解无约束极小化问题 . 取. 解 正定. , 因，所以继续迭代. 计算 但不妨取，于是 因目标函数是严格二次凸函数，所以即是最优解. □ 例3.6 用F-R共轭梯度法求解无约束极小化问题 . 取. 迭代两次. 解 , . . 设，则 . 令，得，所以不是最优点，需继续迭代. 计算 . 不妨取，并设，有 令 , 得,. 因, 所以不是最优点. □ 4.DFP法 DFP法迭代公式 , k=1,2,… , DFP法是二次收敛算法.对于以n元正定二次目标函数，DFP法至多迭代n次即可求到极小点；对于n元非二次目标函数，共轭梯度法一般不会在有限步迭代终止. 例3.7 用DFP法求解无约束极小化问题 . 取. 解 正定. , 因，所以继续迭代. 计算 , . 不妨取，于是 因目标函数是严格二次凸函数，所以即是最优解. 例3.8 用DFP法求解无约束极小化问题 . 取. 迭代二次. 解　计算 , , 设，则 . 令得，所以继续迭代. 计算, . 不妨取. 设，则 令 , 得,. 因, 所以还需继续迭代. □ 5.步长加速法 例3.9(P183 例3.5) 解 令，计算. 开始Ⅰ型探测 × √ 记，接着计算 × √ 得及. 因为，于是进行第一次模式移动 ， 并计算. 接下来开始Ⅱ型探测 × √ 记，接着计算 × √ 得及. 因为，于是进行第二次模式移动 ， 并计算. 又开始Ⅱ型探测 × × √ 得及. 因为，于是又可以进行第三次模式移动 ，并计算. 再一次开始Ⅱ型探测 √ 记，接着计算 √ 得及. 因为，所以上次模式移动作废.重令，则，并又开始Ⅰ型探测 × × × × 探测失败，需缩小步长.新的步长向量，……. □ 以上过程的路径如下图所示. 通过本题熟悉步长加速法的解题过程. 例3.10 用步长加速法求解无约束问题 . 取，收缩系数，要求一直迭代到步长向量满足为止. 解 令，计算. 开始Ⅰ型探测 √ 记，接着计算 × √ 得及. 因为，于是进行第一次模式移动 ， 并计算. 接下来进行Ⅱ型探测 × × × × 得及. 因为，于是进行第二次模式移动 ， 并计算. 又开始Ⅱ型探测 × √ 记，接着计算 √ 得及. 因为，所以上次模式移动作废. 重令，则，又开始Ⅰ型探测 × × × × 探测失败，需缩小步长. 新的步长向量，……. □ 6. 最小二乘法 例3.11(P206 例3.8) 例3.12