Research ArticleOpen AccessGoogle Scholar indexed
An Efficient Random Algorithm for Box Constrained Weighted Maximin Dispersion Problem
Department of Mathematics, Shanghai University, Shanghai, China
- 1 Department of Mathematics, Shanghai University, Shanghai, China
Advances in Pure Mathematics·Volume 09 (2019)·Pages 330–336·Published 11 April 2019·DOI10.4236/apm.2019.94015
Copy link · social · email
Abstract
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 reformulate the max i min dispersion problem as a non-convex quadratically constrained quadratic programming (QCQP) problem. We adopt the successive convex approximation (SCA) algorithm to solve the problem. Numerical results show that the proposed algorithm is efficient.
KeywordsMaximin Dispersion ProblemSuccessive Convex Approximation AlgorithmQuadratically Constrained Quadratic Programming (QCQP)
- Wang, S. and Xia, Y. (2016) On the Ball-Consterained Weighted Maximin Dispersion Problem. SIAM Journal on Optimization, 26, 1565-1588.
- White, D.J. (1996) A Heuristic Approach to a Weighted Maxmin Disperation Problem. IMA Journal of Management Mathematics, 7, 219-231. https://doi.org/10.1093/imaman/7.3.219
- Ravi, S.S., Rosenkrantz, D.J. and Tayi, G.K. (1994) Heuristic and Special Case Algorithms for Dispersion Problems. Operations Research, 42, 299-310. https://doi.org/10.1287/opre.42.2.299
- Dasarthy, B. and White, L.J. (1980) A Maximin Location Problem. Operations Research, 28, 1385-1401. https://doi.org/10.1287/opre.28.6.1385
- Wu, Z.P., Xia, Y. and Wang, S. (2017) Approximating the Weighted Maximin Dispersion Problem over an l_p-ball: SDP Relaxation Is Misleading. Optimization Letters, 12, 875-883.
- Haines, S., Loeppky, J., Tseng, P. and Wang, X. (2013) Convex Relaxations of the Weighted Maxmin Dispersion Problem. SIAM Journal on Optimization, 23, 2264-2294. https://doi.org/10.1137/120888880
- Konar, A. and Sidiropoulos, N.D. (2017) Fast Approximation Algorithms for a Class of Nonconvex QCQP Problems Using First-Order Methods. IEEE Transactions on Signal Processing, 65, 3494-3509.
- Grant, M. and Boyd, S. (2010) CVX User’s Guide: For CVX Version 1.21. User’s Guide, 24-75.