A Combined D.C. Optimization—Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems

Le Thi Hoai An (), Pham Dinh Tao () and Le Dung Muu ()
Additional contact information
Le Thi Hoai An: Group Mathematical Modelling and Applied Optimization
Pham Dinh Tao: Group Mathematical Modelling and Applied Optimization
Le Dung Muu: Institute of Mathematics, Hanoi

Journal of Combinatorial Optimization, 1998, vol. 2, issue 1, No 2, 9-28

Abstract: Abstract In this paper we propose a new branch-and-bound algorithm by using an ellipsoidal partition for minimizing an indefinite quadratic function over a bounded polyhedral convex set which is not necessarily given explicitly by a system of linear inequalities and/or equalities. It is required that for this set there exists an efficient algorithm to verify whether a point is feasible, and to find a violated constraint if this point is not feasible. The algorithm is based upon the fact that the problem of minimizing an indefinite quadratic form over an ellipsoid can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms. In particular, the d.c. (difference of convex functions) algorithm (DCA) with restarting procedure recently introduced by Pham Dinh Tao and L.T. Hoai An is applied to globally solving this problem. DCA is also used for locally solving the nonconvex quadratic program. It is restarted with current best feasible points in the branch-and-bound scheme, and improved them in its turn. The combined DCA-ellipsoidal branch-and-bound algorithm then enhances the convergence: it reduces considerably the upper bound and thereby a lot of ellipsoids can be eliminated from further consideration. Several numerical experiments are given.

Keywords: indefinite quadratic programming; branch-and-bound; ellipsoid methods; d.c. optimization; ball constrained quadratic problem (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009777410170 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:2:y:1998:i:1:d:10.1023_a:1009777410170

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009777410170

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().