约束优化_惩罚函数法.pdf

1 约束优化问题约束优化问题 可行域可行域 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 特殊特殊问题问题 线性约束线性约束问题 可行方向法问题 可行方向法 对偶对偶问题 次梯度优化问题 次梯度优化 一般一般问题 逐步二次规划法 惩罚函数法 内点法 问题 逐步二次规划法 惩罚函数法 内点法 原对偶内点法原对偶内点法 凸规划 凸规划 常 用 方 法常 用 方 法 优化理论优化理论 第10讲第10讲 约束优化约束优化惩罚函数法惩罚函数法 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 约束优化约束优化 惩罚函数法惩罚函数法 Constrained Optimization Penalty Function Method 约束优化问题约束优化问题 其中函数其中函数 假定假定 算法分析与设计算法分析与设计 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 假定假定 算法分析与设计算法分析与设计 注 注 实践中该假定经常不满足 但没关系 实践中该假定经常不满足 但没关系 有时有时C 2 导数是 导数是Lipschitz 连续连续 罚函数法罚函数法 序列无约束序列无约束极小化法 外点罚函数 内点罚函数 极小化法 外点罚函数 内点罚函数 障碍罚函数障碍罚函数 精确罚函数 精确罚函数 惩罚函数法 惩罚函数法 外点外点罚函数罚函数 二次惩罚函数 二次惩罚函数 乘子乘子法 惩罚函数法 惩罚函数 障碍函数法 障碍函数法 内点内点罚函数罚函数 原始对数障碍法原始对数障碍法 现代内点法现代内点法 原原 对偶路径跟随法对偶路径跟随法 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 原始对数障碍法原始对数障碍法 现代内点法现代内点法 原原对偶路径跟随法对偶路径跟随法 二次惩罚函数法二次惩罚函数法 条件数条件数 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 二次惩罚函数法 续 二次惩罚函数法 续 0 是是惩罚惩罚参数参数 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 一定条件下 当时一定条件下 当时 病态病态海森矩阵 海森矩阵 特点 特点 光滑光滑的 一阶可微 但需要的 一阶可微 但需要 2 精确罚函数法精确罚函数法SQP中常用 中常用 例例 特点 在特点 在 x1 1 处不可微 进行整理 得处不可微 进行整理 得 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 结论 对任一罚函数的解与原问题的相同 结论 对任一罚函数的解与原问题的相同 精确罚函数法精确罚函数法SQP中常用 中常用 存在 当时 求解即可 一定条件下 存在 当时 求解即可 一定条件下 特点 不需要 是特点 不需要 是非非光滑的 光滑的 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 避免了无约束优化问题的病态性 避免了无约束优化问题的病态性 先验确定惩罚参数很难 通常是计算一系列子问题 并在计算过程中调整该参数 与逐步二次规划法有密切联系 先验确定惩罚参数很难 通常是计算一系列子问题 并在计算过程中调整该参数 与逐步二次规划法有密切联系 SQP的线搜索实现中 通常以惩罚函数作为评价函数 的线搜索实现中 通常以惩罚函数作为评价函数 乘子罚函数法乘子罚函数法 例例 以以x k 为初始点为初始点利用纯粹牛顿法求解无约束极小化问题利用纯粹牛顿法求解无约束极小化问题 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 以以x k 为初始点为初始点 利用纯粹牛顿法求解无约束极小化问题利用纯粹牛顿法求解无约束极小化问题 解的初始猜测和解的初始猜测和Lagrange乘子的初始猜测分别为 惩罚参数 乘子的初始猜测分别为 惩罚参数 乘子罚函数法乘子罚函数法 续续 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 乘子罚函数法乘子罚函数法 续续 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 可以用 使用导数的方法 求解子问题 可以用 使用导数的方法 求解子问题 避免了病态海森矩阵 避免了病态海森矩阵 增广增广Lagrange乘子法的特点 所得子问题是 乘子法的特点 所得子问题是光滑光滑的 一定条件下 不需要的 一定条件下 不需要 算法的动机与框架算法的动机与框架 乘子罚函数法乘子罚函数法 续续 乘子法乘子法 增广增广Lagrange函数法函数法 Method of multipliers Augmented Lagrangian method 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 存在 当时 可以一定条件下 存在 当时 可以一定条件下 实际计算中 对乘子进行更新 实际计算中 对乘子进行更新 3 乘子罚函数法乘子罚函数法 续续 算法算法 tt技术技术 第第 k 次迭代固定参数 次迭代固定参数 以以 x k 为初始点求为初始点求 给定初始惩罚参数 最优解和乘子的估计给定初始惩罚参数 最优解和乘子的估计 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 warm start技术技术 更新乘子 更新乘子 根据需要根据需要更新惩罚参数 且更新惩罚参数 且不必不必趋于无穷 趋于无穷 对数障碍函数法对数障碍函数法 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 对数障碍函数法对数障碍函数法 续续 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 障碍函数的海森矩阵的条件数近似地等于 障碍函数法 障碍函数的海森矩阵的条件数近似地等于 障碍函数法 原始内点法原始内点法 的两个潜在困难 的两个潜在困难 随着障碍参数趋于零 障碍函数的海森矩阵病态性加剧随着障碍参数趋于零 障碍函数的海森矩阵病态性加剧 前一次的迭代点作为本次无约束优化问题的初始点太差 前一次的迭代点作为本次无约束优化问题的初始点太差 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 对数障碍函数法对数障碍函数法 续续 凸规划 凸规划 障碍函数是凸函数 故求它的驻点即可 障碍函数是凸函数 故求它的驻点即可 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 4 对数障碍函数法对数障碍函数法 续续 障碍因子障碍因子 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约束优化 惩罚函数法数学与系统科学学院数学与系统科学学院 一定条件下 当时一定条件下 当时 特点 特点 光滑光滑的 一阶可微 但需要的 一阶可微 但需要 病态病态海森矩阵 海森矩阵 原问题是凸规划时 障碍函数是凸函数 原问题是凸规划时 障碍函数是凸函数 基本基本 原始原始 primal 障碍函数法障碍函数法 对数障碍函数法对数障碍函数法 续续 优化理论优化理论 第第10讲 约束优化 惩罚函数法讲 约