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

Zi Xu; Siwen Wang; Jinjin Huang

doi:10.3934/jimo.2020007

Article Contents

2021, Volume 17, Issue 2: 971-979. Doi: 10.3934/jimo.2020007

This issue Previous Article Designing prorated lifetime warranty strategy for high-value and durable products under two-dimensional warranty Next Article Optimal reinsurance-investment and dividends problem with fixed transaction costs

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
^* Corresponding author: Zi Xu

Received: September 2018

Revised: August 2019

Early access: January 2020

Published: March 2021

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

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C06, 90C26; Secondary: 93E10.

Citation:

Full Text(HTML)

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
$ n $	$ m $	CR	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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.