Abstract
As computing resources continue to improve, global solutions for larger size quadrically constrained optimization problems become more achievable. In this paper, we focus on larger size problems and get accurate bounds for optimal values of such problems with the successive use of SDP relaxations on a parallel computing system called Ninf (Network-based Information Library for high performance computing).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
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.
Calamai, P.H. and Vicente, L.N. (1994), Generating Quadratic Bilevel Programming Problems, ACM Transactions on Mathematical Software 20, 103–122.
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.
Fujie, T. and Kojima, M. (1997), Semidefinite Relaxation for Nonconvex Programs, Journal of Global Optimization 10, 367–380.
Fujisawa, K., Kojima, M. and Nakata, K. (1997), Exploiting Sparsity in Primal-Dual Interior-Point Methods for Semidefinite Programming, Mathematical Programming 79, 235–253.
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.
Kojima, M. and Takeda, A. (2001), Complexity Analysis of Successive Convex Relaxation Methods for Nonconvex Sets, Mathematics of Operations Research 26, 519–542.
Kojima, M. and Tunçel, L. (2000), Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets, SIAM Journal on Optimization 10, 750–778.
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.
Lovász, L. and Schrijver, A. (1991), Cones of Matrices and Set Functions and 0–1 Optimization, SIAM Journal on Optimization 1, 166–190.
Horst, R. and Tuy, H. (1992), Global Optimization, Second, Revised Edition, Springer, Berlin.
McCormick, G.P. (1976), Computability of Global Solutions to Factorable Nonconvex Programs: Part I-Convex Underestimating Problems, Mathematical Programming 10, 147–175.
Nicholls, M.G. (1996), The Application of Non-Linear Bilevel Programming to the Aluminium Industry, Journal of Global Optimization 8, 245–261.
Pardalos, P.M. and Rodgers, G. (1990), Computational Aspects of a Branch and Bound Algorithm for Quadratic 0–1 Programming, Computing 45, 131–144.
Pardalos, P.M. and Vavasis, S.A. (1991), Quadratic Programming with One Negative Eigenvalue is NP-Hard, Journal of Global Optimization 1, 843–855.
Ryoo, H.S. and Sahinidis, N.V. (1996), A Branch-and-Reduce Approach to Global Optimization, Journal of Global Optimization 8, 107–139.
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.
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).
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.
Sherali, H.D. and Alameddine, A. (1992), A New Reformulation-Linearization Technique for Bilinear Programming Problems, Journal of Global Optimization 2, 379–410.
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.
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.
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.
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.
Vicente, L.N. and Calamai, P.H. (1994), Bilevel and Multilevel Programming: A Bibliography Review, Journal of Global Optimization 5, 291–306.
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.
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.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Takeda, A., Fujisawa, K., Fukaya, Y. et al. Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems. Journal of Global Optimization 24, 237–260 (2002). https://doi.org/10.1023/A:1020299805773
Issue Date:
DOI: https://doi.org/10.1023/A:1020299805773