常用无约束最优化方法.ppt

第五章 常用无约束优化方法 5.8 单纯形法 单纯形法基本原理 以二元函数为例，说明单纯形法的原理． 设二元函数 在平面上取不在同一条直线上的三个点 ， 和 ，并以它们为顶点构成一单纯形——三角形．算出各顶点的函数值 ， ， ，比较其大小，不妨假定比较后有 这说明 点最差， 点最好， 点次差． 为了寻找极小点，一般来说应向最差点的反对称方向进行搜索．以 记为 的中点，在 的延长线上取点 ，使 称为 关于 的反射点． 第五章 常用无约束优化方法 计算函数值 ，可能出现以下几种情形： (1) 说明搜索方向正确，可进一步扩大效果，继续 沿向前搜索，也就是向前扩张．这时取 其中 为扩张因子，一般取 ． 如果 ，说明扩张有利，以点 代替点 构成新的单纯形 . 如果 ，说明扩张不利，舍去 ，仍以 代替点 构成新的单纯形 . 第五章 常用无约束优化方法 式（5.25）中含有问题（5.13）的目标函数系数矩阵，这对于目标函数是非二次函数的问题是不方便的．通过简化，一般可以利用目标函数的梯度信息，来产生n个共轭方向 由此得共轭梯度法． 第五章 常用无约束优化方法 迭代步骤 已知目标函数 ，终止限 ． （1）选取初始点 ，给定终止限 ． （2）求初始梯度．计算 ，若 ，停止迭 代输出 ，否则转（3）． （3）构造初始搜索方向．取 ，令 ，转（4）． （4）进行一维搜索．求 使得 令 ，转（5）． （5）求梯度向量．计算 ，若 ，停止迭代 输出 ．否则转（6）． （6）检验迭代次数．若 ，令 ，转（3），否 则转（7）． （7）构造共轭方向．取 ， 令 ，转（4）． 第五章 常用无约束优化方法 第五章 常用无约束优化方法 例5.3 用共轭梯度法求 其中 ，选初始点为 ． 解 令 ∴ ∴ ∴ 第五章 常用无约束优化方法 则 故 令 ∴ ∴ 由于 ∴ 第五章 常用无约束优化方法 有关说明 实际上，可以把共轭梯度法看作是最速下降法的一种改进．当 时，就变为最速下降法． 共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题． 另外，共轭梯度法不要求精确的直线搜索．但是，不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低方法的效能．克服的办法是，重设初始点，即把经过n次迭代得到的Xn作为初始点重新迭代． 第五章 常用无约束优化方法 5.6 变尺度法 我们知道Newton法最突出的优点是收敛速度快，在这一点上其它算法无法比拟的．因此，建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解．然而Newton法还有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵，当问题的维数较大时，计算量迅速增加，从而就抵消了Newton法的优点．为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点，又可以摆脱关于Hesse矩阵的计算，这就是本节要给大家介绍的变尺度算法． 变尺度法是一种非常好的方法．其中DFP算法和BFGS算法，可以说直到目前为止是在不用Hesse矩阵的方法中最好的算法． 第五章 常用无约束优化方法 一、变尺度法基本原理 Newton法在基本迭代公式 中， ， 。记 则