• Previous Article
    Partial myopia vs. forward-looking behaviors in a dynamic pricing and replenishment model for perishable items
  • JIMO Home
  • This Issue
  • Next Article
    Continuity, differentiability and semismoothness of generalized tensor functions
doi: 10.3934/jimo.2020007

An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem

Department of Mathematics, College of Sciences, Shanghai University, 200444 Shanghai, China

* Corresponding author: Zi Xu

Received  September 2018 Revised  August 2019 Published  January 2020

Fund Project: The first author is supported by National Natural Science Foundation of China under the grant 11571221 and 11771208.

The box-constrained weighted maximin dispersion problem is to find a point in an $ n $-dimensional box such that the minimum of the weighted Euclidean distance from given $ m $ points is maximized. In this paper, we first propose a two-phase method to solve it. In the first phase, we adopt a block successive upper bound minimization (BSUM) algorithm framework and choose a special piecewise linear upper bound function for the weighted maximin dispersion problem. The per-iteration complexity of our algorithm is very low, since the subproblem is a one-dimensional piecewise linear minimax problem over the box constraints, or eqivalently, a two-dimensional linear programming problem which can be solved in at most $ O(m) $ time by existing algorithms. In the second phase, a useful rounding is employed to enhance the solution. Moreover, we propose another strengthened two-phase algorithm, which employs a maximum improvement successive upper-bound minimization (MISUM) algorithm instead of BSUM algorithm in the first phase. At each step, only the block that provides the maximum improvement of the upper bound function is updated. Then, it can be proved that every limit point of the iterate generated by this strengthened algorithm is a stationary point. Numerical results show that the proposed algorithms are efficient.

Citation: Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020007
References:
[1]

B. ChenS. HeZ. Li and S. Zhang, Maximum block improvement and polynomial optimization, SIAM J. Optim., 22 (2012), 87-107.  doi: 10.1137/110834524.  Google Scholar

[2]

B. Dasarthy and L. White, A maximin location problem, Oper. Res., 28 (1980), 1385-1401.  doi: 10.1287/opre.28.6.1385.  Google Scholar

[3]

M. Grant and S. Boyd, CVX User's guide: For CVX version 1.21, User's Guide, (2010), 24–75. Google Scholar

[4]

S. HainesJ. LoeppkyP. Tseng and X. Wang, Convex relaxations of the weighted maxmin dispersion problem, SIAM J. Optim., 23 (2013), 2264-2294.  doi: 10.1137/120888880.  Google Scholar

[5]

M. JohbsonL. Moore and D. Ylvisaker, Maximin Distance Designs, Statist. Plann. J., 26 (1990), 131-148.  doi: 10.1016/0378-3758(90)90122-B.  Google Scholar

[6]

A. Konar and N. Sidiropoulos, Fast approximation algorithms for a class of nonconvex QCQP problems using first-order methods, IEEE Trans. Signal Process, 65 (2017), 3494-3509.  doi: 10.1109/TSP.2017.2690386.  Google Scholar

[7]

N. Megiddo, Linear-time algorithms for linear programming in $\mathbb{R}^3$ and related problems, SIAM J. Comput., 12 (1983), 759-776.  doi: 10.1137/0212052.  Google Scholar

[8]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ. 1970.  Google Scholar

[9]

S. RaviD. Rosenkrantz and G. Tayi, Heuristic and special case algorithms for dispersion problems, Oper. Res., 42 (1994), 299-310.  doi: 10.1287/opre.42.2.299.  Google Scholar

[10]

M. RazaviyaynM. Hong and Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM J. Optim., 23 (2013), 1126-1153.  doi: 10.1137/120891009.  Google Scholar

[11]

S. Wang and Y. Xia, On the ball-constrained weighted maximin dispersion problem, SIAM J. Optim., 26 (2016), 1565-1588.  doi: 10.1137/15M1047167.  Google Scholar

[12]

D. J. White, A heuristic approach to a weighted maxmin disperation problem, IMA J. Math. Appl. Bus. Indust., 7 (1996), 219-231.  doi: 10.1093/imaman/7.3.219.  Google Scholar

[13]

Z. WuY. Xia and S. Wang, Approximating the weighted maximin dispersion problem over an $\ell_{p}-$ball: SDP relaxation is misleading, Optim. Lett., 12 (2018), 875-883.  doi: 10.1007/s11590-017-1177-y.  Google Scholar

show all references

References:
[1]

B. ChenS. HeZ. Li and S. Zhang, Maximum block improvement and polynomial optimization, SIAM J. Optim., 22 (2012), 87-107.  doi: 10.1137/110834524.  Google Scholar

[2]

B. Dasarthy and L. White, A maximin location problem, Oper. Res., 28 (1980), 1385-1401.  doi: 10.1287/opre.28.6.1385.  Google Scholar

[3]

M. Grant and S. Boyd, CVX User's guide: For CVX version 1.21, User's Guide, (2010), 24–75. Google Scholar

[4]

S. HainesJ. LoeppkyP. Tseng and X. Wang, Convex relaxations of the weighted maxmin dispersion problem, SIAM J. Optim., 23 (2013), 2264-2294.  doi: 10.1137/120888880.  Google Scholar

[5]

M. JohbsonL. Moore and D. Ylvisaker, Maximin Distance Designs, Statist. Plann. J., 26 (1990), 131-148.  doi: 10.1016/0378-3758(90)90122-B.  Google Scholar

[6]

A. Konar and N. Sidiropoulos, Fast approximation algorithms for a class of nonconvex QCQP problems using first-order methods, IEEE Trans. Signal Process, 65 (2017), 3494-3509.  doi: 10.1109/TSP.2017.2690386.  Google Scholar

[7]

N. Megiddo, Linear-time algorithms for linear programming in $\mathbb{R}^3$ and related problems, SIAM J. Comput., 12 (1983), 759-776.  doi: 10.1137/0212052.  Google Scholar

[8]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ. 1970.  Google Scholar

[9]

S. RaviD. Rosenkrantz and G. Tayi, Heuristic and special case algorithms for dispersion problems, Oper. Res., 42 (1994), 299-310.  doi: 10.1287/opre.42.2.299.  Google Scholar

[10]

M. RazaviyaynM. Hong and Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM J. Optim., 23 (2013), 1126-1153.  doi: 10.1137/120891009.  Google Scholar

[11]

S. Wang and Y. Xia, On the ball-constrained weighted maximin dispersion problem, SIAM J. Optim., 26 (2016), 1565-1588.  doi: 10.1137/15M1047167.  Google Scholar

[12]

D. J. White, A heuristic approach to a weighted maxmin disperation problem, IMA J. Math. Appl. Bus. Indust., 7 (1996), 219-231.  doi: 10.1093/imaman/7.3.219.  Google Scholar

[13]

Z. WuY. Xia and S. Wang, Approximating the weighted maximin dispersion problem over an $\ell_{p}-$ball: SDP relaxation is misleading, Optim. Lett., 12 (2018), 875-883.  doi: 10.1007/s11590-017-1177-y.  Google Scholar

Table 1.  Numerical results for Algorithm 2, Algorithm 4 and a randomized algorithm in [13]
$ n $ $ m $ CR Algorithm in [13] Algorithm 2 Algorithm 4
max min ave time(s) $ f(\bar{x}) $ $ f(\tilde{x}) $ time(s) $ f(\bar{x}) $ $ f(\tilde{x}) $ time(s)
10 5 27.23 24.46 9.12 15.41 0.17 25.26 24.46 0.30 25.06 24.62 0.11
10 18.84 17.24 5.53 10.38 0.16 15.75 15.73 0.07 16.65 15.99 0.08
15 20.70 18.58 4.88 10.12 0.19 16.98 16.98 0.10 18.23 17.68 0.16
20 19.61 16.58 4.27 9.07 0.19 12.76 12.30 0.08 14.91 12.75 0.24
50 25 125.01 100.04 64.56 82.91 0.36 100.11 98.81 0.65 100.83 97.12 1.45
50 119.37 97.73 58.83 78.78 0.46 102.54 102.52 0.51 96.28 96.24 1.93
75 116.26 91.54 61.52 77.06 0.65 93.45 91.85 0.56 93.50 92.08 2.00
100 111.27 90.98 57.09 74.20 0.80 87.20 85.38 0.56 90.22 88.04 2.40
100 50 248.61 203.88 149.11 179.52 0.64 205.35 203.69 1.11 206.61 206.25 5.57
100 237.30 201.19 148.41 174.23 0.91 194.10 198.58 1.14 198.03 195.88 5.19
150 229.82 189.37 143.86 169.15 1.60 190.54 189.85 1.17 191.68 191.02 6.89
200 225.29 186.59 141.19 166.47 1.88 182.12 182.01 1.09 192.98 190.41 5.13
200 100 486.61 415.95 330.52 381.25 1.35 414.23 411.46 2.18 418.68 418.04 11.48
200 470.68 407.27 339.75 373.47 1.92 400.76 398.18 2.17 408.94 406.36 17.38
300 458.86 392.36 327.42 364.31 3.00 390.41 389.97 2.30 396.74 394.95 20.16
400 455.93 386.82 327.51 362.83 3.88 387.63 389.83 2.36 390.20 388.69 13.95
500 250 1195.38 1057.93 949.65 1007.69 3.25 1062.99 1065.15 8.05 1067.74 1067.13 58.52
500 1170.13 1038.79 927.82 991.64 6.95 1037.89 1036.55 6.67 1045.27 1040.02 69.19
750 1158.40 1036.04 921.19 990.71 10.56 1043.01 1043.29 8.53 1041.21 1039.92 72.33
1000 1153.98 1026.42 918.45 985.13 14.17 1029.30 1028.34 9.71 1043.27 1040.64 88.20
1000 500 2372.10 2155.47 1979.65 2090.65 10.81 2153.46 2153.81 13.66 2169.29 2167.92 151.93
1000 2338.73 2130.04 1965.58 2075.21 20.56 2133.01 2132.86 19.45 2146.65 2145.80 186.37
1500 2323.82 2124.92 1973.03 2063.91 30.24 2116.10 2112.71 26.33 2125.68 2123.82 306.66
2000 2315.50 2115.62 1991.24 2061.12 40.06 2129.96 2130.49 34.37 2139.15 2137.68 355.30
2000 1000 4725.17 4386.88 4168.28 4299.25 37.99 4396.60 4398.16 42.95 4413.11 4413.68 437.40
2000 4676.85 4358.33 4151.69 4279.57 65.00 4375.92 4379.46 69.17 4379.41 4377.45 820.25
3000 4653.55 4344.27 4142.43 4266.76 99.39 4343.23 4345.99 98.43 4370.00 4365.32 1135.90
4000 4637.74 4334.58 4109.75 4256.80 132.17 4336.27 4334.29 129.59 4361.70 4361.22 1797.67
$ n $ $ m $ CR Algorithm in [13] Algorithm 2 Algorithm 4
max min ave time(s) $ f(\bar{x}) $ $ f(\tilde{x}) $ time(s) $ f(\bar{x}) $ $ f(\tilde{x}) $ time(s)
10 5 27.23 24.46 9.12 15.41 0.17 25.26 24.46 0.30 25.06 24.62 0.11
10 18.84 17.24 5.53 10.38 0.16 15.75 15.73 0.07 16.65 15.99 0.08
15 20.70 18.58 4.88 10.12 0.19 16.98 16.98 0.10 18.23 17.68 0.16
20 19.61 16.58 4.27 9.07 0.19 12.76 12.30 0.08 14.91 12.75 0.24
50 25 125.01 100.04 64.56 82.91 0.36 100.11 98.81 0.65 100.83 97.12 1.45
50 119.37 97.73 58.83 78.78 0.46 102.54 102.52 0.51 96.28 96.24 1.93
75 116.26 91.54 61.52 77.06 0.65 93.45 91.85 0.56 93.50 92.08 2.00
100 111.27 90.98 57.09 74.20 0.80 87.20 85.38 0.56 90.22 88.04 2.40
100 50 248.61 203.88 149.11 179.52 0.64 205.35 203.69 1.11 206.61 206.25 5.57
100 237.30 201.19 148.41 174.23 0.91 194.10 198.58 1.14 198.03 195.88 5.19
150 229.82 189.37 143.86 169.15 1.60 190.54 189.85 1.17 191.68 191.02 6.89
200 225.29 186.59 141.19 166.47 1.88 182.12 182.01 1.09 192.98 190.41 5.13
200 100 486.61 415.95 330.52 381.25 1.35 414.23 411.46 2.18 418.68 418.04 11.48
200 470.68 407.27 339.75 373.47 1.92 400.76 398.18 2.17 408.94 406.36 17.38
300 458.86 392.36 327.42 364.31 3.00 390.41 389.97 2.30 396.74 394.95 20.16
400 455.93 386.82 327.51 362.83 3.88 387.63 389.83 2.36 390.20 388.69 13.95
500 250 1195.38 1057.93 949.65 1007.69 3.25 1062.99 1065.15 8.05 1067.74 1067.13 58.52
500 1170.13 1038.79 927.82 991.64 6.95 1037.89 1036.55 6.67 1045.27 1040.02 69.19
750 1158.40 1036.04 921.19 990.71 10.56 1043.01 1043.29 8.53 1041.21 1039.92 72.33
1000 1153.98 1026.42 918.45 985.13 14.17 1029.30 1028.34 9.71 1043.27 1040.64 88.20
1000 500 2372.10 2155.47 1979.65 2090.65 10.81 2153.46 2153.81 13.66 2169.29 2167.92 151.93
1000 2338.73 2130.04 1965.58 2075.21 20.56 2133.01 2132.86 19.45 2146.65 2145.80 186.37
1500 2323.82 2124.92 1973.03 2063.91 30.24 2116.10 2112.71 26.33 2125.68 2123.82 306.66
2000 2315.50 2115.62 1991.24 2061.12 40.06 2129.96 2130.49 34.37 2139.15 2137.68 355.30
2000 1000 4725.17 4386.88 4168.28 4299.25 37.99 4396.60 4398.16 42.95 4413.11 4413.68 437.40
2000 4676.85 4358.33 4151.69 4279.57 65.00 4375.92 4379.46 69.17 4379.41 4377.45 820.25
3000 4653.55 4344.27 4142.43 4266.76 99.39 4343.23 4345.99 98.43 4370.00 4365.32 1135.90
4000 4637.74 4334.58 4109.75 4256.80 132.17 4336.27 4334.29 129.59 4361.70 4361.22 1797.67
[1]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[2]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269

[3]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[4]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[5]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[6]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[7]

Serge Dumont, Olivier Goubet, Youcef Mammeri. Decay of solutions to one dimensional nonlinear Schrödinger equations with white noise dispersion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020456

[8]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[9]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[10]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[11]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[12]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[13]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[14]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[15]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[16]

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

[17]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[18]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[19]

Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

[20]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]