An Algorithm for Solving Quadratic Programming Problems with an M-matrix

  • Katia Hassaini Research Unit LaMOS, Department of Operations Research, University of Bejaia, 06000 Bejaia, Algeria.
  • Mohand Ouamer Bibi Research Unit LaMOS (Modelling and Optimization of Systems)
Keywords: Support method, M-matrix, Convex quadratic programming, Projection, Newton method


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.


[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,
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.
Research Articles