A Combined D.C. Optimization—Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems |
| |
Authors: | Le Thi Hoai An Pham Dinh Tao Le Dung Muu |
| |
Institution: | (1) Laboratory of Mathematics-INSA Rouen—CNRS UPRES-A 6085, Group Mathematical Modelling and Applied Optimization, BP 08, 76131 Mont Saint Aignan, France;(2) Institute of Mathematics, Hanoi, Box 631, Vietnam |
| |
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 |
本文献已被 SpringerLink 等数据库收录! |