Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels

Previous Article
Finite-time stabilization and $H_\infty$ control of nonlinear delay systems via output feedback
JIMO Home
This Issue
Next Article
Quadratic optimization over a polyhedral cone

January 2016, 12(1): 285-301. doi: 10.3934/jimo.2016.12.285

Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels

Fengqiu Liu ^1, and Xiaoping Xue ^2,

1.	Department of Mathematics, Harbin University of Science and Technology, Harbin, 150080, China
2.	Department of Mathematics, Harbin Institute of Technology, Harbin 150001

Received June 2012 Revised January 2015 Published April 2015

Abstract
Related Papers

Support vector machines (SVMs) with positive semidefinite kernels yield convex quadratic programming problems. SVMs with indefinite kernels yield nonconvex quadratic programming problems. Most optimization methods for SVMs rely on the convexity of objective functions and are not efficient for solving such nonconvex problems. In this paper, we propose a subgradient-based neural network (SGNN) for the problems cast by SVMs with indefinite kernels. It is shown that the state of the proposed neural network has finite length, and as a consequence it converges toward a singleton. The coincidence between the solution and the slow solution of SGNN is also proved starting from the initial value of SGNN. Moreover, we employ the Łojasiewicz inequality to exploit the convergence rate of trajectory of SGNN. The obtained results show that each trajectory is either exponentially convergent, or convergent in finite time, toward a singleton belonging to the set of constrained critical points through a quantitative evaluation of the Łojasiewicz exponent at the equilibrium points. This method is easy to implement without adding any new parameters. Three benchmark data sets from the University of California, Irvine machine learning repository are used in the numerical tests. Experimental results show the efficiency of the proposed neural network.

Keywords: support vector machine., indefinite kernels, neural networks, Sub-gradient, Łojasiewicz inequality.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial and Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285

References:

[1]	J. P. Aubin and A. Cellina, Differential Inclusions, Springer-Verlag, Berlin, 1984. doi: 10.1007/978-3-642-69512-4.
[2]	J. P. Aubin and H. Frankowska, Set-Valued Analysis, MA: Birkauser, Boston, 1990.
[3]	E. K. P. Chong, S. Hui and S. H. Zak, An analysis of a class of neural networks for solving linear programming problems, Automatic Control, IEEE Transactions on, 44 (1999), 1995-2006. doi: 10.1109/9.802909.
[4]	J. Chen and J. Ye, Training SVM with indefinite kernels, In Proceedings of the 25th International Conference on Machine Learning, (2008), 136-143. doi: 10.1145/1390156.1390174.
[5]	F. H. Clarke, Optimization and Non-smooth Analysis, Wiley, New York, 1969.
[6]	L. Fengqiu and X. Xiaoping, Design of natural classification kernels using prior knowledge, Fuzzy Systems, IEEE Transactions on, 20 (2012), 135-152.
[7]	A. F. Filippove, Differential Equations with Discontinuous Right-Hand Side, Mathematics and Its Applications (Soviet Series), Boston, MA: Kluwer, 1988.
[8]	M. Forti, P. Nistri and M. Quincampoix, Convergence of neural networks for programming problems via a nonsmooth Łojasiewicz inequality, Neural Networks, IEEE Transactions on, 17 (2006), 1471-1486.
[9]	M. Forti and A. Tesi, Absolute stability of analytic neural networks: An approach based on finite trajectory length, Circuits System I, IEEE Transation on, 51 (2004), 2460-2469. doi: 10.1109/TCSI.2004.838143.
[10]	B. Haasdonk, Feature space interpretation of svms with indefinite kernels, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27 (2005), 482-492. doi: 10.1109/TPAMI.2005.78.
[11]	M. Hein and O. Bousquet, Hilbertian metrics and positive definite kernels on probability measures, In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, (eds. Z. Ghahramani and R. Cowell), Society for Artificial Intelligence and Statistics, United States, (2005), 136-143.
[12]	J. J. Hopfield and D. W. Tank, "Neural" computation of decisions in optimization problems, Biological cybernetics, 52 (1985), 141-152.
[13]	R. Luss and A. d'Aspremon, Support vector machine classification with indefinite kernels, Mathematical Programming Computation, 1 (2009), 97-118. doi: 10.1007/s12532-009-0005-5.
[14]	I. Mierswa, Making Indefinite Kernel Learning Practical, Technical report, Artificial Intelligence Unit Department of Computer Science University of Dortmund, 2006.
[15]	J. C. Platt, Fast training of support vector machines using sequential minimal optimization, In Advances in Kernel Methods, (eds. Schölkopf, C. Burges and A. Smola), MIT, (1999), 185-208.
[16]	T. Rockafellar and R. Wets, Variational Analysis, Springer-Verlag, Germany, 1998. doi: 10.1007/978-3-642-02431-3.
[17]	S. Shalev-Shwartz, Y. Singer, N. Srebro and A. Cotter, Pegasos: Primal estimated sub-gradient solver for SVM, Math. Program., 127 (2011), 3-30. doi: 10.1007/s10107-010-0420-4.
[18]	H. Saigo, J. P. Vert, N. Ueda and T. Akutsu, Protein homology detection using string alignment kernels, Bioinformatics, 20 (2004), 1682-1689. doi: 10.1093/bioinformatics/bth141.
[19]	B. Schölkopf and A. J. Smola, Learning with Kernels, MIT, Cambridge, MA, 2002.
[20]	B. Schölkopf, P. Simard, A. J. Smola and V. N. Vapnik, Prior Knowledge in Support Vector Kernels, MIT, Cambridge, MA, 1998.
[21]	V. N. Vapnik, Statistical Learning Theory, Wiley, New York, 1998.
[22]	B. Wei and X. Xiaoping, Subgradient-based neural networks for nonsmooth nonconvex optimization problems, Circuits and Systems I: Regular Papers, IEEE Transactions on, 55 (2008), 2378-2391. doi: 10.1109/TCSI.2008.920131.
[23]	Y. Xia and J. Wang, A one-layer recurrent neural network for support vector machine learning, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 34 (2004), 1621-1629. doi: 10.1109/TSMCB.2003.822955.
[24]	S. Ziye and J. Qingwei, Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems, Journal of Industrial and Management Optimization, 10 (2014), 871-882. doi: 10.3934/jimo.2014.10.871.

show all references

References:

[1]	J. P. Aubin and A. Cellina, Differential Inclusions, Springer-Verlag, Berlin, 1984. doi: 10.1007/978-3-642-69512-4.
[2]	J. P. Aubin and H. Frankowska, Set-Valued Analysis, MA: Birkauser, Boston, 1990.
[3]	E. K. P. Chong, S. Hui and S. H. Zak, An analysis of a class of neural networks for solving linear programming problems, Automatic Control, IEEE Transactions on, 44 (1999), 1995-2006. doi: 10.1109/9.802909.
[4]	J. Chen and J. Ye, Training SVM with indefinite kernels, In Proceedings of the 25th International Conference on Machine Learning, (2008), 136-143. doi: 10.1145/1390156.1390174.
[5]	F. H. Clarke, Optimization and Non-smooth Analysis, Wiley, New York, 1969.
[6]	L. Fengqiu and X. Xiaoping, Design of natural classification kernels using prior knowledge, Fuzzy Systems, IEEE Transactions on, 20 (2012), 135-152.
[7]	A. F. Filippove, Differential Equations with Discontinuous Right-Hand Side, Mathematics and Its Applications (Soviet Series), Boston, MA: Kluwer, 1988.
[8]	M. Forti, P. Nistri and M. Quincampoix, Convergence of neural networks for programming problems via a nonsmooth Łojasiewicz inequality, Neural Networks, IEEE Transactions on, 17 (2006), 1471-1486.
[9]	M. Forti and A. Tesi, Absolute stability of analytic neural networks: An approach based on finite trajectory length, Circuits System I, IEEE Transation on, 51 (2004), 2460-2469. doi: 10.1109/TCSI.2004.838143.
[10]	B. Haasdonk, Feature space interpretation of svms with indefinite kernels, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27 (2005), 482-492. doi: 10.1109/TPAMI.2005.78.
[11]	M. Hein and O. Bousquet, Hilbertian metrics and positive definite kernels on probability measures, In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, (eds. Z. Ghahramani and R. Cowell), Society for Artificial Intelligence and Statistics, United States, (2005), 136-143.
[12]	J. J. Hopfield and D. W. Tank, "Neural" computation of decisions in optimization problems, Biological cybernetics, 52 (1985), 141-152.
[13]	R. Luss and A. d'Aspremon, Support vector machine classification with indefinite kernels, Mathematical Programming Computation, 1 (2009), 97-118. doi: 10.1007/s12532-009-0005-5.
[14]	I. Mierswa, Making Indefinite Kernel Learning Practical, Technical report, Artificial Intelligence Unit Department of Computer Science University of Dortmund, 2006.
[15]	J. C. Platt, Fast training of support vector machines using sequential minimal optimization, In Advances in Kernel Methods, (eds. Schölkopf, C. Burges and A. Smola), MIT, (1999), 185-208.
[16]	T. Rockafellar and R. Wets, Variational Analysis, Springer-Verlag, Germany, 1998. doi: 10.1007/978-3-642-02431-3.
[17]	S. Shalev-Shwartz, Y. Singer, N. Srebro and A. Cotter, Pegasos: Primal estimated sub-gradient solver for SVM, Math. Program., 127 (2011), 3-30. doi: 10.1007/s10107-010-0420-4.
[18]	H. Saigo, J. P. Vert, N. Ueda and T. Akutsu, Protein homology detection using string alignment kernels, Bioinformatics, 20 (2004), 1682-1689. doi: 10.1093/bioinformatics/bth141.
[19]	B. Schölkopf and A. J. Smola, Learning with Kernels, MIT, Cambridge, MA, 2002.
[20]	B. Schölkopf, P. Simard, A. J. Smola and V. N. Vapnik, Prior Knowledge in Support Vector Kernels, MIT, Cambridge, MA, 1998.
[21]	V. N. Vapnik, Statistical Learning Theory, Wiley, New York, 1998.
[22]	B. Wei and X. Xiaoping, Subgradient-based neural networks for nonsmooth nonconvex optimization problems, Circuits and Systems I: Regular Papers, IEEE Transactions on, 55 (2008), 2378-2391. doi: 10.1109/TCSI.2008.920131.
[23]	Y. Xia and J. Wang, A one-layer recurrent neural network for support vector machine learning, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 34 (2004), 1621-1629. doi: 10.1109/TSMCB.2003.822955.
[24]	S. Ziye and J. Qingwei, Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems, Journal of Industrial and Management Optimization, 10 (2014), 871-882. doi: 10.3934/jimo.2014.10.871.

[1]	Alain Haraux. Some applications of the Łojasiewicz gradient inequality. Communications on Pure and Applied Analysis, 2012, 11 (6) : 2417-2427. doi: 10.3934/cpaa.2012.11.2417
[2]	Yubo Yuan, Weiguo Fan, Dongmei Pu. Spline function smooth support vector machine for classification. Journal of Industrial and Management Optimization, 2007, 3 (3) : 529-542. doi: 10.3934/jimo.2007.3.529
[3]	Yubo Yuan. Canonical duality solution for alternating support vector machine. Journal of Industrial and Management Optimization, 2012, 8 (3) : 611-621. doi: 10.3934/jimo.2012.8.611
[4]	Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018
[5]	Jian Luo, Shu-Cherng Fang, Yanqin Bai, Zhibin Deng. Fuzzy quadratic surface support vector machine based on fisher discriminant analysis. Journal of Industrial and Management Optimization, 2016, 12 (1) : 357-373. doi: 10.3934/jimo.2016.12.357
[6]	Xin Li, Ziguan Cui, Linhui Sun, Guanming Lu, Debnath Narayan. Research on iterative repair algorithm of Hyperchaotic image based on support vector machine. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1199-1218. doi: 10.3934/dcdss.2019083
[7]	Fatemeh Bazikar, Saeed Ketabchi, Hossein Moosaei. Smooth augmented Lagrangian method for twin bounded support vector machine. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021027
[8]	Xin Yan, Hongmiao Zhu. A kernel-free fuzzy support vector machine with Universum. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021184
[9]	Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1835-1861. doi: 10.3934/jimo.2021046
[10]	Zhuchun Li, Yi Liu, Xiaoping Xue. Convergence and stability of generalized gradient systems by Łojasiewicz inequality with application in continuum Kuramoto model. Discrete and Continuous Dynamical Systems, 2019, 39 (1) : 345-367. doi: 10.3934/dcds.2019014
[11]	Ning Lu, Ying Liu. Application of support vector machine model in wind power prediction based on particle swarm optimization. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1267-1276. doi: 10.3934/dcdss.2015.8.1267
[12]	Huiqin Zhang, JinChun Wang, Meng Wang, Xudong Chen. Integration of cuckoo search and fuzzy support vector machine for intelligent diagnosis of production process quality. Journal of Industrial and Management Optimization, 2022, 18 (1) : 195-217. doi: 10.3934/jimo.2020150
[13]	Qianru Zhai, Ye Tian, Jingyue Zhou. A SMOTE-based quadratic surface support vector machine for imbalanced classification with mislabeled information. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2021230
[14]	Kongzhi Li, Xiaoping Xue. The Łojasiewicz inequality for free energy functionals on a graph. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022066
[15]	Yacine Chitour, Zhenyu Liao, Romain Couillet. A geometric approach of gradient descent algorithms in linear neural networks. Mathematical Control and Related Fields, 2022 doi: 10.3934/mcrf.2022021
[16]	Ying Sue Huang. Resynchronization of delayed neural networks. Discrete and Continuous Dynamical Systems, 2001, 7 (2) : 397-401. doi: 10.3934/dcds.2001.7.397
[17]	K. Schittkowski. Optimal parameter selection in support vector machines. Journal of Industrial and Management Optimization, 2005, 1 (4) : 465-476. doi: 10.3934/jimo.2005.1.465
[18]	Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial and Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031
[19]	Florian Dumpert. Quantitative robustness of localized support vector machines. Communications on Pure and Applied Analysis, 2020, 19 (8) : 3947-3956. doi: 10.3934/cpaa.2020174
[20]	Hong-Gunn Chew, Cheng-Chew Lim. On regularisation parameter transformation of support vector machines. Journal of Industrial and Management Optimization, 2009, 5 (2) : 403-415. doi: 10.3934/jimo.2009.5.403

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Fengqiu Liu Xiaoping Xue
on Google Scholar
Fengqiu Liu Xiaoping Xue

[Back to Top]