约束优化理论介绍.ppt

《约束优化理论介绍.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第09章：约束优化：理论TheoryofConstrainedOptimization约束优化可行域：局部解/全局解在设计和分析算法时，通常假设f(x)是连续可微(二阶连续可微)的，且梯度是李普希兹连续的！两个重要概念可行解处的积极约束、积极(active)集积极(约束指标)集积极的不等式约束指标集例2.2.2Lagrange函数：一阶条件◎称为对应的Lagrange乘子一阶条件：KKT条件正则性假设1：◎Karush-Kuhn-Tucker条件,KKT条件/KKT点◎互补条件/严格互补定理(一阶条件).若x*是局部极小点且在x*处

2、正则性假设1成立，则存在Lagrange乘子使得满足一阶条件(续)一阶条件(续)一阶条件(续)Lagrange乘子法引入Lagrange函数：当约束规范成立时，必要条件一阶必要条件即凸规划(convexprogramming)注1.凸规划的所有局部解也是全局解。注2.线性规划是凸规划；二次规划中目标函数的海森矩阵半正定时，也是凸规划.凸规划(convexprogramming)：凸集K上极小化凸函数定理.凸规划的任一KKT点是全局极小点.乘子的解释－灵敏度对约束进行扰动Lagrange乘子的解释：－(最优值关于约束的)灵敏度约束函数

3、变化时，对应的最优值的变化率！记扰动问题的解和乘子分别为，则一阶条件的理论证明点与闭凸集的分离定理及应用给定中的向量令分离定理.存在超平面分离闭凸集C和非零向量.Farkas引理.集合是空集当且仅当存在使得给定中的向量.Farkas引理.集合是空集当且仅当存在使得一阶必要条件f在x’的下降方向集引理设x*是约束问题的局部极小点，则在x*处没有可行的下降方向，即称　的聚点p是序列可行方向，全体记为引理：线性化可行方向集，记为LFD其中　　　且，　　　是长度固定的向量.考虑可行序列，则◎称为对应的Lagrange乘子一阶必要条件：KKT

4、条件正则性假设1：◎Karush-Kuhn-Tucker条件,KKT条件/KKT点◎互补条件/严格互补定理(一阶条件).若x*是局部极小点且在x*处正则性假设1成立，则存在Lagrange乘子使得满足正则性假设1minimizex2subjecttominimizex1subjectto正则性假设1：例考虑约束条件在x*=(0,0)的情况定理设x*是约束问题的局部极小点，且在x*处LCQ或者LICQ成立,则x*满足KKT条件.约束规范约束规范(constraintquality,CQ)：引理常用的约束规范.当i)(LCQ)，或者ii

5、)线性无关时(LICQ)，有二阶条件二阶必要条件：如果x*是极小点，且CQ成立，则等式约束问题--二阶条件约束规范(CQ)：二阶充分条件：如果事实成立，则x*必是严格局部极小点.二阶必要条件：对任一序列可行方向p，有设x*是问题的局部极小点，且满足KKT条件二阶条件(续)问题：讨论参数取何值时，x*=0是局部极小点当严格互补条件成立时，二阶必要/充分条件与如下等式约束问题相同：弱积极约束与强积极约束◎非积极约束；积极约束(弱积极约束/强积极约束)强(或严格）积极约束一般地，需要定义强(或者严格）积极(stronglyorstrict

6、lyactive)约束指标集二阶正则性假设定义事实：正则性假设2：一般约束问题－－二阶条件定理(二阶必要条件).若x*是局部极小点，且在x*处正则性假设1成立，则存在Lagrange乘子使得KKT条件成立。对任一这样的乘子，如果正则性假设2成立，则定理(二阶充分条件).如果在x*处存在Lagrange乘子使得KKT条件成立，且对该乘子，满足则x*是约束问题的严格局部极小点.Lagrange对偶线性规划的对偶理论原问题－minimize，对偶问题－maximize原问题最优解所对应的单纯形乘子是对偶问题的解弱对偶性强对偶性(之一有解，

7、则另一个必有解，且最优值相等)线性规划的对偶理论：原问题←→对偶问题◎Lagrange对偶(计算)与Fenche对偶(理论)！◎希望解决的问题⊙定义新问题，以为变量？且解是!⊙新问题的解可给原问题提供一个下界！◎建立对偶理论的基本思路⊙将约束极小化问题“min-max”问题⊙定义对偶问题是“max-min”问题建立对偶理论的基本思路二人零和博弈(zero-sumgame)◎前提:两人采取理性行为－不管对方采取何种策略，该行为都能保证自己的最大获益◎Peter和Harriet的策略集分别为X和Y◎博弈规则:同时公布所选策略，若Pete

8、r选，Harriet选,Peter付给HarrietPeter的问题选,最多要支付min-max问题←→原问题Harriet的问题max-min问题←→对偶问题选,最少收到Lagrange对偶min-max问题是研究对偶问题的基础！各