American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2020171

ADMM-type methods for generalized multi-facility Weber problem

Shun Zhang 1, , Jianlin Jiang 1,2, , Su Zhang 3,, , Yibing Lv 2, and  Yuzhen Guo 1,

1. 

Department of Mathematics, College of Science, Nanjing University of Aeronautics and Astronautics, 29 Yudao Street, Qinhuai District, Nanjing, 210016, China
2. 

School of Information and Mathematics, Yangtze University, 1 Nanhuan Road, Jingzhou, 434023, China
3. 

Business School, Nankai University, 94 Weijin Road, Nankai District, Tianjin, 300071, China

* Corresponding author: Su Zhang

Received  July 2020 Revised  September 2020 Published  November 2020

Fund Project: This work was supported by National Natural Science Foundation of China (Grant No. 11971230, 12071234) and National Social Science Fund of China (Grant No. 18BGL063)

The well-known multi-facility Weber problem (MFWP) is one of fundamental models in facility location. With the aim of enhancing the practical applicability of MFWP, this paper considers a generalized multi-facility Weber problem (GMFWP), where the gauge is used to measure distances and the locational constraints are imposed to new facilities. This paper focuses on developing efficient numerical methods based on alternating direction method of multipliers (ADMM) to solve GMFWP. Specifically, GMFWP is equivalently reformulated into a minmax problem with special structure and then some ADMM-type methods are proposed for its primal problem. Global convergence of proposed methods for GMFWP is established under mild assumptions. Preliminary numerical results are reported to verify the effectiveness of proposed methods.

Keywords: Multi-facility Weber problem, singularity, gauge, locational constraints, alternating direction method of multipliers.
Mathematics Subject Classification: Primary:90C30;Secondary:90B85.
Citation: Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020171
References:
[1]

S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed Optimization and Statistical Learning Via the Alternating Direction Method of Multipliers, Now Foundations and Trends, 2011. doi: 10.1561/9781601984616.  Google Scholar

[2]

E. Carrizosa, E. Conde, M. Muñoz-Márquez and J. Puerto, Simpson points in planar problems with locational constraints. The polyhedral-gauge case, Math. Oper. Res., 22 (1997), 291-300.  doi: 10.1287/moor.22.2.291.  Google Scholar

[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.  Google Scholar

[4]

C. Chen, B. He, Y. Ye and X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[5]

Y.-H. Dai, D. Han, X. Yuan and W. Zhang, A sequential updating scheme of the Lagrange multiplier for separable convex programming, Math. Comp., 86 (2017), 315-343.  doi: 10.1090/mcom/3104.  Google Scholar

[6]

F. Daneshzand and R. Shoeleh, Multifacility location problem, in Facility Location, Contributions to Management Science, Physica, Heidelberg, 2009, 69–92. doi: 10.1007/978-3-7908-2151-2_4.  Google Scholar

[7]

Z. Drezner, Facility Location. A Survey of Applications and Methods, Springer Series in Operations Research, Springer-Verlag, New York, 1995.  Google Scholar

[8]

Z. Drezner and H. W. Hamacher, Facility Location. Applications and Theory, Springer-Verlag, Berlin, 2002.  Google Scholar

[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), 1-6.  doi: 10.1080/05695557308974875.  Google Scholar

[10]

M. Fortin and R. Glowinski, On decomposition-coordination methods using an augmented Lagrangian, in Studies in Mathematics and Its Applications, 15, Elsevier, Amsterdam, 1983, 97–146. doi: 10.1016/S0168-2024(08)70028-6.  Google Scholar

[11]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[12]

R. Glowinski, Lectures on Numerical Methods for Non-linear Variational Problems, Research Lectures on Mathematics and Physics, 65, Tata Institute of Fundamental Research, Bombay; sh Springer-Verlag, Berlin-New York, 1980.  Google Scholar

[13]

R. Glowinski and A. Marrocco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité, d'une classe de problèmes de Dirichlet non linéaires, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér, 9 (1975), 41–76. doi: 10.1051/m2an/197509R200411.  Google Scholar

[14]

K. Guo, D. Han and X. Yuan, Convergence analysis of Douglas–Rachford splitting method for "strongly + weakly" convex programming, SIAM J. Numer. Anal., 55 (2017), 1549-1577.  doi: 10.1137/16M1078604.  Google Scholar

[15]

B. He, F. Ma and X. Yuan, Optimally linearizing the alternating direction method of multipliers for convex programming, Comput. Optim. Appl., 75 (2020), 361-388.  doi: 10.1007/s10589-019-00152-3.  Google Scholar

[16]

B. He, X. Yuan and W. 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.  Google Scholar

[17]

B. S. He, A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63.   Google Scholar

[18]

J. Jiang, S. Zhang, Y. Lv, X. Du and Z. Yan, An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge, J. Global Optim., 76 (2020), 793-818.  doi: 10.1007/s10898-019-00796-9.  Google Scholar

[19]

J. Jiang, S. Zhang, S. Zhang and J. Wen, A variational inequality approach for constrained multifacility Weber problem under gauge, J. Ind. Manag. Optim., 14 (2018), 1085-1104.  doi: 10.3934/jimo.2017091.  Google Scholar

[20]

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.  Google Scholar

[21]

X. Li, D. Sun and K.-C. Toh, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155 (2016), 333-373.  doi: 10.1007/s10107-014-0850-5.  Google Scholar

[22]

Z. Lin, R. Liu and H. Li, Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning, Mach. Learn., 99 (2015), 287-325.  doi: 10.1007/s10994-014-5469-5.  Google Scholar

[23]

R. F. Love and J. G. Morris, Mathematical models of road travel distances, Manag. Sci., 25 (1979), 117-210.  doi: 10.1287/mnsc.25.2.130.  Google Scholar

[24]

W. Miehle, Link-length minimization in networks, Operations Res., 6 (1958), 232-243.  doi: 10.1287/opre.6.2.232.  Google Scholar

[25]

H. Minkowski, Theorie der Konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911. Google Scholar

[26]

L. M. Ostresh, The multifacility location problem: applications and descent theorems, J. Regional. Sci., 17 (2006), 409-419.  doi: 10.1111/j.1467-9787.1977.tb00511.x.  Google Scholar

[27]

Y. Peng, A. Ganesh, J. Wright, W. Xu and Y. Ma, RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, CA, 2010. doi: 10.1109/CVPR.2010.5540138.  Google Scholar

[28]

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.  Google Scholar

[29]

F. Plastria, The Weiszfeld algorithm: Proof, amendments, and extensions, in Foundations of Location Analysis, International Series in Operations Research & Management Science, 155, Springer, New York, 2011, 357–389. doi: 10.1007/978-1-4419-7572-0_16.  Google Scholar

[30]

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.  Google Scholar

[31]

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.  Google Scholar

[32]

D. Sun, K.-C. Toh and L. Yang, A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J. Optim., 25 (2015), 882-915.  doi: 10.1137/140964357.  Google Scholar

[33]

M. Tao and X. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21 (2011), 57-81.  doi: 10.1137/100781894.  Google Scholar

[34]

X. Wang and X. Yuan, The linearized alternating direction method of multipliers for Dantzig selector, SIAM J. Sci. Comput., 34 (2012), A2792–A2811. doi: 10.1137/110833543.  Google Scholar

[35]

J. E. Ward and R. E. Wendell, Using block norms for location modeling, Oper. Res., 33 (1985), 1074-1090.  doi: 10.1287/opre.33.5.1074.  Google Scholar

[36]

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

[37]

Z. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), 203-230.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[38]

C. Witzgall, Optimal Location of a Central Facility, Mathematical Models and Concepts, Report 8388, National Bureau of Standards, Washington D.C., 1964. Google Scholar

[39]

X. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2011), 20-46.  doi: 10.1007/s10915-010-9408-8.  Google Scholar

show all references

References:
[1]

S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed Optimization and Statistical Learning Via the Alternating Direction Method of Multipliers, Now Foundations and Trends, 2011. doi: 10.1561/9781601984616.  Google Scholar

[2]

E. Carrizosa, E. Conde, M. Muñoz-Márquez and J. Puerto, Simpson points in planar problems with locational constraints. The polyhedral-gauge case, Math. Oper. Res., 22 (1997), 291-300.  doi: 10.1287/moor.22.2.291.  Google Scholar

[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.  Google Scholar

[4]

C. Chen, B. He, Y. Ye and X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[5]

Y.-H. Dai, D. Han, X. Yuan and W. Zhang, A sequential updating scheme of the Lagrange multiplier for separable convex programming, Math. Comp., 86 (2017), 315-343.  doi: 10.1090/mcom/3104.  Google Scholar

[6]

F. Daneshzand and R. Shoeleh, Multifacility location problem, in Facility Location, Contributions to Management Science, Physica, Heidelberg, 2009, 69–92. doi: 10.1007/978-3-7908-2151-2_4.  Google Scholar

[7]

Z. Drezner, Facility Location. A Survey of Applications and Methods, Springer Series in Operations Research, Springer-Verlag, New York, 1995.  Google Scholar

[8]

Z. Drezner and H. W. Hamacher, Facility Location. Applications and Theory, Springer-Verlag, Berlin, 2002.  Google Scholar

[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), 1-6.  doi: 10.1080/05695557308974875.  Google Scholar

[10]

M. Fortin and R. Glowinski, On decomposition-coordination methods using an augmented Lagrangian, in Studies in Mathematics and Its Applications, 15, Elsevier, Amsterdam, 1983, 97–146. doi: 10.1016/S0168-2024(08)70028-6.  Google Scholar

[11]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[12]

R. Glowinski, Lectures on Numerical Methods for Non-linear Variational Problems, Research Lectures on Mathematics and Physics, 65, Tata Institute of Fundamental Research, Bombay; sh Springer-Verlag, Berlin-New York, 1980.  Google Scholar

[13]

R. Glowinski and A. Marrocco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité, d'une classe de problèmes de Dirichlet non linéaires, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér, 9 (1975), 41–76. doi: 10.1051/m2an/197509R200411.  Google Scholar

[14]

K. Guo, D. Han and X. Yuan, Convergence analysis of Douglas–Rachford splitting method for "strongly + weakly" convex programming, SIAM J. Numer. Anal., 55 (2017), 1549-1577.  doi: 10.1137/16M1078604.  Google Scholar

[15]

B. He, F. Ma and X. Yuan, Optimally linearizing the alternating direction method of multipliers for convex programming, Comput. Optim. Appl., 75 (2020), 361-388.  doi: 10.1007/s10589-019-00152-3.  Google Scholar

[16]

B. He, X. Yuan and W. 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.  Google Scholar

[17]

B. S. He, A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14 (1996), 54-63.   Google Scholar

[18]

J. Jiang, S. Zhang, Y. Lv, X. Du and Z. Yan, An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge, J. Global Optim., 76 (2020), 793-818.  doi: 10.1007/s10898-019-00796-9.  Google Scholar

[19]

J. Jiang, S. Zhang, S. Zhang and J. Wen, A variational inequality approach for constrained multifacility Weber problem under gauge, J. Ind. Manag. Optim., 14 (2018), 1085-1104.  doi: 10.3934/jimo.2017091.  Google Scholar

[20]

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.  Google Scholar

[21]

X. Li, D. Sun and K.-C. Toh, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155 (2016), 333-373.  doi: 10.1007/s10107-014-0850-5.  Google Scholar

[22]

Z. Lin, R. Liu and H. Li, Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning, Mach. Learn., 99 (2015), 287-325.  doi: 10.1007/s10994-014-5469-5.  Google Scholar

[23]

R. F. Love and J. G. Morris, Mathematical models of road travel distances, Manag. Sci., 25 (1979), 117-210.  doi: 10.1287/mnsc.25.2.130.  Google Scholar

[24]

W. Miehle, Link-length minimization in networks, Operations Res., 6 (1958), 232-243.  doi: 10.1287/opre.6.2.232.  Google Scholar

[25]

H. Minkowski, Theorie der Konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911. Google Scholar

[26]

L. M. Ostresh, The multifacility location problem: applications and descent theorems, J. Regional. Sci., 17 (2006), 409-419.  doi: 10.1111/j.1467-9787.1977.tb00511.x.  Google Scholar

[27]

Y. Peng, A. Ganesh, J. Wright, W. Xu and Y. Ma, RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, CA, 2010. doi: 10.1109/CVPR.2010.5540138.  Google Scholar

[28]

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.  Google Scholar

[29]

F. Plastria, The Weiszfeld algorithm: Proof, amendments, and extensions, in Foundations of Location Analysis, International Series in Operations Research & Management Science, 155, Springer, New York, 2011, 357–389. doi: 10.1007/978-1-4419-7572-0_16.  Google Scholar

[30]

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.  Google Scholar

[31]

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.  Google Scholar

[32]

D. Sun, K.-C. Toh and L. Yang, A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J. Optim., 25 (2015), 882-915.  doi: 10.1137/140964357.  Google Scholar

[33]

M. Tao and X. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21 (2011), 57-81.  doi: 10.1137/100781894.  Google Scholar

[34]

X. Wang and X. Yuan, The linearized alternating direction method of multipliers for Dantzig selector, SIAM J. Sci. Comput., 34 (2012), A2792–A2811. doi: 10.1137/110833543.  Google Scholar

[35]

J. E. Ward and R. E. Wendell, Using block norms for location modeling, Oper. Res., 33 (1985), 1074-1090.  doi: 10.1287/opre.33.5.1074.  Google Scholar

[36]

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

[37]

Z. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), 203-230.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[38]

C. Witzgall, Optimal Location of a Central Facility, Mathematical Models and Concepts, Report 8388, National Bureau of Standards, Washington D.C., 1964. Google Scholar

[39]

X. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2011), 20-46.  doi: 10.1007/s10915-010-9408-8.  Google Scholar

Table 1.  MA, GMA, ADMM-a, ADMM-b and ADMM-c for MFWP
Problem MA GMA ADMM-a ADMM-b ADMM-c
E1 CPU 0.0003 0.0005 0.0117 0.0096 0.0070
Iter. 2 9 240 135 62
Obj. 182.23 182.43 181.42 181.42 181.42
E2 CPU 0.0069 0.0004 0.0127 0.0097 0.0095
Iter. 206 5 240 135 82
Obj. 182.19 182.68 181.42 181.42 181.42
E1$ ^\prime $ CPU / / 0.0125 0.0084 0.0081
Iter. 244.99 118.45 70.28
Obj. 181.42 181.42 181.42
E2$ ^\prime $ CPU / / 0.0117 0.0076 0.0073
Iter. 244.31 117.05 69.32
Obj. 181.42 181.42 181.42
E3 CPU 0.1774 0.1670 0.0095 0.0109 0.0092
Iter. 4502.30 56.70 203.15 168.30 89.10
Obj. 65724.12 68142.84 65317.20 65317.20 65317.19
Table Options

Download as excel

Problem MA GMA ADMM-a ADMM-b ADMM-c
E1 CPU 0.0003 0.0005 0.0117 0.0096 0.0070
Iter. 2 9 240 135 62
Obj. 182.23 182.43 181.42 181.42 181.42
E2 CPU 0.0069 0.0004 0.0127 0.0097 0.0095
Iter. 206 5 240 135 82
Obj. 182.19 182.68 181.42 181.42 181.42
E1$ ^\prime $ CPU / / 0.0125 0.0084 0.0081
Iter. 244.99 118.45 70.28
Obj. 181.42 181.42 181.42
E2$ ^\prime $ CPU / / 0.0117 0.0076 0.0073
Iter. 244.31 117.05 69.32
Obj. 181.42 181.42 181.42
E3 CPU 0.1774 0.1670 0.0095 0.0109 0.0092
Iter. 4502.30 56.70 203.15 168.30 89.10
Obj. 65724.12 68142.84 65317.20 65317.20 65317.19
Table 2.  HAP, GHAP, SHAP, SGHAP, ADMM-a, ADMM-b and ADMM-c for MFWP
m HAP GHAP SHAP SGHAP ADMM-a ADMM-b ADMM-c
$ \varepsilon $=5 $ \varepsilon $=0.5 $ \varepsilon $=0.05 $ \varepsilon $=5 $ \varepsilon $=0.5 $ \varepsilon $=0.05
2 CPU 0.2439 0.5834 1.4800 0.1494 0.3407 0.8399 0.6142 0.5791 0.0589 0.0742 0.0556
Iter. 99.65 241.65 612.35 61.05 137.75 348.45 254.45 237.15 355.18 407.11 208.99
Dobj. 25.92 8.07 2.14 25.92 8.07 2.14 2.14 2.14 0 -0.06 -0.43
4 CPU 1.3323 3.5621 9.5611 0.7189 1.9040 4.9394 2.0067 1.6763 0.0783 0.0981 0.0664
Iter. 265.55 709.90 1905.55 143.55 369.95 987.00 406.90 336.35 260.72 296.51 126.30
Dobj. 91.88 28.71 8.22 91.88 28.71 8.22 8.22 8.21 0 -0.10 -0.66
6 CPU 3.3433 8.7684 23.9782 1.7638 4.6869 12.6427 4.2423 2.9516 0.1061 0.1400 0.1041
Iter. 420.80 1130.30 3035.30 226.10 600.10 1615.80 439.00 370.10 243.37 279.75 121.83
Dobj. 170.51 53.47 15.83 170.51 53.47 15.82 15.81 15.81 0 -0.22 -1.35
8 CPU 6.1408 16.4112 44.5874 3.2534 8.7586 23.5766 4.9028 3.8896 0.1092 0.1859 0.1079
Iter. 614.00 1666.40 4485.80 323.00 867.80 2337.60 490.80 384.80 197.44 260.48 118.38
Dobj. 233.83 73.59 22.29 233.83 73.59 22.29 22.30 22.28 0 -0.30 -1.47
10 CPU 9.8082 27.1206 73.7662 5.2726 14.7574 39.6916 12.3670 7.7926 0.1790 0.2487 0.1668
Iter. 763.62 2099.02 5717.02 407.22 1116.22 3052.62 942.82 597.22 176.86 235.07 113.66
Dobj. 278.14 86.02 24.69 278.14 86.02 24.68 24.69 24.67 0 0.33 -1.91
Table Options

Download as excel

m HAP GHAP SHAP SGHAP ADMM-a ADMM-b ADMM-c
$ \varepsilon $=5 $ \varepsilon $=0.5 $ \varepsilon $=0.05 $ \varepsilon $=5 $ \varepsilon $=0.5 $ \varepsilon $=0.05
2 CPU 0.2439 0.5834 1.4800 0.1494 0.3407 0.8399 0.6142 0.5791 0.0589 0.0742 0.0556
Iter. 99.65 241.65 612.35 61.05 137.75 348.45 254.45 237.15 355.18 407.11 208.99
Dobj. 25.92 8.07 2.14 25.92 8.07 2.14 2.14 2.14 0 -0.06 -0.43
4 CPU 1.3323 3.5621 9.5611 0.7189 1.9040 4.9394 2.0067 1.6763 0.0783 0.0981 0.0664
Iter. 265.55 709.90 1905.55 143.55 369.95 987.00 406.90 336.35 260.72 296.51 126.30
Dobj. 91.88 28.71 8.22 91.88 28.71 8.22 8.22 8.21 0 -0.10 -0.66
6 CPU 3.3433 8.7684 23.9782 1.7638 4.6869 12.6427 4.2423 2.9516 0.1061 0.1400 0.1041
Iter. 420.80 1130.30 3035.30 226.10 600.10 1615.80 439.00 370.10 243.37 279.75 121.83
Dobj. 170.51 53.47 15.83 170.51 53.47 15.82 15.81 15.81 0 -0.22 -1.35
8 CPU 6.1408 16.4112 44.5874 3.2534 8.7586 23.5766 4.9028 3.8896 0.1092 0.1859 0.1079
Iter. 614.00 1666.40 4485.80 323.00 867.80 2337.60 490.80 384.80 197.44 260.48 118.38
Dobj. 233.83 73.59 22.29 233.83 73.59 22.29 22.30 22.28 0 -0.30 -1.47
10 CPU 9.8082 27.1206 73.7662 5.2726 14.7574 39.6916 12.3670 7.7926 0.1790 0.2487 0.1668
Iter. 763.62 2099.02 5717.02 407.22 1116.22 3052.62 942.82 597.22 176.86 235.07 113.66
Dobj. 278.14 86.02 24.69 278.14 86.02 24.68 24.69 24.67 0 0.33 -1.91
Table 3.  Numerical results for GMFWP under Euclidean distances
n m PC method PPA Projection ADMM-a ADMM-b ADMM-c
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.0206 34.08 0.0077 29.10 0.0077 28.72 0.0017 24.58 0.0031 34.52 0.0088 78.36
4 0.0414 39.46 0.0169 34.02 0.0160 32.20 0.0044 35.10 0.0079 45.58 0.0194 83.76
6 0.0838 54.34 0.0287 42.24 0.0286 42.82 0.0068 43.94 0.0139 54.18 0.0371 111.10
8 0.1847 59.34 0.0407 44.12 0.0414 49.22 0.0145 73.32 0.0324 87.78 0.0574 125.04
10 0.3244 74.12 0.0631 57.28 0.0622 61.02 0.0189 78.34 0.0437 88.12 0.0956 157.16
100 2 0.0388 19.00 0.0139 30.84 0.0137 30.42 0.0024 30.72 0.0035 38.80 0.0083 64.70
4 0.0803 19.44 0.0242 31.58 0.0236 31.04 0.0051 38.16 0.0075 41.82 0.0153 66.00
6 0.1244 25.56 0.0378 33.28 0.0377 32.62 0.0083 45.58 0.0144 50.46 0.0240 66.42
8 0.2245 26.16 0.0559 34.78 0.0527 32.86 0.0113 46.92 0.0217 51.34 0.0391 70.92
10 0.2902 33.92 0.0733 37.16 0.0706 34.54 0.0162 54.78 0.0328 57.96 0.0532 73.00
500 2 0.0894 8.38 0.0506 25.24 0.0408 19.90 0.0058 35.94 0.0068 36.38 0.0051 23.10
4 0.4026 10.04 0.1197 33.14 0.0991 26.06 0.0167 50.44 0.0204 50.90 0.0165 28.46
6 1.1204 12.30 0.2026 39.44 0.1651 31.36 0.0313 71.02 0.0393 71.12 0.0301 33.04
8 3.3505 19.32 0.3872 56.92 0.2895 42.24 0.0410 72.04 0.0562 73.04 0.0354 35.76
10 5.8515 20.12 0.4112 57.90 0.3143 45.24 0.0539 73.12 0.0734 73.22 0.0497 38.00
1000 2 0.2795 7.36 0.1047 29.16 0.0853 22.04 0.0113 38.20 0.0131 39.70 0.0088 19.34
4 1.5470 9.14 0.3028 42.30 0.2478 32.06 0.0303 57.66 0.0341 58.22 0.0238 26.34
6 5.7046 14.26 0.4877 48.60 0.3990 37.96 0.0483 66.78 0.0548 67.58 0.0415 30.82
8 12.9352 15.64 0.7822 57.38 0.6016 44.12 0.0708 76.92 0.0895 79.40 0.0654 36.58
10 25.0276 21.38 0.9654 58.16 0.7617 46.14 0.0876 81.78 0.1094 81.96 0.0810 39.50
2000 2 1.4541 7.20 0.2724 34.60 0.2187 26.50 0.0278 44.90 0.0287 45.70 0.0260 18.80
4 10.4432 9.08 0.8724 57.20 0.6840 44.10 0.0602 60.70 0.0630 62.10 0.0577 25.80
6 26.0975 13.60 1.4767 64.80 1.1431 48.30 0.0850 69.90 0.0949 72.60 0.0830 29.70
8 44.1188 10.90 1.8913 67.30 1.3707 49.30 0.1255 77.20 0.1313 79.70 0.1213 36.20
10 69.0254 12.20 2.8059 73.20 2.0799 53.40 0.1518 81.90 0.1719 88.20 0.1470 39.10
Table Options

Download as excel

n m PC method PPA Projection ADMM-a ADMM-b ADMM-c
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.0206 34.08 0.0077 29.10 0.0077 28.72 0.0017 24.58 0.0031 34.52 0.0088 78.36
4 0.0414 39.46 0.0169 34.02 0.0160 32.20 0.0044 35.10 0.0079 45.58 0.0194 83.76
6 0.0838 54.34 0.0287 42.24 0.0286 42.82 0.0068 43.94 0.0139 54.18 0.0371 111.10
8 0.1847 59.34 0.0407 44.12 0.0414 49.22 0.0145 73.32 0.0324 87.78 0.0574 125.04
10 0.3244 74.12 0.0631 57.28 0.0622 61.02 0.0189 78.34 0.0437 88.12 0.0956 157.16
100 2 0.0388 19.00 0.0139 30.84 0.0137 30.42 0.0024 30.72 0.0035 38.80 0.0083 64.70
4 0.0803 19.44 0.0242 31.58 0.0236 31.04 0.0051 38.16 0.0075 41.82 0.0153 66.00
6 0.1244 25.56 0.0378 33.28 0.0377 32.62 0.0083 45.58 0.0144 50.46 0.0240 66.42
8 0.2245 26.16 0.0559 34.78 0.0527 32.86 0.0113 46.92 0.0217 51.34 0.0391 70.92
10 0.2902 33.92 0.0733 37.16 0.0706 34.54 0.0162 54.78 0.0328 57.96 0.0532 73.00
500 2 0.0894 8.38 0.0506 25.24 0.0408 19.90 0.0058 35.94 0.0068 36.38 0.0051 23.10
4 0.4026 10.04 0.1197 33.14 0.0991 26.06 0.0167 50.44 0.0204 50.90 0.0165 28.46
6 1.1204 12.30 0.2026 39.44 0.1651 31.36 0.0313 71.02 0.0393 71.12 0.0301 33.04
8 3.3505 19.32 0.3872 56.92 0.2895 42.24 0.0410 72.04 0.0562 73.04 0.0354 35.76
10 5.8515 20.12 0.4112 57.90 0.3143 45.24 0.0539 73.12 0.0734 73.22 0.0497 38.00
1000 2 0.2795 7.36 0.1047 29.16 0.0853 22.04 0.0113 38.20 0.0131 39.70 0.0088 19.34
4 1.5470 9.14 0.3028 42.30 0.2478 32.06 0.0303 57.66 0.0341 58.22 0.0238 26.34
6 5.7046 14.26 0.4877 48.60 0.3990 37.96 0.0483 66.78 0.0548 67.58 0.0415 30.82
8 12.9352 15.64 0.7822 57.38 0.6016 44.12 0.0708 76.92 0.0895 79.40 0.0654 36.58
10 25.0276 21.38 0.9654 58.16 0.7617 46.14 0.0876 81.78 0.1094 81.96 0.0810 39.50
2000 2 1.4541 7.20 0.2724 34.60 0.2187 26.50 0.0278 44.90 0.0287 45.70 0.0260 18.80
4 10.4432 9.08 0.8724 57.20 0.6840 44.10 0.0602 60.70 0.0630 62.10 0.0577 25.80
6 26.0975 13.60 1.4767 64.80 1.1431 48.30 0.0850 69.90 0.0949 72.60 0.0830 29.70
8 44.1188 10.90 1.8913 67.30 1.3707 49.30 0.1255 77.20 0.1313 79.70 0.1213 36.20
10 69.0254 12.20 2.8059 73.20 2.0799 53.40 0.1518 81.90 0.1719 88.20 0.1470 39.10
Table 4.  Numerical results for GMFWP under gauge
n m PC method PPA Projection ADMM-a ADMM-b ADMM-c
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.0226 26.76 0.0125 32.02 0.0094 23.56 0.0062 69.28 0.0072 69.74 0.0102 131.80
4 0.1120 54.80 0.0394 58.72 0.0352 51.36 0.0112 77.88 0.0172 89.92 0.0367 146.72
6 0.1453 66.66 0.0650 65.42 0.0522 51.48 0.0241 103.96 0.0373 115.60 0.0617 148.30
8 0.2970 73.08 0.0920 67.32 0.0744 54.58 0.0331 109.36 0.0574 116.42 0.0897 150.92
10 0.4527 79.68 0.1171 67.64 0.1045 59.74 0.0564 121.54 0.0874 122.90 0.1414 159.46
100 2 0.0459 21.94 0.0241 34.18 0.0182 28.14 0.0079 85.28 0.0099 89.76 0.0109 60.30
4 0.1011 27.74 0.0426 38.96 0.0357 28.28 0.0164 90.60 0.0206 94.42 0.0201 67.06
6 0.2569 30.30 0.0852 47.28 0.0757 39.06 0.0323 111.66 0.0427 113.36 0.0455 97.42
8 0.3799 40.12 0.1242 51.00 0.0974 40.60 0.0491 132.14 0.0706 133.12 0.0680 98.44
10 0.4327 42.06 0.1516 52.70 0.1249 42.26 0.0695 138.94 0.1077 139.06 0.0905 100.70
500 2 0.1086 8.30 0.0868 31.66 0.0695 26.06 0.0206 95.26 0.0218 96.42 0.0122 40.12
4 0.3752 8.46 0.1778 32.08 0.1339 27.52 0.0437 100.30 0.0509 102.48 0.0309 40.48
6 0.9676 9.86 0.3297 40.86 0.2528 31.32 0.0780 114.80 0.0915 117.78 0.0534 45.54
8 2.6573 14.38 0.5367 49.78 0.3985 35.96 0.1230 124.48 0.1375 127.12 0.0855 53.44
10 5.7330 19.54 0.7646 55.32 0.5923 42.42 0.1628 134.62 0.1987 135.96 0.1489 69.00
1000 2 0.3517 8.28 0.1729 32.26 0.1312 23.92 0.0303 75.32 0.0344 80.06 0.0202 33.08
4 2.1254 11.90 0.5449 47.58 0.3915 36.60 0.0753 100.12 0.0809 100.38 0.0487 40.56
6 9.3411 22.54 0.8087 50.74 0.6333 39.40 0.1279 114.24 0.1378 115.46 0.0909 49.84
8 20.3124 23.86 1.2310 55.32 0.9067 41.00 0.1770 120.34 0.1971 120.72 0.1236 50.38
10 20.6695 25.24 1.6418 59.94 1.1654 42.04 0.2456 130.70 0.2699 130.74 0.1759 53.84
2000 2 1.9512 9.20 0.3199 25.10 0.2638 19.80 0.0647 61.30 0.0595 67.30 0.0443 32.20
4 8.0722 9.30 1.1069 45.60 0.8127 31.20 0.1408 87.10 0.1480 91.40 0.0816 37.00
6 34.8119 17.70 2.7923 73.50 1.9660 52.80 0.2685 121.90 0.2824 122.70 0.1948 57.90
8 79.7269 19.10 3.0159 61.50 2.5028 51.00 0.3592 126.90 0.4011 127.70 0.2539 59.00
10 114.2177 19.40 4.4809 71.50 3.2529 67.70 0.5160 163.30 0.5360 170.80 0.3418 67.50
Table Options

Download as excel

n m PC method PPA Projection ADMM-a ADMM-b ADMM-c
CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
50 2 0.0226 26.76 0.0125 32.02 0.0094 23.56 0.0062 69.28 0.0072 69.74 0.0102 131.80
4 0.1120 54.80 0.0394 58.72 0.0352 51.36 0.0112 77.88 0.0172 89.92 0.0367 146.72
6 0.1453 66.66 0.0650 65.42 0.0522 51.48 0.0241 103.96 0.0373 115.60 0.0617 148.30
8 0.2970 73.08 0.0920 67.32 0.0744 54.58 0.0331 109.36 0.0574 116.42 0.0897 150.92
10 0.4527 79.68 0.1171 67.64 0.1045 59.74 0.0564 121.54 0.0874 122.90 0.1414 159.46
100 2 0.0459 21.94 0.0241 34.18 0.0182 28.14 0.0079 85.28 0.0099 89.76 0.0109 60.30
4 0.1011 27.74 0.0426 38.96 0.0357 28.28 0.0164 90.60 0.0206 94.42 0.0201 67.06
6 0.2569 30.30 0.0852 47.28 0.0757 39.06 0.0323 111.66 0.0427 113.36 0.0455 97.42
8 0.3799 40.12 0.1242 51.00 0.0974 40.60 0.0491 132.14 0.0706 133.12 0.0680 98.44
10 0.4327 42.06 0.1516 52.70 0.1249 42.26 0.0695 138.94 0.1077 139.06 0.0905 100.70
500 2 0.1086 8.30 0.0868 31.66 0.0695 26.06 0.0206 95.26 0.0218 96.42 0.0122 40.12
4 0.3752 8.46 0.1778 32.08 0.1339 27.52 0.0437 100.30 0.0509 102.48 0.0309 40.48
6 0.9676 9.86 0.3297 40.86 0.2528 31.32 0.0780 114.80 0.0915 117.78 0.0534 45.54
8 2.6573 14.38 0.5367 49.78 0.3985 35.96 0.1230 124.48 0.1375 127.12 0.0855 53.44
10 5.7330 19.54 0.7646 55.32 0.5923 42.42 0.1628 134.62 0.1987 135.96 0.1489 69.00
1000 2 0.3517 8.28 0.1729 32.26 0.1312 23.92 0.0303 75.32 0.0344 80.06 0.0202 33.08
4 2.1254 11.90 0.5449 47.58 0.3915 36.60 0.0753 100.12 0.0809 100.38 0.0487 40.56
6 9.3411 22.54 0.8087 50.74 0.6333 39.40 0.1279 114.24 0.1378 115.46 0.0909 49.84
8 20.3124 23.86 1.2310 55.32 0.9067 41.00 0.1770 120.34 0.1971 120.72 0.1236 50.38
10 20.6695 25.24 1.6418 59.94 1.1654 42.04 0.2456 130.70 0.2699 130.74 0.1759 53.84
2000 2 1.9512 9.20 0.3199 25.10 0.2638 19.80 0.0647 61.30 0.0595 67.30 0.0443 32.20
4 8.0722 9.30 1.1069 45.60 0.8127 31.20 0.1408 87.10 0.1480 91.40 0.0816 37.00
6 34.8119 17.70 2.7923 73.50 1.9660 52.80 0.2685 121.90 0.2824 122.70 0.1948 57.90
8 79.7269 19.10 3.0159 61.50 2.5028 51.00 0.3592 126.90 0.4011 127.70 0.2539 59.00
10 114.2177 19.40 4.4809 71.50 3.2529 67.70 0.5160 163.30 0.5360 170.80 0.3418 67.50
[1]

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
[2]

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
[3]

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
[4]

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
[5]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228
[6]

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
[7]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[8]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[9]

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
[10]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[11]

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
[12]

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
[13]

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
[14]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[15]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[16]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[17]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[18]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[19]

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
[20]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (35)
  • HTML views (96)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences