Rank-two update algorithm versus Frank-Wolfe algorithm with away steps for the weighted Euclidean one-center problem. (English) Zbl 1433.90130

Cong, Wei-Jie; Wang, Le; Sun, Hui

Comput. Optim. Appl. 75, No. 1, 237-262 (2020).

Summary: The weighted Euclidean one-center (WEOC) problem is one of the classic problems in facility location theory, which is also a generalization of the minimum enclosing ball (MEB) problem. Given \(m\) points in \({\mathbb{R}}^n \), the WEOC problem computes a center point \(c\in{\mathbb{R}}^n\) that minimizes the maximum weighted Euclidean distance to \(m\) given points. The rank-two update algorithm is an effective method for solving the minimum volume enclosing ellipsoid (MVEE) problem. It updates only two components of the solution at each iteration, which was previously proposed in [W.-j. Cong et al., Comput. Optim. Appl. 51, No. 1, 241–257 (2012; Zbl 1270.90072)]. In this paper, we further develop and analyze the rank-two update algorithm for solving the WEOC problem. At each iteration, the calculation of the optimal step-size for the WEOC problem needs to distinguish four different cases, which is a challenge in comparison with the MVEE problem. We establish the theoretical results of the complexity and the core set size of the rank-two update algorithm for the WEOC problem, which are the generalizations of the currently best-known results for the MEB problem. In addition, by constructing an important inequality for the WEOC problem, we establish the linear convergence of this rank-two update algorithm. Numerical experiments show that the rank-two update algorithm is comparable to the Frank-Wolfe algorithm with away steps for the WEOC problem. In particular, the rank-two update algorithm is more efficient than the Frank-Wolfe algorithm with away steps for problem instances with \(m\gg n\) under high precision.

MSC:

90C27	Combinatorial optimization
90B80	Discrete location and assignment

Keywords:

weighted Euclidean one-center; minimum enclosing ball; minimum volume enclosing ellipsoid; rank-two update algorithm; linear convergence; Frank-Wolfe algorithm with away steps

Citations:

Zbl 1270.90072

References:

[1]	Ahipasaoglu, Sd; Sun, P.; Todd, Mj, Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids, Optim. Methods Softw., 23, 1, 5-19 (2008) · Zbl 1146.90047
[2]	Ahipasaoglu, Sd; Yıldırım, Ea, Identification and elimination of interior points for the minimum enclosing ball problem, SIAM J. Optim., 19, 3, 1392-1396 (2008) · Zbl 1180.90232
[3]	Brimberg, J., The Fermat-Weber location problem revisited, Math. Program., 71, 1, 71-76 (1995) · Zbl 0855.90075
[4]	Bǎdoiu, M.; Clarkson, Kl, Optimal core-sets for balls, Comput. Geom. Theory Appl., 40, 1, 14-22 (2008) · Zbl 1138.68056
[5]	Berger, A.; Grigoriev, A.; Winokurow, A., An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions, Comput. Optim. Appl., 68, 3, 661-669 (2017) · Zbl 1392.90095
[6]	Chandrasekaran, R., The weighted Euclidean 1-center problem, Oper. Res. Lett., 1, 3, 111-112 (1982) · Zbl 0487.90048
[7]	Cong, W-J; Liu, H-W; Ye, F.; Zhou, S-S, Rank-two update algorithms for the minimum volume enclosing ellipsoid problem, Comput. Optim. Appl., 51, 1, 241-257 (2012) · Zbl 1270.90072
[8]	Drezner, Z.; Gavish, B., \( \epsilon \)-approximations for multidimensional weighted location problems, Oper. Res., 33, 4, 772-783 (1985) · Zbl 0575.90021
[9]	Drezner, Z.; Wesolowsky, Go, Single facility \(l_p\)-distance minimax location, SIAM J. Algebr. Discrete Methods, 1, 3, 315-321 (1980) · Zbl 0501.90031
[10]	Francis, Rl, Letter to the editor-some aspects of a minimax location problem, Oper. Res., 15, 6, 1163-1169 (1967)
[11]	Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logist. Q., 3, 1-2, 95-110 (1956)
[12]	Hakimi, Sl, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res., 12, 3, 450-459 (1964) · Zbl 0123.00305
[13]	Hearn, D.; Lowe, Tj, A subgradient procedure for the solution of minimax location problems, Comput. Ind. Eng., 2, 1, 17-25 (1978)
[14]	Hansen, P.; Peeters, D.; Richard, D.; Thisse, Jf, The minisum and minimax location problems revisited, Oper. Res., 33, 6, 1251-1265 (1985) · Zbl 0582.90027
[15]	Kuhn, Hw; Abadie, J., On a pair of dual nonlinear programs, Nonlinear Programming, 37-54 (1967), Amsterdam: North-Holland, Amsterdam · Zbl 0183.22804
[16]	Kumar, P.; Yıldırım, Ea, Minimum-volume enclosing ellipsoids and core sets, J. Optim. Theory Appl., 126, 1, 1-21 (2005) · Zbl 1093.90039
[17]	Kumar, P.; Yıldırım, Ea, An algorithm and a core set result for the weighted Euclidean one-center problem, INFORMS J. Comput., 21, 4, 614-629 (2009) · Zbl 1243.90098
[18]	Megiddo, N., The weighted Euclidean 1-center problem, Math. Oper. Res., 8, 4, 498-504 (1983) · Zbl 0533.90030
[19]	\( \tilde{\text{N}}\) anculef, R., Frandi, E., Sartori, C., Allende, H.: A novel Frank-Wolfe algorithm. Inf. Sci. 285, 66-99 (2014) · Zbl 1355.68234
[20]	Platt, J.; Schölkopf, B.; Burges, Cjc; Smola, Aj, Fast training of support vector machines using sequential minimal optimization, Kernel Methods-Support Vector Learning, 185-208 (1999), Cambridge: MIT Press, Cambridge
[21]	Pronzato, L., On the elimination of inessential points in the smallest enclosing ball problem, Optim. Methods Softw., 34, 2, 225-247 (2019) · Zbl 1407.90257
[22]	Robinson, Sm, Generalized equations and their solutions, part II: applications to nonlinear programming, Math. Program. Study, 19, 200-221 (1982) · Zbl 0495.90077
[23]	Sun, P.; Freund, Rm, Computation of minimum-volume covering ellipsoids, Oper. Res., 52, 5, 690-706 (2004) · Zbl 1165.90571
[24]	Todd, Mj; Yıldırım, Ea, On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids, Discrete Appl. Math., 155, 13, 1731-1744 (2007) · Zbl 1151.90516
[25]	Wolfe, P.; Abadie, J., Convergence theory in nonlinear programming, Integer and Nonlinear Programming, 1-36 (1970), Amsterdam: North-Holland, Amsterdam · Zbl 0336.90045
[26]	Wagner, F., Wolff, A.: A combinatorial framework for map labeling. In: International Symposium on Graph Drawing. LNCS, vol. 1547, pp. 316-331. Springer, Berlin (1998)
[27]	Yıldırım, Ea, Two algorithms for the minimum enclosing ball problem, SIAM J. Optim., 19, 3, 1368-1391 (2008) · Zbl 1180.90240