Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems

1. Audet, C., Hansen, P., Jaumard, B. and Savard, G. (2000), A Branch and Cut Algorithm for Nonconvex Quadratically Constrained Quadratic Programming, Mathematical Programming 87, 131–152.

   Google Scholar 

2. Balas, E., Ceria, S. and Cornuejols, G. (1993), A Lift-and-Project Cutting Plane Algorithm for Mixed 0–1 Programs, Mathematical Programming 58, 295–323.

   Google Scholar 

3. Calamai, P.H. and Vicente, L.N. (1994), Generating Quadratic Bilevel Programming Problems, ACM Transactions on Mathematical Software 20, 103–122.

   Google Scholar 

4. Calamai, P.H., Vincente, L.N. and Judice, J.J. (1993), A New Technique for Generating Quadratic Programming Test Problems, Mathematical Programming 61, 215–231.

   Google Scholar 

5. Fujie, T. and Kojima, M. (1997), Semidefinite Relaxation for Nonconvex Programs, Journal of Global Optimization 10, 367–380.

   Google Scholar 

6. Fujisawa, K., Kojima, M. and Nakata, K. (1997), Exploiting Sparsity in Primal-Dual Interior-Point Methods for Semidefinite Programming, Mathematical Programming 79, 235–253.

   Google Scholar 

7. Fujisawa, K., Kojima, M. and Nakata, K. (1999), SDPA (Semidefinite Programming Algorithm), User's Manual, Technical Report B-308, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152–8552, Japan.

   Google Scholar 

8. Kojima, M. and Takeda, A. (2001), Complexity Analysis of Successive Convex Relaxation Methods for Nonconvex Sets, Mathematics of Operations Research 26, 519–542.

   Google Scholar 

9. Kojima, M. and Tunçel, L. (2000), Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets, SIAM Journal on Optimization 10, 750–778.

   Google Scholar 

10. Kojima, M. and Tunçel, L. (2000), Discretization and Localization in Successive Convex Relaxation Method for Nonconvex Quadratic Optimization Problems, Mathematical Programming 89, 79–111.

    Google Scholar 

11. Lovász, L. and Schrijver, A. (1991), Cones of Matrices and Set Functions and 0–1 Optimization, SIAM Journal on Optimization 1, 166–190.

    Google Scholar 

12. Horst, R. and Tuy, H. (1992), Global Optimization, Second, Revised Edition, Springer, Berlin.

    Google Scholar 

13. McCormick, G.P. (1976), Computability of Global Solutions to Factorable Nonconvex Programs: Part I-Convex Underestimating Problems, Mathematical Programming 10, 147–175.

    Google Scholar 

14. Nicholls, M.G. (1996), The Application of Non-Linear Bilevel Programming to the Aluminium Industry, Journal of Global Optimization 8, 245–261.

    Google Scholar 

15. Pardalos, P.M. and Rodgers, G. (1990), Computational Aspects of a Branch and Bound Algorithm for Quadratic 0–1 Programming, Computing 45, 131–144.

    Google Scholar 

16. Pardalos, P.M. and Vavasis, S.A. (1991), Quadratic Programming with One Negative Eigenvalue is NP-Hard, Journal of Global Optimization 1, 843–855.

    Google Scholar 

17. Ryoo, H.S. and Sahinidis, N.V. (1996), A Branch-and-Reduce Approach to Global Optimization, Journal of Global Optimization 8, 107–139.

    Google Scholar 

18. Sato, M., Nakada, H., Sekiguchi, S., Matsuoka, S., Nagashima, U. and Takagi, H. (1997), Ninf: A Network Based Information Library for a Global World-Wide Computing Infrastructure, in Sloot, P. and Hertzberger, B. (eds.), High-Performance Computing and Networking, Lecture Notes in Computing Science, Vol. 1225, Springer, Berlin.

    Google Scholar 

19. S. Sekiguchi, Sato, M., Nakada, H., Matsuoka, S. and Nagashima, U. (1996), Ninf: Network Based Information Library for Globally Performance Computing, in Proc. of Parallel Object-Oriented Methods and Applications (POOMA’ 96).

20. Sherali, H.D. and Adams, W.P. (1990), A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems, SIAM Journal on Discrete Mathematics 3, 411–430.

    Google Scholar 

21. Sherali, H.D. and Alameddine, A. (1992), A New Reformulation-Linearization Technique for Bilinear Programming Problems, Journal of Global Optimization 2, 379–410.

    Google Scholar 

22. Sherali, H.D. and Tuncbilek, C.H. (1995), A Reformulation-Convexification Approach for Solving Nonconvex Quadratic Programming Problems, Journal of Global Optimization 7, 1–31.

    Google Scholar 

23. Stubbs, R.A. and Mehrotra, S. (1997), A Branch-and-Cut Method for 0–1 Mixed Convex Programming, Technical Report 96–01, Dept. of IE/MS, Northwestern University, Evanston, IL 60208.

    Google Scholar 

24. Takeda, A., Dai, Y., Fukuda, M. and Kojima, M. (2000), Towards the Implementation of Successive Convex Relaxation Method for Nonconvex Quadratic Optimization Problems, in Pardalos, P.M. (ed.), Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Kluwer Academic Publishers, Dordrecht.

    Google Scholar 

25. Takeda, A. and Kojima, M. (2000), Successive Convex Relaxation Approach to Bilevel Quadratic Optimization Problems, in Ferris, M.C., Mangasarian, O.L. and Pang, J.S. (eds.), Applications and Algorithms of Complementarity, Kluwer Academic Publishers, Dordrecht.

    Google Scholar 

26. Vicente, L.N. and Calamai, P.H. (1994), Bilevel and Multilevel Programming: A Bibliography Review, Journal of Global Optimization 5, 291–306.

    Google Scholar 

27. Visweswaran, V., Floudas, C.A., Ierapetritou, M.G. and Pistikopoulos, E.N. (1996), A Decomposition-Based Global Optimization Approach for Solving Bilevel Linear and Quadratic Programs, in Floudas, C.A. and Pardalos, P.M. (eds.), State of the Art in Global Optimization, Kluwer Academic Publishers, Dordrecht.

    Google Scholar 

28. Voorhis, T.V. and Al-khayyal, F. (1996), Accelerating Convergence of Branch-and-Bound Algorithms for Quadrically Constrained Optimization Problems, in Floudas, C.A. and Pardalos, P.M. (1996), State of the Art in Global Optimization, Kluwer Academic Publishers, Dordrecht.

    Google Scholar 

Download references