American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Partial myopia vs. forward-looking behaviors in a dynamic pricing and replenishment model for perishable items
  • JIMO Home
  • This Issue
  • Next Article
    Angel capitalists exit decisions under information asymmetry: IPO or acquisitions
doi: 10.3934/jimo.2020007

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

Zi Xu , , Siwen Wang and  Jinjin Huang

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.

Keywords: Maximin dispersion problem, block successive upper bound minimization, maximum improvement successive upper-bound minimization, successive convex approximation.
Mathematics Subject Classification: Primary: 90C06, 90C26; Secondary: 93E10.
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. Chen, S. He, Z. 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. Haines, J. Loeppky, P. 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. Johbson, L. 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. Ravi, D. 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. Razaviyayn, M. 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. Wu, Y. 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. Chen, S. He, Z. 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. Haines, J. Loeppky, P. 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. Johbson, L. 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. Ravi, D. 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. Razaviyayn, M. 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. Wu, Y. 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
Table Options

Download as excel

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

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651
[2]

Walter Briec, Bernardin Solonandrasana. Some remarks on a successive projection sequence. Journal of Industrial & Management Optimization, 2006, 2 (4) : 451-466. doi: 10.3934/jimo.2006.2.451
[3]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[4]

Giuseppe D'Onofrio, Enrica Pirozzi. Successive spike times predicted by a stochastic neuronal model with a variable input signal. Mathematical Biosciences & Engineering, 2016, 13 (3) : 495-507. doi: 10.3934/mbe.2016003
[5]

Alain Miranville, Xiaoming Wang. Upper bound on the dimension of the attractor for nonhomogeneous Navier-Stokes equations. Discrete & Continuous Dynamical Systems - A, 1996, 2 (1) : 95-110. doi: 10.3934/dcds.1996.2.95
[6]

Gang Meng. The optimal upper bound for the first eigenvalue of the fourth order equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (12) : 6369-6382. doi: 10.3934/dcds.2017276
[7]

Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83
[8]

S. E. Kuznetsov. An upper bound for positive solutions of the equation \Delta u=u^\alpha. Electronic Research Announcements, 2004, 10: 103-112.

[9]

Naoufel Ben Abdallah, Irene M. Gamba, Giuseppe Toscani. On the minimization problem of sub-linear convex functionals. Kinetic & Related Models, 2011, 4 (4) : 857-871. doi: 10.3934/krm.2011.4.857
[10]

Mrinal Kanti Roychowdhury. Least upper bound of the exact formula for optimal quantization of some uniform Cantor distributions. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4555-4570. doi: 10.3934/dcds.2018199
[11]

Frédéric Vanhove. A geometric proof of the upper bound on the size of partial spreads in $H(4n+1,$q2$)$. Advances in Mathematics of Communications, 2011, 5 (2) : 157-160. doi: 10.3934/amc.2011.5.157
[12]

Xing Liu, Daiyuan Peng. Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions. Advances in Mathematics of Communications, 2014, 8 (3) : 359-373. doi: 10.3934/amc.2014.8.359
[13]

Mourad Choulli. Local boundedness property for parabolic BVP's and the Gaussian upper bound for their Green functions. Evolution Equations & Control Theory, 2015, 4 (1) : 61-67. doi: 10.3934/eect.2015.4.61
[14]

Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070
[15]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018
[16]

Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems & Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645
[17]

M. Zuhair Nashed, Alexandru Tamasan. Structural stability in a minimization problem and applications to conductivity imaging. Inverse Problems & Imaging, 2011, 5 (1) : 219-236. doi: 10.3934/ipi.2011.5.219
[18]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79
[19]

Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341
[20]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (10)
  • HTML views (27)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences