4 无约束优化方法.pptVIP

从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念 对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升，即出现f(xk+1)f(xk)的现象 4.3 共轭方向法 一、 共轭方向 对于N维二次函数 (当N=2，为同心椭圆族)，函数 f 的黑塞矩阵[H]为正定对称阵。若存在两个方向向量 ，满足 ，则称 与 为共轭方向。 二、 共轭方向原理 * 牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的主要缺点是。另外从计算机存储方面考虑，牛顿型方法所需的存储量也是很大的。最速下降法的收敛速度比牛顿法慢，而牛顿法又存在上述缺点。针对这些缺点，近年来人们研究了很多改进的算法，如针对最速下降法(梯度法) 提出只用梯度信息，但比最速下降法收敛速度快的共轭梯度法；针对牛顿法提出变尺度法等。这将在下几节中予以讨论。 * * 5.DFP变尺度法 能否克服各自的缺点，综合发挥其优点？ 2）阻尼牛顿法 1）梯度法 一）问题的提出 由Davidan、Fletcher、Powell共同提出。 * 简单，开始时目标函数值下降较快，但越来越慢。 * 目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。 * * 二）基本思路 2）迭代终了， 具有二阶收敛性。 *1）当 和梯度法一样，便于突破函数的非二次性； 式中，1.Ak —构造矩阵（在迭代中产生，不用求导和作矩阵求逆） 迭代公式： ---拟牛顿方向 2. * * 三）构造矩阵应满足的条件 1） 应为正定对称矩阵； (1) 应为对称矩阵； E和 均为对称矩阵 (2) 应为正定矩阵； 因为 应使 为函数下降方向,即 与 的夹角应小于900: 二次型正定 * * 2） 能逼近 以近似二次函数的梯度作为下一迭代点处的梯度: 其梯度 用 代替 , 得 拟牛顿条件 * * 四. 的构造方法 用递推方法构造 于是有 关键是确定 校正矩阵 (1) 再令 (2) 代入(1): 两边对比得: 回代到(2)得: (3) 待定常数 可保证AK的对称性 * * 五.迭代步骤 是 是 否 否 因计算机的舍入误差，构造矩阵的正定性可能遭到破坏，故作n次后重置单位矩阵。 * * 6.坐标轮换法 1)几何描述(以二维问题为例） 二）迭代步骤 依次沿个n个正交坐标轴的方向有哪些信誉好的足球投注网站： 一）有哪些信誉好的足球投注网站方向 * * 2) 坐标轮换法流程图 从 出发沿 方向进行一维有哪些信誉好的足球投注网站得 ： 给定 结束 * * 三) 算法特点 如:(1)等值线为椭圆,且长短轴分别平行于坐标轴时--高效 (2)等值线为如图脊线时--无效 (3)一般情况--低效 1）编程简单，容易掌握； 2）收敛速度通常较低（其有效性取决于目标函数的性态），仅适于低维的情况。 * * 7. 鲍威尔方法 3）若目标函数为正定二次函数，n轮结束后即可到达最优点。 2）每轮迭代产生一个新方向取代原来的第一方向，n轮迭代后可产生n个彼此共轭的方向； 1）开始采用坐标轴方向； 一）Powell基本算法 * * 二）Powell法（ Powell修正算法） 应用 Powell基本算法时，若有一次有哪些信誉好的足球投注网站的最优步长为0，且该方向被换掉，则该算法失效。 1）问题的提出 * * 2)Powell对基本算法的改进 在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向. * ①根据Powell条件判定是否需换方向； ②如需换向，则换掉函数值下降量最大的方向. * * 三）Powell条件 如下述两不等式 同时成立则需换向，否则仍取原方向组。 计算: （映射计算） * * 四）更换方向的步骤 3）更换方向： 2）构造新方向： 1）找出该轮迭代中目标函数值下降量最大的方向（假定其标号为m）； * * Powell 修正算法 F3F1 QD Si=Si+1 i=m,m+1,…n i = n 输出X*=Xn F*=F（X*） 结束 给定X0,Si=ei i=1,2,…n, ε K=0 i=1 自Xi-1始，沿Si方向有哪些信誉好的足球投注网站得一维最优点Xi i=i+1 Xn+1=2Xn-X0 Sn+1=Xn-X0 自Xn始，沿Sn+1方向有哪些信誉好的足球投注网站得一维最优点X* K=K+1 F1=F(X0), F2=F(Xn), F3=F(Xn+1) 求Δ及方向标号m Y Y Y Y N N N X0=X* N Xn-X0 ≤ε * * 无约束优化方法的