_无约束优化方法.ppt

第四章 无约束优化方法 §4-1 最速下降法（梯度法） §4-2 牛顿类方法 §4-3 变尺度法 §4-4 共轭方向法 §4-5 鲍威尔方法 §4-6 其它方法（如坐标轮换法、单纯形法） 第1章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。 为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 4-1 梯度法 根据一元函数极值的必要条件和多元复合函数求导公式，得 梯度法的特点 （1）理论明确，程序简单，对初始点要求不严格。 （2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。 （3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。 （4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。 4-2 牛顿法及其改进 方法特点 （1） 初始点应选在X*附近，有一定难度； （2） 尽管每次迭代都不会是函数值上升，但不能保证每次下降 ； （3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向； ??（4）?不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。 虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。 4-3 变尺度法 构造尺度矩阵Ak 从初始矩阵A0=I(单位矩阵)开始，通过对公式 2）BFGS算法(Broyden-Fletcher-Gold frob-Shanno ) DFP算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳定。BFGS算法对于维数较高问题具有更好的稳定性。 例4-3： 用DFP算法求下列问题的极值： 沿d0方向进行一维搜索，得 4-4 共轭方向法 如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x* ，即有 3.共轭梯度法 共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。 从xk出发，沿负梯度方向作一维搜索: 则： 4-5 鲍威尔方法 鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。 1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。 梯度和等值面相垂直的性质, dj和 xk, xk+1两点处的梯度gk,gk+1之间存在关系: 2.基本算法 二维情况描述鲍威尔的基本算法: 把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是： 在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。 用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。 因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成n维空间，可能求不到极小点，所以上述基本算法有待改进。 为此，要解决两个关键问题： （1）dk＋1是否较好？是否应该进入新的方向组？即方向组是否进行更新？ 则在循环中函数下降最多的第m次迭代是 这样重复迭代的结果，后面加进去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于二次函次，最多n次就可找到极小点，而对一般函数，往往要超过n次才能找到极小点（这里“n”表示设计空间的维数）。 例4-5 用改进的鲍威尔法求目标函数 （2）第2轮迭代计算 反射点及其函数值 检验终止条件 实际上，前两轮迭代的 ， 为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性