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

1、实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院约束优化问题约束优化问题可行域可行域：特殊特殊问题问题可行方向法线性约束问题可行方向法线性约束问题次梯度优化对偶问题次梯度优化对偶问题 一般一般问题问题逐步二次规划法逐步二次规划法惩罚函数法惩罚函数法内点法内点法(原对偶内点法原对偶内点法)凸规划凸规划常常 用用 方方 法法1实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院第第1010章：约束优化：二次规划与逐步二次规划法章：约束优化：二次规划与逐步二次规

2、划法 Constrained Optimization:Quadratic Programming and SQP 2实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院解的情况：无可行解、无界、有解解的情况：无可行解、无界、有解其中其中 G 是是 n 阶对称方阵，阶对称方阵，ai,d是是 n 维常向量维常向量有解时：有解时：G半正定：半正定：KKT点即为全局极小点点即为全局极小点 G 正正 定定：有惟一的极小点：有惟一的极小点 G 不不 定：局部解有可能不是全局解，此时找全定：局部解有可能不是全局解，此时找全 局解是局解是N

3、P-难问题难问题G 半正定半正定凸二次规划凸二次规划3实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院有价证券的组合优化有价证券的组合优化 投资组合：设对第投资组合：设对第 i 项投资的资金投放比例为项投资的资金投放比例为 xi 问题：对收益与风险的折衷进行建模问题：对收益与风险的折衷进行建模投资集合投资集合1,n，可能收益为，可能收益为ri 假定假定II 所有资金均投资，不允许卖空所有资金均投资，不允许卖空 假定假定I 设设 是随机变量是随机变量4实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规

4、划与SQP数学与系统科学学院数学与系统科学学院有价证券的组合优化有价证券的组合优化(续续)证卷组合：证卷组合：证卷组合的证卷组合的利润利润：证卷组合的证卷组合的期望收益期望收益和和方差方差：G 是半正定矩阵！是半正定矩阵！证卷组合优化证卷组合优化(portfolio optimization)：5实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院有价证券的组合优化有价证券的组合优化(续续)Markowitz引入引入风险容许参数风险容许参数(risk tolerance parameter)找出找出“最优的最优的”证券投资组合

5、！证券投资组合！参数参数 ，设定值依赖于投资者的个人偏好，设定值依赖于投资者的个人偏好保守型投资者：大的参数取值保守型投资者：大的参数取值冒险性投资者：小的参数取值冒险性投资者：小的参数取值6实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院l 等式约束二次规划等式约束二次规划l 积极集法积极集法l 逐步二次规划法逐步二次规划法7实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束二次规划等式约束二次规划8实用优化方法实用优化方法第第10章章 约束优

6、化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束二次规划等式约束二次规划其中其中假定假定:线性无关线性无关核心思想：消元法核心思想：消元法(基本、广义基本、广义)其中其中 ，A1可逆可逆9实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院代入代入 q(x)等式约束二次规划基本消元法等式约束二次规划基本消元法消去消去 x310实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束二次规划基本消元法等式约束二次规划基本消

7、元法(续续)找找 A 的可逆子矩阵的可逆子矩阵 A1，进行消元，进行消元如果如果 正定，解方程组正定，解方程组 可得惟一解可得惟一解11实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束二次规划广义消元法等式约束二次规划广义消元法令令 Y 和和 Z 分别是分别是 nm 与与 n(n-m)矩阵，满足矩阵，满足考察方程组考察方程组ATx=b:Yb是特解；通解是特解；通解x=Yb+s，其中其中s 是齐次线性方程组是齐次线性方程组ATs=0的解的解 任一可行解均可表示为任一可行解均可表示为:x=Yb+Zy如果如果ZTGZ正定

8、，则原问题有惟一解，解方程组正定，则原问题有惟一解，解方程组12实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束二次规划广义消元法等式约束二次规划广义消元法(续续)构造构造 Y 和和 Z的正交分解法的正交分解法对矩阵对矩阵 A 进行进行QR分解，即分解，即13实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束二次规划广义消元法等式约束二次规划广义消元法(续续)14实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划

9、与SQP数学与系统科学学院数学与系统科学学院实用二次规划算法综述实用二次规划算法综述 经典积极集法经典积极集法(classical active-set methods)求解凸和非凸二次规划问题中小规模求解凸和非凸二次规划问题中小规模(几百个变量！几百个变量！)梯度投影法梯度投影法(gradient-projection methods)界约束界约束QP(BoxQP)!内点法内点法(interior-point methods)大规模凸二次规划！大规模凸二次规划！15实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院积极集法

10、积极集法16实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院技术注记：技术注记：此处用线性约束规范代替此处用线性约束规范代替LICQ!故二次规划的任故二次规划的任一解一解x*均满足均满足KKT条件条件其中其中 G 是是 n 阶对称方阵，阶对称方阵，ai,d是是 n 维常向量维常向量解的情况：无可行解、无界、有解解的情况：无可行解、无界、有解G 半正定半正定凸二次规划凸二次规划积极集法积极集法问题问题最优积极集！最优积极集！17实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学

11、学院数学与系统科学学院积极集法积极集法算法的动机算法的动机(motivation)如果如果提前提前知道知道，求解求解对最优积极集进行猜测，并不断修正，直到得到正确的！对最优积极集进行猜测，并不断修正，直到得到正确的！考虑第考虑第 k 次迭代：次迭代：x(k)是可行点，是可行点，Wk 是工作集是工作集(由等式约束和部分或全部由等式约束和部分或全部积极不等式约束组成积极不等式约束组成)其中其中18实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院积极集法积极集法算法的原理算法的原理 x(k)不是当前等式约束问题的解，即不是当前等

12、式约束问题的解，即s(k)0:x(k)+s(k)满足其它约束：满足其它约束：，工作集保持不变，工作集保持不变 x(k)+s(k)不满足某些约束，找阻滞约束和步长：不满足某些约束，找阻滞约束和步长：称取到最小值的指标称取到最小值的指标 p对应的约束为对应的约束为阻滞阻滞(blocking)约束约束无阻滞约束时，工作无阻滞约束时，工作集不变；否则给工作集不变；否则给工作集添加一个阻滞约束集添加一个阻滞约束19实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院积极集法积极集法算法的原理算法的原理(续续)乘子中与不等式约束对应的分量

13、非负：乘子中与不等式约束对应的分量非负：x(k)是原问题的是原问题的KKT点，进而是全局解点，进而是全局解 x(k)是当前等式约束问题的解，即是当前等式约束问题的解，即s(k)=0：设当前等式约束问题的设当前等式约束问题的Lagrange乘子是乘子是 否则，存在否则，存在 通常取指标通常取指标 q 满足：满足：20实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院积极集法积极集法算例算例21实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院积极集法积极集法

14、算例算例(续续)作业中用同样的初始点和不同的初始工作集进行迭代求解作业中用同样的初始点和不同的初始工作集进行迭代求解22实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院积极集法积极集法算法算法算法算法10.2.1 求解凸二次规划的积极集法求解凸二次规划的积极集法23实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院定理定理10.2.2 假设假设 s(k)是关于增量的等式约束二次规划子问题是关于增量的等式约束二次规划子问题的最优解，且满足该问题的二阶充分条

15、件，则的最优解，且满足该问题的二阶充分条件，则 p(k)=s(k)是是原目标函数的下降方向原目标函数的下降方向.积极集法积极集法理论分析理论分析线搜索法、每个迭代点都可行线搜索法、每个迭代点都可行定理定理10.2.1 设设 x(k)是等式约束二次规划子问题的最优解，是等式约束二次规划子问题的最优解，是对应的乘子是对应的乘子.假设约束的梯度向量假设约束的梯度向量 线性无关，且存在指标线性无关，且存在指标 使得使得 .考虑考虑问题问题设该问题的解为设该问题的解为 s.则则 s 是第是第 j 个约束的可行方向，即个约束的可行方向，即 .此外，如果此外，如果 s 满足二阶充分条件，则满足二阶充分条件，

16、则 .24实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院 存在许多技术确定初始点存在许多技术确定初始点比如人工变量法！比如人工变量法！在恰当的假定下可证明在恰当的假定下可证明算法有限步找到解！算法有限步找到解！可以推广来求解非凸二次规划可以推广来求解非凸二次规划积极集法积极集法进一步说明进一步说明 初试点相同，但初始工作集不同，则后面的迭代不同；初试点相同，但初始工作集不同，则后面的迭代不同；即使初始工作集相同，后面的迭代也可能不同即使初始工作集相同，后面的迭代也可能不同 迭代次数有可能超过不等式约束的个数迭代次数有可能

17、超过不等式约束的个数 选取初试工作集的额外要求：所选约束的梯度线性无关选取初试工作集的额外要求：所选约束的梯度线性无关25实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院逐步二次规划法逐步二次规划法Successive Quadratic Programming Method26实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院假设和记号假设和记号 在设计和分析算法时，通常假设在设计和分析算法时，通常假设 f(x),ci(x)是连续是连续可微可微(二阶连

18、续可微二阶连续可微)的，且导数是李普希兹连续的！的，且导数是李普希兹连续的！27实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束问题等式约束问题Lagrange-Newton法法KKT条件：条件：其中其中28实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束问题等式约束问题Lagrange-Newton法法KKT条件：条件：其中其中设设 是近似解，则其牛顿校正是近似解，则其牛顿校正 满足满足29实用优化方法实用优化方法第第10章章 约束优

19、化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院等式约束问题等式约束问题Lagrange-Newton法法(续续)令令 ，上述方程组即，上述方程组即给定初始点给定初始点 ，利用上面两式进行迭代，利用上面两式进行迭代 解等式约束问题的解等式约束问题的 Lagrange-Newton法法定理定理 假设假设 x*是等式约束问题的满足二阶充分条件的局是等式约束问题的满足二阶充分条件的局部极小点部极小点,且且rank(A*)=m，是惟一的是惟一的Lagrange乘子乘子.则当则当 充分接近充分接近 时，时，Lagrange-Newton法有定义，且由该方法产生的序列法有定义，

20、且由该方法产生的序列 二次二次收敛到收敛到 .30实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院基本基本/局部逐步二次规划法局部逐步二次规划法考虑二次规划问题考虑二次规划问题的解和对应的的解和对应的Lagrange乘子，其中乘子，其中二次规划的二次规划的KKT条件条件31实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院基本基本/局部逐步二次规划法局部逐步二次规划法(续续)假设假设 是等式约束问题的满足二阶充分条件的极是等式约束问题的满足二阶充分条件的

21、极小点，即小点，即这里这里 Z 是是A*Ts=0的基础解系组成的矩阵的基础解系组成的矩阵.则则s*=0(x*)是下列问题的惟一最优解是下列问题的惟一最优解32实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院基本基本/局部逐步二次规划法局部逐步二次规划法(续续)算法算法10.3.1 基本基本SQP法法33实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院基本基本/局部逐步二次规划法局部逐步二次规划法(续续)例例34实用优化方法实用优化方法第第10章章 约束

22、优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院基本基本/局部逐步二次规划法局部逐步二次规划法(续续)优点：局部二阶收敛优点：局部二阶收敛 存在问题存在问题 初始点不好时，迭代可能发散初始点不好时，迭代可能发散 子问题的解可能不存在子问题的解可能不存在无界无界或者或者不可行不可行 需要二阶导数需要二阶导数W(k)35实用优化方法实用优化方法第第10章章 约束优化：二次规划与约束优化：二次规划与SQP数学与系统科学学院数学与系统科学学院实用逐步二次规划法实用逐步二次规划法 全局化策略：使用线搜索策略或者信赖域策略全局化策略：使用线搜索策略或者信赖域策略 评价函数法评价函数法 常用的是常用的是 l1 1 精确罚函数，迭代中需更新惩罚因子；精确罚函数，迭代中需更新惩罚因子；滤子滤子(Filter)法法 存在问题存在问题：具有：具有Martos效应，需要采取校正措施效应，需要采取校正措施 近似二阶导数近似二阶导数 用近似矩阵用近似矩阵B(k)代替代替W(k)用近似矩阵代替既约海森矩阵用近似矩阵代替既约海森矩阵Z(k)TW(k)Z(k)子问题的求解子问题的求解 36