International Journal of Nonlinear Analysis and Applications

Gradient projection algorithms for optimization problems on convex sets and application to SVM

Document Type : Research Paper

Authors

1 The Laboratory of Mathematical Modelling and Numeric in Engineering Sciences, National Engineering School of Tunis, University of Tunis El Manar, Rue B\'echir Salem Belkhiria Campus Universitaire, B.P. 37, 1002 Tunis Belvedere, Tunisia

2 The Laboratory of Mathematical Modelling and Numeric in Engineering Sciences, National Engineering School of Tunis, University of Tunis El Manar, Rue Bechir Salem Belkhiria Campus universitaire, B.P. 37, 1002 Tunis Belvédère, Tunisia

Abstract

In this paper, we present some gradient projection algorithms for solving optimization problems with a convex-constrained set. We derive the optimality condition when the convex set is a cone and under some mild assumptions, we prove the convergence of these algorithms. Finally, we apply them to quadratic problems arising in training support vector machines for the Wisconsin Diagnostic Breast Cancer (WDBC) classification problem.

Keywords

[1] L. Armijo, Minimization of functions having Lipschitz continuous first partial derivatives, Pacific J. Math. 16 (1966), no. 1, 1–3.
[2] D.P. Bertsekas, On the Goldstein-Levitin-Polyak gradient projection method, IEEE Trans. Automatic Control 21 (1976), no. 2, 174–184.
[3] P.H. Calamai and J.J. More, Projected gradient methods for linearly constrained problems, Math. Program. 39 (1987), 93–116.
[4] R.E. Fan, P.H. Chen, C.J. Lin, and T. Joachims, Working set selection using second order information for training support vector machines, J. Machine Learn. Res. 6 (2005), no. 12, 1889–1918.
[5] E.M. Gafni and D.P. Bertsekas, Two-metric projection methods for constrained optimization, SIAM J. Control Optim. 22 (1984), 936–964,
[6] J. Gondzio, Interior point methods 25 years later, Eur. J. Oper. Res. 218 (2012), 587–601.
[7] M.W. Huang, C.W. Chen, W.C. Lin, S.W. Ke, and C.F. Tsai, SVM and SVM ensembles in breast cancer prediction, PloS one 12 (2017), no. 1, e0161501.
[8] S.G. Jacob and R.G. Ramani, Efficient classifier for classification of prognostic breast cancer data through data mining techniques, Proc. World Cong. Engin. Comput. Sci., 2012, pp. 24–26.
[9] H. Karimi, J. Nutini, and M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the polyak- lojasiewicz condition, Machine Learn. Knowledge Discov. Databases: Eur. Conf. ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proc. Part I 16, Springer International Publishing, 2016, pp. 795–811.
[10] S.S. Keerthi, D. DeCoste, and T. Joachims, A modified finite Newton method for fast solution of large scale linear SVMs, J. Mach. Learn. Res. 6 (2005), no. 3, 341–361.
[11] E.S. Levitin and B.T. Polyak, Constrained minimization problems, USSR Comput Math. Phys. 6 (1966), 1–50.
[12] N. Liu, E.S. Qi, M. Xu, B. Gao, and G.Q. Liu, A novel intelligent classification model for breast cancer diagnosis, Inf. Process. Manag. 56 (2019), no. 3, 609–623.
[13] G.P. Mccormick, R.A. Tapia, The gradient projection method under mild differentiability conditions, SIAM J. Control 10 (1972), no. 1, 93–98.
[14] J.C. Platt, Sequential minimal optimization: A fast algorithm for training support vector machines, Published by Microsoft, MSR-TR-98-14, 1998.
[15] B.T. Polya, Introduction to Optimization, Optimization Software, New York, 1987.
[16] A. Ruszczynski, Nonlinear Optimization, Princeton University Press, New Jersey, 2006.
[17] F. Steinke, B. Scholkopf, and V. Blanz, Support vector machines for 3D shape processing, Comput. Graphics Forum 24 (1982-2005), no. 3, 285-294.
[18] M. Su and H.-K. Xu, Remarks on the gradient-projection algorithm, J. Nonlinear Anal. Optim. 1 (2010), 35–43.
[19] P. Taylor, J. Fox, and A. Todd-Pokropek, Evaluation of a decision Aid for the classification of micro calcifications, Digital Mammog.: Nijmegen 1998 (1998), 237–244.
[20] G.D. Tourassi, M.K. Markey, J.Y. Lo, and C.E. Floyd Jr, A neural network approach to breast cancer diagnosis as a constraint satisfaction problem, Med. Phys. 28 (2001), 804–811.
[21] V. Vapnik, I. Guyon, and T. Hastie, Support vector machines, Mach. Learn. 20 (1995), no. 3, 273–297.
[22] B.P. Vrigazova, Detection of malignant and benign breast cancer using the Anova-Bootstrap-SVM, J. Data Inf. Sci. 5 (2020), no. 2, 62–75.
International Journal of Nonlinear Analysis and Applications
Volume 14, Issue 8
August 2023
Pages 197-215
  • Receive Date: 03 March 2021
  • Revise Date: 20 May 2021
  • Accept Date: 29 May 2021