zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A primal-dual algorithm for the Fermat-Weber problem involving mixed gauges. (English) Zbl 0641.90034

Summary: We give a new algorithm for solving the Fermat-Weber location problem involving mixed gauges. This algorithm, which is derived from the partial inverse method developed by J. E. Spingarn [Appl. Math. Optimization 10, 247-265 (1983; Zbl 0524.90072)] simultaneously generates two sequences globally converging to a primal and a dual solution respectively. In addition, the updating formulae are very simple; a stopping rule can be defined though the method is not dual feasible and the entire set of optimal location can be obtained from the dual solution by making use of optimality conditions.

When polyhedral gauges are used, we show that the algorithm terminates in a finite number of steps, provided that the set of optimal locations has nonempty interior and a counterexample to finite termination is given in case where this property is violated.

Finally, numerical results are reported and we discuss possible extensions of these results.

MSC:
90B05Inventory, storage, reservoirs
90C90Applications of mathematical programming
65K05Mathematical programming (numerical methods)
References:
[1]R.D. Armstrong, ”A primal simplex algorithm to solve a rectilinear distance facility location problem,”Naval Research Logistics Quarterly 24 (1977) 619–626. · Zbl 0372.90080 · doi:10.1002/nav.3800240409
[2]L. Cooper and I.N. Katz, ”The Weber problem revisited,”Computers and Mathematics with Applications 7 (1981) 225–234. · Zbl 0457.65044 · doi:10.1016/0898-1221(81)90082-1
[3]P.H. Calamai and A.R. Conn, ”A stable algorithm for solving the multifacility location problem involving Euclidean distances,”SIAM Journal on Scientific and Statistical Computing 1 (1980) 512–526. · Zbl 0469.65040 · doi:10.1137/0901037
[4]P.H. Calamai and A.R. Conn, ”A second order method for solving the continuous multifacility location problem,” in: G.A. Watson, ed.,Numerical Analysis: Proceedings of the Ninth Biennial Conference. Dundee, Scotland, Lecture Notes in Mathematics 912 (Springer-Verlag, Berlin, Heidelberg and New York, 1982), pp. 1–25.
[5]F. Cordellier and J.C. Fiorot, ”On the Fermat-Weber problem with convex cost functions,”Mathematical Programming 14 (1978) 295–311. · Zbl 0374.90057 · doi:10.1007/BF01588972
[6]A. Dax, ”The use of Newton’s method for solving Euclidean multifacility location problems,” Tech. Report. Hydrological Service (Jerusalem, 1985).
[7]P.D. Dowling and R.F. Love, ”Bounding methods for facilities location algorithms,” Research and Working Paper Series No. 219, McMaster University (Hamilton, Ontario, 1984).
[8]P.D. Dowling and R.F. Love, ”An evaluation of the dual as a lower bound in facilities location problems,” Research and Working Paper Series No. 236, McMaster University (Hamilton, Ontario, 1985).
[9]R. Durier, ”On efficient points and Fermat-Weber problem,” Working Paper, Université de Bourgogne, (Dijon, France, 1984).
[10]R. Durier, ”Weighting factor results in vector optimization,” Working Paper, Université de Bourgogne (Dijon, France, 1984).
[11]R. Durier and C. Michelot, ”Geometrical properties of the Fermat-Weber problem,”European Journal of Operational Research 20 (1985) 332–343. · Zbl 0564.90013 · doi:10.1016/0377-2217(85)90006-2
[12]R. Durier and C. Michelot, ”Sets of efficient points in a normed space,”Journal of Mathematical Analysis and Applications 117 (1986), 506–528. · Zbl 0605.49020 · doi:10.1016/0022-247X(86)90237-4
[13]U. Eckhardt, ”Theorems on the dimension of convex sets,”Linear Algebra and its Applications 12 (1975) 63–76. · Zbl 0317.52004 · doi:10.1016/0024-3795(75)90127-5
[14]D.J. Elzinga and D.W. Hearn, ”On stopping rules for facilities location algorithms,”IIE Transactions 15 (1983) 81–83. · doi:10.1080/05695558308974616
[15]R.L. Francis and J.M. Goldstein, ”Location theory: A selective bibliography,”Operations Research 22 (1974) 400–410. · Zbl 0274.90028 · doi:10.1287/opre.22.2.400
[16]R.L. Francis and J.A. White,Facility Layout and Location: An Analytical Approach (Prentice-Hall, Englewood Cliffs, NJ, 1974).
[17]I.N. Katz, ”Local convergence in Fermat’s problem,”Mathematical Programming 6 (1974), 89–104. · Zbl 0291.90069 · doi:10.1007/BF01580224
[18]H.W. Kuhn, ”A note on Fermat’s problem,”Mathematical Programming 4 (1973) 98–107. · Zbl 0255.90063 · doi:10.1007/BF01584648
[19]H.W. Kuhn and R.E. Kuenne, ”An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics”,Journal of Regional Science 4 (1962) 21–23. · doi:10.1111/j.1467-9787.1962.tb00902.x
[20]R.F. Love and W.Y. Yeong, ”A stopping rule for facilities location algorithms,”AIIE Transactions 13 (1981) 357–362.
[21]L.M. Ostresch, ”On the convergence of a class of iterative methods for solving the Weber location problem,”Operations Research 26 (1978) 597–609. · Zbl 0396.90073 · doi:10.1287/opre.26.4.597
[22]L.M. Ostresh, ”Convergence and descent in the Fermat location problem,”Transportation Science 12 (1978) 153–164. · doi:10.1287/trsc.12.2.153
[23]M.L. Overton, ”A quadratically convergent method for minimizing a sum of Euclidean norms,”Mathematical Programming 27 (1983) 34–63. · Zbl 0536.65053 · doi:10.1007/BF02591963
[24]A. Planchart and A.P. Hurter, ”An efficient algorithm for the solution of Weber problem with mixed norms,”SIAM Journal on Control 13 (1975) 650–665. · Zbl 0297.90088 · doi:10.1137/0313036
[25]F. Plastria, ”Continuous location problems solved by cutting planes,” Working Paper, Vrije Universiteit brussels, (Bruxelles, 1982).
[26]R.T. RockafellarConvex Analysis, (Princeton University Press, Princeton, NJ, 1970).
[27]R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053 · doi:10.1137/0314056
[28]J.E. Spingarn, ”Partial inverse of a monotone operator,”Applied Mathematics and Optimization 10 (1983) 247–265. · Zbl 0524.90072 · doi:10.1007/BF01448388
[29]J.E. Spingarn, ”A primal-dual projection method for solving systems of linear inequalities,”Linear Algebra and its Applications 65 (1985) 45–62. · Zbl 0564.65044 · doi:10.1016/0024-3795(85)90086-2
[30]J.E. Ward and R.E. Wendell, ”Using block norms for location modeling,”Operations Research 33 (1985) 1074–1090. · Zbl 0582.90026 · doi:10.1287/opre.33.5.1074
[31]E. Weiszfeld, ”Sur le point pour lequel la somme des distances den points donnés est minimum,”The Tôhoku Mathematical Journal 43 (1937) 355–386.
[32]R.E. Wendell and E.L. Peterson, ”A dual approach for obtaining lower bounds to the Weber problem,”Journal of Regional Science 24 (1984) 219–228. · doi:10.1111/j.1467-9787.1984.tb01033.x
[33]C. Witzgall, ”Optimal location of a central facility: Mathematical models and Concepts,” National Bureau of Standards, Report 8388 (Washington, 1964).