求解互补支持向量机的非单调信赖域算法*

高雷阜，于冬梅，赵世杰

(辽宁工程技术大学优化与决策研究所，辽宁 阜新 123000)

摘要：求解支持向量机的核心问题是对一个大规模凸二次规划问题进行求解。基于支持向量机的修正模型，得到一个与之等价的互补问题，利用Fischer-Burmeister互补函数，从一个新的角度提出了求解互补支持向量机的非单调信赖域算法。新算法避免了求解Hesse矩阵或矩阵求逆运算，减少了工作量，提高了运算效率。在不需要任何假设的情况下，证明算法具有全局收敛性。数值实验结果表明，对于大规模非线性分类问题，该算法的运行速度比LSVM算法和下降法快，为求解SVM优化问题提供了一种新的可行方法。

关键词：支持向量机；信赖域方法；互补函数；非单调策略

中图分类号：TP301.6 文献标志码：A

doi:10.3969/j.issn.1007-130X.2015.06.016

收稿日期：*2014-04-14;修回日期：2014-08-11

基金项目：教育部高校博士学科科研基金联合资助项目(20132121110009)

作者简介:

通信地址：123000 辽宁省阜新市辽宁工程技术大学理学院

Address:College of Science,Liaoning Technical University,Fuxin 123000,Liaoning,P.R.China

A non-monotonic trust region algorithm for solving complementary support vector machine

GAO Lei-fu,YU Dong-mei,ZHAO Shi-jie

(Research Institute of Optimization and Decision,Liaoning Technical University,Fuxin 123000,China)

Abstract:Solving a large-scale convex quadratic programming problem is the core of the support vector machine. An equivalence complementarity problem can be obtained based on an amended model of the surpport vector machine(SVM), therefore we propose a non-monotonic trust region algorithm for solving the complementarity problem based on the Fischer-Burmeister complementarity function. The new algorithm need not compute any Hesse or the inverse matrix, thus reducing the amount of computational work. Global convergence of the algorithm is proved without any assumptions. Numerical experiments show that the running speed of the algorithm is faster than that of the LSVM algorithm and the descent algorithm when solving large-scale nonlinear classification problems and thus it provides a feasible method for solving SVM.

Key words:support vector machine；trust-region method；complementarity function；non-monotonic strategies

1引言

支持向量机SVM(Support Vector Machine)是由Vapnik V[1,2]基于统计学理论中的结构风险极小化原则提出的，它是一种有监督的机器学习，是模式识别中分类、函数近似和回归估计的有效工具。在二分类问题模型中，支持向量机模型采用结构风险极小化原则和核函数方法来构造分类模型，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并推广应用到函数拟合等其他研究领域中，例如图像处理[3]、信用风险评估[4]、股指期货预测[5]等方面的应用。……