Abstract

We study a location problem that involves a weighted sum of distances to closed convex sets. As several of the weights might be negative, traditional solution methods of convex optimization are not applicable. After obtaining some existence theorems, we introduce a simple, but effective, algorithm for solving the problem. Our method is based on the Pham Dinh - Le Thi algorithm for d.c. programming and a generalized version of the Weiszfeld algorithm, which works well for convex location problems.

Author information

Contact details are reproduced from the original publication and may be historical.

Nguyen Thai An

Thua Thien Hue College of Education, 123 Nguyen Hue, Hue City, Vietnam

thaian2784@gmail.com

Nguyen Mau Nam

Fariborz Maseeh Dept. of Mathematics and Statistics, Portland State University, PO Box 751, Portland, OR 97207, U.S.A.

mau.nam.nguyen@pdx.edu

Nguyen Dong Yen

Institute of Mathematics, Vietnam Academy of Science and Technology, 18 Hoang Quoc Viet, Hanoi 10307, Vietnam

ndyen@math.ac.vn

Keywords

  • d.c. programming
  • nonconvex location problem
  • Pham Dinh - Le Thi algorithm
  • difference of convex functions
  • Weiszfeld algorithm

Mathematics Subject Classification

49J52, 49J53, 90C31

References

  1. J. Brimberg: The Fermat Weber location problem revisited, Math. Program. A71 (1995) 71–76.https://doi.org/10.1007/BF01592245Google Scholar
  2. J. Brimberg, R. Chen, D. Chen: Accelerating convergence in the Fermat-Weber location problem, Oper. Res. Lett. 22 (1998) 151–157.https://doi.org/10.1016/S0167-6377(98)00016-9Google Scholar
  3. P.-C. Chen, P. Hansen, B. Jaumard, H. Tuy: Weber’s problem with attraction and repulsion, J. Regional Sci. 32 (1992) 467–486.https://doi.org/10.1111/j.1467-9787.1992.tb00200.xGoogle Scholar
  4. E. Chi, H. Zhou, K. Lange: Distance majorization and its applications, Math. Program. A146(1–2) (2014) 409–436.https://doi.org/10.1007/s10107-013-0697-1Google Scholar
  5. F. H. Clarke: Optimization and Nonsmooth Analysis, SIAM, Philadelphia (1990).https://doi.org/10.1137/1.9781611971309Google Scholar
  6. L. Cooper, I. Katz: The Weber problem revisited, Comput. Math. Appl. 7 (1981) 225–234.https://doi.org/10.1016/0898-1221(81)90082-1Google Scholar
  7. Z. Drezner: On the convergence of the generalized Weiszfeld algorithm, Ann. Oper. Res. 167 (2009) 327–336.https://doi.org/10.1007/s10479-008-0336-zGoogle Scholar
  8. U. Eckhardt: Weber’s problem and Weiszfeld’s algorithm in general spaces, Math. Program. 18 (1980) 186–196.https://doi.org/10.1007/BF01588313Google Scholar
  9. A. D. Ioffe, V. M. Tihomirov: Theory of Extremal Problems, North-Holland, Amsterdam (1979).Google Scholar
  10. H. W. Kuhn: A note on Fermat-Torricelli problem, Math. Program. 4 (1973) 98–107.https://doi.org/10.1007/BF01584648Google Scholar
  11. H. A. Le Thi, M. T. Belghiti, T. Pham Dinh: A new efficient algorithm based on DC programming and DCA for clustering, J. Glob. Optim. 37 (2007) 583–608.https://doi.org/10.1007/s10898-006-9066-4Google Scholar
  12. J.-J. Moreau: Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci., Paris 255 (1962) 2897–2899.Google Scholar
  13. J.-J. Moreau: Fonctionnelles sous-différentiables, C. R. Acad. Sci., Paris 257 (1963) 4117–4119.Google Scholar
  14. J.-J. Moreau: Proximité dualité dans espace hilbertien, Bull. Soc. Math. France 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  15. B. S. Mordukhovich, N. M. Nam: Applications of variational analysis to a generalized Fermat-Torricelli problem, J. Optim. Theory Appl. 148 (2011) 431–454.https://doi.org/10.1007/s10957-010-9761-7Google Scholar
  16. B. S. Mordukhovich, N. M. Nam, J. Salinas: Applications of variational analysis to a generalized Heron problem, Appl. Anal. 91 (2012) 1915–1942.https://doi.org/10.1080/00036811.2011.604849Google Scholar
  17. B. S. Mordukhovich, N. M. Nam: An Easy Path to Convex Analysis and Applications, Morgan & Claypool, San Rafael (2014).https://doi.org/10.1007/978-3-031-02406-1Google Scholar
  18. J. G. Morris, W. A. Verdini: Minisum ℓp distance location problems solved via a perturbed problem and Weiszfeld’s algorithm, Oper. Res. 27 (1979) 1180–1188.https://doi.org/10.1287/opre.27.6.1180Google Scholar
  19. N. M. Nam, N. Hoang: A generalized Sylvester problem and a generalized Fermat-Torricelli problem, J. Convex Analysis 20 (2013) 669–687.https://doi.org/10.68381/jca20038Google Scholar
  20. T. Pham Dinh, H. A. Le Thi: Convex analysis approach to d.c. programming: theory, algorithms and applications, Acta Math. Vietnam. 22 (1997) 289–355.Google Scholar
  21. T. Pham Dinh, H. A. Le Thi: A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim. 8 (1998) 476–505.https://doi.org/10.1137/S1052623494274313Google Scholar
  22. F. Plastria: The Weiszfeld algorithm: proof, amendments and extensions, in: Foundations of Location Analysis, H. A. Eiselt, V. Marianov (eds.), Internat. Ser. Oper. Res. Management Sci. 155, Springer, New York (2011) 357–389.https://doi.org/10.1007/978-1-4419-7572-0_16Google Scholar
  23. R. T. Rockafellar: Convex Functions and Dual Extremum Problems, Ph.D. Thesis, Department of Mathematics, Harvard University, Cambridge (1963).Google Scholar
  24. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  25. A. Ruszczyński: Nonlinear Optimization, Princeton University Press, Princeton (2006).https://doi.org/10.1515/9781400841059Google Scholar
  26. H. Üster, R. F. Love: The convergence of the Weiszfeld algorithm, Comput. Math. Appl. 40 (2000) 443–451.https://doi.org/10.1016/S0898-1221(00)00172-3Google Scholar
  27. Y. Vardi, C.-H. Zhang: A modified Weiszfeld algorithm for the Fermat-Weber location problem, Math. Program. A90 (2001) 559–566.https://doi.org/10.1007/PL00011435Google Scholar
  28. E. Weiszfeld: Sur le point pour lequel la somme des distances de n points donnés est minimum, Tôhoku Math. J. 43 (1937) 355–386.Google Scholar
  29. E. Weiszfeld, F. Plastria: On the point for which the sum of the distances to n given points is minimum, Ann. Oper. Res. 167 (2009) 7–41.https://doi.org/10.1007/s10479-008-0352-zGoogle Scholar
  30. C. Witzgall: Optimal location of a central facility: mathematical models and concepts, Technical Report 8388, National Bureau of Standards, Washington (1984).Google Scholar

Suggested citation

N. T. An, N. M. Nam, N. D. Yen. “A D.C. Algorithm via Convex Analysis Approach for Solving a Location Problem Involving Sets.” Journal of Convex Analysis 23 (2016), No. 1, 77–101. https://doi.org/10.68381/jca23004

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2016. Rights now held by Banach Press LLC.