约束优化-二次规划与SQP.ppt

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