二次规划求解

Reading time ~1 minute

二次规划(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: 该问题无解

示例:

编写程序:

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
   

bitcoin中的矿池运营与破产

# 1.泊松分布与挖矿问题[泊松分布](http://baike.baidu.com/link?url=G_p2pcziH7dsjuum83USwOumJgO7TK41ZxuGTdI03jLF_Ugd4Q5KkpITcTSAeIuMao5royrH86GBvJS8DKh0R...… Continue reading

word2vec中的Skip-gram

Published on February 02, 2016

word2vec中的Hierarchical Softmax

Published on February 02, 2016