CANFile约束优化理论

,单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,数学与系统科学学院,实用优化方法,第,09,章,约束优化：理论,第,09,章：约束优化：理论,Theory of Constrained Optimization,约束优化,可行域,：,局部,解,/,全局,解,在设计和分析算法时，,通常假设,f,(x),是连续可微,(,二阶连续可微,),的，且梯度是李普希兹连续的！,两个重要概念,可行解 处的,积极约束,、积极,(active),集,积极,(,约束指标,),集,积极的不等式约束指标集,例,2.2.2,Lagrange,函数,：,一阶条件,称 为对应的,Lagrange,乘子,一阶条件：,KKT,条件,正则性假设,1,：,Karush-Kuhn-Tucker,条件,KKT,条件,/KKT,点,互补条件,/,严格互补,定理,(,一阶条件,),.,若,x*,是局部极小点且在,x*,处正则性假设,1,成立，则存在,Lagrange,乘子 使得 满足,一阶条件,(,续,),一阶条件,(,续,),一阶条件,(,续,),Lagrange,乘子法,引入,Lagrange,函数,：,当,约束规范成立,时，必要条件,一阶必要条件即,凸规划,(convex programming),注,1.,凸规划的所有,局部解也是全局解,。,注,2.,线性规划,是凸规划；,二次规划,中目标函数的海森矩阵 半正定时，也是凸规划,.,凸规划,(convex programming),：,凸集,K,上极小化凸函数,定理,.,凸规划的任一,KKT,点是全局极小点,.,乘子的解释灵敏度,对约束进行,扰动,Lagrange,乘子的解释：,(,最优值关于约束的,),灵敏度,约束函数变化时，对应的最优值的变化率！,记扰动问题的解和乘子分别为 ，则,一阶条件,的,理论证明,点与闭凸集的分离定理及应用,给定 中的向量,令,分离定理,.,存在超平面 分离闭凸集,C,和非零向量,.,Farkas,引理,.,集合,是空集当且仅当存在 使得,给定 中的向量,.,Farkas,引理,.,集合,是空集当且仅当存在,使得,一阶必要条件,f,在,x,的,下降方向,集,引理,设,x*,是约束问题的局部极小点，则在,x*,处没有,可行,的,下降,方向，即,称 的聚点,p,是,序列可行方向,，全体记为,引理：,线性化可行方向,集，记为,LFD,其中 且 ，是长度固定的向量,.,考虑可行序列 ，则,称 为对应的,Lagrange,乘子,一阶必要条件：,KKT,条件,正则性假设,1,：,Karush-Kuhn-Tucker,条件,KKT,条件,/KKT,点,互补条件,/,严格互补,定理,(,一阶条件,),.,若,x*,是局部极小点且在,x*,处正则性假设,1,成立，则存在,Lagrange,乘子 使得 满足,正则性假设,1,minimize x,2,subject to,minimize x,1,subject to,正则性假设,1,：,例,考虑约束条件 在,x*=(0, 0),的情况,定理 设,x*,是约束问题的局部极小点，且在,x*,处,LCQ,或者,LICQ,成立,则,x*,满足,KKT,条件,.,约束规范,约束规范,(,constraint quality, CQ,),：,引理,常用的约束规范,.,当,i) (LCQ),，或者,ii),线性无关时,(LICQ),，有,二阶条件,二阶必要,条件：如果,x*,是极小点，且,CQ,成立，则,等式约束问题,-,二阶条件,约束规范,(CQ),：,二阶充分,条件：如果事实,成立，则,x*,必是严格局部极小点,.,二阶必要,条件：对任一序列可行方向,p,，有,设,x*,是问题的局部极小点，且满足,KKT,条件,二阶条件,(,续,),问题,：讨论参数 取何值时，,x*=0,是局部极小点,当严格互补条件成立时，二阶必要,/,充分条件与如下等式约束问题相同：,弱,积极约束与,强,积极约束,非积极,约束；,积极,约束,(,弱,积极约束,/,强,积极约束,),强,(,或严格）积极约束,一般地，需要定义,强,(,或者严格）积极,(strongly,or strictly,active),约束指标集,二阶正则性假设,定义,事 实：,正则性假设,2,：,一般约束问题,二阶条件,定理,(,二阶必要条件,),.,若,x*,是局部极小点，且在,x*,处正则性假设,1,成立，则存在,Lagrange,乘子 使得,KKT,条件成立。对任一这样的乘子 ，如果正则性假设,2,成立，则,定理,(,二阶充分条件,),.,如果在,x*,处存在,Lagrange,乘子 使得,KKT,条件成立，且对该乘子 ，满足,则,x*,是约束问题的严格局部极小点,.,Lagrange,对偶,线性规划的对偶理论,原问题,minimize,，对偶问题,maximize,原问题最优解所对应的单纯形乘子是对偶问题的解,弱,对偶性,强,对偶性,(,之一有解，则另一个必有解，且最优值相等,),线性规划的对偶理论：,原问题对偶问题,Lagrange,对偶,(,计算,),与,Fenche,对偶,(,理论,),！, 希望解决的,问题, 定义新问题，以 为变量？且解是,!, 新问题的解可给原问题提供一个下界！, 建立对偶理论的,基本思路, 将约束极小化问题 “,min-max”,问题, 定义对偶问题是 “,max-min”,问题,建立对偶理论的基本思路,二人零和博弈,(zero-sum game),前提,:,两人采取理性行为,不管对方采取何种策略，该行为都能保证自己的最大获益,Peter,和,Harriet,的策略集分别为,X,和,Y, 博弈规则,:,同时公布所选策略，,若,Peter,选 ，,Harriet,选,Peter,付给,Harriet,Peter,的问题,选,最多要支付,min-max,问题,原,问题,Harriet,的问题,max-min,问题,对偶,问题,选,最少收到,Lagrange,对偶,min-max,问题是研究对偶问题的基础！,各种对偶的区别：,的定义方式,不同,！,原问题,(primal),是希望,分别,处理的其它约束,Lagrange,函数：,Lagrange,对偶,(,续,),对任意的 ，定义,原问题,(primal),即,对任意的 ，定义,对偶问题即,如果要求,c,i,(x)=0,，则对偶问题中与之对应的变量,没有符号限制,例,2.,对偶问题,Lagrange,对偶,(,续,),例,3.,对偶问题,对偶问题的目标函数,没有解析,形式,Lagrange,对偶,(,续,),弱对偶定理,推论,3.,如果原问题无界，则它的对偶问题不可行,;,如果对偶问题无界，则原问题不可行,.,所有 表示,对偶问题,不可行！,弱对偶定理：,推论,2.,设 是原问题的可行解， 是对偶问题的可行解，且 ，则二者分别是各自问题的最优解,例,4.,对偶,间隙,(,duality,gap),：,弱对偶定理,(,续,),强对偶定理,强对偶定理,线性规划的对偶, 不管原问题是不是凸的，对偶问题为凹函数的,极大化问题,(,凸规划,),！, 对偶问题的约束仅有“,界约束,”，相当简单，在,很多时候求解对偶问题要容易得多,., 以支撑矢量机,(SVM),为例进行说明！,Lagrange,对偶的优点,半定规划,(,Introduction to Semidefinite Programming,),a good website for semidefinite programming is:,半 定 规 划,是数学规划在二十世纪九十年代最令人兴奋的发展,应用,：传统的凸优化、控制理论和组合优化等领域,求解,：内点法,(,有效求解,SDP),半 定 规 划,-,预备知识,原始问题,对偶问题,在,x,必须满足,m,个给定的,方程,且属于闭凸锥 的条件下，极小化线性函数,弱,对偶定理,.,原始问题在任一可行解处的值不比对偶的小,.,强,对偶定理,.,只要原始问题或者对偶问题之一有解，则另一个问题也有解，且对偶间隙是零,.,半 定 规 划,-,预备知识, 称,K,是,闭凸锥,(closed convex cone),，如果,K,是,闭,集, 由闭凸锥,K,可以定义,序,n,阶对称矩阵的全体,n,阶对称半正定矩阵的全体,n,阶,对称正定,矩阵的全体,是闭凸锥,闭凸锥与序,半 定 规 划,-,预备知识,半正定锥 中定义的序，设,半 定 规 划预备知识,X,是一个对称矩阵,X,是一个形如 的向量,X,是 空间中的向量,关于,X,的,线性,泛函,：,注,.,因为 ，不失一般性，可假设,半 定 规 划模型,原问题, 目标函数是线性函数,X,必须位于对称半正定矩阵,(,闭凸,),锥,X,必须满足,m,个线性方程,特点,确定,SDP,的数据：,半 定 规 划,-,模型,(,续,),例,设确定线性规划标准形的数据为,半 定 规 划,-,模型,(,续,),线性规划是半定规划的特例,第,(,i,j,),和,(,j,i,),个元素是,1,，其余为,0,令,半 定 规 划,-,对偶理论,对偶问题,等价于,原始问题,半 定 规 划,-,对偶理论,(,续,),等价于,3,个,(,线性,)+3,个,(,二次,)+1,个,(,三次,),不等式！,半 定 规 划,-,对偶理论,(,续,),上例的可行解和最优解的图示：,半 定 规 划,-,对偶理论,(,续,),定理,1.,设,X,和,( y, S,),分别是,SDP,和,SDD,的可行解，则,Slater,constraint quality!,迹的定义及性质：,.,则,SDP,和,SDD,都将取到它们各自的最优值，且最优值相等,.,定理,2.,假设存在,SDP,和,SDD,的可行解 满足,半 定 规 划,-,应用,最大割,问题,(max-cut), 是无向图，顶点集, 找子集 ，极大化,半 定 规 划,-,应用,最大割,问题,(max-cut),令,半 定 规 划,-,应用,(,续,),最大割问题的等价表述及,SDP,松弛,松弛：去掉秩,1,约束！,最大割问题的,SDP,松弛,半 定 规 划,-,应用,(,续,),松驰问题的可行集是,真正可行集的,外逼近,n,=3,时松弛问题的可行集,已证明,表明,SDP,松驰值不会比最大割,(,NP-,难,),的值高,13%,半 定 规 划,-,应用,(,续,),凸二次约束二次规划,(QCQP),等价表述,半 定 规 划,-,应用,(,续,),P,在,M,中的,Schur,补,特征值优化,(EOP),问题,：希望,S,的最大和最小特征值之差尽可能小,半 定 规 划,-,应用,(,续,),给定对称矩阵，构造矩阵,分别为,S,的最大和最小特征值,EOP,的,SDP,表述,半 定 规 划,-,应用,(,续,),