American Institute of Mathematical Sciences

Advanced
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

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 & 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, (1984).  doi: 10.1007/978-3-642-69512-4.  Google Scholar

[2]

J. P. Aubin and H. Frankowska, Set-Valued Analysis,, MA: Birkauser, (1990).   Google Scholar

[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, 44 (1999), 1995.  doi: 10.1109/9.802909.  Google Scholar

[4]

J. Chen and J. Ye, Training SVM with indefinite kernels,, In Proceedings of the 25th International Conference on Machine Learning, (2008), 136.  doi: 10.1145/1390156.1390174.  Google Scholar

[5]

F. H. Clarke, Optimization and Non-smooth Analysis,, Wiley, (1969).   Google Scholar

[6]

L. Fengqiu and X. Xiaoping, Design of natural classification kernels using prior knowledge,, Fuzzy Systems, 20 (2012), 135.   Google Scholar

[7]

A. F. Filippove, Differential Equations with Discontinuous Right-Hand Side, Mathematics and Its Applications (Soviet Series),, Boston, (1988).   Google Scholar

[8]

M. Forti, P. Nistri and M. Quincampoix, Convergence of neural networks for programming problems via a nonsmooth Łojasiewicz inequality,, Neural Networks, 17 (2006), 1471.   Google Scholar

[9]

M. Forti and A. Tesi, Absolute stability of analytic neural networks: An approach based on finite trajectory length,, Circuits System I, 51 (2004), 2460.  doi: 10.1109/TCSI.2004.838143.  Google Scholar

[10]

B. Haasdonk, Feature space interpretation of svms with indefinite kernels,, Pattern Analysis and Machine Intelligence, 27 (2005), 482.  doi: 10.1109/TPAMI.2005.78.  Google Scholar

[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, (2005), 136.   Google Scholar

[12]

J. J. Hopfield and D. W. Tank, "Neural" computation of decisions in optimization problems,, Biological cybernetics, 52 (1985), 141.   Google Scholar

[13]

R. Luss and A. d'Aspremon, Support vector machine classification with indefinite kernels,, Mathematical Programming Computation, 1 (2009), 97.  doi: 10.1007/s12532-009-0005-5.  Google Scholar

[14]

I. Mierswa, Making Indefinite Kernel Learning Practical,, Technical report, (2006).   Google Scholar

[15]

J. C. Platt, Fast training of support vector machines using sequential minimal optimization,, In Advances in Kernel Methods, (1999), 185.   Google Scholar

[16]

T. Rockafellar and R. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[17]

S. Shalev-Shwartz, Y. Singer, N. Srebro and A. Cotter, Pegasos: Primal estimated sub-gradient solver for SVM,, Math. Program., 127 (2011), 3.  doi: 10.1007/s10107-010-0420-4.  Google Scholar

[18]

H. Saigo, J. P. Vert, N. Ueda and T. Akutsu, Protein homology detection using string alignment kernels,, Bioinformatics, 20 (2004), 1682.  doi: 10.1093/bioinformatics/bth141.  Google Scholar

[19]

B. Schölkopf and A. J. Smola, Learning with Kernels,, MIT, (2002).   Google Scholar

[20]

B. Schölkopf, P. Simard, A. J. Smola and V. N. Vapnik, Prior Knowledge in Support Vector Kernels,, MIT, (1998).   Google Scholar

[21]

V. N. Vapnik, Statistical Learning Theory,, Wiley, (1998).   Google Scholar

[22]

B. Wei and X. Xiaoping, Subgradient-based neural networks for nonsmooth nonconvex optimization problems,, Circuits and Systems I: Regular Papers, 55 (2008), 2378.  doi: 10.1109/TCSI.2008.920131.  Google Scholar

[23]

Y. Xia and J. Wang, A one-layer recurrent neural network for support vector machine learning,, Systems, 34 (2004), 1621.  doi: 10.1109/TSMCB.2003.822955.  Google Scholar

[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.  doi: 10.3934/jimo.2014.10.871.  Google Scholar

show all references

References:
[1]

J. P. Aubin and A. Cellina, Differential Inclusions,, Springer-Verlag, (1984).  doi: 10.1007/978-3-642-69512-4.  Google Scholar

[2]

J. P. Aubin and H. Frankowska, Set-Valued Analysis,, MA: Birkauser, (1990).   Google Scholar

[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, 44 (1999), 1995.  doi: 10.1109/9.802909.  Google Scholar

[4]

J. Chen and J. Ye, Training SVM with indefinite kernels,, In Proceedings of the 25th International Conference on Machine Learning, (2008), 136.  doi: 10.1145/1390156.1390174.  Google Scholar

[5]

F. H. Clarke, Optimization and Non-smooth Analysis,, Wiley, (1969).   Google Scholar

[6]

L. Fengqiu and X. Xiaoping, Design of natural classification kernels using prior knowledge,, Fuzzy Systems, 20 (2012), 135.   Google Scholar

[7]

A. F. Filippove, Differential Equations with Discontinuous Right-Hand Side, Mathematics and Its Applications (Soviet Series),, Boston, (1988).   Google Scholar

[8]

M. Forti, P. Nistri and M. Quincampoix, Convergence of neural networks for programming problems via a nonsmooth Łojasiewicz inequality,, Neural Networks, 17 (2006), 1471.   Google Scholar

[9]

M. Forti and A. Tesi, Absolute stability of analytic neural networks: An approach based on finite trajectory length,, Circuits System I, 51 (2004), 2460.  doi: 10.1109/TCSI.2004.838143.  Google Scholar

[10]

B. Haasdonk, Feature space interpretation of svms with indefinite kernels,, Pattern Analysis and Machine Intelligence, 27 (2005), 482.  doi: 10.1109/TPAMI.2005.78.  Google Scholar

[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, (2005), 136.   Google Scholar

[12]

J. J. Hopfield and D. W. Tank, "Neural" computation of decisions in optimization problems,, Biological cybernetics, 52 (1985), 141.   Google Scholar

[13]

R. Luss and A. d'Aspremon, Support vector machine classification with indefinite kernels,, Mathematical Programming Computation, 1 (2009), 97.  doi: 10.1007/s12532-009-0005-5.  Google Scholar

[14]

I. Mierswa, Making Indefinite Kernel Learning Practical,, Technical report, (2006).   Google Scholar

[15]

J. C. Platt, Fast training of support vector machines using sequential minimal optimization,, In Advances in Kernel Methods, (1999), 185.   Google Scholar

[16]

T. Rockafellar and R. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[17]

S. Shalev-Shwartz, Y. Singer, N. Srebro and A. Cotter, Pegasos: Primal estimated sub-gradient solver for SVM,, Math. Program., 127 (2011), 3.  doi: 10.1007/s10107-010-0420-4.  Google Scholar

[18]

H. Saigo, J. P. Vert, N. Ueda and T. Akutsu, Protein homology detection using string alignment kernels,, Bioinformatics, 20 (2004), 1682.  doi: 10.1093/bioinformatics/bth141.  Google Scholar

[19]

B. Schölkopf and A. J. Smola, Learning with Kernels,, MIT, (2002).   Google Scholar

[20]

B. Schölkopf, P. Simard, A. J. Smola and V. N. Vapnik, Prior Knowledge in Support Vector Kernels,, MIT, (1998).   Google Scholar

[21]

V. N. Vapnik, Statistical Learning Theory,, Wiley, (1998).   Google Scholar

[22]

B. Wei and X. Xiaoping, Subgradient-based neural networks for nonsmooth nonconvex optimization problems,, Circuits and Systems I: Regular Papers, 55 (2008), 2378.  doi: 10.1109/TCSI.2008.920131.  Google Scholar

[23]

Y. Xia and J. Wang, A one-layer recurrent neural network for support vector machine learning,, Systems, 34 (2004), 1621.  doi: 10.1109/TSMCB.2003.822955.  Google Scholar

[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.  doi: 10.3934/jimo.2014.10.871.  Google Scholar

[1]

Alain Haraux. Some applications of the Łojasiewicz gradient inequality. Communications on Pure & 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 & 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 & Management Optimization, 2012, 8 (3) : 611-621. doi: 10.3934/jimo.2012.8.611
[4]

Zhuchun Li, Yi Liu, Xiaoping Xue. Convergence and stability of generalized gradient systems by Łojasiewicz inequality with application in continuum Kuramoto model. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 345-367. doi: 10.3934/dcds.2019014
[5]

Jian Luo, Shu-Cherng Fang, Yanqin Bai, Zhibin Deng. Fuzzy quadratic surface support vector machine based on fisher discriminant analysis. Journal of Industrial & 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 & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1199-1218. doi: 10.3934/dcdss.2019083
[7]

Ning Lu, Ying Liu. Application of support vector machine model in wind power prediction based on particle swarm optimization. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1267-1276. doi: 10.3934/dcdss.2015.8.1267
[8]

Ying Sue Huang. Resynchronization of delayed neural networks. Discrete & Continuous Dynamical Systems - A, 2001, 7 (2) : 397-401. doi: 10.3934/dcds.2001.7.397
[9]

K. Schittkowski. Optimal parameter selection in support vector machines. Journal of Industrial & Management Optimization, 2005, 1 (4) : 465-476. doi: 10.3934/jimo.2005.1.465
[10]

Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial & Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031
[11]

Hong-Gunn Chew, Cheng-Chew Lim. On regularisation parameter transformation of support vector machines. Journal of Industrial & Management Optimization, 2009, 5 (2) : 403-415. doi: 10.3934/jimo.2009.5.403
[12]

Florian Dumpert. Quantitative robustness of localized support vector machines. Communications on Pure & Applied Analysis, 2020, 19 (8) : 3947-3956. doi: 10.3934/cpaa.2020174
[13]

Tatyana S. Turova. Structural phase transitions in neural networks. Mathematical Biosciences & Engineering, 2014, 11 (1) : 139-148. doi: 10.3934/mbe.2014.11.139
[14]

Delio Mugnolo, René Pröpper. Gradient systems on networks. Conference Publications, 2011, 2011 (Special) : 1078-1090. doi: 10.3934/proc.2011.2011.1078
[15]

Ricai Luo, Honglei Xu, Wu-Sheng Wang, Jie Sun, Wei Xu. A weak condition for global stability of delayed neural networks. Journal of Industrial & Management Optimization, 2016, 12 (2) : 505-514. doi: 10.3934/jimo.2016.12.505
[16]

Benedetta Lisena. Average criteria for periodic neural networks with delay. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 761-773. doi: 10.3934/dcdsb.2014.19.761
[17]

Larry Turyn. Cellular neural networks: asymmetric templates and spatial chaos. Conference Publications, 2003, 2003 (Special) : 864-871. doi: 10.3934/proc.2003.2003.864
[18]

Benedict Leimkuhler, Charles Matthews, Tiffany Vlaar. Partitioned integrators for thermodynamic parameterization of neural networks. Foundations of Data Science, 2019, 1 (4) : 457-489. doi: 10.3934/fods.2019019
[19]

Siamak RabieniaHaratbar. Support theorem for the Light-Ray transform of vector fields on Minkowski spaces. Inverse Problems & Imaging, 2018, 12 (2) : 293-314. doi: 10.3934/ipi.2018013
[20]

Keiji Tatsumi, Masashi Akao, Ryo Kawachi, Tetsuzo Tanino. Performance evaluation of multiobjective multiclass support vector machines maximizing geometric margins. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 151-169. doi: 10.3934/naco.2011.1.151

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (26)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences