Computing the halfspace depth with multiple try algorithm and simulated annealing algorithm

The halfspace depth is a powerful tool for the nonparametric multivariate analysis. However, its computation is very challenging for it involves the infimum over infinitely many directional vectors. The exact computation of the halfspace depth is a NP-hard problem if both sample size n and dimension d are parts of input. The approximate algorithms often can not get accurate (exact) results in high dimensional cases within limited time. In this paper, we propose a new general stochastic optimization algorithm, which is the combination of simulated annealing and the multiple try Metropolis algorithm. As a by product of the new algorithm, it is then successfully applied to the computation of the halfspace depth of data sets which are not necessarily in general position. The simulation and real data examples indicate that the new algorithm is highly competitive to, especially in the high dimension and large sample cases, other (exact and approximate) algorithms, including the simulated annealing and the quasi-Newton method and so on, both in accuracy and efficiency.