## Discretization and Localization in Successive Convex Relaxation
Methods for Nonconvex Quadratic Optimization Problems

###
Masakazu Kojima and Levent Tuncel

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*, 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: kojima@is.titech.ac.jp