IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v2y1998i1d10.1023_a1009777410170.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Le Thi Hoai An & Pham Dinh Tao & Le Dung Muu, 1998. "A Combined D.C. Optimization—Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems," Journal of Combinatorial Optimization, Springer, vol. 2(1), pages 9-28, March.
    • Handle: RePEc:spr:jcomop:v:2:y:1998:i:1:d:10.1023_a:1009777410170
    DOI: 10.1023/A:1009777410170
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1009777410170
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1009777410170?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gomez, Manuel A., 2005. "A null-space method for computing the search direction in the general inertia-controlling method for dense quadratic programming," European Journal of Operational Research, Elsevier, vol. 161(3), pages 655-662, March.
    2. David Wozabal, 2012. "A framework for optimization under ambiguity," Annals of Operations Research, Springer, vol. 193(1), pages 21-47, March.
    3. Marcia Fampa & Jon Lee & Wendel Melo, 2017. "On global optimization with indefinite quadratics," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 309-337, September.
    4. X. J. Zheng & X. L. Sun & D. Li, 2010. "Separable Relaxation for Nonconvex Quadratic Integer Programming: Integer Diagonalization Approach," Journal of Optimization Theory and Applications, Springer, vol. 146(2), pages 463-489, August.
    5. X. Zheng & X. Sun & D. Li, 2011. "Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations," Journal of Global Optimization, Springer, vol. 50(4), pages 695-712, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:2:y:1998:i:1:d:10.1023_a:1009777410170. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.