Gradient projection methods for quadratic programs and applications in training support vector machines
Optimization methods & softwarePublished 18 January 2005Open access
Thomas Serafini, Gaetano Zanghirati, Luca Zanni
Citations126
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new adaptive steplength alternating rule is proposed, which becomes the basis for a generalized version of the variable projection method (GVPM) and its effectiveness is shown by means of an extensive computational study on several test problems, including the special quadratic programs arising in training support vector machines (SVMs).
Abstract
Gradient projection methods based on the Barzilai-Borwein spectral steplength choices are considered for quadratic programming (QP) problems with simple constraints. Well-known nonmonotone spectral projected gradient methods and variable projection methods are discussed. For both approaches, the behavior of different combinations of the two spectral steplengths is investigated. A new adaptive steplength alternating rule is proposed, which becomes the basis for a generalized version of the variable projection method (GVPM). Convergence results are given for the proposed approach and its effectiveness is shown by means of an extensive computational study on several test problems, including the special quadratic programs arising in training support vector machines (SVMs). Finally, the GVPM behavior as inner QP solver in decomposition techniques for large-scale SVMs is also evaluated.
Keywords
Computer ScienceMathematics
ACM Transactions on Intelligent Systems and TechnologyLIBSVM
41,340 Citations2011Chih-Chung Chang, Chih‐Jen Lin
Issues such as solving SVM optimization problems theoretical convergence multiclass classification probability estimates and parameter selection are discussed in detail.
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Data Mining and Knowledge DiscoveryA Tutorial on Support Vector Machines for Pattern Recognition
16,433 Citations1998Christopher J. C. Burges
There are several arguments which support the observed high accuracy of SVMs, which are reviewed and numerous examples and proofs of most of the key theorems are given.
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
International Conference on Neural Information ProcessingAdvances in kernel methods: support vector learning
5,815 Citations1999Bernhard Schölkopf, Christopher J. C. Burges +1 more
Support vector machines for dynamic reconstruction of a chaotic system, Klaus-Robert Muller et al pairwise classification and support vector machines, Ulrich Kressel.
The MIT Press eBooksFast Training of Support Vector Machines Using Sequential Minimal Optimization
5,462 Citations1998John Platt
Technical reportsMaking Large-Scale SVM Learning Practical
4,317 Citations2006Thorsten Joachims
This chapter presents algorithmic and computational results developed for SVM light V 2.0, which make large-scale SVM training more practical and give guidelines for the application of SVMs to large domains.
IMA Journal of Numerical AnalysisTwo-Point Step Size Gradient Methods
2,891 Citations1988Jonathan Barzilai, Jonathan M. Borwein
SIAM Journal on Numerical AnalysisA Nonmonotone Line Search Technique for Newton’s Method
1,134 Citations1986Luigi Grippo, F. Lampariello +1 more
A nonmonotone steplength selection rule for Newton's method is proposed, which can be viewed as a generalization of Armijo’s rule, which indicates that the proposed technique may allow a considerable saving both in the number of line searches and in thenumber of function evaluations.
SIAM Journal on OptimizationNonmonotone Spectral Projected Gradient Methods on Convex Sets
1,069 Citations2000Ernesto G. Birgin, J. M. Martı́nez +1 more
The classical projected gradient schemes are extended to include a nonmonotone steplength strategy that is based on the Grippo--Lampariello--Lucidi non monotone line search that is combined with the spectral gradient choice of steplENGTH to accelerate the convergence process.
An improved training algorithm for support vector machines
1,066 Citations2002E. Osuna, Robert M. Freund +1 more
This paper presents a decomposition algorithm that is guaranteed to solve the QP problem and that does not make assumptions on the expected number of support vectors.
Optimization methods & softwareLOQO:an interior point code for quadratic programming
472 Citations1999Robert J. Vanderbei
This paper describes a software package, called LOQO, which implements a primal-dual interior-point method for general nonlinear programming, and shows that the industry standard MPS format can be nicely formulated in such a way to provide quasidefiniteness.
Applied Physics Letters10.1162/15324430152733142
389 Citations2000Ronan Collobert, Samy Bengio
A decomposition algorithm, SVMTorch, similar to SVM-Light proposed by Joachims (1999) for classification problems, but adapted to regression problems is proposed, which can now efficiently solve large-scale regression problems.
Machine LearningEfficient SVM Regression Training with SMO
317 Citations2002Gary William Flake, Steve Lawrence
This work generalizes SMO so that it can handle regression problems, and addresses problems with several modifications that enable caching to be effectively used with SMO.
IMA Journal of Numerical AnalysisR-linear convergence of the Barzilai and Borwein gradient method
305 Citations2002Y. H. Dai
The R-linear convergence of the BB method for any-dimensional strongly convex quadratics is established, which means that the stepsize in theBB method will always be accepted by the non-monotone line search when the iterate is close to the solution.
Machine LearningA Simple Decomposition Method for Support Vector Machines
300 Citations2002Chih‐Wei Hsu, Chih‐Jen Lin
This paper through the design of decomposition methods for bound-constrained SVM formulations it is demonstrated that the working set selection is not a trivial task and a simple selection is proposed which leads to faster convergences for difficult cases.
Nonconvex optimization and its applicationsEquilibrium Problems and Variational Models
250 Citations2003Patrizia Daniele, F. Giannessi +1 more
IEEE Transactions on Neural NetworksOn the convergence of the decomposition method for support vector machines
249 Citations2001Chih‐Jen Lin
The asymptotic convergence of the algorithm used by the software SVM(light) and other later implementation is proved and the size of the working set can be any even number.
Applied optimizationOn the Barzilai-Borwein Method
248 Citations2005R. Fletcher
A review is given of the underlying theory and recent developments in regard to the Barzilai-Borwein steepest descent method for large scale unconstrained optimization to assess why the method seems to be comparable in practical efficiency to conjugate gradient methods.
SIAM Journal on OptimizationInterior-Point Methods for Massive Support Vector Machines
190 Citations2002Michael C. Ferris, Todd Munson
This work investigates the use of interior-point methods for solving quadratic programming problems with a small number of linear constraints, where the quadratics term consists of a low-rank update to a positive semidefinite matrix.
Mathematical ProgrammingAn algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds
176 Citations1990Pãnos M. Pardalos, Nainan Kovoor
An O(n) algorithm for a singly constrained convex quadratic program using binary search to solve the Kuhn-Tucker system is given.
SIAM Journal on Numerical AnalysisGradient Method with Retards and Generalizations
161 Citations1998Ana Friedlander, J. M. Martı́nez +2 more
Computational Optimization and ApplicationsRelaxed Steepest Descent and Cauchy-Barzilai-Borwein Method
156 Citations2002Marcos Raydan, B. F. Svaiter
It is stressed out that the poor behavior of the steepest descent methods is due to the optimal Cauchy choice of steplength and not to the choice of the search direction, and the advantages of using nonmonotone overrelaxations of the gradient method are illustrated.
Parallel ComputingA parallel solver for large quadratic programs in training support vector machines
147 Citations2003Gaetano Zanghirati, Luca Zanni
An easily parallelizable approach based on a decomposition technique that splits the problem into a sequence of smaller quadratic programming subproblems that can achieve good efficiency and scalability on a multiprocessor system is presented.
Computational Optimization and ApplicationsNonmonotone Globalization Techniques for the Barzilai-Borwein Gradient Method
127 Citations2002Luigi Grippo, Marco Sciandrone
A class of algorithms that combine nonmonotone watchdog techniques with non monotone linesearch rules are defined and the global convergence of these schemes is proved.
Computational Optimization and ApplicationsModified Two-Point Stepsize Gradient Methods for Unconstrained Optimization
113 Citations2002Yu‐Hong Dai, Jinyun Yuan +1 more
This paper interprets the choice for the stepsize in the two-point stepsize gradient method from the angle of interpolation and proposes two modified two- Point Stepsize gradient methods, which are globally convergent under some mild assumptions on the objective function.
Transportation ScienceSolution Algorithms for Network Equilibrium Models with Asymmetric User Costs
83 Citations1982C.S. Fisk, Sang Quang Nguyen
Comparing the performance of several existing methods for determining the equilibrium network flows of a small realistic network model in which intersection controls are incorporated which lead to particularly asymmetric cost functions is compared.
Nova Science Publishers, Inc. eBooksRecent trends in numerical analysis
78 Citations2000Donato Trigiante
The contributions for this volume, dedicated to honour the 65th birthday of Professor I Galligani, have been numerous and cover a wide range of topics of the current Numerical Analysis and of its applications.
Journal of Optimization Theory and ApplicationsA Modified Projection Algorithm for Large Strictly-Convex Quadratic Programs
21 Citations2000Valeria Ruggiero, Luca Zanni
A modified projection-type method for solving strictly-convex quadratic programs that consists in updating the Hessian matrix of the subproblems by a convenient scaling parameter and its effectiveness as a solver of large and very sparse quadRatic programs is evaluated.
Nonconvex optimization and its applicationsVariable Projection Methods for Large—Scale Quadratic Optimization in Data Analysis Applications
3 Citations2003Emanuele Galligani, Valeria Ruggiero +1 more
This paper concerns with the numerical evaluation of the variable projection method for quadratic programming problems in three data analysis applications with remarkable differences in the Hessian definition and the structure of the constraints.
IRIS UNIMORE (University of Modena and Reggio Emilia)Projection-type methods for large convex quadratic programs: theory and computational experience
2 Citations2000Emanuele Galligani, Valeria Ruggiero +1 more