Minimizing differences of convex functions with applications to facility location and clustering (Q2401517)

The authors consider the weighted Fermat-Torricelli problem, that is, the problem of minimizing an averaged sum of distances to a finite number of points in \(\mathbb{R}^{n}\), with both positive and negative weights. The distance involved does not need to be a genuine distance as, rather than being induced by a norm, it is actually generated by the Minkowski gauge of a compact convex set containing the origin in its interior. The presence of negative weights makes the problem nonconvex; more specifically, the objective function is DC (that is, a difference of convex functions). To solve the problem, following an approach initiated by \textit{Le Thi Hoai An} et al. [J. Glob. Optim. 37, No. 4, 593--608 (2007; Zbl 1198.90327)] for clustering problems, the authors develop numerical methods based on the difference of convex functions algorithm (DCA) due to \textit{Pham Dinh Tao} and \textit{S. El Bernoussi} [in: Fermat days 85: Mathematics for optimization, Toulouse/France 1985, North-Holland Math. Stud. 129, 249--271 (1986; Zbl 0638.90087)], which they combine with the \textit{Yu. Nesterov} smoothing technique [Math. Program. 103, No. 1 (A), 127--152 (2005; Zbl 1079.90102)]. They also propose the DCA to solve a set clustering problem, consisting in finding the points \(x^{1},\dots,x^{k}\in \mathbb{R}^{n}\) that minimize \( \sum\limits_{i=1}^{m}\min_{i=1,\dots,l}[d(x^{l};\Omega ^{i})]^{2},\) the sets \( \Omega ^{i}\subset \mathbb{R}^{n}\) being nonempty, convex and closed and \(d\) denoting the Euclidean distance;\ the DC decomposition considered for this objective function is based on the equality \(\min_{i=1,...,l}[d(x^{l};\Omega ^{i})]^{2}=\sum\limits_{l=1}^{k}[d(x^{l};\Omega ^{i})]^{2}-\max_{r=1,\dots,k}\sum\limits_{l=1,l\neq r}^{k}[d(x^{l};\Omega ^{i})]^{2}\), with \(\sum\limits_{l=1}^{k}[d(x^{l};\Omega ^{i})]^{2}\) being further decomposed as \(\sum\limits_{l=1}^{k}\left\| x^{l}\right\| ^{2}-\sum\limits_{l=1}^{k}\varphi _{\Omega ^{i}}(x^{l})\); as proved in the paper, the functions \(\varphi _{\Omega ^{i}}:\mathbb{R}^{n}\rightarrow \mathbb{R}\) defined by \(\varphi _{\Omega ^{i}}(x):=\left\| x\right\| ^{2}-[d(x^{l};\Omega ^{i})]^{2}\) are convex and differentiable. Numerical examples are provided to illustrate the proposed algorithms. Another recent DC approach to facility location can be found in [\textit{A. Wagner} et al., J. Convex Anal. 23, No. 4, 1185--1204 (2016; Zbl 1354.49077)].