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

约束优化问题可行域：

特殊问题可行方向法－线性约束问题次梯度优化－对偶问题

一般问题逐步二次规划法惩罚函数法内点法(原对偶内点法)－凸规划常用方法1约束优化问题可行域：特殊问题第10章：约束优化：二次规划与逐步二次规划法

ConstrainedOptimization:QuadraticProgrammingandSQP

2第10章：约束优化：二次规划与逐步二次规划法

Constr解的情况：无可行解、无界、有解其中G是n阶对称方阵，ai,d是n

维常向量有解时：⊙

G半正定：KKT点即为全局极小点⊙

G正定：有惟一的极小点⊙

G不定：局部解有可能不是全局解，此时找全局解是NP-难问题G半正定凸二次规划3解的情况：无可行解、无界、有解其中G是n阶对称方阵，有价证券的组合优化⊙投资组合：设对第i项投资的资金投放比例为xi⊙问题：对收益与风险的折衷进行建模投资集合{1,…,n}，可能收益为ri

假定II所有资金均投资，不允许卖空

假定I

设

是随机变量4有价证券的组合优化⊙投资组合：设对第i项投资的资金投放有价证券的组合优化(续)⊙证卷组合：证卷组合的利润：证卷组合的期望收益和方差：G是半正定矩阵！⊙证卷组合优化(portfoliooptimization)：5有价证券的组合优化(续)⊙证卷组合：证卷组合的利润：证卷组有价证券的组合优化(续)Markowitz引入风险容许参数(risktoleranceparameter)找出“最优的”证券投资组合！⊙参数，设定值依赖于投资者的个人偏好保守型投资者：大的参数取值冒险性投资者：小的参数取值6有价证券的组合优化(续)Markowitz引入风险容许参数(

等式约束二次规划积极集法逐步二次规划法7等式约束二次规划7等式约束二次规划8等式约束二次规划8等式约束二次规划其中假定:线性无关核心思想：消元法(基本、广义)其中，A1可逆9等式约束二次规划其中假定:代入q(x)等式约束二次规划－基本消元法消去x310代入q(x)等式约束二次规划－基本消元法消去x310等式约束二次规划－基本消元法(续)找A的可逆子矩阵A1，进行消元如果正定，解方程组可得惟一解11等式约束二次规划－基本消元法(续)找A的可逆子矩阵A1等式约束二次规划－广义消元法令Y和Z分别是n×m与n×(n-m)矩阵，满足考察方程组ATx=b:Yb是特解；通解x=Yb+s，其中s是齐次线性方程组ATs=0的解任一可行解均可表示为:x=Yb+Zy如果ZTGZ正定，则原问题有惟一解，解方程组12等式约束二次规划－广义消元法令Y和Z分别是n×m等式约束二次规划－广义消元法(续)构造Y和Z的正交分解法对矩阵A进行QR分解，即13等式约束二次规划－广义消元法(续)构造Y和Z的正交分解等式约束二次规划－广义消元法(续)14等式约束二次规划－广义消元法(续)14实用二次规划算法综述⊙经典积极集法(classicalactive-setmethods)求解凸和非凸二次规划问题－－中小规模(几百个变量！)⊙梯度投影法(gradient-projectionmethods)界约束QP(BoxQP)!⊙内点法(interior-pointmethods)大规模凸二次规划！15实用二次规划算法综述⊙经典积极集法(classicala积极集法16积极集法16技术注记：此处用线性约束规范代替LICQ!故二次规划的任一解x*均满足KKT条件其中G是n阶对称方阵，ai,d是n

维常向量解的情况：无可行解、无界、有解G半正定凸二次规划积极集法－问题最优积极集！17技术注记：此处用线性约束规范代替LICQ!故二次规划的任积极集法－算法的动机(motivation)如果提前知道，求解对最优积极集进行猜测，并不断修正，直到得到正确的！考虑第k次迭代：x(k)是可行点，Wk

是工作集(由等式约束和部分或全部积极不等式约束组成)其中18积极集法－算法的动机(motivation)如果提前知道积极集法－算法的原理◎x(k)不是当前等式约束问题的解，即s(k)≠0:⊙x(k)+s(k)满足其它约束：，工作集保持不变⊙x(k)+s(k)不满足某些约束，找阻滞约束和步长：称取到最小值的指标p对应的约束为阻滞(blocking)约束无阻滞约束时，工作集不变；否则给工作集添加一个阻滞约束19积极集法－算法的原理◎x(k)不是当前等式约束问题的解，即积极集法－算法的原理(续)⊙乘子中与不等式约束对应的分量非负：

x(k)是原问题的KKT点，进而是全局解◎x(k)是当前等式约束问题的解，即s(k)=0：设当前等式约束问题的Lagrange乘子是⊙否则，存在通常取指标q满足：20积极集法－算法的原理(续)⊙乘子中与不等式约束对应的分量积极集法－算例21积极集法－算例21积极集法－算例(续)作业中用同样的初始点和不同的初始工作集进行迭代求解22积极集法－算例(续)作业中用同样的初始点和不同的初始工作集进积极集法－算法算法10.2.1求解凸二次规划的积极集法23积极集法－算法算法10.2.1求解凸二次规划的积极集法23定理10.2.2

假设s(k)

是关于增量的等式约束二次规划子问题的最优解，且满足该问题的二阶充分条件，则p(k)=s(k)

是原目标函数的下降方向.积极集法－理论分析线搜索法、每个迭代点都可行定理10.2.1

设x(k)

是等式约束二次规划子问题的最优解，是对应的乘子.假设约束的梯度向量线性无关，且存在指标使得.考虑问题设该问题的解为s’.则s’是第j个约束的可行方向，即

.此外，如果s’满足二阶充分条件，则.24定理10.2.2假设s(k)是关于增量的等式约束二次规⊙存在许多技术确定初始点－－比如人工变量法！⊙在恰当的假定下可证明－－算法有限步找到解！⊙可以推广来求解非凸二次规划积极集法－进一步说明⊙初试点相同，但初始工作集不同，则后面的迭代不同；即使初始工作集相同，后面的迭代也可能不同⊙迭代次数有可能超过不等式约束的个数⊙选取初试工作集的额外要求：所选约束的梯度线性无关25⊙存在许多技术确定初始点－－比如人工变量法！⊙在恰当的假逐步二次规划法SuccessiveQuadraticProgrammingMethod26逐步二次规划法26假设和记号

在设计和分析算法时，通常假设f(x),ci(x)是连续可微(二阶连续可微)的，且导数是李普希兹连续的！27假设和记号在设计和分析算法时，通常假设f(x等式约束问题－Lagrange-Newton法KKT条件：其中28等式约束问题－Lagrange-Newton法KKT条件：其等式约束问题－Lagrange-Newton法KKT条件：其中设是近似解，则其牛顿校正满足29等式约束问题－Lagrange-Newton法KKT条件：其等式约束问题－Lagrange-Newton法(续)令，上述方程组即给定初始点，利用上面两式进行迭代解等式约束问题的－Lagrange-Newton法定理假设x*是等式约束问题的满足二阶充分条件的局部极小点,且rank(A*)=m，是惟一的Lagrange乘子.则当充分接近时，Lagrange-Newton法有定义，且由该方法产生的序列二次收敛到.30等式约束问题－Lagrange-Newton法(续)令基本/局部逐步二次规划法考虑二次规划问题的解和对应的Lagrange乘子，其中二次规划的KKT条件31基本/局部逐步二次规划法考虑二次规划问题的解和对应的Lagr基本/局部逐步二次规划法(续)假设是等式约束问题的满足二阶充分条件的极小点，即这里Z是A*Ts=0的基础解系组成的矩阵.则s*=0(x*)是下列问题的惟一最优解32基本/局部逐步二次规划法(续)假设基本/局部逐步二次规划法(续)算法10.3.1基本SQP法33基本/局部逐步二次规划法(续)算法10.3.1基本SQP法基本/局部逐步二次规划法(续)例34基本/局部逐步二次规划法(续)例34基本/局部逐步二次规划法(续)优点：局部二阶收敛存在问题

⊙初始点不好时，迭代可能发散

⊙子问题的解可能不存在－无界或者不可行

⊙需要二阶导数－W(k)35基本/局部逐步二次规划法(续)优点：局部二阶收敛35实用逐步二次规划法全局化策略：使用线搜索策略或者信赖域策略

⊙评价函数法常用的是l1精确罚函数，迭代中需更新惩罚因子；

⊙滤子(Filter)法

存在问题：具有Martos效应，需要采取校正措施近似二阶导数

⊙用近似矩阵B(k)代替W(k)

⊙用近似矩阵代替既约海森矩阵Z(k)TW(k)Z(k)子问题的求解36实用逐步二次规划法全局化策略：使用线搜索策略或者信赖域策略3约束优化问题可行域：

特殊问题可行方向法－线性约束问题次梯度优化－对偶问题

一般问题逐步二次规划法惩罚函数法内点法(原对偶内点法)－凸规划常用方法37约束优化问题可行域：特殊问题第10章：约束优化：二次规划与逐步二次规划法

ConstrainedOptimization:QuadraticProgrammingandSQP

38第10章：约束优化：二次规划与逐步二次规划法

Constr解的情况：无可行解、无界、有解其中G是n阶对称方阵，ai,d是n

维常向量有解时：⊙

G半正定：KKT点即为全局极小点⊙

G正定：有惟一的极小点⊙

G不定：局部解有可能不是全局解，此时找全局解是NP-难问题G半正定凸二次规划39解的情况：无可行解、无界、有解其中G是n阶对称方阵，有价证券的组合优化⊙投资组合：设对第i项投资的资金投放比例为xi⊙问题：对收益与风险的折衷进行建模投资集合{1,…,n}，可能收益为ri

假定II所有资金均投资，不允许卖空

假定I

设

是随机变量40有价证券的组合优化⊙投资组合：设对第i项投资的资金投放有价证券的组合优化(续)⊙证卷组合：证卷组合的利润：证卷组合的期望收益和方差：G是半正定矩阵！⊙证卷组合优化(portfoliooptimization)：41有价证券的组合优化(续)⊙证卷组合：证卷组合的利润：证卷组有价证券的组合优化(续)Markowitz引入风险容许参数(risktoleranceparameter)找出“最优的”证券投资组合！⊙参数，设定值依赖于投资者的个人偏好保守型投资者：大的参数取值冒险性投资者：小的参数取值42有价证券的组合优化(续)Markowitz引入风险容许参数(

等式约束二次规划积极集法逐步二次规划法43等式约束二次规划7等式约束二次规划44等式约束二次规划8等式约束二次规划其中假定:线性无关核心思想：消元法(基本、广义)其中，A1可逆45等式约束二次规划其中假定:代入q(x)等式约束二次规划－基本消元法消去x346代入q(x)等式约束二次规划－基本消元法消去x310等式约束二次规划－基本消元法(续)找A的可逆子矩阵A1，进行消元如果正定，解方程组可得惟一解47等式约束二次规划－基本消元法(续)找A的可逆子矩阵A1等式约束二次规划－广义消元法令Y和Z分别是n×m与n×(n-m)矩阵，满足考察方程组ATx=b:Yb是特解；通解x=Yb+s，其中s是齐次线性方程组ATs=0的解任一可行解均可表示为:x=Yb+Zy如果ZTGZ正定，则原问题有惟一解，解方程组48等式约束二次规划－广义消元法令Y和Z分别是n×m等式约束二次规划－广义消元法(续)构造Y和Z的正交分解法对矩阵A进行QR分解，即49等式约束二次规划－广义消元法(续)构造Y和Z的正交分解等式约束二次规划－广义消元法(续)50等式约束二次规划－广义消元法(续)14实用二次规划算法综述⊙经典积极集法(classicalactive-setmethods)求解凸和非凸二次规划问题－－中小规模(几百个变量！)⊙梯度投影法(gradient-projectionmethods)界约束QP(BoxQP)!⊙内点法(interior-pointmethods)大规模凸二次规划！51实用二次规划算法综述⊙经典积极集法(classicala积极集法52积极集法16技术注记：此处用线性约束规范代替LICQ!故二次规划的任一解x*均满足KKT条件其中G是n阶对称方阵，ai,d是n

维常向量解的情况：无可行解、无界、有解G半正定凸二次规划积极集法－问题最优积极集！53技术注记：此处用线性约束规范代替LICQ!故二次规划的任积极集法－算法的动机(motivation)如果提前知道，求解对最优积极集进行猜测，并不断修正，直到得到正确的！考虑第k次迭代：x(k)是可行点，Wk

是工作集(由等式约束和部分或全部积极不等式约束组成)其中54积极集法－算法的动机(motivation)如果提前知道积极集法－算法的原理◎x(k)不是当前等式约束问题的解，即s(k)≠0:⊙x(k)+s(k)满足其它约束：，工作集保持不变⊙x(k)+s(k)不满足某些约束，找阻滞约束和步长：称取到最小值的指标p对应的约束为阻滞(blocking)约束无阻滞约束时，工作集不变；否则给工作集添加一个阻滞约束55积极集法－算法的原理◎x(k)不是当前等式约束问题的解，即积极集法－算法的原理(续)⊙乘子中与不等式约束对应的分量非负：

x(k)是原问题的KKT点，进而是全局解◎x(k)是当前等式约束问题的解，即s(k)=0：设当前等式约束问题的Lagrange乘子是⊙否则，存在通常取指标q满足：56积极集法－算法的原理(续)⊙乘子中与不等式约束对应的分量积极集法－算例57积极集法－算例21积极集法－算例(续)作业中用同样的初始点和不同的初始工作集进行迭代求解58积极集法－算例(续)作业中用同样的初始点和不同的初始工作集进积极集法－算法算法10.2.1求解凸二次规划的积极集法59积极集法－算法算法10.2.1求解凸二次规划的积极集法23定理10.2.2

假设s(k)

是关于增量的等式约束二次规划子问题的最优解，且满足该问题的二阶充分条件，则p(k)=s(k)

是原目标函数的下降方向.积极集法－理论分析线搜索法、每个迭代点都可行定理10.2.1

设x(k)

是等式约束二次规划子问题的最优解，是对应的乘子.假设约束的梯度向量线性无关，且存在指标使得.考虑问题设该问题的解为s’.则s’是第j个约束的可行方向，即

.此外，如果s’满足二阶充分条件，则.60定理10.2.2假设s(k)是关于增量的等式约束二次规⊙存在许多技术确定初始点－－比如人工变量法！⊙在恰当的假定下可证明－－算法有限步找到解！⊙可以推广来求解非凸二次规划积极集法－进一步说明⊙初试点相同，但初始工作集不同，则后面的迭代不同；即使初始工作集相同，后面的迭代也可能不同⊙迭代次数有可能超过不等式约束的个数⊙选取初试工作集的额外要求：所选约束的梯度线性无关61⊙存在许多技术确定初始点－－比如人工变量法！⊙在恰当的假逐步二次规划法SuccessiveQuadraticProgrammingMethod62逐步二次规划法26假设和记号

在设计和分析算法时，通常假设f(x),ci(x)是连续可微(二阶连续可微)的，且导数是李普希兹连续的！63假设和记号在设计和分析算法时，通常假设f(x等式约束问题－Lagrange-Newton法KKT条件：其中64等式约束问题－Lagrange-Newton法KKT条件：其等式约束问题－Lagrange-Newton法KKT条件：其中设是近似解，则其牛顿校正满足65等式约束问题－Lagrange-Newton法KKT条件：其等式约束问题－Lagrange-Newton法(续)令，上述方程组即给定初始点，利用上面两式进行迭代解等式约