A COMBINED DC OPTIMIZATION ELLIPSOIDAL BRANCH-AND-BOUND ALGORITHM FORSOLVING NONCONVEX QUADRATIC-PROGRAMMING PROBLEMS

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 ex plicitly by a system of linear inequalities and/or equalities. It is r equired that for this set there exists an efficient algorithm to verif y whether a point is feasible, and to find a violated constraint if th is point is not feasible. The algorithm is based upon the fact that th e problem of minimizing an indefinite quadratic form over an ellipsoid can be efficiently solved by some available (polynomial and nonpolyno mial time) algorithms. In particular, the d.c. (difference of convex f unctions) algorithm (DCA) with restarting procedure recently introduce d by Pham Dinh Tao and L.T. Hoai An is applied to globally solving thi s problem. DCA is also used for locally solving the nonconvex quadrati c program. It is restarted with current best feasible points in the br anch-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 ellipsoi ds can be eliminated from further consideration. Several numerical exp eriments are given.