无约束最优化直接方法和间接方法的异同

最优化理论与算法小论文 无约束最优化直接方法和间接方法的异同 翁乐怡 1 无约束最优化直接方法和间接方法的异同无约束最优化直接方法和间接方法的异同 1 什么是无约束最优化什么是无约束最优化 最优化方法 也称做运筹学方法 是近几十年形成的 它主要运用数学方 法研究各种系统的优化途径及方案 为决策者提供科学决策的依据 最优化方 法的主要研究对象是各种有组织系统的管理问题及其生产经营活动 其的目的 在于针对所研究的系统 求得一个合理运用人力 物力和财力的最佳方案 发 挥和提高系统的效能及效益 最终达到系统的最优目标 实践表明 随着科学 技术的日益进步和生产经营的日益发展 最优化方法已成为现代管理科学的重 要理论基础和不可缺少的方法 被人们广泛地应用到公共管理 经济管理 工 程建设 国防等各个领域 发挥着越来越重要的作用 最优化问题分为无约束最优化和约束最优化问题 约束最优化问题是具有 辅助函数和形态约束条件的优化问题 而无约束优化问题则没有任何限制条件 无约束最优化问题实际上是一个多元函数无条件极值问题 虽然在工程实践中 大多数问题都是具有约束的优化问题 但是优化问题 的处理上可以将有约束的优化问题转化为无约束最优化问题 然后按无约束方 法进行处理 或者是将约束优化问题部分转化为无约束优化问题 在远离极值 点和约束边界处按无优化约束来处理 在接近极值点或者约束边界时按照约束 最优化问题处理 所以无约束优化问题的解法不仅是优化设计方法的基本组成 部分 也是优化方法的基础 无约束最优化方法大致分为两类 一类是使用导数的间接方法 即在计算 过程中要用到目标函数的导数 另一类是直接方法 即只要用到目标函数值 不需要计算导数 这里我们比较这两类方法的异同 2 无约束最优化方法无约束最优化方法 1 使用导数的间接方法使用导数的间接方法 1 1 最速下降法最速下降法 函数的负梯度方向是函数值在该点下降最快的方向 将 n 维问题转化为一 系列沿负梯度方向用一维搜索方法寻优的问题 利用负梯度作为搜索方向 故 最优化理论与算法小论文 无约束最优化直接方法和间接方法的异同 翁乐怡 2 称最速下降法或梯度法 无约束优化问题的数学模型可以表示为 我们假设函数 n Rf xx x min 具有一阶连续偏导数 最速下降法在处理这一类问题时 从初始迭代点 xf 出发 选择一个目标函数值下降最快的方向 以利于尽快达到极小点 1 x k d 最速下降法的迭代公式为 1 给定初点 允许误差 置 n R 1 x0 1 k 2 计算搜索方向 kk f xd 3 若 则停止计算 否则 从出发 沿着进行一维搜索 求 k d k x k d 使得 k min kkk k k ffdxdx 4 令 置 转步骤 2 k k kk dxx 1 1 kk 梯度下降法有如下特点 1 理论明确 程序简单 对初始点要求不严格 2 对一般函数而言 梯度法的收敛速度并不快 线性收敛 因为最速下 降方向仅仅是指某点的一个局部性质 3 梯度法相邻两次搜索方向的正交性 决定了迭代全过程的搜索路线呈锯 齿状 在远离极小点时逼近速度较快 而在接近极小点时逼近速度较慢 4 梯度法的收敛速度与目标函数的性质密切相关 对于等值线 面 为同心 圆 球 的目标函数 一次搜索即可达到极小点 1 2 牛顿法牛顿法 牛顿法在邻域内用一个二次函数来近似代替原目标函数 并将的极小点 k x 作为对目标函数求优的下一个迭代点 经多次迭代 使之逼近目标函数的极小 点 牛顿法的迭代公式为 121kkkk ffxxxx 牛顿法有如下特点 1 初始点应选在极点附近 有一定难度 2 若迭代点的海赛矩阵为奇异 则无法求逆矩阵 不能构造牛顿法方向 3 不仅要计算梯度 还要求海赛矩阵及其逆矩阵 计算量和存储量大 此 最优化理论与算法小论文 无约束最优化直接方法和间接方法的异同 翁乐怡 3 外 对于二阶不可微的函数也不适用 4 虽然牛顿法有上述缺点 但在特定条件下它具有收敛最快的优点 2 级 收敛 并为其他的算法提供了思路和理论依据 1 3 共轭梯度法共轭梯度法 共轭梯度法的基本思想是把共轭性与最速下降法相结合 利用已知点处的 梯度构造一组共轭方向 并沿着这组方向进行搜索 求出目标函数的极小点 其计算步骤为 1 给定初点 允许误差 置 n R 1 x0 1 1111 jkf ydxy 2 若 则停止计算 否则 做一维搜索 求 使得 j f y j 令 min jjj j j ffdydy j j jj dyy 1 3 如果 转步骤 4 否则转步骤 5 nj 4 令 其中 j j jj yfdd 11 2 2 1 j j j yf yf 5 令 置 转步骤 2 111111 ydxyyxf knk 1 1 kkj 共轭梯度法有如下特点 1 程序简单 存储量少 具有最速下降法的优点 而在收敛速度上比最速 下降法快 具有二次收敛性 2 适用于维数较高 50 维以上 一阶偏导数易求的优化问题 共轭梯度法 在第一个搜索方向取负梯度方向 而其余各步的搜索方向将负梯度偏转一个角 度 即对负梯度进行修正 实质上是对最速下降法的改进 在 n 次迭代后如果 没有达到收敛精度 则通常以重置负梯度方向开始 直到满足精度为止 1 4 拟牛顿法拟牛顿法 牛顿法成功的关键在于利用了 Hesse 矩阵提供的曲率信息 而计算 Hesse 矩 阵工作量大 并且有的目标函数的 Hesse 矩阵很难计算 甚至不好求出 为了 克服牛顿法的缺点 人们提出仅利用目标函数一阶导数的方法 拟牛顿法就是 利用目标函数值 f 和一阶导数 g 的信息 构造出目标函数的 Hesse 矩阵的曲率 最优化理论与算法小论文 无约束最优化直接方法和间接方法的异同 翁乐怡 4 近似 同时具有收敛速度快的优点 1 5 信赖域方法信赖域方法 无优化方法的一般策略是 给定点后 定义搜索方向 再从出发 k x k d k x 沿着做一维搜索 而信赖域方法另辟蹊径 给定点后 确定一个变化范 k d k x 围 通过常取为中心的区域 称为信赖域 在此域内优化目标函数的二次逼 k x 近式 按照一定模式求出后继点 如果不满足精度要求 再定义为中 1 k x 1 k x 心的信赖域 并在此域内优化目标函数新的二次逼近式 直到达到精度 该方 法的特点是在一定条件下具有全局收敛性 2 直接方法直接方法 2 1 模式搜索法模式搜索法 搜索模式法是 Hooke 和 Jeeves 在 1961 年提出的 这种方法的基本思想 从 几何意义上看 寻找具有较小函数值的 山谷 力图使迭代产生的序列沿 山 谷 走向逼近极小点 算法从初始基点开始 包括两种类型的移动 探测移动 和模式移动 探测移动依次沿 n 个坐标轴进行 用以确定新的基点和有利于函 数值下降的方向 模式移动沿相邻两个基点连线方向进行 试图顺着 山谷 使函数值更快地减小 有如下特点 1 最简单的直接优化方法之一 方法易懂 程序简单 无需求导 计算费 用低 2 可靠性差 效率低 当目标函数等值线具有脊线形态时可能失败 3 该方法适用于目标函数导数不存在或不易求得 维数较低 一般 l 5 的情况 其探索路线较长 而且显然是问题的维数愈多求最优解得效率愈低 2 2 单纯形法单纯形法 单纯形法也是一种不使用导数的求解无约束极小化问题的直接搜索方法 与前面几种方法不同 在这种方法中 给定中的一个单纯形后 求出 n 1 个 n R 顶点上的函数值 确定出有最大函数值的点 和最小函数值的点 然后通过反 射 扩展 压缩等方法求出一个较好点 用它取代最高点 构成新的单纯形 或者通过向最低点收缩形成新的单纯形 用这样的方法逼近极小点 最优化理论与算法小论文 无约束最优化直接方法和间接方法的异同 翁乐怡 5 2 3 Powell 方法方法 Powell 法是以共轭方向为基础的收敛较快的直接法之一 是一种十分有效 的算法 直接利用迭代点的目标函数值来构造共轭方向 然后从任一初始点开 始 逐次沿共轭方向作一维搜索求极小点 该方法直接利用函数值逐次构造共轭方向 并在改进的算法中增加了判断 原方向组是否需要替换和哪个方向需要替换 保证了共轭方向的生成 具有二 次收敛性 收敛速度快 可靠性好 但编程较复杂 是直接搜索法中最为有效 的算法之一 3 无约束最优化直接方法和间接方法的异同无约束最优化直接方法和间接方法的异同 直接方法与使用导数的方法相比 一般来说 收敛的比较慢 但是 它对 目标函数不要求导数存在 迭代简单 编制程序一般也比较容易 如下表所示 无约束最优化算法计算量存储量收敛速度复杂性 最速下降法 需要计算一 阶导数 计 算量不大 存储量小慢 线性收 敛 仅计算一阶 导数 不复 杂 牛顿法需要计算海