An Algorithm for Solving Quadratic Programming Problems with an M-matrix
Keywords:
Support method, M-matrix, Convex quadratic programming, Projection, Newton method
Abstract
In this study, we propose an approach for solving a quadraticprogramming problem with an M-matrix and simple constraints (QPs). It isbased on the algorithms of Luk-Pagano and Stachurski. These methods usethe fact that an M-matrix possesses a nonnegative inverse which allows tohave a sequence of feasible points monotonically increasing. Introducing theconcept of support for an objective function developed by Gabasov et al., ourapproach leads to a more general condition which allows to have an initialfeasible solution, related to a coordinator support and close to the optimalsolution. The programming under MATLAB of our method and that of Lukand Pagano has allowed us to make a comparison between them, with anillustration on two numerical examples.References
[1] Atamtürk, A. and Gómez, A. (2018) ’Strong formulations for quadratic optimization with M-matrices and indicator variables’, Math. Program, Vol. 170, pp.141–176.
[2] Berman, A. and Plemmons, R. J. (1979) ’Nonnegative Matrices in Mathematical Sciences’, Academic Press, New York.
[3] Bertsekas, D. P. (1982) ’Projection Newton Method for Optimization Problems with Simple Constraints’, SIAM J. Control and Optimization, Vol. 20, No. 2, pp.221-246.
[4] Bibi, M. O., Ikheneche, N. & Bentobache, M. (2020) ’A hybrid direction algorithm for solving a convex quadratic problem’, International Journal of Mathematics in
Operations Research, Vol. 16, No. 2, pp. 159-178.
[5] Bounceur, A., Djemai, S., Brahmi, B., Bibi, M. O.,&Euler, R. (2018) ’A Classification Approach for an Accurate Analog/RF BIST Evaluation Based on the Process
Parameters’, Journal of Electronic Testing: Theory and Application. Vol. 34, No.3, pp.321–335.
[6] Brahmi, B. and Bibi, M. O. (2010) ’Dual Support method for solving convex quadratic programs’, Optimization, Vol. 59, No. 6, pp.851-872.
[7] Céa, J. and Glowinski, R. (1973) ’Sur des méthodes d’optimisation par relaxation’, RAIRO, Vol. 7, No. R-3, pp.5-32. (in French).
[8] Chen, Y. H. and Fang, S. C. (2000) ’Neurocomputing with time delay analysis for solving convex quadratic programming problems’, IEEE Transactions on Neural
Networks, Vol. 11, No. 1, pp. 230-240.
[9] Daryina, A. N. and Izmailov, A. F. (2012) ’On Active-Set Methods for the Quadratic Programming Problem’, Computational Mathematics and Mathematical Physics, Vol.
52, No. 4, pp. 512–523.
[10] Djemai, S., Brahmi, B. and Bibi, M. O. (2016) ’A primal–dual method for SVM training’, Neurocomputing, Vol. 211, pp. 34–40.
[11] Gabasov, R., Kirillova, F. M., Kostyukova, O. I. and Raketsky, V. M. (1987) ’Constructive methods of optimization’, volume 4: Convex Problems, University
Publishing House, Minsk. (in Russian).
[12] Hochbaum, D.S. (2013) ’Multi-label markov random fields as an efficient and effective tool for image segmentation, total variations and regularization’, Numer. Math. theory Methods Appl., Vol. 6, N. 1, pp. 169–198.
[13] Hungerländer, P. and Rendl, F. (2015) ’A feasible active set method for strictly convex quadratic problems with simple bounds’, SIAM Journal on Optimization, Vol. 25, No.
3, pp.1633–1659.
[14] Jiang, Y. J. and Zeng, J. P. (2011) ’Direct algorithm for the solution of two-sided obstacle problems with M-matrix’, Numerical Linear Algebra with Applications, Vol.
18, No. 1, pp. 167-173
[15] Kärkkäinen, T., Kunisch, K. and Tarvainen, P. (2003) ’Augmented Lagrangian Active Set Methods for Obstacle Problems’, Journal of optimization theory and applications,
Vol. 119, No. 3, pp. 499–533.
[16] Kunisch, K. and Rendl, F. (2003) ’An infeasible active set method for convex problems with simple bounds’, SIAM Journal on Optimization, Vol. 14, No. 1, pp.35–52.
[17] Levati, G., Scarpini, F. and Volpi, G. (1974) ’Sul trattamento numerico di alcuni problemi variazionali di tipo unilaterale’, Laboratorio di analisi numerica del
Consiglio nazionale delle ricerche, Univ. of Pavia, Vol. 82.
[18] Li, L. and Kobayashi, Y. (2006) ’A block recursive algorithm for the linear complementarity problem with an M-matrix’, International Journal of Innovative,
Computing, Information and Control, Vol. 2, No. 6, pp.1327-1335.
[19] Lobo, M.S, Fazel, M. and Boyd, S. (2007) ’Portfolio optimization with linear and fixed transaction costs’, Annals of Operations Research, Vol. 152, pp.341–365.
[20] Luk, F. T. and Pagano, M. (1980) ’Quadratic programming with M-Matrices’, Linear Algebra And Its Applications, Vol. 33, No. 2, pp.15-40.
[21] Pakdaman, M. and Effati, S. (2017) ’Bounds for convex quadratic programming problems and some important applications’, International Journal of Operational
Research, Vol. 30, No. 2, pp.277-287.
[22] Radjef, S. and Bibi, M. O. (2012) ’An Effective Generalization of the Direct Support Method in Quadratic Convex Programming’, Applied Mathematical Sciences, Vol. 6,
No. 31, pp.1525-1540.
[23] Scarpini, F. (1975) ’Some algorithms solving the unilateral Dirichlet problems with two constraints’, Calcolo, Vol. 12, No. 2, pp.113-149.
[24] Šiljak, D. D. (1978) ’Large-scale Dynamic Systems: Stability and Structure’, North-Holland, New York.
[25] Song, Q., Liu, F., Cao, J. andYu,W. (2013) ’M-matrix strategies for pinning-controlled leader-following consensus in multiagent systems with nonlinear dynamics’, IEEE
Trans Cybern, Vol 43, No 6, pp. 1688-1697.
[26] Stachurski, A. (2017) ’On a conjugate directions method for solving strictly convex QP problem’, Math Meth Oper Res, Vol. 86, No. 3, pp.523–548
[27] Stachurski, A. (1990) ’An Equivalence between two algorithms for a class of quadratic programming problems with M-matrices’, Optimization, Vol. 21, No. 6, pp.871-878.
[28] Stachurski, A. (1986) ’Monotone sequences of feasible solutions for quadratic programming problems with M-matrices and box constraints’, In System Modeling
and Optimization. Book series: Lecture Notes in Control and Information Sciences, Vol. 84, pp.896-902.
[29] Stipanovic, D. M. and Šiljak, D. D. (2000) ’Stability of polytopic systems via convex M-matrices and parameter-dependent Liapunov functions’, Nonlinear Analysis, Vol.
40, pp.589-609.
[30] Stipanovic, D. M., Shankaran, S. and Tomlin, C. J. (2005) ’Multi-agent avoidance control using an M-matrix property. Electronic Journal of Linear Algebra’, A
publication of the International Linear Algebra Society, Vol. 12, pp.64-72.
[31] Tardieu, N. Youbissi, F. and Chamberland, E. (2008) ’Un algorithme de Gradient Conjugué Projeté préconditionné pour la résolution de problèmes unilatéraux’, C. R.
Mecanique, Vol. 336, No. 11, pp.840–845.
[32] Varga, R. S. (1962) ’Matrix Iterative Analysis’, Springer, Berlin, Heidelberg.
[33] Windisch, G. (1989) ’M-matrices in Numerical Analysis’, Teubner-verlag, Leipzig,
Germany.
[2] Berman, A. and Plemmons, R. J. (1979) ’Nonnegative Matrices in Mathematical Sciences’, Academic Press, New York.
[3] Bertsekas, D. P. (1982) ’Projection Newton Method for Optimization Problems with Simple Constraints’, SIAM J. Control and Optimization, Vol. 20, No. 2, pp.221-246.
[4] Bibi, M. O., Ikheneche, N. & Bentobache, M. (2020) ’A hybrid direction algorithm for solving a convex quadratic problem’, International Journal of Mathematics in
Operations Research, Vol. 16, No. 2, pp. 159-178.
[5] Bounceur, A., Djemai, S., Brahmi, B., Bibi, M. O.,&Euler, R. (2018) ’A Classification Approach for an Accurate Analog/RF BIST Evaluation Based on the Process
Parameters’, Journal of Electronic Testing: Theory and Application. Vol. 34, No.3, pp.321–335.
[6] Brahmi, B. and Bibi, M. O. (2010) ’Dual Support method for solving convex quadratic programs’, Optimization, Vol. 59, No. 6, pp.851-872.
[7] Céa, J. and Glowinski, R. (1973) ’Sur des méthodes d’optimisation par relaxation’, RAIRO, Vol. 7, No. R-3, pp.5-32. (in French).
[8] Chen, Y. H. and Fang, S. C. (2000) ’Neurocomputing with time delay analysis for solving convex quadratic programming problems’, IEEE Transactions on Neural
Networks, Vol. 11, No. 1, pp. 230-240.
[9] Daryina, A. N. and Izmailov, A. F. (2012) ’On Active-Set Methods for the Quadratic Programming Problem’, Computational Mathematics and Mathematical Physics, Vol.
52, No. 4, pp. 512–523.
[10] Djemai, S., Brahmi, B. and Bibi, M. O. (2016) ’A primal–dual method for SVM training’, Neurocomputing, Vol. 211, pp. 34–40.
[11] Gabasov, R., Kirillova, F. M., Kostyukova, O. I. and Raketsky, V. M. (1987) ’Constructive methods of optimization’, volume 4: Convex Problems, University
Publishing House, Minsk. (in Russian).
[12] Hochbaum, D.S. (2013) ’Multi-label markov random fields as an efficient and effective tool for image segmentation, total variations and regularization’, Numer. Math. theory Methods Appl., Vol. 6, N. 1, pp. 169–198.
[13] Hungerländer, P. and Rendl, F. (2015) ’A feasible active set method for strictly convex quadratic problems with simple bounds’, SIAM Journal on Optimization, Vol. 25, No.
3, pp.1633–1659.
[14] Jiang, Y. J. and Zeng, J. P. (2011) ’Direct algorithm for the solution of two-sided obstacle problems with M-matrix’, Numerical Linear Algebra with Applications, Vol.
18, No. 1, pp. 167-173
[15] Kärkkäinen, T., Kunisch, K. and Tarvainen, P. (2003) ’Augmented Lagrangian Active Set Methods for Obstacle Problems’, Journal of optimization theory and applications,
Vol. 119, No. 3, pp. 499–533.
[16] Kunisch, K. and Rendl, F. (2003) ’An infeasible active set method for convex problems with simple bounds’, SIAM Journal on Optimization, Vol. 14, No. 1, pp.35–52.
[17] Levati, G., Scarpini, F. and Volpi, G. (1974) ’Sul trattamento numerico di alcuni problemi variazionali di tipo unilaterale’, Laboratorio di analisi numerica del
Consiglio nazionale delle ricerche, Univ. of Pavia, Vol. 82.
[18] Li, L. and Kobayashi, Y. (2006) ’A block recursive algorithm for the linear complementarity problem with an M-matrix’, International Journal of Innovative,
Computing, Information and Control, Vol. 2, No. 6, pp.1327-1335.
[19] Lobo, M.S, Fazel, M. and Boyd, S. (2007) ’Portfolio optimization with linear and fixed transaction costs’, Annals of Operations Research, Vol. 152, pp.341–365.
[20] Luk, F. T. and Pagano, M. (1980) ’Quadratic programming with M-Matrices’, Linear Algebra And Its Applications, Vol. 33, No. 2, pp.15-40.
[21] Pakdaman, M. and Effati, S. (2017) ’Bounds for convex quadratic programming problems and some important applications’, International Journal of Operational
Research, Vol. 30, No. 2, pp.277-287.
[22] Radjef, S. and Bibi, M. O. (2012) ’An Effective Generalization of the Direct Support Method in Quadratic Convex Programming’, Applied Mathematical Sciences, Vol. 6,
No. 31, pp.1525-1540.
[23] Scarpini, F. (1975) ’Some algorithms solving the unilateral Dirichlet problems with two constraints’, Calcolo, Vol. 12, No. 2, pp.113-149.
[24] Šiljak, D. D. (1978) ’Large-scale Dynamic Systems: Stability and Structure’, North-Holland, New York.
[25] Song, Q., Liu, F., Cao, J. andYu,W. (2013) ’M-matrix strategies for pinning-controlled leader-following consensus in multiagent systems with nonlinear dynamics’, IEEE
Trans Cybern, Vol 43, No 6, pp. 1688-1697.
[26] Stachurski, A. (2017) ’On a conjugate directions method for solving strictly convex QP problem’, Math Meth Oper Res, Vol. 86, No. 3, pp.523–548
[27] Stachurski, A. (1990) ’An Equivalence between two algorithms for a class of quadratic programming problems with M-matrices’, Optimization, Vol. 21, No. 6, pp.871-878.
[28] Stachurski, A. (1986) ’Monotone sequences of feasible solutions for quadratic programming problems with M-matrices and box constraints’, In System Modeling
and Optimization. Book series: Lecture Notes in Control and Information Sciences, Vol. 84, pp.896-902.
[29] Stipanovic, D. M. and Šiljak, D. D. (2000) ’Stability of polytopic systems via convex M-matrices and parameter-dependent Liapunov functions’, Nonlinear Analysis, Vol.
40, pp.589-609.
[30] Stipanovic, D. M., Shankaran, S. and Tomlin, C. J. (2005) ’Multi-agent avoidance control using an M-matrix property. Electronic Journal of Linear Algebra’, A
publication of the International Linear Algebra Society, Vol. 12, pp.64-72.
[31] Tardieu, N. Youbissi, F. and Chamberland, E. (2008) ’Un algorithme de Gradient Conjugué Projeté préconditionné pour la résolution de problèmes unilatéraux’, C. R.
Mecanique, Vol. 336, No. 11, pp.840–845.
[32] Varga, R. S. (1962) ’Matrix Iterative Analysis’, Springer, Berlin, Heidelberg.
[33] Windisch, G. (1989) ’M-matrices in Numerical Analysis’, Teubner-verlag, Leipzig,
Germany.
Published
2024-02-18
How to Cite
Hassaini, K., & Bibi, M. O. (2024). An Algorithm for Solving Quadratic Programming Problems with an M-matrix. Statistics, Optimization & Information Computing, 12(2), 405-417. https://doi.org/10.19139/soic-2310-5070-1399
Issue
Section
Research Articles
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
