约束优化_二次规划与SQP

约束优化问题,可行域：,特殊问题可行方向法线性约束问题次梯度优化对偶问题,一般问题逐步二次规划法惩罚函数法内点法(原对偶内点法)凸规划,常用方法,第10章：约束优化：二次规划与逐步二次规划法ConstrainedOptimization:QuadraticProgrammingandSQP,解的情况：无可行解、无界、有解,其中G是n阶对称方阵，ai,d是n维常向量,有解时：G半正定：KKT点即为全局极小点G正定：有惟一的极小点G不定：局部解有可能不是全局解，此时找全局解是NP-难问题,有价证券的组合优化,投资组合：设对第i项投资的资金投放比例为xi,问题：对收益与风险的折衷进行建模,投资集合1,n，可能收益为ri,有价证券的组合优化(续),证卷组合优化(portfoliooptimization)：,有价证券的组合优化(续),Markowitz引入风险容许参数(risktoleranceparameter),找出“最优的”证券投资组合！,等式约束二次规划积极集法逐步二次规划法,等式约束二次规划,等式约束二次规划,代入q(x),等式约束二次规划基本消元法,消去x3,等式约束二次规划基本消元法(续),找A的可逆子矩阵A1，进行消元,如果正定，解方程组可得惟一解,等式约束二次规划广义消元法,令Y和Z分别是nm与n(n-m)矩阵，满足,如果ZTGZ正定，则原问题有惟一解，解方程组,等式约束二次规划广义消元法(续),构造Y和Z的正交分解法,对矩阵A进行QR分解，即,等式约束二次规划广义消元法(续),实用二次规划算法综述,经典积极集法(classicalactive-setmethods),求解凸和非凸二次规划问题中小规模(几百个变量！),梯度投影法(gradient-projectionmethods),界约束QP(BoxQP)!,内点法(interior-pointmethods),大规模凸二次规划！,积极集法,技术注记：此处用线性约束规范代替LICQ!故二次规划的任一解x*均满足KKT条件,其中G是n阶对称方阵，ai,d是n维常向量,解的情况：无可行解、无界、有解,积极集法问题,最优积极集！,积极集法算法的动机(motivation),如果提前知道，求解,对最优积极集进行猜测，并不断修正，直到得到正确的！,考虑第k次迭代：x(k)是可行点，Wk是工作集(由等式约束和部分或全部积极不等式约束组成),其中,积极集法算法的原理,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求解凸二次规划的积极集法,定理10.2.2假设s(k)是关于增量的等式约束二次规划子问题的最优解，且满足该问题的二阶充分条件，则p(k)=s(k)是原目标函数的下降方向.,积极集法理论分析,线搜索法、每个迭代点都可行,定理10.2.1设x(k)是等式约束二次规划子问题的最优解，是对应的乘子.假设约束的梯度向量线性无关，且存在指标使得.考虑问题,设该问题的解为s.则s是第j个约束的可行方向，即.此外，如果s满足二阶充分条件，则.,存在许多技术确定初始点比如人工变量法！,在恰当的假定下可证明算法有限步找到解！,可以推广来求解非凸二次规划,积极集法进一步说明,初试点相同，但初始工作集不同，则后面的迭代不同；即使初始工作集相同，后面的迭代也可能不同,迭代次数有可能超过不等式约束的个数,选取初试工作集的额外要求：所选约束的梯度线性无关,逐步二次规划法SuccessiveQuadraticProgrammingMethod,假设和记号,在设计和分析算法时，通常假设f(x),ci(x)是连续可微(二阶连续可微)的，且导数是李普希兹连续的！,等式约束问题Lagrange-Newton法,等式约束问题Lagrange-Newton法,设是近似解，则其牛顿校正满足,等式约束问题Lagrange-Newton法(续),令，上述方程组即,给定初始点，利用上面两式进行迭代解等式约束问题的Lagrange-Newton法,定理假设x*是等式约束问题的满足二阶充分条件的局部极小点,且rank(A*)=m，是惟一的Lagrange乘子.则当充分接近时，Lagrange-Newton法有定义，且由该方法产生的序列二次收敛到.,基本/局部逐步二次规划法,考虑二次规划问题,的解和对应的Lagrange乘子，其中,二次规划的KKT条件,基本/局部逐步二次规划法(续),假设是等式约束问题的满足二阶充分条件的极小点，即,这里Z是A*Ts=0的基础解系组成的矩阵.,则s*=0(x*)是下列问题的惟一最优解,基本/局部逐步二次规划法(续),算法10.3.1基本SQP法,基本/局部逐步二次规划法(续),例,基本/局部逐步二次规划法(续),优点：局部二阶收敛存在问题初始点不好时，迭代可能发散子问题的解可能不存在无界或者不可行需要二阶导数W(k),实用逐步二次规划法,全局化策略：使用线搜索策略或者