The box-constrained weighted maximin dispersion problem is to
find a point in an n-dimensional box such that the minimum of the weighted
Euclidean distance from given m points is maximized. In this paper, We
first rewrite the maximin dispersion problem as a eqivalent minimax problem. Then, we propose a two phase method to solve it. In the first phase,
we adopt a block successive upper-bound minimization algorithm framework
and choose a special piecewise linear upper bound function for the weighted
maximin dispersion problem. The periteration complexity of our algorithm is
very low, since the subproblem is a one dimensional piecewise linear minimax
problem over the box constraints, or eqivalently, a two dimensional linear programming problem which can be solved very efficiently by existing algorithms.
In the second phase, a useful rounding is employed to enhance the solution.
It can be proved that the proposed algorithm converges to a stationary point.
Numerical results show that the proposed algorithm is efficient.