-
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. 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. |
[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. 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. |
[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] |
Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 |
[2] |
Helin Guo, Huan-Song Zhou. Properties of the minimizers for a constrained minimization problem arising in Kirchhoff equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1023-1050. doi: 10.3934/dcds.2020308 |
[3] |
Weinan E, Weiguo Gao. Orbital minimization with localization. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 249-264. doi: 10.3934/dcds.2009.23.249 |
[4] |
Gaojun Luo, Xiwang Cao. Two classes of near-optimal codebooks with respect to the Welch bound. Advances in Mathematics of Communications, 2021, 15 (2) : 279-289. doi: 10.3934/amc.2020066 |
[5] |
Xiaoming Wang. Upper semi-continuity of stationary statistical properties of dissipative systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 521-540. doi: 10.3934/dcds.2009.23.521 |
[6] |
Joan Carles Tatjer, Arturo Vieiro. Dynamics of the QR-flow for upper Hessenberg real matrices. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1359-1403. doi: 10.3934/dcdsb.2020166 |
[7] |
Rim Bourguiba, Rosana Rodríguez-López. Existence results for fractional differential equations in presence of upper and lower solutions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1723-1747. doi: 10.3934/dcdsb.2020180 |
[8] |
Alessandro Fonda, Rodica Toader. A dynamical approach to lower and upper solutions for planar systems "To the memory of Massimo Tarallo". Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021012 |
[9] |
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 |
[10] |
Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021001 |
[11] |
Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
[12] |
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, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269 |
[13] |
Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 |
[14] |
Bao Wang, Alex Lin, Penghang Yin, Wei Zhu, Andrea L. Bertozzi, Stanley J. Osher. Adversarial defense via the data-dependent activation, total variation minimization, and adversarial training. Inverse Problems & Imaging, 2021, 15 (1) : 129-145. doi: 10.3934/ipi.2020046 |
[15] |
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 |
[16] |
Yanjun He, Wei Zeng, Minghui Yu, Hongtao Zhou, Delie Ming. Incentives for production capacity improvement in construction supplier development. Journal of Industrial & Management Optimization, 2021, 17 (1) : 409-426. doi: 10.3934/jimo.2019118 |
[17] |
Hong Fu, Mingwu Liu, Bo Chen. Supplier's investment in manufacturer's quality improvement with equity holding. Journal of Industrial & Management Optimization, 2021, 17 (2) : 649-668. doi: 10.3934/jimo.2019127 |
[18] |
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 |
[19] |
Kevin Li. Dynamic transitions of the Swift-Hohenberg equation with third-order dispersion. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2021003 |
[20] |
Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020389 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]