最优化理论与方法ppt课件.ppt

使用导数的无约束最优化方法 策略表现形式方法线性近似最速下降法二次近似Newton法共轭梯度法用布鲁丹 Broyden 族或黄 Huang 族拟Newton法修正公式 1 最速下降法 SteepestMethod 考虑无约束问题下降算法对于下降方向的要求 最速下降法的要求 2 最速下降法 SteepestMethod 最速下降法的计算步骤 1 给出初始点和精度 2 计算 如果 则令 停止 否则 转 3 3 令 求解得到 4 令 转 2 3 最速下降法 SteepestMethod 对于最速下降法的几点说明 1 锯齿现象 目标函数在负梯度方向下降得最快只是局部性质 2 改进策略 在计算的开始阶段使用最速下降法 在迭代数次后 改用其他算法 4 最速下降法 SteepestMethod 二次函数情形下最速下降法的收敛速度定理考虑无约束最优化问题其中G是n阶对称正定矩阵 和分别是G的最大特征值和最小特征值 设是问题的解点 则最速下降法至少具有线性的收敛速度 并且满足下面的界 5 最速下降法 SteepestMethod 对于定理的说明 1 在上面定理中 如果考虑的是如下一般二次目标函数 其中G是n阶对称正定矩阵 则有类似的证明方法证明定理同样成立 2 当目标函数是二阶连续可微的一致凸函数时 由上章的推导可知 采用精确线性搜索的最速下降法产生的迭代点列至少是线性收敛的 6 最速下降法 SteepestMethod 定理 设最速下降法产生的点列收敛到 在附近二阶连续可微 且 正定 则线性收敛到 即其中M和m满足 和分别是的最小特征值和最大特征值 7 Newton法及其改进 Nowton法的主要内容 1 牛顿法的基本思想 2 阻尼牛顿法 3 带保护措施的阻尼牛顿法 4 吉尔 默里稳定牛顿法 5 信赖域方法 一 8 Newton法及其改进 1 牛顿法的基本思想 在目标函数的极小点的近似点附近将二阶Tayler展开 用展开的二次函数去逼近 将这个二次函数的极小点作为的一个新的近似点依次下去 用一系列二次函数的极小点去逼近的极小点 9 Newton法及其改进 设二次连续可微 则在处的二次近似为 令即 10 Newton法及其改进 若正定 对称 则存在 Newton迭代公式Newton方向 11 Newton法及其改进 定理 Newton法收敛定理 设二阶连续可微 是的局部最优解 正定 Hesse矩阵满足Lipschitz条件 即存在 使得对所有的i j 有其中是Hesse矩阵的元素 则当初始点充分靠近时 对于一切的k 牛顿迭代公式有定义 并且所得迭代点列收敛到 并且具有二阶收敛速度 12 Newton法及其改进 牛顿法面临的主要困难 1 很难检验初始点是否靠近最优解因而不能保证Hesse矩阵是否正定 得到的方向是下降方向 迭代点列的收敛性及收敛速度 2 牛顿法对目标函数要求高 二阶连续可微 且需较多的存储单元 每次迭代均要进行矩阵求逆运算 3 二次终止性 对于二次凸函数 用牛顿法求解 经1次迭代即达极小点 13 Newton法及其改进 2 阻尼牛顿法 在标准牛顿法增加了沿牛顿方向的直线搜索 阻尼牛顿法在适当的条件下具有全局收敛性 且为2级收敛 14 Newton法及其改进 阻尼牛顿法的缺点 阻尼牛顿法克服了牛顿法要求初始点充分靠近目标函数的极小点的缺点 但只有当目标函数的Hesse矩阵处处正定时 才具有全局收敛性 如果Hesse矩阵不是处处正定 当初始点远离局部极小点时 Hesse矩阵可能不正定 这时Hesse矩阵可能奇异也可能是非奇异 若Hesse矩阵奇异 求解方向的方程组可能无解 或者虽然有解 但求出的方向不能使迭代过程继续进行下去 若Hesse矩阵非奇异 但不正定 则求得的方向可能不是下降方向 15 Newton法及其改进 例 取 则 显然 是可逆矩阵 但不正定 其逆矩阵为于是 沿此方向进行线性搜索 其极小点为 因此迭代不能继续进行下去 16 Newton法及其改进 3 带保护措施的阻尼牛顿法 Goldstein和Price 1967 假设可逆 若正定 否则 17 Newton法及其改进 4 吉尔 默里稳定牛顿法 Gill和Murray 1974 定义 设在开集D上二次连续可微 i 如果Hesse矩阵至少有一个负特征值 则叫做不定点 ii 如果X是一个不定点 若方向d满足则称d为在X处的负曲率方向 18 Newton法及其改进 负曲率方向的性质 1 若方向d为负曲率方向 则也是负曲率方向 2 在鞍点处 负曲率方向必是下降方向 3 在一般点处 若负曲率方向d满足 则d与均是下降方向 则d是下降方向 则是下降方向 19 Newton法及其改进 Gill Murray稳定牛顿法的基本思想 当Hesse矩阵在迭代点处为不定矩阵时 对其进行强迫正定的分解 当趋于零时 采用负曲率方向使函数值下降 构造一个对称正定矩阵在处做下降方向 20 Newton法及其改进 算法 Gill Murray稳定牛顿法 1 给定初始点 精度 常数令 2 计算梯度和Hesse矩阵 令 3 若 则停止计算 输出 4 判断是否正定 若正定 转 6 否则转 5 5 计算 转 4 21 Newton法及其改进 算法 Gill Murray稳定牛顿法 6 求解求出搜索方向 7 直线搜索 且令 8 令 转 2 22 Newton法及其改进 定理 设二阶连续可微 且存在 使得为有界闭凸集 假定在吉尔 默里稳定牛顿法中取 且初始点 则吉尔 默里稳定牛顿法产生的迭代序列满足 i 当为有穷点列时 其最后一个元素必为的稳定点 ii 当为无穷点列时 它必有聚点 且它的所有聚点都是的平稳点 23 共轭方向法 概述 共轭方向法是介于最速下降法与牛顿法之间的一类方法 它仅需利用一阶导数信息 但克服了最速下降法收敛慢的缺点 又避免了存储和计算牛顿法所需要的二阶导数信息 因而简便 易实现 且十分适合大规模 稀疏 优化问题的计算 通常只经过较少的迭代次数就能获得满足所要求精度的近似解 共轭方向法是从研究二次函数的极小化产生的 但是它可以推广到处理非二次函数的极小化问题 最典型的共轭方向法就是本节研究的共轭梯度法 下一节介绍的拟牛顿法也是共轭方向法 24 共轭方向法 概述 例 设 其中A为正定矩阵 能否从任意初始点出发 经过至多两步迭代达到其极限点 最优解 定义 共轭方向 设A为n阶对称正定矩阵 是n维非零向量 如果 则称向量和是关于A共轭的 类似地 设是m个n维向量 如果 则称是关于A共轭的向量组 25 共轭方向法 概述 定理 设A为n阶对称正定矩阵 则关于A共轭的非零向量是线性无关的 定理 共轭方向法基本定理 设二次函数的极小化问题为 其中A是n阶对称正定矩阵 是任意一组关于A共轭的非零向量 若从任意初始点出发 依次沿方向进行精确线性搜索 则至多经过n次迭代就可达到问题的最优解 26 共轭梯度法 定理 设向量线性无关 则由这组向量可以构造m个关于A共轭的向量 共轭梯度法的基本思想是把共轭性与最速下降方法相结合 利用已知点处的梯度构成一组共轭方向 并沿这组方向进行搜索 求出目标函数的最小点 根据共轭方向的基本性质 这种方法具有二次终止性 27 共轭梯度法 二次函数 考虑其中A为对称正定矩阵 给定初始点 计算若 则 停止计算 否则 令 若已知点和搜索方向 则其中使用精确线性搜索得到 28 共轭梯度法 二次函数 此时 令则有对于二次函数 有即解得 29 共轭梯度法 二次函数 计算在处的梯度若 则停止计算 否则 用和构造 设要求与关于A共轭 解得再从出发 沿方向搜索 30 共轭梯度法 二次函数 共轭梯度法的迭代公式为 对于二次函数有 31 共轭梯度法 二次函数 FR 1964 32 共轭梯度法 二次函数 定理 设目标函数为正定二次函数则采用精确线性搜索的共轭梯度法经步终止 且对所有成立下列关系式 33 共轭梯度法 二次函数 FR 1964 PRP 1969 CW 1972 Dixon 1972 34 共轭梯度法 二次函数 例3 30 用共轭梯度法求解取初始点为 35 共轭梯度法 二次函数 共轭梯度法的计算步骤 1 给定初始值 令 2 计算 若 则 停止计算 否则 转 3 3 计算共轭系数 36 共轭梯度法 二次函数 共轭梯度法的计算步骤 4 构造搜索方向 5 计算令 6 令 转 2 37 共轭梯度法 非二次函数 1 步长不能用显式格式计算 必须用其他直线搜索方法来确定 2 矩阵A不再是常数矩阵 需要用现行点处的Hesse矩阵 改进思路 将共轭梯度法应用于非二次函数的极小化时 每迭代n次就周期地选取负梯度方向作为搜索方向 所以这种算法称作重新开始的共轭梯度法 即令 38 共轭梯度法 非二次函数 鲍威尔 对非二次函数 在计算中可能出现与几乎正交的情况 此时FR PRP 39 共轭梯度法 二次函数 共轭梯度法的计算步骤 1 给定初始值 令 2 计算 若 则 停止计算 否则 转 3 3 计算共轭系数 40 共轭梯度法 二次函数 共轭梯度法的计算步骤 4 构造搜索方向 5 做直线搜索计算令 6 若 则 停止计算 否则 令 转 2 41 共轭梯度法 非二次函数 重新开始的共轭梯度法允许采用近似线性搜索过程 只是在采用近似线性搜索时 要采取一定的检查措施 以保证所得到的搜索方向是下降方向 但是 如果频繁地利用负梯度方向作为搜索方向 将大大降低共轭梯度法的效率 而使算法的性态变得更象最速下降法 采取检查措施可以克服这个困难 42 拟牛顿法 最速下降法具有结构简单 计算量小的优点 但其收敛速度较慢 共轭梯度类算法具有计算存储量小的优点 一般使用于大规模优化问题 而牛顿法及各种改进的牛顿法具有收敛速度快的优点 但要求在迭代过程中每次构造搜索方向时 首先要计算目标函数的Hesse矩阵 然后需要求解一个线性方程组 从而计算量大 存储量也大 而且有的目标函数的Hesse矩阵很难计算 甚至不好求出 这就抵消了牛顿法收敛速度快的优点 这类算法只适用于中小规模的优化问题 43 拟牛顿法 拟牛顿算法只需利用目标函数及其一阶导数的信息 构造对称正定的矩阵来近似牛顿法中的Hesse矩阵或者其逆矩阵 产生较好的近似牛顿方向 避免了Hesse矩阵的计算 减少了计算量 并且具有超线性收敛的优点 该法被认为是无约束优化 中小规模 问题中最有效的算法 44 拟牛顿法 设二次连续可微 则在处的二次近似为 则即拟牛顿法的基本迭代格式 45 拟牛顿法 记则若Hesse矩阵可逆 则拟牛顿条件或拟牛顿方程 46 拟牛顿法 二次近似满足性质 47 拟牛顿法 拟牛顿算法的一般框架与牛顿法相比 拟牛顿法还要求以下几点 1 或 是对称正定矩阵 从而是下降方向 使得方法具有下降性质 2 或称 或 为校正矩阵 上两个方程为校正条件 48 拟牛顿法 拟牛顿算法框架 1 给出初始值 令 2 计算 如果 则令 停止迭代 否则 计算 3 沿方向d作线性搜索求 令 4 计算校正产生使得拟牛顿条件成立的 令 返回 2 49 拟牛顿法 秩1校正解得 设则有即从而 50 拟牛顿法 这时 称为秩1校正公式 为了保证矩阵的对称性 若取称为对称秩1校正公式 51 拟牛顿法 若取称为布鲁丹 Broyden 秩1校正公式 52 拟牛顿法 对称秩2校正公式 53 第3 2 5节信赖域方法 信赖域方法的基本思想 首先选取一个信赖域半径 并由此定义的一个邻域使得n维二次模型是目标函数的一个合适的模拟 然后求解具有信赖域约束的子问题 54 第3 2 5节信赖域方法 实际下降量 预测下降量 衡量二次模型近似目标函数的指标 55 第3 2 5节信赖域方法 1 给定初始点 初始步长 精度 阈值 满足放大系数令 2 计算 如果 则 停止 否则 形成矩阵 3 求解子问题 求出 56 第3 2 5节信赖域方法 4 计算和的值 如果 那么 如果和 那么 否则 令 5 如果 那么 否则 转 2 57 第3 2 5节信赖域方法 例3 20 用信赖域方法求解