A Dual Method for Solving General Convex Quadratic Programs

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.

• Belkacem Brahmi
• Mohand Ouamer Bibi

• Convex quadratic programming
• dual support methods
• active set methods.

[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.