二次规划

二次规划（Quadratic programming），在运筹学当中，是一种特殊类型的最佳化问题。

一个有n个变数与m个限制的二次规划问题可以用以下的形式描述。首先给定：

则此二次规划问题的目标即是在限制条件为

的条件下，找一个n 维的向量 x ，使得

为最小。其中${\displaystyle x^T}$是${\displaystyle x}$的转置。

根据不同的参数特性，可以得到对问题不同的结论

根据优化理论，一个点x成为全局最小值的必要条件是满足Karush-Kuhn-Tucker条件（KKT）。当f(x)是凸函数时，KKT条件也是充分条件。

当二次规划问题只有等式约束时，二次规划可以用线性方程求解。否则的话，常用的二次规划解法有：

凸集二次规划问题是凸优化问题的一个特例。

每个二次规划问题的对偶问题也是二次规划问题。以正定矩阵Q为例：

对偶问题${\displaystyle g(\mathrm{\lambda <!--\; \lambda \; -->})}$，可定义为

可用${\displaystyle {\mathrm{\nabla <!--\; \nabla \; -->}}_{x}L(x,\mathrm{\lambda <!--\; \lambda \; -->})=0}$:得到${\displaystyle L}$的极小

对偶函数：

对偶问题为：

maximize :${\displaystyle -<!--\; -\; -->(1/2){\mathrm{\lambda <!--\; \lambda \; -->}}^{T}A{Q}^{-<!--\; -\; -->1}{A}^T\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->(c^T{Q}^{-<!--\; -\; -->1}{A}^T+b^T)\mathrm{\lambda <!--\; \lambda \; -->}}$

subject to :${\displaystyle \mathrm{\lambda <!--\; \lambda \; -->}\ge <!--\; \ge \; -->0}$

当Q正定时，用椭圆法可在多项式时间内解二次规划问题。当Q非正定时，二次规划问题是NP困难的（NP-Hard）。即使Q只存在一个负特征值时，二次规划问题也是NP困难的。