1. 凸优化问题
对于一般的非线性规划，若目标函数是凸函数，约束集合
D
D
D
是凸集，则称该非线性规划是
凸规划
。
若上述约束规划中只含有不等式约束，又
c
i
(
x
)
(
i
∈
I
)
c_i(x)(i∈I)
c
i
(
x
)
(
i
∈
I
)
是凸函数，则约束集
D
D
D
是
凸集
。
对于混合约束问题，若
c
i
(
x
)
(
i
∈
E
)
c_i(x)(i∈E)
c
i
(
x
)
(
i
∈
E
)
是线性函数，
c
i
(
x
)
(
i
∈
I
)
c_i(x)(i∈I)
c
i
(
x
)
(
i
∈
I
)
是凸函数，则
D
D
D
是
凸集
。
定理 4：
凸规划的局部解必是全局解。
定理 5：
设目标函数
f
(
x
)
f(x)
f
(
x
)
和约束函数
c
i
(
x
)
c_i(x)
c
i
(
x
)
一阶连续可微，并且
c
i
(
x
)
(
i
∈
E
)
c_i(x)(i∈E)
c
i
(
x
)
(
i
∈
E
)
是线性函数，
c
i
(
x
)
(
i
∈
I
)
c_i(x)(i∈I)
c
i
(
x
)
(
i
∈
I
)
是凸函数。若凸规划的可行点
x
∗
x^*
x
∗
是K-T点，则
x
∗
x^*
x
∗
必是全局解。
2. 凸二次规划问题
一般的约束规划问题求解非常困难，从下面开始我们将仅讨论凸二次规划问题的求解方法。考虑如下约束优化问题：
其中
G
G
G
为
n
×
n
n×n
n
×
n
对称矩阵，
r
,
α
i
(
i
∈
E
∪
I
)
r,α_i(i∈E∪I)
r
,
α
i
(
i
∈
E
∪
I
)
为
n
n
n
维实向量，
b
i
(
i
∈
E
∪
I
)
b_i(i∈E∪I)
b
i
(
i
∈
E
∪
I
)
为实数，称上述问题为
二次规划
（quadratic programming）问题。
如果
G
G
G
为（正定）半正定矩阵，则称上述问题为（严格）
凸二次规划
（convex quadratic programming）。（严格）凸二次规划问题的局部解均是全局最优解。
定理 6：
x
∗
x^*
x
∗
是上述
凸二次规划问题
的全局最优解得充分必要条件是：
x
∗
x^*
x
∗
是K-T点，即存在
λ
∗
=
(
λ
1
∗
,
λ
2
∗
,
…
,
λ
l
+
m
∗
)
λ^∗=(λ^∗_1,λ^∗_2,…,λ^∗_{l+m})
λ
∗
=
(
λ
1
∗
,
λ
2
∗
,
…
,
λ
l
+
m
∗
)
使得：
定理 7：
若
x
∗
x^*
x
∗
是上述
凸二次规划
的全局最优解，则
x
∗
x^*
x
∗
是如下等式
约束二次规划问题
的全局最优解。
参考资料：
约束规划问题与凸二次规划