Convex relaxations of the maximin dispersion problem

Recently, convex relaxations have achieved notable success in solving NP-hard optimization problems. This thesis studies semidefinite and second-order cone programming convex relaxations of the maximin dispersion problem. Providing nontrivial approximation bounds, we believe that our SDP and SOCP relaxation methods are useful in large-scale optimization. The thesis is organized as follows. We begin by recalling some basic concepts from convex analysis, nonsmooth analysis, and optimization. We then introduce the weighted maximin dispersion optimization problem; locating point(s) in a given region X ⊆ R^{n} that is/are furthest from a given set of m points. Also given are several reformulations of the original problem, including a convex relaxation problem and semidefinite and second order cone programming relaxations. Using well known results on Lipschitz functions and subdifferentials of Lipschitz functions we then derive a theoretical characterization of the optimal solutions for a given convex region X and equal weights. Next, we provide a proof that the weighted maximin dispersion problem is NP-hard even in the case where X is a box and the weights are equal. We then propose an algorithm for finding an approximate solution using the SDP relaxation, and derive an approximation bound that depends on the subset X. In the case that X is a box or a product of low-dimensional spheres, we show that the convex relaxation reduces to a second-order cone program, and provide further results on the bound provided. Lastly, we provide numerical examples using the SDP and SOCP relaxations, and suggest future work.Arts and Sciences, Irving K. Barber School of (Okanagan)Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)Graduat