什么是二次规划？

Question

如题，最好能通俗易懂点，鄙人比较愚钝

Answer 1

二次规划是非线形规划中一类特殊的数学规划问题，它的解是可以通过求解得到的。通常通过解其库恩—塔克条件（KT条件）,获取一个KT条件的解称为KT对，其中与原问题的变量对应的部分称为KT点。
二次规划分为凸二次规划与非凸二次规划，前者的KT点便是其全局极小值点，而后者的KT点可能连局部极小值点都不是。若它的目标函数是二次函数，则约束条件是线性的。由于求解二次规划的方法很多，所以较为复杂；其较简便易行的是沃尔夫法，它是依据库恩－塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。

参考资料：http://baike.baidu.com/view/953399.htm

Answer 2

二次规划（Quadratic
programming），在运筹学当中，是一种特殊类型的最佳化问题。
[编辑]
简介二次规划问题可以以下形式来描述：
f(x)
=
(1
/
2)xTQx
+
cTx
受到一个或更多如下型式的限制条件：
Ex
=
d
vT
是
v
的转置。
如果Q是半正定矩阵，那么f(x)是一个凸函数。如果有至少一个向量x满足约束而且f(x)在可行域有下界，二次规划问题就有一个全局最小值x。
如果Q是正定矩阵，那么全局最小值就是唯一的。如果Q=0，二次规划问题就变成线性规划问题。
根据优化理论，一个点x
成为全局最小值的必要条件是满足
Karush-Kuhn-Tucker(KKT)条件。当f(x)是凸函数时，KKT条件也是充分条件。
当二次规划问题只有等式约束时，二次规划可以用线性方程求解。否则的话，常用的二次规划解法有：内点法(interior
point)、active
set和共轭梯度法等。凸集二次规划问题是凸优化问题的一个特例。
[编辑]
对偶每个二次规划问题的对偶问题也是二次规划问题。我们以正定矩阵Q为例：
L(x,λ)
=
(1
/
2)xTQx
+
λT(Ax
−
b)
+
cTx
对偶问题g(λ)，可定义为
我们可用
:
得到L的极小
x
*
=
−
Q
−
1(ATλ
+
c),
对偶函数：
g(λ)
=
−
(1
/
2)λTAQ
−
1ATλ
−
cTQ
−
1ATλ
−
bTλ
对偶问题为：
maximize
:
−
(1
/
2)λTAQ
−
1ATλ
−
(ctQ
−
1AT
+
bT)λ
subject
to
:
计算复杂性当Q正定时，用椭圆法可在多项式时间内解二次规划问题。当Q负定时，二次规划问题是NP困难的(NP-Hard)。即使Q
存在一个负特征值时，二次规划问题就是NP困难的。

Answer 3

二次规划是最简单的非线性规划，目标函数是二次函数，而约束函数是线性函数。