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.