约束优化算法ppt课件.ppt

《约束优化算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、优化理论第6讲约束优化问题的算法约束优化问题可行域：特殊问题可行方向法－线性约束问题次梯度优化－对偶问题一般问题逐步二次规划法惩罚函数法内点法(原对偶内点法)－凸规划常用方法假设和记号在设计和分析算法时，通常假设f(x),ci(x)是连续可微(二阶连续可微)的，且导数是李普希兹连续的！逐步二次规划法SuccessiveQuadraticProgrammingMethod等式约束问题－Lagrange-Newton法KKT条件：其中等式约束问题－Lagrange-Newton法KKT条件：其中设是近似解，则其牛顿校正满足等式约束问题－Lagrange-

2、Newton法(续)令，上述方程组即给定初始点，利用上面两式进行迭代解等式约束问题的－Lagrange-Newton法定理假设x*是等式约束问题的满足二阶充分条件的局部极小点,且rank(A*)=m，是惟一的Lagrange乘子.则当充分接近时，Lagrange-Newton法有定义，且由该方法产生的序列二次收敛到.基本/局部逐步二次规划法考虑二次规划问题的解和对应的Lagrange乘子，其中二次规划的KKT条件基本/局部逐步二次规划法(续)假设是等式约束问题的满足二阶充分条件的极小点，即这里Z是A*Ts=0的基础解系组成的矩阵.则s*=0(x*)是下

3、列问题的惟一最优解基本/局部逐步二次规划法(续)算法9.2基本SQP法基本/局部逐步二次规划法(续)例基本/局部逐步二次规划法(续)优点：局部二阶收敛存在问题⊙初始点不好时，迭代可能发散⊙子问题的解可能不存在－无界或者不可行⊙需要二阶导数－W(k)实用逐步二次规划法全局化策略：使用线搜索策略或者信赖域策略⊙评价函数法常用的是l1精确罚函数，迭代中需更新惩罚因子；⊙滤子(Filter)法存在问题：具有Martos效应，需要采取校正措施近似二阶导数⊙用近似矩阵B(k)代替W(k)⊙用近似矩阵代替既约海森矩阵Z(k)TW(k)Z(k)子问题的求解罚函数法Pe

4、naltyFunctionMethod约束优化问题其中函数假定（算法分析与设计）：注：实践中该假定经常不满足,但没关系！⊙　　　(有时C2)，导数是Lipschitz连续罚函数法/序列无约束极小化法：外点罚函数、内点罚函数(障碍罚函数)、精确罚函数惩罚函数法－外点罚函数二次惩罚函数、乘子法、惩罚函数障碍函数法－内点罚函数现代内点法－原－对偶路径跟随法二次惩罚函数法>0是惩罚参数一定条件下，当时病态海森矩阵！特点：光滑的(一阶可微)，但需要二次惩罚函数法(续)条件数精确罚函数法SQP中常用*****例存在，当时，求解即可一定条件下，避免了无约束优化问题的

5、病态性！特点：不需要；是非光滑的！结论：对任一罚函数的解与原问题的相同特点：在x1=1处不可微；进行整理，得精确罚函数法(续)⊙先验确定惩罚参数很难；通常是计算一系列子问题，并在计算过程中调整该参数⊙与逐步二次规划法有密切联系；SQP的线搜索实现中通常以惩罚函数作为评价函数精确罚函数法(续)算法的动机与框架乘子罚函数法乘子法/增广Lagrange函数法Methodofmultipliers/AugmentedLagrangianmethod存在，当时，可以一定条件下，实际计算中，对乘子进行更新！乘子罚函数法(续)算法：warmstart技术第k次迭代固

6、定参数，以x(k)为初始点求更新乘子：根据需要更新惩罚参数(且不必趋于无穷)：给定初始惩罚参数；最优解和乘子的估计乘子罚函数法(续)例解和Lagrange乘子的初始猜测：以x(k)为初始点，利用纯粹牛顿法求解无约束极小化问题惩罚参数：乘子罚函数法(续)乘子罚函数法(续)可以用使用导数的算法求解子问题！避免了病态海森矩阵！增广Lagrange乘子法的特点：所得子问题是光滑的；一定条件下，不需要对数障碍函数法障碍因子一定条件下，当时特点：光滑的(一阶可微)，但需要病态海森矩阵！原问题是凸规划时，障碍函数是凸函数！对数障碍函数法(续)对数障碍函数法(续)障碍

7、函数的海森矩阵的条件数障碍函数法(原始内点法)的两个潜在困难：⊙随着障碍参数趋于零，障碍函数的海森矩阵病态性加剧⊙前一次的迭代点作为本次无约束优化的初始点太差！基本/原始(primal)障碍函数法对数障碍函数法(续)对数障碍函数法(续)凸规划！障碍函数是凸函数，故求它的驻点即可！原－对偶路径跟随法跟踪方程的保持的解，直至　逐渐缩减到零！KKT条件“扰动的”(perturbed)KKT条件: