Complexity Analysis of Successive Convex Relaxation Methods for Nonconvex Sets

References

• Balas E., Ceria S., Cornuéjols G. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Programming (1993) 58:295–323Crossref, Google Scholar
• Kojima M., Tunçel L. Cones of matrices and successive convex relaxations of nonconvex sets. SIAM J. Optim. (2000a) 10:750–778Crossref, Google Scholar
• Kojima M. Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization problems. Math. Programming (2000b) 89:79–111Crossref, Google Scholar
• Kojima M., Matsumoto T., Shida M. Moderate nonconvexity = convexity + quadratic concavity. (1999) . Technical report B-348, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo, JapanGoogle Scholar
• Lovász L., Schrijver A. Cones of matrices and set functions and 0-1 optimization. SIAM J. Optim. (1991) 1:166–190Crossref, Google Scholar
• Horst R., Tuy H.Global Optimization, Second, Revised Edition (1992) (Springer-Verlag, Berlin. Germany) Google Scholar
• Sherali H. D., Adams W. P. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Disc. Math. (1990) 3:411–430Crossref, Google Scholar
• Sherali H. D., Adams H. D., Adams W. P. A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Disc. Appl. Math. (1994) 52:83–106Crossref, Google Scholar
• Sherali H. D., Almeddine. A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. (1992) 2:379–410Crossref, Google Scholar
• Sherali H. D., Tuncbilek C. H. A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Global Optim. (1992) 2:101–112Crossref, Google Scholar
• Sherali H. D. A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Global Optim. (1995) 7:1–31Crossref, Google Scholar
• Shor N. Z. Dual quadratic estimates in polynomial and boolean programming. Ann. Oper. Res. (1990) 25:163–168Crossref, Google Scholar
• Takeda A., Dai Y., Fukuda M., Kojima M., Pardalos P. M. Towards implementations of successive convex relaxation methods for nonconvex quadratic optimization problems. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems (2000) (Kluwer Academic Publishers)489–510Crossref, Google Scholar
• Tunçel L., Xu S. Complexity analyses of discretized successive convex relaxation methods. . CORR 99-37, Dept. of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, CanadaGoogle Scholar
• Tuy H.Convex analysis and Global Optimization (1998) (Kluwer, Dordrecht, The Netherlands) Crossref, Google Scholar