-
Previous Article
Optimal reinsurance-investment and dividends problem with fixed transaction costs
- JIMO Home
- This Issue
-
Next Article
Designing prorated lifetime warranty strategy for high-value and durable products under two-dimensional warranty
An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem
Department of Mathematics, College of Sciences, Shanghai University, 200444 Shanghai, China |
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.
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. |
[2] |
B. Dasarthy and L. White,
A maximin location problem, Oper. Res., 28 (1980), 1385-1401.
doi: 10.1287/opre.28.6.1385. |
[3] |
M. Grant and S. Boyd, CVX User's guide: For CVX version 1.21, User's Guide, (2010), 24–75. |
[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. |
[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. |
[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. |
[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. |
[8] |
R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ. 1970. |
[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. |
[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. |
[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. |
[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. |
[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. |
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. |
[2] |
B. Dasarthy and L. White,
A maximin location problem, Oper. Res., 28 (1980), 1385-1401.
doi: 10.1287/opre.28.6.1385. |
[3] |
M. Grant and S. Boyd, CVX User's guide: For CVX version 1.21, User's Guide, (2010), 24–75. |
[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. |
[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. |
[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. |
[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. |
[8] |
R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ. 1970. |
[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. |
[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. |
[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. |
[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. |
[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. |
CR | Algorithm in [13] | Algorithm 2 | Algorithm 4 | |||||||||
max | min | ave | time(s) | time(s) | 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 |
CR | Algorithm in [13] | Algorithm 2 | Algorithm 4 | |||||||||
max | min | ave | time(s) | time(s) | 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] |
Mohammed Mesk, Ali Moussaoui. On an upper bound for the spreading speed. Discrete and Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021210 |
[2] |
Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial and Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651 |
[3] |
Walter Briec, Bernardin Solonandrasana. Some remarks on a successive projection sequence. Journal of Industrial and Management Optimization, 2006, 2 (4) : 451-466. doi: 10.3934/jimo.2006.2.451 |
[4] |
Yuntao Zang. An upper bound of the measure-theoretical entropy. Discrete and Continuous Dynamical Systems, 2022 doi: 10.3934/dcds.2022052 |
[5] |
Xueling Zhou, Meixia Li, Haitao Che. Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2557-2572. doi: 10.3934/jimo.2020082 |
[6] |
Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 |
[7] |
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 |
[8] |
Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems and Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 |
[9] |
Alain Miranville, Xiaoming Wang. Upper bound on the dimension of the attractor for nonhomogeneous Navier-Stokes equations. Discrete and Continuous Dynamical Systems, 1996, 2 (1) : 95-110. doi: 10.3934/dcds.1996.2.95 |
[10] |
Gang Meng. The optimal upper bound for the first eigenvalue of the fourth order equation. Discrete and Continuous Dynamical Systems, 2017, 37 (12) : 6369-6382. doi: 10.3934/dcds.2017276 |
[11] |
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 |
[12] |
S. E. Kuznetsov. An upper bound for positive solutions of the equation \Delta u=u^\alpha. Electronic Research Announcements, 2004, 10: 103-112. |
[13] |
Naoufel Ben Abdallah, Irene M. Gamba, Giuseppe Toscani. On the minimization problem of sub-linear convex functionals. Kinetic and Related Models, 2011, 4 (4) : 857-871. doi: 10.3934/krm.2011.4.857 |
[14] |
Gaurav Nagpal, Udayan Chanda, Nitant Upasani. Inventory replenishment policies for two successive generations price-sensitive technology products. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1629-1650. doi: 10.3934/jimo.2021036 |
[15] |
Mrinal Kanti Roychowdhury. Least upper bound of the exact formula for optimal quantization of some uniform Cantor distributions. Discrete and Continuous Dynamical Systems, 2018, 38 (9) : 4555-4570. doi: 10.3934/dcds.2018199 |
[16] |
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 |
[17] |
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 |
[18] |
Mourad Choulli. Local boundedness property for parabolic BVP's and the Gaussian upper bound for their Green functions. Evolution Equations and Control Theory, 2015, 4 (1) : 61-67. doi: 10.3934/eect.2015.4.61 |
[19] |
Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070 |
[20] |
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 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]