×

zbMATH — the first resource for mathematics

Gradient projection methods for quadratic programs and applications in training support vector machines. (English) Zbl 1072.90026
Summary: 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.

MSC:
90C20 Quadratic programming
90C52 Methods of reduced gradient type
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1093/imanum/8.1.141 · Zbl 0638.65055
[2] DOI: 10.1137/S1052623497330963 · Zbl 1047.90077
[3] DOI: 10.1023/A:1004605612267 · Zbl 0962.90036
[4] Ruggiero V, Recent Trends in Numerical Analysis (2000)
[5] DOI: 10.1137/0723046 · Zbl 0616.65067
[6] Bertsekas DP, Nonlinear Programming (1999)
[7] Galligani E, Monograph 5 (2000)
[8] Galligani E, Equili-brium Problems and Variational Models (2003)
[9] DOI: 10.1023/A:1020587701058 · Zbl 1028.90061
[10] DOI: 10.1016/S0167-8191(03)00021-8
[11] Fung G, Data Mining Institute Technical Report 01-02, Computer Sciences Department, University of Wisconsin (2001)
[12] DOI: 10.1023/A:1009715923555 · Zbl 05470543
[13] Cortes C, Machine Learning 20 pp 1– (1995)
[14] Cristianini N, An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, Cambridge University Press (2000) · Zbl 0994.68074
[15] Vapnik VN, Statistical Learning Theory (1998)
[16] DOI: 10.1137/S1052623400374379 · Zbl 1039.90092
[17] Chang CC Lin CJ 2002 LIBSVM: A library for support vector machines Available at: <http://www.csie.ntu.edu.tw/ cjlin/libsvm, >
[18] DOI: 10.1023/A:1012474916001 · Zbl 0998.68107
[19] Platt JC, Advances in Kernel Methods–Support Vector Learning (1998)
[20] DOI: 10.1162/15324430152733142 · Zbl 1052.68111
[21] DOI: 10.1023/A:1012427100071 · Zbl 0998.68108
[22] Joachims T, Advances in Kernel Methods–Support Vector Learning (1998)
[23] Osuna E, Proceedings of the IEEE Workshop on Neural Networks for Signal Processing, IEEE Press (1997)
[24] DOI: 10.1093/imanum/22.1.1 · Zbl 1002.65069
[25] Fletcher R 2001 On the Barzilai–Borwein Method, Numerical Analysis Report NA/207
[26] Dai YH, Chinese Academy of Sciences (2001)
[27] DOI: 10.1023/A:1014838419611 · Zbl 1008.90056
[28] DOI: 10.1137/S003614299427315X · Zbl 0940.65032
[29] DOI: 10.1023/A:1013708715892
[30] DOI: 10.1287/trsc.16.3.361
[31] LeCun Y The MNIST database of handwritten digits Available at: <http://yann.lecun.com/exdb/mnist, >
[32] Murphy PM Aha DW 1992 UCI repository of machine learning databases Available at: <http://www.ics.uci.edu/ mlearn/MLRepository.html, >
[33] DOI: 10.1007/BF01585748 · Zbl 0711.90061
[34] Vanderbei RJ, Princeton University (1998)
[35] Smola AJ 1998 pr_LOQO optimizer Available at: <http://www.kernel-machines.org/code/prloqo.tar.gz, >
[36] Murtagh B, Stanford University (1995)
[37] DOI: 10.1109/72.963765
[38] Lin CJ, Department of Computer Science and Information Engineering, National Taiwan University (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.