《西瓜书》第六章 公式6.6 凸二次规划问题

1. 凸优化问题

对于一般的非线性规划，若目标函数是凸函数，约束集合 $D$D 是凸集，则称该非线性规划是凸规划。
若上述约束规划中只含有不等式约束，又 $c_i(x)(i∈I)$ci​(x)(i∈I)是凸函数，则约束集 $D$D 是凸集。
对于混合约束问题，若 $c_i(x)(i∈E)$ci​(x)(i∈E)是线性函数，$c_i(x)(i∈I)$ci​(x)(i∈I) 是凸函数，则 $D$D 是凸集。

定理 4： 凸规划的局部解必是全局解。
定理 5： 设目标函数 $f(x)$f(x) 和约束函数 $c_i(x)$ci​(x)一阶连续可微，并且 $c_i(x)(i∈E)$ci​(x)(i∈E) 是线性函数， $c_i(x)(i∈I)$ci​(x)(i∈I) 是凸函数。若凸规划的可行点 $x^*$x∗ 是K-T点，则 $x^*$x∗ 必是全局解。

2. 凸二次规划问题

一般的约束规划问题求解非常困难，从下面开始我们将仅讨论凸二次规划问题的求解方法。考虑如下约束优化问题：

其中 $G$G 为 $n×n$n×n 对称矩阵，$r,α_i(i∈E∪I)$r,αi​(i∈E∪I) 为 $n$n维实向量， $b_i(i∈E∪I)$bi​(i∈E∪I) 为实数，称上述问题为二次规划（quadratic programming）问题。
如果$G$G 为（正定）半正定矩阵，则称上述问题为（严格）凸二次规划（convex quadratic programming）。（严格）凸二次规划问题的局部解均是全局最优解。

定理 6： $x^*$x∗ 是上述凸二次规划问题的全局最优解得充分必要条件是： $x^*$x∗是K-T点，即存在 $λ^∗=(λ^∗_1,λ^∗_2,…,λ^∗_{l m})$λ∗=(λ1∗​,λ2∗​,…,λl m∗​) 使得：

定理 7： 若 $x^*$x∗ 是上述凸二次规划的全局最优解，则 $x^*$x∗是如下等式约束二次规划问题的全局最优解。

参考资料：约束规划问题与凸二次规划

来源：http://www.icode9.com/content-4-216901.html