Solving Regularized Multifacility Location Problems with Unknown Number of Centers via Difference-of-Convex Optimization

W. Geremew, V. S. T. Long , N. M. Nam, A. Solano-Herrera · 2026

Read Solving Regularized Multifacility Location Problems with Unknown Number of Centers via Difference-of-Convex Optimization by W. Geremew, V. S. T. Long , N. M. Nam, A. Solano-Herrera (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16576.txt.

Introduction

W. Geremew, V. S. T. Long, N. M. Nam, and A. Solano-Herrera work on a hard math task. A firm must place sites, like depots or shops, to serve many users. The best count of sites is not known in advance. Their 2026 preprint builds a new model for this task.

The model adds a cost term that curbs needless sites. The team then finds a way to solve it step by step. They prove that best-fit answers do exist. They also study traits of those best answers. Tests on a screen back the math. The work may aid plans for stores, clinics, and charge points.

Catalog record

CREATORW. Geremew, V. S. T. Long , N. M. Nam, A. Solano-Herrera
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16576

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving Regularized Multifacility Location Problems with Unknown Number of Centers via Difference-of-Convex Optimization W. Geremew, V. S. T. Long , N. M. Nam, A. Solano-Herrera Abstract In this paper, we develop optimization methods for a new model of multifacility location problems defined by a Minkowski gauge with Laplace-type regularization terms. The model is analyzed from both theoretical and numerical perspectives. In particular, we establish the existence of optimal solutions and study qualitative properties of global minimizers. By combining Nesterov’s smoothing technique with recent advances in difference-of-convex optimization, following the pioneering work of P. D. Tao and L. T. H. An and others, we propose efficient numerical algorithms for minimizing the objective function of this model. As an application, our approach provides an effective method for determining the number of centers in gauge-based multifacility location and clustering problems. Our results extend and complement recent developments by L. T. H. An in [ 1 ] . Keywords: Multifacility location; clustering; Laplace-type regularization; Minkowski gauge; DC programming; DCA. Mathematics Subject Classification 49J52; 68Q25; 90C26; 90C90; 90C31; 90C35 1 Introduction The multifacility location problem aims to place several facilities in optimal locations to minimize the total distance to a set of demand points. These problems are closely related to clustering, which plays a central role in data analysis, signal processing, and machine learning. Given a finite collection of data points, the goal of a clustering problem is to identify a prescribed number of representative centers that capture the underlying structure of the data. Classical formulations, such as the k -means algorithm, typically rely on squared Euclidean distances and lead to nonconvex and nonsmooth optimization models. Their theoretical analysis and numerical solution have been extensively studied in the literature; see, for instance, [ 14 , 15 , 16 , 20 , 23 , 24 , 26 ] . Let F\subset\mathbb{R}^{d} be a fixed compact convex set containing the origin in its interior and let \rho_{F}\colon\mathbb{R}^{d}\to\mathbb{R} be its associated Minkowski gauge function defined by \rho_{F}(x)=\inf\{\lambda\geq 0\mid x\in\lambda F\}. (1) In this paper, we propose a new model of multifacility location and clustering based on generalized distances defined by Minkowski gauges and Laplace-type regularization terms. Consider a finite number of distinct data points a_{i} for i=1,\ldots,n in \mathbb{R}^{d} . We consider the optimization problem: \min_{X\in\mathbb{R}^{k\times d}}\Biggl\{f(X)=\sum_{i=1}^{n}\min_{1\leq\ell\leq k}\rho(x_{\ell}-a_{i})+\frac{\lambda n}{2}\sum_{1\leq s<t\leq k}\|x_{s}-x_{t}\|^{2}\Biggr\}, (2) where \lambda>0 is a regularization parameter and x_{\ell} denotes the \ell th row of the matrix variable X for \ell=1,\ldots,k . Here and throughout the paper we use \rho instead of \rho_{F} for simplicity. The first term measures the data fidelity through a generalized distance induced by \rho , while the second term is a quadratic fusion penalty that promotes closeness among cluster centers. where \lambda>0 is a parameter. In contrast to prior work that uses squared Euclidean losses for data fitting, our gauge optimization model allows us to solve problems of multifacility location and clustering, while the regularization term enhance stability, robustness, and interpretability. By controlling the parameter \lambda , the regularization term encourages nearby centers to contract. Therefore, our new model also allows us to determine the effective number of cluster centers in multifacility location. The use of a regularization term in clustering can be found, for example, in [ 1 , 11 , 17 , 18 , 22 , 23 ] . The main difficulty in solving problem ( 2 ) stems from the fact that its objective function is both nonsmooth and nonconvex. To address this challenge, we employ Nesterov’s smoothing technique (see [ 28 , 29 ] ) to approximate the generalized distance \rho(x_{\ell}-a_{i}) , which constitutes the data fidelity term of the objective function f , by a C^{1,1} function. This smooth approximation also enables us to express f as a difference of convex functions, making it amenable to difference-of-convex (DC) optimization methods. In particular, we apply the difference-of-convex algorithm (DCA) introduced by Tao and Souad [ 34 ] (see also [ 3 , 4 , 5 , 32 , 33 ] for further developments), together with its boosted variants from [ 7 , 8 ] . Our work builds on the successful use of DC programming in clustering, facility location, and related nonsmooth models developed in [ 1 , 2 , 7 , 8 , 9 , 26 , 27 ] . The main contributions of this paper include: • A new model of gauge multifacility location and clustering: We propose a new model of multifacility location and clustering based on generalized distances defined by Minkowski gauges and Laplace-type regularization terms as in ( 2 ). The model is applicable to multifacility location and, at the same time, extends classical clustering frameworks beyond standard Euclidean distances. • Qualitative analysis: We establish the existence of solutions and investigate qualitative properties of both global and local minimizers of the proposed problem. In particular, we analyze the compactness of the set of global solutions as well as the stability of the optimal value function and the associated solution mapping under data perturbations. • Advanced DC programming via Nesterov’s smoothing techniques: We establish an exact DC decomposition of the nonsmooth objective function f in ( 2 ) that is well suited for advanced optimization techniques in DC programming, including the DCA and its boosted variants. • Simultaneous clustering and model selection: We develop the LDCA-K algorithm, which incorporates an adaptive cluster deletion mechanism. This approach allows the model to identify the optimal number of clusters during the optimization process. Our results extend and complement recent developments by L. T. H. An in [ 1 ] . The paper is structured as follows. Section 2 provides the qualitative analysis including existence results. Section 3 discusses stability properties. Sections 4 and 5 are devoted to the DC programming framework and the LDCA-K algorithm. Convergence analysis and numerical results are presented in Sections 6 , and 7 . Our analysis is conducted entirely in finite-dimensional Euclidean spaces and relies on tools from convex analysis, variational analysis, and matrix spectral theory; see [ 12 , 25 , 30 , 31 ] and the references therein. Throughout the paper, we consider the Euclidean space \mathbb{R}^{d} equipped with the inner product \langle\cdot,\cdot\rangle and the Euclidean norm \|\cdot\| . The closed and open Euclidean balls with center a\in\mathbb{R}^{n} and radius R>0 are respectively defined by B[a;R]=\{x\in\mathbb{R}^{n}\mid\|x-a\|\leq R\}\quad\text{and}\quad B(a;R)=\{x\in\mathbb{R}^{n}\mid\|x-a\|<R\}, respectively. We also consider the space \mathbb{R}^{k\times d} of all k\times d real matrices equipped with the Frobenius norm . 2 The Existence of Solutions We begin this section by recalling some basic notions and definitions from convex analysis that will be employed throughout the paper. Definition 2.1 . Let \Omega be a nonempty subset of \mathbb{R}^{d} . (a) The distance function associated with \Omega is given by d(x;\Omega)=\inf\left\{\|x-w\|\mid w\in\Omega\right\},\quad x\in\mathbb{R}^{d}. (b) For any x\in\mathbb{R}^{d} , the Euclidean projection of x onto \Omega is given as the set P(x;\Omega)=\{\omega\in\Omega\mid\|x-\omega\|=d(x;\Omega)\}. The polar set F^{\circ} of a subset F\subset\mathbb{R}^{d} is defined by F^{\circ}=\{v\in\mathbb{R}^{d}\mid\langle v,x\rangle\leq 1\text{ for all }x\in F\}. To simplify our estimates, we denote the maximum norms associated with the set F and its polar F^{\circ} as: \|F\|=\sup\{\|x\|\mid x\in F\}\quad\text{and}\quad\|F^{\circ}\|=\sup\{\|v\|\mid v\in F^{\circ}\}. We will use the following properties concerning the Minkowski function in our subsequent analysis. These results can be found in [

Read the complete text