约束优化-二次规划与SQPPPT课件.ppt

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