An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints

Authors
Citation
Lth. An, An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints, MATH PROGR, 87(3), 2000, pp. 401-426
Citations number
30
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
87
Issue
3
Year of publication
2000
Pages
401 - 426
Database
ISI
SICI code
0025-5610(200005)87:3<401:AEAFGM>2.0.ZU;2-1
Abstract
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids. The first approach is the d.c. (difference of convex Functions) optimization algorithm (abbr. DCA) whose main tools are the proximal point algorithm and/or the projecti on subgradient method in convex minimization. The second is a branch-and-bo und scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham Dinh in 1986 for a gener al d.c. program and later developed by our various work is a local method b ut, from a good starting point, it provides often a global solution. This m otivates us to combine the DCA and our branch and bound algorithm in order to obtain a good initial point for the DCA and to prove the globality of th e DCA. In both approaches we attempt to use the ellipsoidal constrained qua dratic programs as the main subproblems. The idea is based upon the fact th at these programs can be efficiently solved by some available (polynomial a nd nonpolynomial time) algorithms, among them the DCA with restarting proce dure recently proposed by Pham Dinh and Le Thi has been shown to be the mos t robust and fast For large-scale problems. Several numerical experiments w ith dimension up to 200 are given which show the effectiveness and the robu stness of the DCA and the combined DCA-branch-and-bound algorithm.