caa a22 4500 475769244 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000501xx s 000 0 eng 10.1007/s101070050003 doi (NATIONALLICENCE)springer-10.1007/s101070050003 Hoai An Le Thi Mathematical Modelling and Applied Optimization Group, Laboratory of Mathematics, National Institute for Applied Sciences-Rouen, BP 8, F 76 131 Mont Saint Aignan Cedex, France, e-mail: lethi@insa-rouen.fr, FR aut An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints [Elektronische Daten] [Le Thi Hoai An] 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 projection subgradient method in convex minimization. The second is a branch-and-bound scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting point, it provides often a global solution. This motivates 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 the DCA. In both approaches we attempt to use the ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems. Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA and the combined DCA-branch-and-bound algorithm. Springer-Verlag Berlin Heidelberg, 2000 Key words: d.c. optimization - DCA - branch and bound - combined DCA-branch and bound - projection subgradient method - dual method - Lagrangian duality - proximal point algorithm nationallicence https://doi.org/10.1007/s101070050003 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101070050003 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Hoai An Le Thi Mathematical Modelling and Applied Optimization Group, Laboratory of Mathematics, National Institute for Applied Sciences-Rouen, BP 8, F 76 131 Mont Saint Aignan Cedex, France, e-mail: lethi@insa-rouen.fr, FR aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer