,实用优化方法,第10章 约束优化：二次规划与SQP,单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学与系统科学学院,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,*,约束优化问题,可行域,：,特殊,问题,可行方向法线性约束问题,次梯度优化对偶问题,一般,问题,逐步二次规划法,惩罚函数法,内点法(原对偶内点法)凸规划,常 用 方 法,约束优化问题可行域：特殊问题,1,第10章：约束优化：二次规划与逐步二次规划法,Constrained Optimization:Quadratic Programming and SQP,第10章：约束优化：二次规划与逐步二次规划法 Constr,2,解的情况：无可行解、无界、有解,其中 G 是,n,阶对称方阵，a,i,d是,n,维常向量,有解时：,G半正定：KKT点即为全局极小点,G 正 定：有惟一的极小点,G 不 定：局部解有可能不是全局解，此时找全,局解是NP-难问题,G 半正定,凸二次规划,解的情况：无可行解、无界、有解其中 G 是 n 阶对称方阵，,3,有价证券的组合优化,投资组合：设对第,i,项投资的资金投放比例为,x,i,问题：对收益与风险的折衷进行建模,投资集合1,n,，可能收益为,r,i,假定II 所有资金均投资，不允许卖空,假定I,设,是随机变量,有价证券的组合优化 投资组合：设对第 i 项投资的资金投放,4,有价证券的组合优化(续),证卷组合：,证卷组合的,利润,：,证卷组合的,期望收益,和,方差,：,G 是半正定矩阵！,证卷组合优化,(portfolio optimization)：,有价证券的组合优化(续)证卷组合：证卷组合的利润：证卷组,5,有价证券的组合优化(续),Markowitz引入,风险容许参数,(risk tolerance parameter),找出“,最优的,”证券投资组合！,参数 ，设定值依赖于投资者的个人偏好,保守型投资者：大的参数取值,冒险性投资者：小的参数取值,有价证券的组合优化(续)Markowitz引入风险容许参数(,6,等式约束二次规划,积极集法,逐步二次规划法,等式约束二次规划,7,等式约束二次规划,等式约束二次规划,8,等式约束二次规划,其中,假定:线性无关,核心思想：消元法(基本、广义),其中 ，A,1,可逆,等式约束二次规划其中假定:,9,代入,q,(x),等式约束二次规划基本消元法,消去,x,3,代入 q(x)等式约束二次规划基本消元法消去 x3,10,等式约束二次规划基本消元法(续),找 A 的可逆子矩阵 A,1,，进行消元,如果 正定，解方程组 可得惟一解,等式约束二次规划基本消元法(续)找 A 的可逆子矩阵 A1,11,等式约束二次规划广义消元法,令 Y 和 Z 分别是,n,m,与,n,(,n,-,m,)矩阵，满足,考察方程组A,T,x=b:Yb是特解；通解x=Yb+s，,其中s 是齐次线性方程组A,T,s=0的解,任一可行解均可表示为:x=Yb+Zy,如果Z,T,GZ正定，则原问题有惟一解，解方程组,等式约束二次规划广义消元法令 Y 和 Z 分别是 nm,12,等式约束二次规划广义消元法(续),构造 Y 和 Z的正交分解法,对矩阵 A 进行QR分解，即,等式约束二次规划广义消元法(续)构造 Y 和 Z的正交分解,13,等式约束二次规划广义消元法(续),等式约束二次规划广义消元法(续),14,实用二次规划算法综述,经典积极集法(classical active-set methods),求解凸和非凸二次规划问题中小规模(几百个变量！),梯度投影法(gradient-projection methods),界约束QP(BoxQP)!,内点法(interior-point methods),大规模凸二次规划！,实用二次规划算法综述 经典积极集法(classical a,15,积极集法,积极集法,16,技术注记：,此处用线性约束规范代替LICQ!故二次规划的任一解,x*,均满足KKT条件,其中 G 是,n,阶对称方阵，a,i,d是,n,维常向量,解的情况：无可行解、无界、有解,G 半正定,凸二次规划,积极集法,问题,最优积极集！,技术注记：此处用线性约束规范代替LICQ!故二次规划的任,17,积极集法,算法的动机(motivation),如果,提前,知道,，,求解,对最优积极集进行猜测，并不断修正，直到得到正确的！,考虑第,k,次迭代：,x,(,k,),是可行点，,W,k,是工作集(由等式约束和部分或全部积极不等式约束组成),其中,积极集法算法的动机(motivation)如果提前知道,18,积极集法,算法的原理,x,(,k,),不是当前等式约束问题的解，即s,(,k,),0:,x,(,k,),+s,(,k,),满足其它约束：,，工作集保持不变,x,(,k,),+s,(,k,),不满足某些约束，找阻滞约束和步长：,称取到最小值的指标 p对应的约束为,阻滞(blocking),约束,无阻滞约束时，工作集不变；否则给工作集添加一个阻滞约束,积极集法算法的原理 x(k)不是当前等式约束问题的解，即,19,积极集法,算法的原理(续),乘子中与不等式约束对应的分量非负：,x,(,k,),是原问题的KKT点，进而是全局解,x,(,k,),是当前等式约束问题的解，即s,(,k,),=,0：,设当前等式约束问题的Lagrange乘子是,否则，存在,通常取指标,q,满足：,积极集法算法的原理(续)乘子中与不等式约束对应的分量,20,积极集法,算例,积极集法算例,21,积极集法,算例(续),作业中用同样的初始点和不同的初始工作集进行迭代求解,积极集法算例(续)作业中用同样的初始点和不同的初始工作集进,22,积极集法,算法,算法10.2.1 求解凸二次规划的积极集法,积极集法算法算法10.2.1 求解凸二次规划的积极集法,23,定理10.2.2,假设 s,(,k,),是关于增量的等式约束二次规划子问题的最优解，且满足该问题的二阶充分条件，则 p,(,k,),=,s,(,k,),是原目标函数的下降方向.,积极集法,理论分析,线搜索法、每个迭代点都可行,定理10.2.1,设 x,(,k,),是等式约束二次规划子问题的最优解，,是对应的乘子.假设约束的梯度向量 线性无关，且存在指标 使得 .考虑问题,设该问题的解为 s.则 s 是第,j,个约束的可行方向，即,.此外，如果 s 满足二阶充分条件，则 .,定理10.2.2 假设 s(k)是关于增量的等式约束二次规,24,存在许多技术确定初始点,比如人工变量法！,在恰当的假定下可证明,算法有限步找到解！,可以推广来求解非凸二次规划,积极集法,进一步说明,初试点相同，但初始工作集不同，则后面的迭代不同；,即使初始工作集相同，后面的迭代也可能不同,迭代次数有可能超过不等式约束的个数,选取初试工作集的额外要求：所选约束的梯度线性无关,存在许多技术确定初始点比如人工变量法！在恰当的假,25,逐步二次规划法,Successive,Quadratic Programming,Method,逐步二次规划法,26,假设和记号,在设计和分析算法时，通常假设,f,(x),c,i,(x)是连续可微(二阶连续可微)的，且导数是李普希兹连续的！,假设和记号 在设计和分析算法时，通常假设 f(x,27,等式约束问题,Lagrange-Newton法,KKT条件：,其中,等式约束问题Lagrange-Newton法KKT条件：其,28,等式约束问题,Lagrange-Newton法,KKT条件：,其中,设 是近似解，则其牛顿校正 满足,等式约束问题Lagrange-Newton法KKT条件：其,29,等式约束问题,Lagrange-Newton法(续),令 ，上述方程组即,给定初始点 ，利用上面两式进行迭代,解等式约束问题的,Lagrange-Newton法,定理,假设 x*是等式约束问题的满足二阶充分条件的局部极小点,且rank(A*)=,m,，是惟一的Lagrange乘子.则当 充分接近 时，Lagrange-Newton法有定义，且由该方法产生的序列 二次,收敛到 .,等式约束问题Lagrange-Newton法(续)令,30,基本/局部逐步二次规划法,考虑二次规划问题,的解和对应的Lagrange乘子，其中,二次规划的KKT条件,基本/局部逐步二次规划法考虑二次规划问题的解和对应的Lagr,31,基本/局部逐步二次规划法(续),假设 是等式约束问题的满足二阶充分条件的极小点，即,这里 Z 是A*,T,s=0的基础解系组成的矩阵.,则s*=0(x*)是下列问题的惟一最优解,基本/局部逐步二次规划法(续)假设,32,基本/局部逐步二次规划法(续),算法10.3.1 基本SQP法,基本/局部逐步二次规划法(续)算法10.3.1 基本SQP法,33,基本/局部逐步二次规划法(续),例,基本/局部逐步二次规划法(续)例,34,基本/局部逐步二次规划法(续),优点：局部二阶收敛,存在问题,初始点不好时，迭代可能发散,子问题的解可能不存在,无界,或者,不可行,需要二阶导数,W,(,k,),基本/局部逐步二次规划法(续)优点：局部二阶收敛,35,实用逐步二次规划法,全局化策略：使用线搜索策略或者信赖域策略,评价函数法,常用的是,l,1,精确罚函数，迭代中需更新惩罚因子；,滤子,(Filter),法,存在问题,：具有,Martos,效应，需要采取校正措施,近似二阶导数,用近似矩阵,B,(,k,),代替,W,(,k,),用近似矩阵代替既约海森矩阵,Z,(,k,)T,W,(,k,),Z,(,k,),子问题的求解,实用逐步二次规划法全局化策略：使用线搜索策略或者信赖域策略,36,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,感谢亲观看此幻灯片，此课件部分内容来源于网络，,37,