最优化方法幻灯片.ppt

作　业 用FR共轭梯度法求解： 多维约束最优化方法 惩罚函数法 SUMT:序列无约束极小化方法 (Sequential Unconstrained Minimization Technique) 乘子法 外点法（二次罚函数方法） 内点法（内点障碍罚函数法） 罚函数法 基本思想 设法将约束问题求解转化为无约束问题求解． 具体说： 根据约束的特点，构造某种惩罚函数， 然后把它加到目标函数中去，将约束问题的 求解化为一系列无约束问题的求解．　　 惩罚策略： 企图违反约束的迭代点给予很大的　　 目标函数值． 迫使一系列无约束问题的极小点或 者无限地靠近可行域，或者一直保持在可行域 内移动，直到收敛到极小点． 外罚函数法（外点法） 引例： 求解等式约束问题: 解: 图解法求出最优解 构造： 但是 性态极坏， 无法用有效的无约束 优化算法求解． 设想构造： 其中 是很大的正数． 求解此无约束问题得： 当 时， 有： 等式约束问题 构造： 其中 为参数，称为罚因子． 分析： 当 不是可行解时， 越大， 惩罚越重． 因此当 充分大时， 应充分小． 即 的极小点应充分逼近可行域， 进而 逼近(1)的最优解． 不等式约束问题 构造： 分析： 当 不是可行解时， 越大， 惩罚越重． 因此当 充分大时， 应充分小． 即 的极小点应充分逼近可行域， 进而 逼近(2)的最优解． 一般约束问题 构造： 其中： 例1： 用外罚函数法求解： 解： 即： 因此： 牛顿法优点 (1) (2) 对正定二次函数，迭代一次就可以得到 极小点． 如果 正定且初始点选取合适， 算法 二阶收敛． 牛顿法缺点 (1) (2) 对多数问题算法不是整体收敛的． 每次都需要计算 计算量大． (3) 每次都需要解 方程组有时奇异或病态的， 无法确定 或 不是下降方向． (4) 收敛到鞍点或极大点的可能性并不小． 阻尼牛顿法算法 Step1: 给出 Step2: 计算 如果 停． Step3: 否则计算 Step4: 沿 并且求解方程 得出 进行线有哪些信誉好的足球投注网站， 得出 Step5: 令 转Step2. 阻尼牛顿法收敛定理 定理2: 设 二阶连续可微， 又设对任意的 存在常数 使得 在 上满足： 则在精确线有哪些信誉好的足球投注网站条件下， 阻尼牛顿法产生的点列 满足： (1) 当 是有限点列时， 其最后一个点为 的唯一极小点． (2) 当 是无限点列时， 收敛到 的唯一极小点． 阻尼牛顿法收敛定理 定理3: 设 二阶连续可微， 又设对任意的 存在常数 使得 在 上满足： 则在Wolfe不精确线有哪些信誉好的足球投注网站条件下， 阻尼牛顿法 产生的点列 满足： 且 收敛到 的唯一极小点． 例2： 用阻尼牛顿法求解： 解： 显然 不是正定的， 但： 于是， 沿方向 进行线有哪些信誉好的足球投注网站， 得其极小点 从而迭代不能继续下去． 带保护的牛顿法算法 给出 Step1: 若 为奇异的，转Step8，否则， Step2: 令 Step3: 若 为奇异的，转Step8，否则， 则转Step8，否则， Step4: 若 则转Step9，否则， Step5: 沿方向 进行线有哪些信誉好的足球投注网站， 求出 并令 Step6: 若 停； Step7: 令 转Step1； Step8: 令 转Step5； Step9: 令 转Step5. 例3： 用带保护的牛顿法求解： 解： 显然 不是正定的， 但： 于是， 因为， 故令， 沿 进行线有哪些信誉好的足球投注网站得： 第二次迭代： 而： 使 故令 沿 进行线有哪些信誉好的足球投注网站， 得出 于是: 此时: 共轭梯度法 问题1: 如何建立有效的算法？ 从二次模型到一般模型 问题2: 什么样的算法有效呢？ 二次终止性(经过有限次迭代必达到极小点的性质） 算法特点 （１）建立在二次模型上，具有二次终止性． （２）有效的算法，克服了最速下降法的慢 收敛性，又避免了牛顿法的计算量大和局部收 性的缺点． （３）算法简单，易于编程，需存储空间小等 优点，是求解大规模问题的主要方法． 共轭方向及其性质 定义1: 设 是 中任一组 非零向量， 如果： 则称 是关于 共轭的． 注： 若 则是正交的，因此共轭是 正交的推广． 定理1: 设 为 阶正定阵， 非零向量组 关于 共轭， 则必线性无关． 推论1: 设 为 阶正定阵， 非零向量组 关于 共轭， 则向量构成 的一组基． 推论2: 设 为 阶正定阵， 非零向量组 关于 共轭， 若向量 与 关于 共轭， 则 求 的极小点的方法共轭方向法算法 Step1: 给出 计算 和初始下降方向 Step2: 如果 停止迭代． Step3: 计算 使得 Step4: 采用某种共轭方向法计算 使得： Step5: 令 转Step2. 共轭方向法基本定理 定义2: 设 维向量组 线性无关， 向量集合 为 与 生成