Towards the Implementation of Successive Convex Relaxation Method for Nonconvex Quadratic Optimization Problems

Akiko Takeda, Yang Dai, Mituhiro Fukuda, and Masakazu Kojima

Recently Kojima and Tun\c{c}el proposed new successive convex relaxation methods and their localized-discretized variants for general nonconvex quadratic programs. Although an upper bound of the objective function value within {\sl a prior} precision can be found theoretically by solving a finite number of linear programs, several important implementation problems remain unsolved. In this paper we discuss these issues, present practically implementable algorithms and report numerical results.

Research Reports on Information Sciences, No. B-347, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, March 1999.