二次规划

维基百科,自由的百科全书
跳转至: 导航搜索

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

簡介[编辑]

一個有n個變數與m個限制的二次規劃問題可以用以下的形式描述。首先給定:

  • 一個n 維的向量 c
  • 一個n × n 維的對稱矩陣Q
  • 一個m × n 維的矩陣A
  • 一個m 維的向量 b

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

的條件下,找一個n 維的向量 x ,使得

為最小。其中的转置。

根據不同的參數特性,可以得到對問題不同的結論

  • 如果Q是半正定矩阵,那么f(x)是一个凸函数
  • 如果Q是正定矩阵,那么全局最小值就是唯一的。
  • 如果Q=0,二次规划问题就变成线性规划问题。
  • 如果有至少一个向量x满足约束而且f(x)在可行域有下界,二次规划问题就有一个全局最小值x。

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

当二次规划问题只有等式约束时,二次规划可以用线性方程求解。否则的话,常用的二次规划解法有:内点法(interior point)、active set和共轭梯度法等。凸集二次规划问题是凸优化问题的一个特例。

对偶[编辑]

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

对偶问题,可定义为

我们可用:得到的极小

,

对偶函数:

对偶问题为:

maximize :

subject to :

计算复杂性[编辑]

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