查看“︁二次规划”︁的源代码

{{专家|subject=数学}}
'''二次规划'''（{{lang|en|Quadratic programming}}），在[[运筹学]]当中，是一种特殊类型的[[最优化]]问题。

==簡介==
一個有n個變數與m個限制的二次規劃問題可以用以下的形式描述。首先給定：
* 一個 <math>n</math> 維的向量 <math>\mathbf{c}</math>
* 一個 <math>n\times n</math> 維的對稱矩陣 <math>Q</math>
* 一個 <math>m\times n</math> 維的矩陣<math>A</math>
* 一個 <math>m</math> 維的向量 <math>\mathbf{b}</math>

則此二次規劃問題的目標即是在限制條件為

:<math>Ax \le b  </math>

的條件下，找一個{{mvar|n}} 維的向量 {{math|'''x'''}} ，使得
 
:<math>f(x)=(1/2)x^TQx + c^Tx</math>
 
為最小。其中<math>x^T</math>是<math>x</math>的转置。

根據不同的參數特性，可以得到對問題不同的結論
* 如果Q是[[半正定矩阵]]，那么f(x)是一个[[凸函数]]。相应的二次规划为凸二次规划问题；此时若约束条件定义的可行域不为空，且目标函数在此可行域有下界，则该问题有全局最小值。
* 如果Q是[[正定矩阵]]，则该问题有唯一的全局最小值。
* 若Q为非正定矩阵，则目标函数是有多个[[平稳点]]和局部极小点的[[NP问题|NP问题]]。
* 如果Q=0，二次规划问题就变成线性规划问题。

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

当二次规划问题只有等式约束时，二次规划可以用线性方程求解。否则的话，常用的二次规划解法有：
* [[内点法]](interior point) 
* active set 
* 共轭梯度法 
* 椭球法 若Q为正定矩阵，则相应的二次规划问题可由椭球法在多项式时间内求解。 
* 增广拉格朗日法 
* 梯度投影法 
凸集二次规划问题是[[凸优化]]问题的一个特例。

== 对偶==
每个二次规划问题的[[對偶性 (最佳化)|对偶问题]]也是二次规划问题。以正定矩阵Q为例：

:<math>L(x,\lambda) = (1/2)x^TQx + \lambda^T(Ax-b) + c^Tx </math>

对偶问题<math>g(\lambda)</math>，可定义为

:<math>g(\lambda) = \inf_x L(x,\lambda) </math>  

可用<math>\nabla_x L(x,\lambda)=0</math>:得到<math>L</math>的极小 

:<math>x* = -Q^{-1}(A^T\lambda+c)</math>, 

对偶函数：
:<math>g(\lambda) = -(1/2)\lambda^TAQ^{-1}A^T\lambda - c^TQ^{-1}A^T\lambda - b^T\lambda</math>

对偶问题为：

maximize :<math> -(1/2)\lambda^TAQ^{-1}A^T\lambda - (c^TQ^{-1}A^T+b^T)\lambda</math>

subject to :<math>\lambda \ge 0</math>

== 计算复杂性 ==
当Q正定时，用椭圆法可在多项式时间内解二次规划问题。当Q非正定时，二次规划问题是[[NP困难]]的。即使Q只存在一个负特征值时，二次规划问题也是NP困难的。
<ref>{{cite journal | last = Sahni | first = S. | title = Computationally related problems | journal = SIAM Journal on Computing | volume = 3 | issue = 4 | pages = 262–279 | year = 1974 | doi = 10.1137/0203021 | url = http://www.cise.ufl.edu/~sahni/papers/comp.pdf | citeseerx = 10.1.1.145.8685 | access-date = 2022-09-07 | archive-date = 2022-04-26 | archive-url = https://web.archive.org/web/20220426181254/http://www.cise.ufl.edu/~sahni/papers/comp.pdf | dead-url = yes }}</ref> 
<ref>{{cite journal | title = Quadratic programming with one negative eigenvalue is (strongly) NP-hard | first1 = Panos M. | last1 = Pardalos | first2 = Stephen A. | last2 = Vavasis | journal = Journal of Global Optimization | volume = 1 | issue = 1 | year = 1991 | pages = 15–22 | doi=10.1007/bf00120662| s2cid = 12602885 }}</ref>

==参考文献==
{{Reflist}}

[[Category:運籌學]]