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

约束优化问题 可行域 特殊问题可行方向法 线性约束问题次梯度优化 对偶问题 一般问题逐步二次规划法惩罚函数法内点法 原对偶内点法 凸规划 常用方法 1 第10章 约束优化 二次规划与逐步二次规划法ConstrainedOptimization QuadraticProgrammingandSQP 2 解的情况 无可行解 无界 有解 其中G是n阶对称方阵 ai d是n维常向量 有解时 G半正定 KKT点即为全局极小点 G正定 有惟一的极小点 G不定 局部解有可能不是全局解 此时找全局解是NP 难问题 3 有价证券的组合优化 投资组合 设对第i项投资的资金投放比例为xi 问题 对收益与风险的折衷进行建模 投资集合 1 n 可能收益为ri 4 有价证券的组合优化 续 证卷组合优化 portfoliooptimization 5 有价证券的组合优化 续 Markowitz引入风险容许参数 risktoleranceparameter 找出 最优的 证券投资组合 6 等式约束二次规划积极集法逐步二次规划法 7 等式约束二次规划 8 等式约束二次规划 9 代入q x 等式约束二次规划 基本消元法 消去x3 10 等式约束二次规划 基本消元法 续 找A的可逆子矩阵A1 进行消元 如果正定 解方程组可得惟一解 11 等式约束二次规划 广义消元法 令Y和Z分别是n m与n n m 矩阵 满足 如果ZTGZ正定 则原问题有惟一解 解方程组 12 等式约束二次规划 广义消元法 续 构造Y和Z的正交分解法 对矩阵A进行QR分解 即 13 等式约束二次规划 广义消元法 续 14 实用二次规划算法综述 经典积极集法 classicalactive setmethods 求解凸和非凸二次规划问题 中小规模 几百个变量 梯度投影法 gradient projectionmethods 界约束QP BoxQP 内点法 interior pointmethods 大规模凸二次规划 15 积极集法 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 不满足某些约束 找阻滞约束和步长 称取到最小值的指标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 是关于增量的等式约束二次规划子问题的最优解 且满足该问题的二阶充分条件 则p k s k 是原目标函数的下降方向 积极集法 理论分析 线搜索法 每个迭代点都可行 定理10 2 1设x k 是等式约束二次规划子问题的最优解 是对应的乘子 假设约束的梯度向量线性无关 且存在指标使得 考虑问题 设该问题的解为s 则s 是第j个约束的可行方向 即 此外 如果s 满足二阶充分条件 则 24 存在许多技术确定初始点 比如人工变量法 在恰当的假定下可证明 算法有限步找到解 可以推广来求解非凸二次规划 积极集法 进一步说明 初试点相同 但初始工作集不同 则后面的迭代不同 即使初始工作集相同 后面的迭代也可能不同 迭代次数有可能超过不等式约束的个数 选取初试工作集的额外要求 所选约束的梯度线性无关 25 逐步二次规划法SuccessiveQuadraticProgrammingMethod 26 假设和记号 在设计和分析算法时 通常假设f x ci x 是连续可微 二阶连续可微 的 且导数是李普希兹连续的 27 等式约束问题 Lagrange Newton法 28 等式约束问题 Lagrange Newton法 设是近似解 则其牛顿校正满足 29 等式约束问题 Lagrange Newton法 续 令 上述方程组即 给定初始点 利用上面两式进行迭代解等式约束问题的 Lagrange Newton法 定理假设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 实用逐步二次规划法 全局化策略 使用线搜索策略或者