Rank-two update algorithm versus Frank–Wolfe algorithm with away steps for the weighted Euclidean one-center problem

Wei-jie Cong (), Le Wang and Hui Sun
Additional contact information
Wei-jie Cong: Xi’an University of Posts and Telecommunications
Le Wang: Xi’an University of Posts and Telecommunications
Hui Sun: Xi’an University of Posts and Telecommunications

Computational Optimization and Applications, 2020, vol. 75, issue 1, No 9, 237-262

Abstract: Abstract 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}$$Rn, the WEOC problem computes a center point $$c\in {\mathbb {R}}^{n}$$c∈Rn 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 Cong et al. (Comput Optim Appl 51(1):241–257, 2012). 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$$m≫n under high precision.

Keywords: Weighted Euclidean one-center; Minimum enclosing ball; Minimum volume enclosing ellipsoid; Rank-two update algorithm; Linear convergence; Frank–Wolfe algorithm with away steps (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-019-00148-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:75:y:2020:i:1:d:10.1007_s10589-019-00148-z

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-019-00148-z

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().