无约束问题的最优化条件

5 1无约束问题的最优性条件 1 局部极小点2 严格局部极小点3 全局 总体 极小点4 严格全局 总体 极小点 注 在非线性规划中 大多数算法都致力于求最优化问题的局部极小点 一般求全局极小点极为困难 仅当问题为凸规划时 局部极小为全局极小 一 极小点的概念 二 无约束问题最优性条件 5 2最速下降法 解 例1 用最速下降法求 的极小值 只迭代一次 二 算法终止标准 三 最速下降算法收敛性定理 四 最速下降法的收敛速度 五 算法特点 相邻两次迭代的搜索方向是正交的 迭代点列呈锯齿形前进 迭代点越靠近最优解附近 目标函数值下降的速度越慢 算法收敛速度慢 5 3牛顿法 解 1 计算 2 方向 3 求最优步长 代入目标函数得 令 4 判断 即为所求 四 牛顿法的进一步修正 5 4信赖域法 5 5拟牛顿法 最速下降法 牛顿法 拟牛顿法 单纯形搜索法 对偶拟牛顿法 最小二乘法 5 6共轭方向法 5 7powell算法 一 Powell算法 1964年由Powell提出 后经Zangwoll 1967年 和Brent 1973年 改进 是迄今为止最有效的直接搜索法 该算法有效地利用了迭代过程中的历史信息 建立起能加速收敛的方向 有理论基础 以二次函数f x 1 2xTAx bTx c为模型进行研究 为什么选择二次函数作为模型 1 在非线性目标函数中 最简单的是二次函数 故任何对一般函数有效的方法首先应对二次函数有效 2 在最优点附近 非线性函数可用一个二次函数作近似 故对二次函数使用良好的方法 通常对一般函数也有效 3 很多实际问题的目标函数是二次函数 定理 假设1 n元函数f x 1 2xTAx bTx c中矩阵A是对称正定的 2 向量d 0 d 1 d m 1 m n 是互相A共轭的 x 0 x 1 是不同的任意两点 分别从x 0 x 1 出发 依次沿d 0 d 1 d m 1 作一维精确搜索 设最后一次一维搜索的极小点分别为x 0 和x 1 则有 向量d x 0 x 1 与d 0 d 1 d m 1 互为A共轭 以上定理说明如果已知前m个共轭方向 可以找到第m 1个共轭方向 二 Powell算法的迭代过程 一边搜索 一边找共轭方向 共分n个阶段 每一阶段都进行n 1次搜索 最后产生一个共轭方向 二维空间中的Powell方法示意图 以二次函数f x1 x2 为例 例 用Powell法求解 可以验证d 2 3 与d 2 2 关于A共轭 三 Powell算法流程 开始 例 用powell算法求解 书上例11 4 2 5 8单纯形法 一 单纯形 Simplex 定义 二 单纯形搜索法的基本思想 单纯形法是利用单纯形的顶点计算目标函数值 按一定规则进行探索性搜索 对搜索区单纯形顶点的函数值进行比较 判断目标函数的变化趋势 确定有利的单纯体移动的方向 单纯形搜索法中 单纯形的移动是通过反射 收缩 扩张三种运算来实现 最坏点 次坏点 最好点 三 单纯形的搜索移动 为作反射运算 需求出除最坏点外的其余所有顶点的重心 反射运算 求反射点 反射系数 常取 二维单纯形 有四种可能 单纯形搜索法对不同情况给出相应处理措施 情形三 进行收缩运算 情形四 进行收缩运算 计算收缩点 与情形三处理相同 只是收缩点的计算不同 产生新的单纯形后 继续下一轮迭代 5 9坐标轮换法 基本算法 a 搜索有效 b 搜索低效 c 搜索无效 存在的问题 5 10模式搜索法 一 模式搜索法 5 11旋转方向法 旋转方向法是Rosenbrock于1960年提出 旋转方向法是在每一次迭代中采用变步长的轴向移动 然后利用轴向的旋转来产生一组新的方向作为下一次迭代的轴向 其目的是为了加快收敛速度 与模式搜索法中的轴向移动的区别 新轴向的产生 为了提高求解效率 需要进行各轴向的旋转 并以新的n个单位正交方向组作为下一次迭代的轴向 从探测阶段的开始点指向该探测阶段的结束点的方向xk 1 xk很可能是有利于目标函数下降的方向 因此新的一组轴向应该包括这个方向 旋转