-
Previous Article
Portfolio procurement policies for budget-constrained supply chains with option contracts and external financing
- JIMO Home
- This Issue
-
Next Article
Optimal risk control and dividend strategies in the presence of two reinsurers: Variance premium principle
A variational inequality approach for constrained multifacility Weber problem under gauge
1. | Department of Mathematics, College of Science, Nanjing University of Aeronautics and Astronautics, 29 Yudao Street, Qinhuai District, Nanjing 210016, China |
2. | Department of Financial Management, Business School, Nankai University, 94 Weijin Road, Nankai District, Tianjin 300071, China |
The classical multifacility Weber problem (MFWP) is one of the most important models in facility location. This paper considers more general and practical case of MFWP called constrained multifacility Weber problem (CMFWP), in which the gauge is used to measure distances and locational constraints are imposed to facilities. In particular, we develop a variational inequality approach for solving it. The CMFWP is reformulated into a linear variational inequality, whose special structures lead to new projection-type methods. Global convergence of the projection-type methods is proved under mild assumptions. Some preliminary numerical results are reported which verify the effectiveness of proposed methods.
References:
[1] |
R. S. Burachik and A. N. Iusem,
A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM J. Optim., 8 (1998), 197-216.
doi: 10.1137/S1052623495286302. |
[2] |
E. Carrizosa, E. Conde, M. Munõz and J. Puerto,
Simpson points in planar problems with locational constraints -the polyhedral gauge case, Math. Oper. Res., 22 (1997), 297-300.
doi: 10.1287/moor.22.2.291. |
[3] |
M. Cera, J. A. Mesa, F. A. Ortega and F. Plastria,
Locating a central hunter on the plane, J. Optim. Theory Appl., 136 (2008), 155-166.
doi: 10.1007/s10957-007-9293-y. |
[4] |
F. Daneshzand and R. Shoeleh, Multifacility location problem, in Facility Location: Concepts, Models, Algorithms and Case Studies, R.Z. Farahani and M. Hekmatfar (eds.), Springer, Berlin, (2009), 69-92. Google Scholar |
[5] |
Z. Drezner,
Facility Location: A Survey of Applications and Methods, Springer, New York, 1995.
doi: 10.1007/978-1-4612-5355-6. |
[6] |
Z. Drezner and H. W. Hamacher,
Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002.
doi: 10.1007/978-3-642-56082-8. |
[7] |
R. Durier,
On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47 (1990), 65-79.
doi: 10.1007/BF01580853. |
[8] |
B. C. Eaves,
On the basic theorem of complememtarity, Math. Program., 1 (1971), 68-75.
doi: 10.1007/BF01584073. |
[9] |
J. W. Eyster, J. A. White and W. W. Wierwille,
On solving multifacility location problems using a hyperboloid approximation procedure, AIIE Trans., 5 (1973), 275-280.
doi: 10.1080/05695557308974912. |
[10] |
F. Facchinei and J. S. Pang,
Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. |
[11] |
M. C. Ferris and C. Kanzow,
Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[12] |
B. S. He,
A new method for a class of linear variational inequalities, Math. Program., 66 (1994), 137-144.
doi: 10.1007/BF01581141. |
[13] |
B. S. He,
A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63.
|
[14] |
B. S. He, X. M. Yuan and W. X. Zhang,
A customized proximal point algorithm for convex minimization with linear constraints, Comput. Optim. Appl., 56 (2013), 559-572.
doi: 10.1007/s10589-013-9564-5. |
[15] |
I. N. Katz and S. R. Vogl,
A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem, Comput. Math. Appl., 59 (2010), 399-410.
doi: 10.1016/j.camwa.2009.07.007. |
[16] |
R. F. Love and J. G. Morris,
Mathematical models of road travel distances, Manag. Sci., 25 (1979), 130-139.
doi: 10.1287/mnsc.25.2.130. |
[17] |
R. F. Love and J. G. Morris,
On estimating road distances by mathematical functions, Euro. J. Oper. Res., 36 (1988), 251-253.
doi: 10.1016/0377-2217(88)90431-6. |
[18] |
R. F. Love, J. G. Morris and G. O. Wesolowsky,
Facilities Location: Models and Methods, North-Holland, Amsterdam, 1988. |
[19] |
B. Martinet,
Regularision d'inéquations variationnelles par approximations successive, Revue Francaise d'Automatique et Informatique Recherche Opérationnelle, 4 (1970), 154-158.
|
[20] |
W. Miehle,
Link length minimization in networks, Oper. Res., 6 (1958), 232-243.
doi: 10.1287/opre.6.2.232. |
[21] |
H. Minkowski, Theorie der konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911. Google Scholar |
[22] |
S. Nickel,
Restricted center problems under polyhedral gauges, Euro. J. Oper. Res., 104 (1998), 343-357.
doi: 10.1016/S0377-2217(97)00189-6. |
[23] |
L. M. Ostresh,
The multifacility location problem: Applications and descent theorems, J. Regional Sci., 17 (1977), 409-419.
doi: 10.1111/j.1467-9787.1977.tb00511.x. |
[24] |
F. Plastria,
Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, Ann. Oper. Res., 167 (2009), 121-155.
doi: 10.1007/s10479-008-0351-0. |
[25] |
F. Plastria,
The Weiszfeld algorithm: proof, amendments, and extensions, in Foundations of Location Analysis, H.A. Eiselt and V. Marianov (eds.), Springer, US, 155 (2011), 357-389.
doi: 10.1007/978-1-4419-7572-0_16. |
[26] |
J. B. Rosen and G. L. Xue,
On the convergence of Miehle's algorithm for the Euclidean multifacility location problem, Oper. Res., 40 (1992), 188-191.
doi: 10.1287/opre.40.1.188. |
[27] |
J. B. Rosen and G. L. Xue,
On the convergence of a hyperboloid approximation procedure for the perturbed Euclidean multifacility location problem, Oper. Res., 41 (1993), 1164-1171.
doi: 10.1287/opre.41.6.1164. |
[28] |
M. V. Solodov and P. Tseng,
Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 34 (1996), 1814-1830.
doi: 10.1137/S0363012994268655. |
[29] |
H. Uzawa, Iterative methods for concave programming, in Studies in Linear and Nonlinear Programming, K.J. Arrow, L. Hurwicz and H. Uzawa (eds.), Stanford University Press, Stanford, (1958), 154-165. Google Scholar |
[30] |
J. E. Ward and R. E. Wendell, A new norm for measuring distance which yields linear location problems, Oper. Res., 28 (1980), 836-844. Google Scholar |
[31] |
J. E. Ward and R. E. Wendell,
Using block norms for location modelling, Oper. Res., 33 (1985), 1074-1090.
doi: 10.1287/opre.33.5.1074. |
[32] |
E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tohoku Math. J., 43 (1937), 355-386. Google Scholar |
[33] |
C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964. Google Scholar |
show all references
References:
[1] |
R. S. Burachik and A. N. Iusem,
A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM J. Optim., 8 (1998), 197-216.
doi: 10.1137/S1052623495286302. |
[2] |
E. Carrizosa, E. Conde, M. Munõz and J. Puerto,
Simpson points in planar problems with locational constraints -the polyhedral gauge case, Math. Oper. Res., 22 (1997), 297-300.
doi: 10.1287/moor.22.2.291. |
[3] |
M. Cera, J. A. Mesa, F. A. Ortega and F. Plastria,
Locating a central hunter on the plane, J. Optim. Theory Appl., 136 (2008), 155-166.
doi: 10.1007/s10957-007-9293-y. |
[4] |
F. Daneshzand and R. Shoeleh, Multifacility location problem, in Facility Location: Concepts, Models, Algorithms and Case Studies, R.Z. Farahani and M. Hekmatfar (eds.), Springer, Berlin, (2009), 69-92. Google Scholar |
[5] |
Z. Drezner,
Facility Location: A Survey of Applications and Methods, Springer, New York, 1995.
doi: 10.1007/978-1-4612-5355-6. |
[6] |
Z. Drezner and H. W. Hamacher,
Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002.
doi: 10.1007/978-3-642-56082-8. |
[7] |
R. Durier,
On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47 (1990), 65-79.
doi: 10.1007/BF01580853. |
[8] |
B. C. Eaves,
On the basic theorem of complememtarity, Math. Program., 1 (1971), 68-75.
doi: 10.1007/BF01584073. |
[9] |
J. W. Eyster, J. A. White and W. W. Wierwille,
On solving multifacility location problems using a hyperboloid approximation procedure, AIIE Trans., 5 (1973), 275-280.
doi: 10.1080/05695557308974912. |
[10] |
F. Facchinei and J. S. Pang,
Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. |
[11] |
M. C. Ferris and C. Kanzow,
Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[12] |
B. S. He,
A new method for a class of linear variational inequalities, Math. Program., 66 (1994), 137-144.
doi: 10.1007/BF01581141. |
[13] |
B. S. He,
A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63.
|
[14] |
B. S. He, X. M. Yuan and W. X. Zhang,
A customized proximal point algorithm for convex minimization with linear constraints, Comput. Optim. Appl., 56 (2013), 559-572.
doi: 10.1007/s10589-013-9564-5. |
[15] |
I. N. Katz and S. R. Vogl,
A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem, Comput. Math. Appl., 59 (2010), 399-410.
doi: 10.1016/j.camwa.2009.07.007. |
[16] |
R. F. Love and J. G. Morris,
Mathematical models of road travel distances, Manag. Sci., 25 (1979), 130-139.
doi: 10.1287/mnsc.25.2.130. |
[17] |
R. F. Love and J. G. Morris,
On estimating road distances by mathematical functions, Euro. J. Oper. Res., 36 (1988), 251-253.
doi: 10.1016/0377-2217(88)90431-6. |
[18] |
R. F. Love, J. G. Morris and G. O. Wesolowsky,
Facilities Location: Models and Methods, North-Holland, Amsterdam, 1988. |
[19] |
B. Martinet,
Regularision d'inéquations variationnelles par approximations successive, Revue Francaise d'Automatique et Informatique Recherche Opérationnelle, 4 (1970), 154-158.
|
[20] |
W. Miehle,
Link length minimization in networks, Oper. Res., 6 (1958), 232-243.
doi: 10.1287/opre.6.2.232. |
[21] |
H. Minkowski, Theorie der konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911. Google Scholar |
[22] |
S. Nickel,
Restricted center problems under polyhedral gauges, Euro. J. Oper. Res., 104 (1998), 343-357.
doi: 10.1016/S0377-2217(97)00189-6. |
[23] |
L. M. Ostresh,
The multifacility location problem: Applications and descent theorems, J. Regional Sci., 17 (1977), 409-419.
doi: 10.1111/j.1467-9787.1977.tb00511.x. |
[24] |
F. Plastria,
Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, Ann. Oper. Res., 167 (2009), 121-155.
doi: 10.1007/s10479-008-0351-0. |
[25] |
F. Plastria,
The Weiszfeld algorithm: proof, amendments, and extensions, in Foundations of Location Analysis, H.A. Eiselt and V. Marianov (eds.), Springer, US, 155 (2011), 357-389.
doi: 10.1007/978-1-4419-7572-0_16. |
[26] |
J. B. Rosen and G. L. Xue,
On the convergence of Miehle's algorithm for the Euclidean multifacility location problem, Oper. Res., 40 (1992), 188-191.
doi: 10.1287/opre.40.1.188. |
[27] |
J. B. Rosen and G. L. Xue,
On the convergence of a hyperboloid approximation procedure for the perturbed Euclidean multifacility location problem, Oper. Res., 41 (1993), 1164-1171.
doi: 10.1287/opre.41.6.1164. |
[28] |
M. V. Solodov and P. Tseng,
Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 34 (1996), 1814-1830.
doi: 10.1137/S0363012994268655. |
[29] |
H. Uzawa, Iterative methods for concave programming, in Studies in Linear and Nonlinear Programming, K.J. Arrow, L. Hurwicz and H. Uzawa (eds.), Stanford University Press, Stanford, (1958), 154-165. Google Scholar |
[30] |
J. E. Ward and R. E. Wendell, A new norm for measuring distance which yields linear location problems, Oper. Res., 28 (1980), 836-844. Google Scholar |
[31] |
J. E. Ward and R. E. Wendell,
Using block norms for location modelling, Oper. Res., 33 (1985), 1074-1090.
doi: 10.1287/opre.33.5.1074. |
[32] |
E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tohoku Math. J., 43 (1937), 355-386. Google Scholar |
[33] |
C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964. Google Scholar |
Problem | MA | GMA | Algorithm 1 | Algorithm 2 | |
E1 | CPU | 0.0003 | 0.0004 | 0.0147 | 0.0143 |
Iter. | 2 | 9 | 152.44 | 157.52 | |
Obj. | 182.23 | 182.43 | 181.42 | 181.42 | |
E2 | CPU | 0.0109 | 0.0006 | 0.0149 | 0.0144 |
Iter. | 206 | 5 | 158.58 | 159.96 | |
Obj. | 182.19 | 182.68 | 181.42 | 181.42 | |
E1' | CPU | / | / | 0.0145 | 0.0138 |
Iter. | / | / | 154.32 | 156.04 | |
Obj. | / | / | 181.42 | 181.42 | |
E2' | CPU | / | / | 0.0147 | 0.0141 |
Iter. | / | / | 158.84 | 161.82 | |
Obj. | / | / | 181.42 | 181.42 | |
E3 | CPU | 0.1949 | 0.0050 | 0.0206 | 0.0207 |
Iter. | 3733.40 | 85.86 | 195.76 | 197.14 | |
Obj. | 63737.39 | 65188.08 | 63515.97 | 63515.97 |
Problem | MA | GMA | Algorithm 1 | Algorithm 2 | |
E1 | CPU | 0.0003 | 0.0004 | 0.0147 | 0.0143 |
Iter. | 2 | 9 | 152.44 | 157.52 | |
Obj. | 182.23 | 182.43 | 181.42 | 181.42 | |
E2 | CPU | 0.0109 | 0.0006 | 0.0149 | 0.0144 |
Iter. | 206 | 5 | 158.58 | 159.96 | |
Obj. | 182.19 | 182.68 | 181.42 | 181.42 | |
E1' | CPU | / | / | 0.0145 | 0.0138 |
Iter. | / | / | 154.32 | 156.04 | |
Obj. | / | / | 181.42 | 181.42 | |
E2' | CPU | / | / | 0.0147 | 0.0141 |
Iter. | / | / | 158.84 | 161.82 | |
Obj. | / | / | 181.42 | 181.42 | |
E3 | CPU | 0.1949 | 0.0050 | 0.0206 | 0.0207 |
Iter. | 3733.40 | 85.86 | 195.76 | 197.14 | |
Obj. | 63737.39 | 65188.08 | 63515.97 | 63515.97 |
m | HAP | GHAP | SHAP | SGHAP | Algo. 1 | Algo. 2 | |||||||
ε=50 | ε=5 | ε=0.5 | ε=0.05 | ε=50 | s=5 | ε=0.5 | ε=0.05 | ||||||
2 | CPU | 0.21 | 0.44 | 1.08 | 2.75 | 0.15 | 0.27 | 0.60 | 1.53 | 0.87 | 0.80 | 1.38 | 1.32 |
Iter. | 48.52 | 101.78 | 247.60 | 630.34 | 33.88 | 61.28 | 138.00 | 348.72 | 262.84 | 243.48 | 272.78 | 272.84 | |
Dobj. | 82.2151 | 28.6441 | 9.0927 | 2.6080 | 82.2156 | 28.6446 | 9.0932 | 2.6083 | 2.6082 | 2.6052 | 0.0000 | 0.0002 | |
4 | CPU | 0.98 | 2.48 | 6.60 | 17.89 | 0.58 | 1.33 | 3.45 | 9.26 | 2.61 | 2.33 | 2.15 | 2.08 |
Iter. | 107.70 | 270.20 | 720.00 | 1936.20 | 63.50 | 145.90 | 376.10 | 1003.40 | 378.30 | 337.80 | 168.90 | 168.90 | |
Dobj. | 283.4897 | 94.6138 | 30.0266 | 9.0773 | 283.4903 | 94.6144 | 30.0271 | 9.0767 | 9.0713 | 9.0701 | 0.0000 | 0.0005 | |
6 | CPU | 2.26 | 5.95 | 16.08 | 43.94 | 1.28 | 3.17 | 8.52 | 23.22 | 5.71 | 4.00 | 2.82 | 2.73 |
Iter. | 164.36 | 431.30 | 1167.66 | 3145.08 | 92.64 | 230.90 | 616.96 | 1664.60 | 541.94 | 382.48 | 126.82 | 126.84 | |
Dobj. | 475.4137 | 155.9050 | 49.3255 | 15.0577 | 475.4124 | 155.9035 | 49.3238 | 15.0528 | 15.0468 | 15.0480 | 0.0000 | -0.0003 | |
8 | CPU | 3.80 | 10.14 | 27.60 | 74.81 | 2.11 | 5.44 | 14.72 | 39.90 | 8.44 | 5.98 | 3.20 | 3.12 |
Iter. | 216.50 | 578.56 | 1573.84 | 4245.06 | 119.98 | 309.62 | 836.70 | 2262.78 | 638.06 | 453.98 | 101.70 | 101.74 | |
Dobj. | 698.8811 | 227.5549 | 72.0128 | 22.1839 | 698.8829 | 227.5570 | 72.0143 | 22.1790 | 22.1858 | 22.1714 | 0.0000 | 0.0021 | |
10 | CPU | 6.08 | 16.40 | 44.55 | 120.77 | 3.34 | 8.77 | 23.73 | 64.28 | 14.02 | 9.34 | 4.27 | 4.14 |
Iter. | 274.60 | 740.54 | 2012.20 | 5414.64 | 150.90 | 396.42 | 1072.20 | 2899.56 | 840.34 | 563.34 | 97.68 | 97.80 | |
Dobj. | 925.6176 | 299.2628 | 94.3543 | 28.8958 | 925.6183 | 299.2637 | 94.3537 | 28.8839 | 28.8930 | 28.8793 | 0.0000 | -0.0123 |
m | HAP | GHAP | SHAP | SGHAP | Algo. 1 | Algo. 2 | |||||||
ε=50 | ε=5 | ε=0.5 | ε=0.05 | ε=50 | s=5 | ε=0.5 | ε=0.05 | ||||||
2 | CPU | 0.21 | 0.44 | 1.08 | 2.75 | 0.15 | 0.27 | 0.60 | 1.53 | 0.87 | 0.80 | 1.38 | 1.32 |
Iter. | 48.52 | 101.78 | 247.60 | 630.34 | 33.88 | 61.28 | 138.00 | 348.72 | 262.84 | 243.48 | 272.78 | 272.84 | |
Dobj. | 82.2151 | 28.6441 | 9.0927 | 2.6080 | 82.2156 | 28.6446 | 9.0932 | 2.6083 | 2.6082 | 2.6052 | 0.0000 | 0.0002 | |
4 | CPU | 0.98 | 2.48 | 6.60 | 17.89 | 0.58 | 1.33 | 3.45 | 9.26 | 2.61 | 2.33 | 2.15 | 2.08 |
Iter. | 107.70 | 270.20 | 720.00 | 1936.20 | 63.50 | 145.90 | 376.10 | 1003.40 | 378.30 | 337.80 | 168.90 | 168.90 | |
Dobj. | 283.4897 | 94.6138 | 30.0266 | 9.0773 | 283.4903 | 94.6144 | 30.0271 | 9.0767 | 9.0713 | 9.0701 | 0.0000 | 0.0005 | |
6 | CPU | 2.26 | 5.95 | 16.08 | 43.94 | 1.28 | 3.17 | 8.52 | 23.22 | 5.71 | 4.00 | 2.82 | 2.73 |
Iter. | 164.36 | 431.30 | 1167.66 | 3145.08 | 92.64 | 230.90 | 616.96 | 1664.60 | 541.94 | 382.48 | 126.82 | 126.84 | |
Dobj. | 475.4137 | 155.9050 | 49.3255 | 15.0577 | 475.4124 | 155.9035 | 49.3238 | 15.0528 | 15.0468 | 15.0480 | 0.0000 | -0.0003 | |
8 | CPU | 3.80 | 10.14 | 27.60 | 74.81 | 2.11 | 5.44 | 14.72 | 39.90 | 8.44 | 5.98 | 3.20 | 3.12 |
Iter. | 216.50 | 578.56 | 1573.84 | 4245.06 | 119.98 | 309.62 | 836.70 | 2262.78 | 638.06 | 453.98 | 101.70 | 101.74 | |
Dobj. | 698.8811 | 227.5549 | 72.0128 | 22.1839 | 698.8829 | 227.5570 | 72.0143 | 22.1790 | 22.1858 | 22.1714 | 0.0000 | 0.0021 | |
10 | CPU | 6.08 | 16.40 | 44.55 | 120.77 | 3.34 | 8.77 | 23.73 | 64.28 | 14.02 | 9.34 | 4.27 | 4.14 |
Iter. | 274.60 | 740.54 | 2012.20 | 5414.64 | 150.90 | 396.42 | 1072.20 | 2899.56 | 840.34 | 563.34 | 97.68 | 97.80 | |
Dobj. | 925.6176 | 299.2628 | 94.3543 | 28.8958 | 925.6183 | 299.2637 | 94.3537 | 28.8839 | 28.8930 | 28.8793 | 0.0000 | -0.0123 |
n | m | PC method | PPA1 | PPA2 | Algorithm 1 | Algorithm 2 | |||||
CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | ||
50 | 2 | 0.034 | 34.45 | 0.018 | 31.32 | 0.018 | 32.93 | 0.018 | 29.84 | 0.015 | 30.34 |
4 | 0.093 | 40.32 | 0.044 | 36.60 | 0.046 | 37.78 | 0.044 | 36.39 | 0.043 | 37.11 | |
6 | 0.197 | 45.92 | 0.071 | 39.23 | 0.072 | 40.92 | 0.068 | 37.82 | 0.063 | 38.08 | |
8 | 0.314 | 49.93 | 0.096 | 41.63 | 0.100 | 43.87 | 0.093 | 41.91 | 0.090 | 41.76 | |
10 | 0.499 | 53.08 | 0.141 | 47.04 | 0.151 | 49.52 | 0.141 | 45.92 | 0.137 | 45.72 | |
100 | 2 | 0.036 | 17.27 | 0.027 | 25.87 | 0.028 | 27.21 | 0.024 | 22.44 | 0.022 | 22.65 |
4 | 0.135 | 24.74 | 0.063 | 31.24 | 0.065 | 32.14 | 0.057 | 27.51 | 0.054 | 28.48 | |
6 | 0.277 | 26.42 | 0.099 | 33.51 | 0.113 | 35.02 | 0.097 | 31.42 | 0.098 | 31.99 | |
8 | 0.570 | 29.63 | 0.154 | 35.44 | 0.169 | 38.68 | 0.147 | 34.51 | 0.147 | 34.82 | |
10 | 0.830 | 30.46 | 0.221 | 38.73 | 0.238 | 40.56 | 0.221 | 37.22 | 0.219 | 37.81 | |
200 | 2 | 0.098 | 19.98 | 0.054 | 26.81 | 0.059 | 29.40 | 0.051 | 26.68 | 0.052 | 27.49 |
4 | 0.370 | 22.05 | 0.121 | 28.88 | 0.126 | 30.43 | 0.116 | 28.23 | 0.111 | 28.13 | |
6 | 0.825 | 23.80 | 0.216 | 33.26 | 0.243 | 37.04 | 0.208 | 31.44 | 0.202 | 31.59 | |
8 | 1.574 | 24.02 | 0.333 | 35.37 | 0.344 | 36.59 | 0.299 | 31.36 | 0.293 | 32.24 | |
10 | 2.391 | 25.59 | 0.523 | 40.48 | 0.557 | 42.38 | 0.500 | 37.77 | 0.489 | 38.27 | |
500 | 2 | 0.241 | 9.62 | 0.150 | 25.82 | 0.156 | 27.45 | 0.121 | 21.26 | 0.118 | 21.82 |
4 | 1.131 | 11.73 | 0.490 | 37.29 | 0.505 | 38.14 | 0.388 | 29.03 | 0.371 | 28.75 | |
6 | 3.335 | 16.14 | 0.884 | 38.74 | 0.993 | 42.53 | 0.770 | 32.16 | 0.727 | 32.02 | |
8 | 6.072 | 17.01 | 1.281 | 39.89 | 1.358 | 41.56 | 1.057 | 33.45 | 1.006 | 33.16 | |
10 | 9.968 | 18.62 | 2.138 | 48.18 | 2.266 | 50.49 | 1.653 | 36.62 | 1.646 | 37.34 | |
1000 | 2 | 0.716 | 7.78 | 0.386 | 28.34 | 0.414 | 29.86 | 0.321 | 22.47 | 0.320 | 23.51 |
4 | 3.306 | 9.75 | 1.443 | 45.45 | 1.484 | 45.77 | 1.214 | 37.59 | 1.231 | 38.65 | |
6 | 8.109 | 10.88 | 2.879 | 49.66 | 3.036 | 51.44 | 2.108 | 35.86 | 2.132 | 36.42 | |
8 | 20.743 | 13.95 | 4.956 | 55.43 | 5.132 | 56.06 | 3.942 | 42.44 | 3.642 | 40.38 | |
10 | 37.590 | 17.52 | 7.712 | 59.15 | 7.941 | 59.95 | 5.819 | 43.43 | 5.893 | 45.85 |
n | m | PC method | PPA1 | PPA2 | Algorithm 1 | Algorithm 2 | |||||
CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | ||
50 | 2 | 0.034 | 34.45 | 0.018 | 31.32 | 0.018 | 32.93 | 0.018 | 29.84 | 0.015 | 30.34 |
4 | 0.093 | 40.32 | 0.044 | 36.60 | 0.046 | 37.78 | 0.044 | 36.39 | 0.043 | 37.11 | |
6 | 0.197 | 45.92 | 0.071 | 39.23 | 0.072 | 40.92 | 0.068 | 37.82 | 0.063 | 38.08 | |
8 | 0.314 | 49.93 | 0.096 | 41.63 | 0.100 | 43.87 | 0.093 | 41.91 | 0.090 | 41.76 | |
10 | 0.499 | 53.08 | 0.141 | 47.04 | 0.151 | 49.52 | 0.141 | 45.92 | 0.137 | 45.72 | |
100 | 2 | 0.036 | 17.27 | 0.027 | 25.87 | 0.028 | 27.21 | 0.024 | 22.44 | 0.022 | 22.65 |
4 | 0.135 | 24.74 | 0.063 | 31.24 | 0.065 | 32.14 | 0.057 | 27.51 | 0.054 | 28.48 | |
6 | 0.277 | 26.42 | 0.099 | 33.51 | 0.113 | 35.02 | 0.097 | 31.42 | 0.098 | 31.99 | |
8 | 0.570 | 29.63 | 0.154 | 35.44 | 0.169 | 38.68 | 0.147 | 34.51 | 0.147 | 34.82 | |
10 | 0.830 | 30.46 | 0.221 | 38.73 | 0.238 | 40.56 | 0.221 | 37.22 | 0.219 | 37.81 | |
200 | 2 | 0.098 | 19.98 | 0.054 | 26.81 | 0.059 | 29.40 | 0.051 | 26.68 | 0.052 | 27.49 |
4 | 0.370 | 22.05 | 0.121 | 28.88 | 0.126 | 30.43 | 0.116 | 28.23 | 0.111 | 28.13 | |
6 | 0.825 | 23.80 | 0.216 | 33.26 | 0.243 | 37.04 | 0.208 | 31.44 | 0.202 | 31.59 | |
8 | 1.574 | 24.02 | 0.333 | 35.37 | 0.344 | 36.59 | 0.299 | 31.36 | 0.293 | 32.24 | |
10 | 2.391 | 25.59 | 0.523 | 40.48 | 0.557 | 42.38 | 0.500 | 37.77 | 0.489 | 38.27 | |
500 | 2 | 0.241 | 9.62 | 0.150 | 25.82 | 0.156 | 27.45 | 0.121 | 21.26 | 0.118 | 21.82 |
4 | 1.131 | 11.73 | 0.490 | 37.29 | 0.505 | 38.14 | 0.388 | 29.03 | 0.371 | 28.75 | |
6 | 3.335 | 16.14 | 0.884 | 38.74 | 0.993 | 42.53 | 0.770 | 32.16 | 0.727 | 32.02 | |
8 | 6.072 | 17.01 | 1.281 | 39.89 | 1.358 | 41.56 | 1.057 | 33.45 | 1.006 | 33.16 | |
10 | 9.968 | 18.62 | 2.138 | 48.18 | 2.266 | 50.49 | 1.653 | 36.62 | 1.646 | 37.34 | |
1000 | 2 | 0.716 | 7.78 | 0.386 | 28.34 | 0.414 | 29.86 | 0.321 | 22.47 | 0.320 | 23.51 |
4 | 3.306 | 9.75 | 1.443 | 45.45 | 1.484 | 45.77 | 1.214 | 37.59 | 1.231 | 38.65 | |
6 | 8.109 | 10.88 | 2.879 | 49.66 | 3.036 | 51.44 | 2.108 | 35.86 | 2.132 | 36.42 | |
8 | 20.743 | 13.95 | 4.956 | 55.43 | 5.132 | 56.06 | 3.942 | 42.44 | 3.642 | 40.38 | |
10 | 37.590 | 17.52 | 7.712 | 59.15 | 7.941 | 59.95 | 5.819 | 43.43 | 5.893 | 45.85 |
n | m | PC method | PPA1 | PPA2 | Algorithm 1 | Algorithm 2 | |||||
CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | ||
50 | 2 | 0.077 | 58.93 | 0.038 | 52.66 | 0.037 | 53.87 | 0.028 | 39.33 | 0.028 | 40.22 |
4 | 0.219 | 77.85 | 0.084 | 60.53 | 0.086 | 61.71 | 0.066 | 49.14 | 0.063 | 46.94 | |
6 | 0.471 | 86.40 | 0.141 | 65.16 | 0.145 | 68.42 | 0.116 | 54.87 | 0.111 | 54.47 | |
8 | 0.859 | 101.61 | 0.231 | 76.47 | 0.222 | 76.93 | 0.183 | 62.82 | 0.183 | 64.13 | |
10 | 1.238 | 103.24 | 0.300 | 77.12 | 0.306 | 78.26 | 0.264 | 65.93 | 0.254 | 65.08 | |
100 | 2 | 0.130 | 47.82 | 0.053 | 38.50 | 0.055 | 39.37 | 0.038 | 28.84 | 0.039 | 29.39 |
4 | 0.416 | 56.39 | 0.133 | 48.53 | 0.131 | 48.98 | 0.101 | 37.98 | 0.101 | 39.32 | |
6 | 0.778 | 58.80 | 0.239 | 57.14 | 0.235 | 57.93 | 0.175 | 43.07 | 0.174 | 44.15 | |
8 | 1.922 | 86.76 | 0.351 | 62.63 | 0.369 | 66.90 | 0.294 | 52.46 | 0.279 | 51.38 | |
10 | 2.986 | 90.21 | 0.507 | 67.44 | 0.514 | 67.12 | 0.436 | 56.77 | 0.426 | 56.10 | |
200 | 2 | 0.146 | 21.38 | 0.077 | 29.11 | 0.081 | 30.09 | 0.056 | 21.32 | 0.058 | 23.21 |
4 | 0.634 | 31.07 | 0.201 | 37.14 | 0.204 | 37.92 | 0.148 | 27.76 | 0.156 | 30.00 | |
6 | 1.363 | 33.58 | 0.384 | 45.09 | 0.390 | 45.95 | 0.297 | 34.45 | 0.293 | 35.05 | |
8 | 2.796 | 37.18 | 0.622 | 50.46 | 0.651 | 53.04 | 0.473 | 38.48 | 0.510 | 42.54 | |
10 | 8.218 | 79.37 | 1.112 | 69.73 | 1.128 | 69.27 | 0.941 | 57.59 | 0.934 | 58.11 | |
500 | 2 | 0.280 | 9.53 | 0.166 | 23.66 | 0.198 | 29.26 | 0.139 | 20.84 | 0.153 | 23.46 |
4 | 1.686 | 16.28 | 0.579 | 37.75 | 0.624 | 40.80 | 0.420 | 27.21 | 0.470 | 31.33 | |
6 | 5.626 | 22.22 | 1.072 | 41.50 | 1.048 | 40.41 | 0.815 | 31.00 | 0.854 | 33.42 | |
8 | 9.956 | 27.75 | 1.826 | 43.97 | 2.061 | 48.70 | 1.529 | 35.96 | 1.601 | 38.73 | |
10 | 23.448 | 43.14 | 2.762 | 53.52 | 2.831 | 53.89 | 2.067 | 39.27 | 2.228 | 43.10 | |
1000 | 2 | 0.700 | 7.49 | 0.379 | 23.81 | 0.391 | 24.30 | 0.314 | 19.23 | 0.266 | 16.97 |
4 | 3.450 | 8.06 | 1.385 | 32.74 | 1.451 | 33.15 | 0.982 | 22.62 | 1.060 | 24.86 | |
6 | 7.448 | 9.23 | 2.457 | 37.53 | 2.721 | 40.88 | 1.880 | 28.29 | 2.050 | 31.22 | |
8 | 14.150 | 10.25 | 4.177 | 41.70 | 4.380 | 42.95 | 2.981 | 29.10 | 3.212 | 32.05 | |
10 | 39.917 | 13.78 | 8.838 | 51.66 | 9.151 | 51.74 | 6.629 | 38.16 | 6.997 | 41.41 |
n | m | PC method | PPA1 | PPA2 | Algorithm 1 | Algorithm 2 | |||||
CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | CPU | Iter. | ||
50 | 2 | 0.077 | 58.93 | 0.038 | 52.66 | 0.037 | 53.87 | 0.028 | 39.33 | 0.028 | 40.22 |
4 | 0.219 | 77.85 | 0.084 | 60.53 | 0.086 | 61.71 | 0.066 | 49.14 | 0.063 | 46.94 | |
6 | 0.471 | 86.40 | 0.141 | 65.16 | 0.145 | 68.42 | 0.116 | 54.87 | 0.111 | 54.47 | |
8 | 0.859 | 101.61 | 0.231 | 76.47 | 0.222 | 76.93 | 0.183 | 62.82 | 0.183 | 64.13 | |
10 | 1.238 | 103.24 | 0.300 | 77.12 | 0.306 | 78.26 | 0.264 | 65.93 | 0.254 | 65.08 | |
100 | 2 | 0.130 | 47.82 | 0.053 | 38.50 | 0.055 | 39.37 | 0.038 | 28.84 | 0.039 | 29.39 |
4 | 0.416 | 56.39 | 0.133 | 48.53 | 0.131 | 48.98 | 0.101 | 37.98 | 0.101 | 39.32 | |
6 | 0.778 | 58.80 | 0.239 | 57.14 | 0.235 | 57.93 | 0.175 | 43.07 | 0.174 | 44.15 | |
8 | 1.922 | 86.76 | 0.351 | 62.63 | 0.369 | 66.90 | 0.294 | 52.46 | 0.279 | 51.38 | |
10 | 2.986 | 90.21 | 0.507 | 67.44 | 0.514 | 67.12 | 0.436 | 56.77 | 0.426 | 56.10 | |
200 | 2 | 0.146 | 21.38 | 0.077 | 29.11 | 0.081 | 30.09 | 0.056 | 21.32 | 0.058 | 23.21 |
4 | 0.634 | 31.07 | 0.201 | 37.14 | 0.204 | 37.92 | 0.148 | 27.76 | 0.156 | 30.00 | |
6 | 1.363 | 33.58 | 0.384 | 45.09 | 0.390 | 45.95 | 0.297 | 34.45 | 0.293 | 35.05 | |
8 | 2.796 | 37.18 | 0.622 | 50.46 | 0.651 | 53.04 | 0.473 | 38.48 | 0.510 | 42.54 | |
10 | 8.218 | 79.37 | 1.112 | 69.73 | 1.128 | 69.27 | 0.941 | 57.59 | 0.934 | 58.11 | |
500 | 2 | 0.280 | 9.53 | 0.166 | 23.66 | 0.198 | 29.26 | 0.139 | 20.84 | 0.153 | 23.46 |
4 | 1.686 | 16.28 | 0.579 | 37.75 | 0.624 | 40.80 | 0.420 | 27.21 | 0.470 | 31.33 | |
6 | 5.626 | 22.22 | 1.072 | 41.50 | 1.048 | 40.41 | 0.815 | 31.00 | 0.854 | 33.42 | |
8 | 9.956 | 27.75 | 1.826 | 43.97 | 2.061 | 48.70 | 1.529 | 35.96 | 1.601 | 38.73 | |
10 | 23.448 | 43.14 | 2.762 | 53.52 | 2.831 | 53.89 | 2.067 | 39.27 | 2.228 | 43.10 | |
1000 | 2 | 0.700 | 7.49 | 0.379 | 23.81 | 0.391 | 24.30 | 0.314 | 19.23 | 0.266 | 16.97 |
4 | 3.450 | 8.06 | 1.385 | 32.74 | 1.451 | 33.15 | 0.982 | 22.62 | 1.060 | 24.86 | |
6 | 7.448 | 9.23 | 2.457 | 37.53 | 2.721 | 40.88 | 1.880 | 28.29 | 2.050 | 31.22 | |
8 | 14.150 | 10.25 | 4.177 | 41.70 | 4.380 | 42.95 | 2.981 | 29.10 | 3.212 | 32.05 | |
10 | 39.917 | 13.78 | 8.838 | 51.66 | 9.151 | 51.74 | 6.629 | 38.16 | 6.997 | 41.41 |
[1] |
Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827 |
[2] |
David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 |
[3] |
Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 |
[4] |
Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065 |
[5] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[6] |
Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 |
[7] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[8] |
Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463 |
[9] |
Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020401 |
[10] |
Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151 |
[11] |
Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261 |
[12] |
Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090 |
[13] |
Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]