Research ArticleOpen AccessGoogle Scholar indexed
An Efficient Proximal Point Algorithm for Unweighted Max-Min Dispersion Problem*
Department of Mathematics, College of Sciences, Shanghai University, Shanghai, China
- 1 Department of Mathematics, College of Sciences, Shanghai University, Shanghai, China
Advances in Pure Mathematics·Volume 08 (2018)·Pages 400–407·Published 17 April 2018·DOI10.4236/apm.2018.84022
Copy link · social · email
Abstract
In this paper, we first reformulate the max-min dispersion problem as a saddle-point problem. Specifically, we introduce an auxiliary problem whose optimum value gives an upper bound on that of the original problem. Then we propose the saddle-point problem to be solved by an adaptive custom proximal point algorithm. Numerical results show that the proposed algorithm is efficient.
KeywordsMaximum Weighted Dispersion ProblemAdaptive Custom Proximal Point Al-gorithmNP-Hard
- 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
- Johbson, M.E., Moore, L.M. and Ylvisaker, D. (1990) Maximin Distance Designs. Journal of Statistical Planning and Inference, 26, 131-148. https://doi.org/10.1016/0378-3758(90)90122-B
- Schaback, R. (1995) Multivariate Interpolation and Approximation by Translates of A Basis Function. World Scientific, Singapore, 491-514.
- 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
- 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
- Wang, S. and Xia, Y. (2016) On the Ball-Constrained Weighted Maximin Dispersion Problem. SIAM Journal on Optimization, 26, 1565-1588. https://doi.org/10.1137/15M1047167
- 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
- He, B. and Yuan, X. (2010) A Contraction Method with Implementable Proximal Regularization for Linearly Constrained Convex Programming. Optimization Online, 1-14.
- He, B., Fu, X. and Jiang, Z. (2009) A Proximal Point Algorithm Using a Linear Proximal Term. Journal of Optimization Theory and Applications, 141, 209-239. https://doi.org/10.1007/s10957-008-9493-0
- Martinet, B. (1970) Regularisation dinequations variationelles par approximations succesives. Rev. Francaise dInform. Recherche Operation, 4, 154-159.