《约束优化_惩罚函数法》由会员分享，可在线阅读，更多相关《约束优化_惩罚函数法（4页珍藏版）》请在金锄头文库上搜索。
1、1约束优化问题约束优化问题可行域可行域：优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院特殊特殊问题问题 线性约束线性约束问题可行方向法问题可行方向法 对偶对偶问题次梯度优化问题次梯度优化一般一般问题 逐步二次规划法 惩罚函数法 内点法问题 逐步二次规划法 惩罚函数法 内点法(原对偶内点法原对偶内点法)凸规划凸规划常 用 方 法常 用 方 法优化理论优化理论第10讲第10讲 约束优化约束优化惩罚函数法惩罚函数法优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院约束优化约束优化：
2、惩罚函数法惩罚函数法 Constrained Optimization: Penalty Function Method约束优化问题约束优化问题其中函数其中函数假定假定（算法分析与设计算法分析与设计）优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院假定假定（算法分析与设计算法分析与设计）：注：注：实践中该假定经常不满足,但没关系！ 实践中该假定经常不满足,但没关系！(有时有时C 2)，导数是，导数是Lipschitz 连续连续罚函数法罚函数法/序列无约束序列无约束极小化法：外点罚函数、内点罚函数极小化法：外点罚函数、内点罚函数(障碍罚
3、函数障碍罚函数)、精确罚函数、精确罚函数? 惩罚函数法惩罚函数法外点外点罚函数罚函数二次惩罚函数、二次惩罚函数、乘子乘子法、惩罚函数法、惩罚函数 ? 障碍函数法障碍函数法内点内点罚函数罚函数原始对数障碍法原始对数障碍法、 现代内点法现代内点法(原原对偶路径跟随法对偶路径跟随法)优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院原始对数障碍法原始对数障碍法、 现代内点法现代内点法(原原对偶路径跟随法对偶路径跟随法)二次惩罚函数法二次惩罚函数法条件数条件数优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学
4、学院数学与系统科学学院二次惩罚函数法(续)二次惩罚函数法(续)0 是是惩罚惩罚参数参数优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院一定条件下，当时一定条件下，当时病态病态海森矩阵！海森矩阵！特点：特点：光滑光滑的(一阶可微)，但需要的(一阶可微)，但需要2精确罚函数法精确罚函数法SQP中常用中常用*例例特点：在特点：在 x1=1 处不可微；进行整理，得处不可微；进行整理，得优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院结论：对任一罚函数的解与原问题的相同！结论：对任一罚
5、函数的解与原问题的相同！精确罚函数法精确罚函数法SQP中常用中常用*存在，当时，求解即可一定条件下，存在，当时，求解即可一定条件下，特点：不需要；是特点：不需要；是非非光滑的！光滑的！优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院避免了无约束优化问题的病态性！避免了无约束优化问题的病态性！ 先验确定惩罚参数很难；通常是计算一系列子问题， 并在计算过程中调整该参数 与逐步二次规划法有密切联系； 先验确定惩罚参数很难；通常是计算一系列子问题， 并在计算过程中调整该参数 与逐步二次规划法有密切联系；SQP的线搜索实现中 通常以惩罚函数作为
6、评价函数的线搜索实现中 通常以惩罚函数作为评价函数乘子罚函数法乘子罚函数法例例以以x(k)为初始点为初始点利用纯粹牛顿法求解无约束极小化问题利用纯粹牛顿法求解无约束极小化问题优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院以以x(k)为初始点为初始点，利用纯粹牛顿法求解无约束极小化问题利用纯粹牛顿法求解无约束极小化问题解的初始猜测和解的初始猜测和Lagrange乘子的初始猜测分别为惩罚参数：乘子的初始猜测分别为惩罚参数：乘子罚函数法乘子罚函数法(续续)优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科
7、学学院数学与系统科学学院乘子罚函数法乘子罚函数法(续续)优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院可以用“使用导数的方法”求解子问题！可以用“使用导数的方法”求解子问题！避免了病态海森矩阵！避免了病态海森矩阵！增广增广Lagrange乘子法的特点：所得子问题是乘子法的特点：所得子问题是光滑光滑的；一定条件下，不需要的；一定条件下，不需要算法的动机与框架算法的动机与框架乘子罚函数法乘子罚函数法(续续)乘子法乘子法/增广增广Lagrange函数法函数法 Method of multipliers/Augmented Lagrangi
8、an method优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院存在，当时，可以一定条件下， 存在，当时，可以一定条件下，实际计算中，对乘子进行更新！实际计算中，对乘子进行更新！3乘子罚函数法乘子罚函数法(续续)算法算法：tt技术技术第第 k 次迭代固定参数，次迭代固定参数，以以 x(k)为初始点求为初始点求给定初始惩罚参数；最优解和乘子的估计给定初始惩罚参数；最优解和乘子的估计优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院warm start技术技术更新乘子：更新乘子：
9、根据需要根据需要更新惩罚参数(且更新惩罚参数(且不必不必趋于无穷)：趋于无穷)：对数障碍函数法对数障碍函数法优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院对数障碍函数法对数障碍函数法(续续)优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院障碍函数的海森矩阵的条件数近似地等于障碍函数法障碍函数的海森矩阵的条件数近似地等于障碍函数法(原始内点法原始内点法)的两个潜在困难：的两个潜在困难： 随着障碍参数趋于零，障碍函数的海森矩阵病态性加剧随着障碍参数趋于零，障碍函数的海森矩阵病态
10、性加剧 前一次的迭代点作为本次无约束优化问题的初始点太差！前一次的迭代点作为本次无约束优化问题的初始点太差！优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院对数障碍函数法对数障碍函数法(续续)凸规划！凸规划！障碍函数是凸函数，故求它的驻点即可！障碍函数是凸函数，故求它的驻点即可！优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院4对数障碍函数法对数障碍函数法(续续)障碍因
11、子障碍因子优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院一定条件下，当时一定条件下，当时特点：特点：光滑光滑的(一阶可微)，但需要的(一阶可微)，但需要病态病态海森矩阵！海森矩阵！原问题是凸规划时，障碍函数是凸函数！原问题是凸规划时，障碍函数是凸函数！基本基本/原始原始(primal)障碍函数法障碍函数法对数障碍函数法对数障碍函数法(续续)优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院原对偶路径跟随法原对偶路径跟随法KKT条件条件“扰动的扰动的”(perturbed)KKT条件条件:优化理论优化理论第第10讲 约束优化：惩罚函数法讲 约束优化：惩罚函数法数学与系统科学学院数学与系统科学学院跟踪方程跟踪方程的保持的解，直至逐渐缩减到零！的保持的解，直至逐渐缩减到零！
