二次规划(QP)是求解一种特殊的数学优化问题的过程——具体地说，是一个(线性约束)二次优化问题，即优化(最小化或最大化)多个变量的二次函数，并服从于这些变量的线性约束。二次规划是一种特殊的非线性规划。
问题定义
一个有n个变数与m个限制的二次规划问题可以用以下的形式描述。首先给定：
- 一个n 维的向量 c
- 一个n × n 维的对称矩阵Q
- 一个m × n 维的矩阵A
- 一个m 维的向量 b
则此二次规划问题的目标即是在限制条件为
的条件下，找一个n 维的向量 x ，使得
为最小。其中x^T是x的转置。
根据不同的参数特性，可以得到对问题不同的结论
- 如果Q是半正定矩阵，那么f(x)是一个凸函数。
- 如果Q是正定矩阵，那么全局最小值就是唯一的。
- 如果Q=0，二次规划问题就变成线性规划问题。
- 如果有至少一个向量x满足约束而且f(x)在可行域有下界，二次规划问题就有一个全局最小值x。
根据优化理论，一个点x成为全局最小值的必要条件是满足Karush-Kuhn-Tucker条件（KKT）。当f(x)是凸函数时，KKT条件也是充分条件。
当二次规划问题只有等式约束时，二次规划可以用线性方程求解。否则的话，常用的二次规划解法有：内点法(interior point)、active set和共轭梯度法等。凸集二次规划问题是凸优化问题的一个特例。
解决方案：
对于一般问题，常用的方法有很多，包括
- interior point,内点法
- active set 内点法
- augmented Lagrangian
- conjugate gradient,
- gradient projection,
- extensions of the simplex algorithm
对偶
每个二次规划问题的对偶问题也是二次规划问题。我们以正定矩阵Q为例：
对偶g( λ)问题，可定义为
我们可用
得到L的极小
对偶函数：
对偶问题为：
计算复杂性
当Q正定时，用椭圆法可在多项式时间内解二次规划问题。当Q非正定时，二次规划问题是NP困难的（NP-Hard）。即使Q只存在一个负特征值时，二次规划问题也是NP困难的.
【来源：WIKI, URL:https://en.wikipedia.org/wiki/Quadratic_programming 】
发展历史
1950年代
1951年H.W. Kuhn和A.W. Tucker重新创造了非线性问题的最优性条件。约翰在1948年和W. Karush在1939年曾提出过类似的条件。1954年，L.R. Ford和D.R. Fulkerson对网络问题的研究是组合优化研究的起点。提出了拟牛顿法和共轭梯度法等无界问题的算法。1957年，贝尔曼提出了最优性原则。也在这个时代，二次规划问题获得了很多的关注（如，Wolfe P. 1959； BARANKIN, E. W， 1958； BEALE, E. M. 1955 ）。
1960年代，Zoutendijk(1960)提出了一种可行的方法来推广非线性规划的单纯形法。罗森、沃尔夫和鲍威尔也有类似的想法。
序列二次规划法Sequential quadratic programming是威尔逊1963年首次提出的。1975年的Han Han和1977年的鲍威尔再次展示了它。
1973年，数学编程协会成立。1984年，Karmarkar的lp问题多项式时间算法开始了内部点方法的兴起。第一个多项式时间算法，即椭球面法，已于1979年由Khachiyan提出。60年代和70年代发展起来的复杂性分析开始影响到优化理论。1986，Garcia, C. E., & Morshedi, A. M.利用二次规划解决动态矩阵控制问题。随着计算机变得更加高效，启发式算法的全局优化和大规模问题开始流行。90年代，内点方法的使用扩展到半正定优化。
序列二次规划(SQP)方法被证明是在目标和约束条件下求解具有光滑非线性函数的约束优化问题的有效方法。但是依然存在具有一般不等式约束(线性和非线性)的问题。Gill, P. E., Murray, W., & Saunders, M. A.假设第一导数是可用的，约束梯度是稀疏的。二阶导数被认为是不可用的或计算起来太贵。
因此，2005，Gill, P. E., Murray, W., & Saunders, M. A.提出一种用于大规模约束优化的Sequential quadratic programming（SQP）算法。并被广泛的来解决规划问题。
【来源：WEB, URL:http://www.mitrikitti.fi/opthist.html 】
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1956 | Frank, M., & Wolfe, P.提出二次规划算法 | Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics (NRL), 3(1‐2), 95-110. |
| 1986 | Garcia, C. E., & Morshedi, A. M.利用二次规划解决动态矩阵控制问题 | Garcia, C. E., & Morshedi, A. M. (1986). Quadratic programming solution of dynamic matrix control (QDMC). Chemical Engineering Communications, 46(1-3), 73-87. |
| 1995 | Boggs, P. T., & Tolle, J. W.对序列二次规划进行梳理 | Boggs, P. T., & Tolle, J. W. (1995). Sequential quadratic programming. Acta numerica, 4, 1-51. |
| 2005 | Gill, P. E., Murray, W., & Saunders, M. A.提出 *一种用于大规模约束优化的SQP算法 | Gill, P. E., Murray, W., & Saunders, M. A. (2005). SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM review, 47(1), 99-131. |
| 2006 | Nocedal, J., & Wright, S. J.出版序列二次规划书籍 | Nocedal, J., & Wright, S. J. (2006). Sequential quadratic programming (pp. 529-562). Springer New York. |
发展分析
瓶颈
2000年，美国克莱数学研究所公布了世界七大数学难题，又称千禧年大奖难题。其中P与NP问题被列为这七大世界难题之首，从而大大激发了对这一问题的研究热情。它的计算时间是它的致命的问题。对于TSP问题，它的复杂度是按照指数的增长形式的，这样的高花费是不可行的。
未来发展方向
NP问题排在世界七大数学难题之首，七个问题都是经过美国克雷数学研究所的科学顾问委员会精心挑选出来的，这些问题的获解上哪怕是获得了些许的进展，就将对数学理论的发展和应用产生极其巨大的推动作用。研究这些“千年大奖问题”已经成为世界数学界的热点，不少国家的数学家正在组织联合攻关，同时它们也是任何一个数学工作者都梦寐以求予以摘取的数学皇冠上的耀眼明珠。可以预期，这些“千年大奖问题”将会改变新世纪数学发展的历史进程。
当Q正定时，用椭圆法可在多项式时间内解二次规划问题。当Q非正定时，二次规划问题是NP困难的（NP-Hard）。即使Q只存在一个负特征值时，二次规划问题也是NP困难的。
Contributor：Cai Ruiying