A Dual Method for Solving General Convex Quadratic Programs

Authors: Belkacem Brahmi, Mohand Ouamer Bibi

Abstract:

In this paper, we present a new method for solving quadratic programming problems, not strictly convex. Constraints of the problem are linear equalities and inequalities, with bounded variables. The suggested method combines the active-set strategies and support methods. The algorithm of the method and numerical experiments are presented, while comparing our approach with the active set method on randomly generated problems.

Keywords: Convex quadratic programming, dual support methods, active set methods.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1071882

References:

[1] R. Gabasov, F. M. Kirillova and V. M. Raketsky. On methods for solving the general problem of convex quadratic programming. Soviet. Math. Dokl. 23 (1981) 653-657.
[2] R. Gabasov, F. M. Kirillova, V. M. Raketsky and O.I. Kostyukova. Constructive Methods of Optimization, Volume 4: Convex Problems. University Press, Minsk (1987).
[3] E. A. Kostina and O. I. Kostyukova. An algorithm for solving quadratic programming problems with linear equality and inequality constraints. Computational Mathematics and Mathematical Physics, 41(7) (2001) 960-973.
[4] E. A. Kostina and O. I. Kostyukova. A primal-dual active-set method for convex quadratic programming. Preprints of the University of Karlsruhe, Germany (2003).
[5] B. Brahmi and M. O. Bibi. Dual support method for solving convex quadratic programs. To appear in Optimization (2009).
[6] R. Fletcher. Practical Methods of Optimization. J. Wiley and Sons, Chichester, England, second edition (1987).
[7] P. E. Gill, W. Murray, and M. H. Wright. Practical Optimization. Academic Press Inc, London ( 1981).
[8] Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics: Vol 13, Philadelphia (1994).
[9] J. Nocedal and S. J. Wright. Numerical Optimization. Springer-Verlag, New York, second edition (2006).
[10] N. L. Boland. A dual-active-set algorithm for positive semi-definite quadratic programming. Mathematical Programming, 78(1)(1997)1-27.
[11] D. Goldfarb and A. U. Idnani. A numerically stable dual method for solving strictly convex quadratic problems. Mathematical Programming, 27 (1983) 1-33.
[12] C. Van de Panne and A. Whinston. The simplex and dual method for quadratic programming. Operational Research Quarterly Journal, 15 (1964) 355-388.
[13] R. A. Bartlett and L. T. Biegler. QPSchur: A dual, active-set, Schurcomplement method for large-scale and structured convex quadratic programming. Optimization and Engineering, 7 (2006) 5-32.