Given any open convex set U containing F, an implementable discretization of the SSDP (or SSILP) Relaxation Method generates a compact convex set C such that F \subseteq C \subseteq U in a finite number of iterations.The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:
Given any positive number $\epsilon$, an implementable localization -discretization of the SSDP (or SSILP) Relaxation Method generates an upper bound of the objective values within $\epsilon$ of their maximum in a finite number of iterations.
Research Report B-341, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguoro, Tokyo 152, July, 1998. Also issued as COOR 98-34, Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
Contact: [email protected]