Optimization Online


A sparse semismooth Newton based augmented Lagrangian method for large-scale support vector machines

Dunbiao Niu(dunbiaoniu_sc***at***163.com)
Chengjing Wang(renascencewang***at***hotmail.com)
Peipei Tang(tangpp***at***zucc.edu.cn)
Qingsong Wang(nothing2wang***at***hotmail.com)
Enbin Song(e.b.song***at***163.com)

Abstract: Support vector machines (SVMs) are successful modeling and prediction tools with a variety of applications. Previous work has demonstrated the superiority of the SVMs in dealing with the high dimensional, low sample size problems. However, the numerical difficulties of the SVMs will become severe with the increase of the sample size. Although there exist many solvers for the SVMs, only few of them are designed by exploiting the special structures of the SVMs. In this paper, we propose a highly efficient sparse semismooth Newton based augmented Lagrangian method for solving a large-scale convex quadratic programming problem with a linear equality constraint and a simple box constraint, which is generated from the dual problems of the SVMs. By leveraging the primal-dual error bound result, the fast local convergence rate of the augmented Lagrangian method can be guaranteed. Furthermore, by exploiting the second-order sparsity of the problem when using the semismooth Newton method, the algorithm can efficiently solve the aforementioned difficult problems. Finally, numerical comparisons demonstrate that the proposed algorithm outperforms the current state-of-the-art solvers for the large-scale SVMs.

Keywords: support vector machines, semismooth Newton method, augmented Lagrangian method

Category 1: Convex and Nonsmooth Optimization

Category 2: Applications -- Science and Engineering (Data-Mining )

Citation: No.999, Xian Road, West Park, High-tech Zone, Chengdu 611756, China, October 2019

Download: [PDF]

Entry Submitted: 10/01/2019
Entry Accepted: 10/01/2019
Entry Last Modified: 10/01/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society