A computational comparison of some branch and bound methods for indefinite quadratic programs

详细信息    查看全文

• 作者：Riccardo Cambini (1)
  Claudio Sodini (1)
  
• 关键词：Quadratic programming ; Branch and bound ; d.c. decomposition ; 90C20 ; 90C26 ; 90C31 ; C61 ; C63
• 刊名：Central European Journal of Operations Research
• 出版年：2008
• 出版时间：June 2008
• 年：2008
• 卷：16
• 期：2
• 页码：139-152
• 全文大小：215KB
• 参考文献：1. Barrientos O and Correa R (2000). An algorithm for global minimization of linearly constrained quadratic functions. / J Global Optim 16: 77鈥?3 CrossRef
  2. Best MJ and Ding B (1997). Global and local quadratic minimization. / J Global Optim 10: 77鈥?0 CrossRef
  3. Best MJ and Ding B (2000). A decomposition method for global and local quadratic minimization. / J Global Optim 16: 133鈥?51 CrossRef
  4. Bomze IM and Danninger G (1994). A finite algorithm for solving general quadratic problems. / J Global Optim 4: 1鈥?6 CrossRef
  5. Bomze IM (2002). Branch-and-bound approaches to standard quadratic optimization problems. / J Global Optim 22: 17鈥?7 CrossRef
  6. Bomze IM and Locatelli M (2004). Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches. / Comput Optim Appl 28: 227鈥?45 CrossRef
  7. Cambini R and Sodini C (2005). Decomposition methods for solving nonconvex quadratic programs via branch and bound. / J Global Optim 33(3): 313鈥?36 CrossRef
  8. Churilov L and Sniedovich M (1999). A concave composite programming perspective on D.C. programming. In: Eberhard, A, Hill, R, Ralph, D and Glover, BM (eds) Progress in optimization, Applied Optimization, vol 30, pp. Kluwer, Dordrecht
  9. De Angelis PL, Pardalos PM and Toraldo G (1997). Quadratic Programming with Box Constraints. In: Bomze, IM (eds) Developments in global optimization, pp 73鈥?3. Kluwer, Dordrecht,
  10. Floudas CA and Visweswaran V (1995). Quadratic Optimization. In: Horst, R and Pardalos, PM (eds) Handbook of global optimization, nonconvex optimization and its applications, vol 2, pp 217鈥?69. Kluwer, Dordrecht,
  11. Gantmacher FR (1960). The theory of matrices, vol 1. Chelsea, New York
  12. Hansen P, Jaumard B, Ruiz M and Xiong J (1993). Global minimization of indefinite quadratic functions subject to box constraints. / Naval Res Logistics 40: 373鈥?92 CrossRef
  13. Hiriart-Urruty JB (1985) Generalized differentiability, duality and optimization for problems dealing with differences of convex functions. In: Convexity and duality in optimization, Lecture Notes in Economics and Mathematical Systems, vol 256. Springer, Berlin
  14. Horst R (1976). An algorithm for nonconvex programming problems. / Math Program 10(3): 312鈥?21 CrossRef
  15. Horst R (1980). A note on the convergence of an algorithm for nonconvex programming problems. / Math Program 19(2): 237鈥?38 CrossRef
  16. Horst R and Tuy H (1990). Global optimization. Springer, Berlin
  17. Horst R, Pardalos PM and Thoai NV (1995). Introduction to global optimization, nonconvex optimization and its applications, vol 3. Kluwer, Dordrecht
  18. Horst R and Van Thoai N (1996). A new algorithm for solving the general quadratic programming problem. / Comput Optim Appl 5(1): 39鈥?8 CrossRef
  19. Konno H (1976). Maximization of a convex quadratic function under linear constraints. / Math Program 11(2): 117鈥?27 CrossRef
  20. Le Thi Hoai An and Pham Dinh Tao (1997) Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms. J Global Optim 11:253鈥?85
  21. Muu LD and Oettli W (1991). An algorithm for indefinite quadratic programming with convex constraints. / Oper Res Lett 10(6): 323鈥?27 CrossRef
  22. Pardalos PM, Glick JH and Rosen JB (1987). Global minimization of indefinite quadratic problems. / Computing 39(4): 281鈥?91 CrossRef
  23. Pardalos PM (1991). Global optimization algorithms for linearly constrained indefinite quadratic problems. / Comput Math Appl 21: 87鈥?7 CrossRef
  24. Phong Thai Quynh, Le Thi Hoai An and Pham Dinh Tao (1995) Decomposition branch and bound method for globally solving linearly constrained indefinite quadratic minimization problems. Oper Res Lett 17(5):215鈥?20
  25. Rosen JB and Pardalos PM (1986). Global minimization of large scale constrained concave quadratic problems by separable programming. / Math Program 34: 163鈥?74 CrossRef
  26. Thoai NV (2005). General Quadratic Programming. In: Audet, C, Hansen, P and Savard, G (eds) Essays and survey in global optimization, pp 107鈥?29. Springer, Berlin, CrossRef
  27. Tuy H (1995). D.C. Optimization: theory, methods and algorithms. In: Horst, R and Pardalos, PM (eds) Handbook of global optimization, nonconvex optimization and its applications, vol 2, pp 149鈥?16. Kluwer, Dordrecht,
  28. Tuy H (1998). Convex analysis and global optimization, nonconvex optimization and its applications, vol 22. Kluwer, Dordrecht
  
• 作者单位：Riccardo Cambini (1)
  Claudio Sodini (1)
  
  1. Department of Statistics and Applied Mathematics, Faculty of Economics, University of Pisa, Via Cosimo Ridolfi 10, 56124, Pisa, Italy
  

文摘

The aim of this paper is to discuss different branch and bound methods for solving indefinite quadratic programs. In these methods the quadratic objective function is decomposed in a d.c. form and the relaxations are obtained by linearizing the concave part of the decomposition. In this light, various decomposition schemes have been considered and studied. The various branch and bound solution methods have been implemented and compared by means of a deep computational test.