American Institute of Mathematical Sciences

Advanced
January  2022, 18(1): 613-634. 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  January 2022 Early access  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 and Management Optimization, 2022, 18 (1) : 613-634. 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.

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

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

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.

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

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

[7]

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

[8]

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

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

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

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

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

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

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

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

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

[17]

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

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

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

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

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

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

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

[24]

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

[25]

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

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

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

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

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

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

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

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

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

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

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

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

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

[38]

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

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

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.

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

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

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.

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

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

[7]

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

[8]

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

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

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

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

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

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

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

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

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

[17]

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

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

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

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

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

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

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

[24]

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

[25]

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

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

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

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

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

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

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

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

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

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

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

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

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

[38]

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

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

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]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917
[2]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1783-1799. doi: 10.3934/jimo.2019029
[3]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[4]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[5]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247
[6]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037
[7]

Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047
[8]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial and Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078
[9]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057
[10]

Jianlin Jiang, Shun Zhang, Su Zhang, Jie Wen. A variational inequality approach for constrained multifacility Weber problem under gauge. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1085-1104. doi: 10.3934/jimo.2017091
[11]

Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016
[12]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
[13]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial and Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135
[14]

Maria do Rosário de Pinho, Ilya Shvartsman. Lipschitz continuity of optimal control and Lagrange multipliers in a problem with mixed and pure state constraints. Discrete and Continuous Dynamical Systems, 2011, 29 (2) : 505-522. doi: 10.3934/dcds.2011.29.505
[15]

Roman Chapko, B. Tomas Johansson. An alternating boundary integral based method for a Cauchy problem for the Laplace equation in semi-infinite regions. Inverse Problems and Imaging, 2008, 2 (3) : 317-333. doi: 10.3934/ipi.2008.2.317
[16]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[17]

Lotfi Tadj, Zhe George Zhang, Chakib Tadj. A queueing analysis of multi-purpose production facility's operations. Journal of Industrial and Management Optimization, 2011, 7 (1) : 19-30. doi: 10.3934/jimo.2011.7.19
[18]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
[19]

Laura Gardini, Roya Makrooni, Iryna Sushko. Cascades of alternating smooth bifurcations and border collision bifurcations with singularity in a family of discontinuous linear-power maps. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 701-729. doi: 10.3934/dcdsb.2018039
[20]

Andrea Davini, Lin Wang. On the vanishing discount problem from the negative direction. Discrete and Continuous Dynamical Systems, 2021, 41 (5) : 2377-2389. doi: 10.3934/dcds.2020368

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (310)
  • HTML views (576)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy