二次规划求解

二次规划（Quadratic Programming）问题是最基本的非线性规划问题，目标函数是二次函数，约束条件是线性等式或不等式。目前，已经出现了很多求解二次规划问题的算法，并且仍有很多学者在从事这方面的研究工作。

在机器学习中，我们知道QP可以用来解决SVM算法的最优解问题。二次规划问题的求解证明在此处暂不讨论。

二次规划的问题可以用数学公式(octave)描述：

1
2
3
4
5
6
7
8
 min 0.5 x'*H*x + x'*q
  x

    subject to

      A*x = b
      lb <= x <= ub
      A_lb <= A_in*x <= A_ub

相应的函数为：

• Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H)
• Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q)
• Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B)
• Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)
• Function File: [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB, A_LB, A_IN, A_UB)
• Function File: [X, OBJ, INFO, LAMBDA] = qp (…, OPTIONS)

其中，H，q分别是目标函数化成标准形式后得到的实对称矩阵，列向量。求解的目标，x。A，b定义了线性约束。如果没有线性约束，A＝[]，b=[]。LB，UB分别是变量x的下界和上界，如果上界、下界没有约束，则LB＝[]，UB＝[]。可以通过OPTIONS设置其它参数：比如：

‘MaxIter (default: 200)’

INFO表示算法的运行时信息。相应如下：

• ‘solveiter’: 解的迭代数
• ‘info’: 状态码。
• info=0: 表示该问题是可行的，并且是convex问题。找到全局解。
• info=1: 该问题是not convex的。找到局部解。
• info=2: 该问题是not convex的，并且unbounded。
• info=3: 迭代的最大次数
• info=6: 该问题无解

示例：

• $ min f(x)=2x_1^2-4x_1x_2+4x_2^2-6x_1-3x_2 $
• $ x_1+x_2<=3 $
• $ 4x_1+x+2<=9 $
• $ x_1\geq0,x_2\geq0 $

编写程序：

H=[4,-4;-4,8];
Q=[-6;-3];
A=[1,1;4,1];
B=[3;9];
LB=zeros(2,1);
X0=[];
UB=[];
[X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB)

对应的输出为：

X =

   2.0000
   1.0000

OBJ = -11.000
INFO =

  scalar structure containing the fields:

    solveiter =  1
    info = 0

LAMBDA =

  -3.33333
   0.33333
   0.00000
   0.00000