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

《约束优化 二次规划与SQP课件.ppt》由会员分享，可在线阅读，更多相关《约束优化 二次规划与SQP课件.ppt（36页珍藏版）》请在三一办公上搜索。

1、约束优化问题,可行域：,特殊问题可行方向法线性约束问题次梯度优化对偶问题,一般问题逐步二次规划法惩罚函数法内点法(原对偶内点法)凸规划,常 用 方 法,1,第10章：约束优化：二次规划与逐步二次规划法 Constrained Optimization:Quadratic Programming and SQP,2,解的情况：无可行解、无界、有解,其中 G 是 n 阶对称方阵，ai,d是 n 维常向量,有解时：G半正定：KKT点即为全局极小点 G 正 定：有惟一的极小点 G 不 定：局部解有可能不是全局解，此时找全 局解是NP-难问题,3,有价证券的组合优化,投资组合：设对第 i 项投资的资金投

2、放比例为 xi,问题：对收益与风险的折衷进行建模,投资集合1,n，可能收益为ri,4,有价证券的组合优化(续),证卷组合优化(portfolio optimization)：,5,有价证券的组合优化(续),Markowitz引入风险容许参数(risk tolerance parameter),找出“最优的”证券投资组合！,6,等式约束二次规划 积极集法 逐步二次规划法,7,等式约束二次规划,8,等式约束二次规划,9,代入 q(x),等式约束二次规划基本消元法,消去 x3,10,等式约束二次规划基本消元法(续),找 A 的可逆子矩阵 A1，进行消元,如果 正定，解方程组 可得惟一解,11,等式约

3、束二次规划广义消元法,令 Y 和 Z 分别是 nm 与 n(n-m)矩阵，满足,如果ZTGZ正定，则原问题有惟一解，解方程组,12,等式约束二次规划广义消元法(续),构造 Y 和 Z的正交分解法,对矩阵 A 进行QR分解，即,13,等式约束二次规划广义消元法(续),14,实用二次规划算法综述,经典积极集法(classical active-set methods),求解凸和非凸二次规划问题中小规模(几百个变量！),梯度投影法(gradient-projection methods),界约束QP(BoxQP)!,内点法(interior-point methods),大规模凸二次规划！,15,积

4、极集法,16,技术注记：此处用线性约束规范代替LICQ!故二次规划的任一解x*均满足KKT条件,其中 G 是 n 阶对称方阵，ai,d是 n 维常向量,解的情况：无可行解、无界、有解,积极集法问题,最优积极集！,17,积极集法算法的动机(motivation),如果提前知道，求解,对最优积极集进行猜测，并不断修正，直到得到正确的！,考虑第 k 次迭代：x(k)是可行点，Wk 是工作集(由等式约束和部分或全部积极不等式约束组成),其中,18,积极集法算法的原理,x(k)不是当前等式约束问题的解，即s(k)0:,x(k)+s(k)满足其它约束：,，工作集保持不变,x(k)+s(k)不满足某些约束，

5、找阻滞约束和步长：,称取到最小值的指标 p对应的约束为阻滞(blocking)约束,无阻滞约束时，工作集不变；否则给工作集添加一个阻滞约束,19,积极集法算法的原理(续),乘子中与不等式约束对应的分量非负：x(k)是原问题的KKT点，进而是全局解,x(k)是当前等式约束问题的解，即s(k)=0：设当前等式约束问题的Lagrange乘子是,否则，存在,通常取指标 q 满足：,20,积极集法算例,21,积极集法算例(续),作业中用同样的初始点和不同的初始工作集进行迭代求解,22,积极集法算法,算法10.2.1 求解凸二次规划的积极集法,23,定理10.2.2 假设 s(k)是关于增量的等式约束二次

6、规划子问题的最优解，且满足该问题的二阶充分条件，则 p(k)=s(k)是原目标函数的下降方向.,积极集法理论分析,线搜索法、每个迭代点都可行,定理10.2.1 设 x(k)是等式约束二次规划子问题的最优解，是对应的乘子.假设约束的梯度向量 线性无关，且存在指标 使得.考虑问题,设该问题的解为 s.则 s 是第 j 个约束的可行方向，即.此外，如果 s 满足二阶充分条件，则.,24,存在许多技术确定初始点比如人工变量法！,在恰当的假定下可证明算法有限步找到解！,可以推广来求解非凸二次规划,积极集法进一步说明,初试点相同，但初始工作集不同，则后面的迭代不同；即使初始工作集相同，后面的迭代也可能不同

7、,迭代次数有可能超过不等式约束的个数,选取初试工作集的额外要求：所选约束的梯度线性无关,25,逐步二次规划法Successive Quadratic Programming Method,26,假设和记号,在设计和分析算法时，通常假设 f(x),ci(x)是连续可微(二阶连续可微)的，且导数是李普希兹连续的！,27,等式约束问题Lagrange-Newton法,28,等式约束问题Lagrange-Newton法,设 是近似解，则其牛顿校正 满足,29,等式约束问题Lagrange-Newton法(续),令，上述方程组即,给定初始点，利用上面两式进行迭代 解等式约束问题的 Lagrange-Ne

8、wton法,定理 假设 x*是等式约束问题的满足二阶充分条件的局部极小点,且rank(A*)=m，是惟一的Lagrange乘子.则当 充分接近 时，Lagrange-Newton法有定义，且由该方法产生的序列 二次收敛到.,30,基本/局部逐步二次规划法,考虑二次规划问题,的解和对应的Lagrange乘子，其中,二次规划的KKT条件,31,基本/局部逐步二次规划法(续),假设 是等式约束问题的满足二阶充分条件的极小点，即,这里 Z 是A*Ts=0的基础解系组成的矩阵.,则s*=0(x*)是下列问题的惟一最优解,32,基本/局部逐步二次规划法(续),算法10.3.1 基本SQP法,33,基本/局部逐步二次规划法(续),例,34,基本/局部逐步二次规划法(续),优点：局部二阶收敛存在问题 初始点不好时，迭代可能发散 子问题的解可能不存在无界或者不可行 需要二阶导数W(k),35,实用逐步二次规划法,全局化策略：使用线搜索策略或者信赖域策略 评价函数法 常用的是 l1 精确罚函数，迭代中需更新惩罚因子；滤子(Filter)法 存在问题：具有Martos效应，需要采取校正措施近似二阶导数 用近似矩阵B(k)代替W(k)用近似矩阵代替既约海森矩阵Z(k)TW(k)Z(k)子问题的求解,36,