支持向量机子问题的算法研究

付三平，于 静，韩丛英

（山东科技大学信息科学与工程学院，山东青岛266590）

1 预备知识

考虑以下支持向量机模型

其中y＝［y1，…∈｛－1，1｝，α＝［α1，…αn] ，α∈Rn为列向量，e＝（1，…，1）T∈Rn，C≥0，可以根据具体实验取值，但大多数情况下取C＝10，G是实对称半正定矩阵，且Gij＝yiyjK（αi，αj），i，j＝1，…，n，函数K：Rn×Rn→R为核函数．常用核函数有：多项式核函数：K（s，t）＝（1＋sTt）d，高斯核函数：K（s，t）＝，e＝2．718 28…，σ∈R且不为零．E．Osuna［1]奠定了工作集方法的理论基础，随后产生了SVMlight［2]和libSVM［3]算法，并且被广泛应用．然而，工作集方法在算法的收敛速度和每个迭代步求解二次规划子问题的计算代价之间不易取得平衡．鉴于工作集方法的缺陷，2003年Zanni［4]等人提出将SVMlight算法中的二次规划子问题并行求解．2006年，Serafini［5]等人对文献［4] 作了详细的论述，文献［5] 中给出了其他迭代步的详细并行求解思路，大大提高了算法效率．本文是在工作集方法和并行化方法结合的基础上，不直接利用投影梯度法求子问题，而是采用乘子罚函数［6－7]先将子问题转化成只含界约束的二次规划问题［8－10]，再利用有限记忆拟牛顿（BFGS），方法［11－12]求解界约束优化问题．

2 分解技术及全局算法

文献［4－5] 给出了问题（1）的全局分解解法，算法中变量αi被分成两种类型：αB集合代表自由（基）变量，αN集合代表固定（非基）变量．集合B称为工作集，集合N称为非工作集．根据集合B和N把α，y，G，e分解成如下：

算法1

步1：令α1是（1）式的初始可行点，nsp，nc为两个整数，且n≥nsp≥nc≥0，nc为偶数．任意选择nsp作为工作集B的指标且令k＝1．

步2：计算GBB的元素，令q＝－eB，t＝－．

步3：解决子问题．其中αB∈Rnsp，

0≤αi≤C，i∈B

步4：更新梯度．▽f（αk＋1）＝▽f（αk）＋如果满足KKT条件，则终止；否则，转步5．

步5：更新工作集B．解出下面关于d的解，找出其元素不为零的指标，

di≥0，使得＝0

di≤0，使得＝C，｜｛di｜di≠0｝｜≤nc．

算法1的详细步骤见参考文献［5] ．本文的重点是对步3中的子问题求解进行修改，下面给出步3中子问题的解法及其收敛性的证明．

3 子问题的解法及收敛性

3．1 求解子问题算法

对子问题（2）式，记其增广拉格朗日函数为g（αB，λ，σ），则

其中Q＝GBB＋＝q－λyB－σtyB，c＝λt＋．令x＝αB，x∈，则（2）式可以变形成如下形式的优化问题：

算法2

步1：初始化．x0∈为给定初始点，λ0为初始乘子，σ0为初始罚因子且为非负实数，常数a＞1，η∈（0，1），精度ε＞0．令k＝1．

步2：以xk为初始点，求解界约束问题（3）式，得到一个解xk＋1．

步5：λk＋1＝λk－，令k＝k＋1，转步2．

3．2 算法2的收敛性

把子问题（2）式写成如下一般形式：

定理1 假设原问题（4）式的可行域为X且非空，如果｛λk｝有界，则算法1或者有限终止或者产生的点列｛xk｝的任何聚点是原问题的解．

证明 反证法．假设定理不成立，即算法不有限终止且产生点列存在某个聚点不是原问题的解．设x是原问题的可行点，则h（x）＝0．由xk＋1的定义，则

得

令f＊表示原问题的最优解，那么f＊＝（x）．对（5）式两边同时关于x求下确界得

因为｛λk｝有界，所以必存在上极限点假设λk→．假设是｛xk｝的任意聚点，由f（x）和h（x）的连续性，对（6）式两边取上极限，

由于算法不有限终止，所以σk→∞．为了使（7）式成立，h（xk＋1）→0，即＝0．

因为原问题的可行域是有界闭集，则¯x是可行点，f＊≤．可得

所以点列｛xk｝的任何聚点是原问题（4）式的解，与假设矛盾，定理得证．

4 有限BFGS方法求解界约束优化问

在算法2中，把（3）式抽象成一般的界约束优化模型：

其中F：Rnsp→R是连续可微的，x，l，u∈Rnsp且l＜u（在本文中li＝0，ui＝C）．针对（8）式的求解，利用文献［9] 中的修正子空间有限记忆BFGS方法．其主要思想是用积极集法把变量分成有效变量和非有效变量，再使用修正的有限记忆BFGS方法更新有效变量．（8）式求解过程参考文献［9] 的算法2．1．

5 结束语

本文主要介绍了一种求解大规模支持向量机问题分解算法，对子问题，利用增广拉格朗日函数将二次规划子问题的求解转化成只含界约束的二次规划求解．利用修正的子空间有限记忆BFGS算法求解界约束问题，不仅节约了内存而且提高了计算效率．当外部循环次数比较大时，每一次迭代中子问题的求解对于整个问题的优化至关重要．

［1] Osuna E，Freund R，Girosi F．An improved training algorithm for support vector machines．Proceedings of IEEE Workshop on Neural Networks and Signal Processing［J] ．Amelia Island，1997：276－285．

［2] Joachims T．Maling large－scale SVM learning practical［C] ／／Massachusettes Intitute of Technology press，1999：169－184．

［3] Chih C C，Chih J L，LIBSVM：A library for support vector machines［EB／OL] ．（2001）［2011－11－9] ．http：／／www，csie，ntu．edu．tw／－cjlin／libsvm．

［4] Zanghitati G，Zanni L．A parallel solover for large quadratic programs in training support vector machines［J] ．Parallel Computer，2003，29：535－551．

［5] Zanni L，Serafini T，Zanghitati G，Parrllel sofeware for training large scale support vector machines on multiprocessor system［J] ．Journal of Machine Learning Research，2006，7：1 467－1 492．

［6] 袁亚湘，孙文瑜．最优化理论与算法［M] ．北京：科学出版社1997．

［7] Gasimov R N．Augmented lagrangian duality and nondifferentiable optimization methods in nonconvex programming［J] ．Journal of Global Optimization，2002，24，187－203．

［8] Xiao Y H，Li D H．An active set limited memory BFGS algorithm for largescale bound constrained optimization［J] ．Mathematical Methods of Operations Research，2008，67：443－454．

［9] Xiao Y H，Zhang H C．Modified subspace limited memory BFGS algorithm for large－scale bound constrained optimization［J] ．Journal of Computational and Applied Mathematics，2008，222：429－439．

［10] Xiao Y H，Wei Z X．A new subspace limited memory BFGS algorithm for large－scale bound constrained optimization［J] ．Applied Mathematics and Computation，2007，185：350－359．

［11] Xiao Y H，Wei Z X，Wang Z G．A limited memory BFGS－type method for large－scale unconstrained optimization［J] ．Journal of Computational and Applied Mathematics，2008，56：1 001－1 009．

［12] Byrd R H，Nocedal J，Schnabel R B．Representations of quasinewton matrices and their use in limited memory methods［J] ．Mathematical Programming，1994，63：129－156．