caa a22 4500 475769449 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20001101xx s 000 0 eng 10.1007/PL00011394 doi (NATIONALLICENCE)springer-10.1007/PL00011394 Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization [Elektronische Daten] [Masakazu Kojima, Levent Tunçel] Abstract. : Based on the authors' previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, "discretization” and "localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:¶•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆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 ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Springer-Verlag Berlin Heidelberg, 2000 Key words: nonconvex quadratic optimization problem - semidefinite programming - linear matrix inequality - global optimization - SDP relaxation - semi-infinite LP relaxation - interior-point method nationallicence Kojima Masakazu Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan. e-mail: kojima@is.titech.ac.jp, JP aut Tunçel Levent Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada. e-mail: ltuncel@math.uwaterloo.ca, CA aut https://doi.org/10.1007/PL00011394 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/PL00011394 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kojima Masakazu Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152, Japan. e-mail: kojima@is.titech.ac.jp, JP aut NATIONALLICENCE 700 1- Tunçel Levent Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada. e-mail: ltuncel@math.uwaterloo.ca, CA aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer