De-singularity Subgradient for the q q -th-Powered ℓ p \ell_{p} -Norm Weber Location Problem

Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen, Cheng Li · 2024

Read De-singularity Subgradient for the q q -th-Powered ℓ p \ell_{p} -Norm Weber Location Problem by Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen, Cheng Li (2024) 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-2412-15546.txt.

Introduction

Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen, and Cheng Li extend a method for the Weber location problem in two thousand twenty-four. The problem picks the best site for a facility by weighing distance to a set of demand points. Its cost curve has kinks where the slope does not exist, which stalls standard methods.

A past fix handled only one norm and a narrow power range, with few kink points. The new work covers the rest of the range, where the kink set forms a full continuum and the shape is far more complex. Their algorithm, built on a classic update rule, is shown to descend and converge. Tests on six real data sets show a fast, steady rate in practice.

Catalog record

CREATORZhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen, Cheng Li
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15546

Browse the full library · About the Tower of Babel

Full text

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

De-singularity Subgradient for the q q -th-Powered ℓ p \ell_{p} -Norm Weber Location Problem Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen, Cheng Li Abstract The Weber location problem is widely used in several artificial intelligence scenarios. However, the gradient of the objective does not exist at a considerable set of singular points. Recently, a de-singularity subgradient method has been proposed to fix this problem, but it can only handle the q q -th-powered ℓ 2 \ell_{2} -norm case ( 1 ⩽ q < 2 1\leqslant q<2 ), which has only finite singular points. In this paper, we further establish the de-singularity subgradient for the q q -th-powered ℓ p \ell_{p} -norm case with 1 ⩽ q ⩽ p 1\leqslant q\leqslant p and 1 ⩽ p < 2 1\leqslant p<2 , which includes all the rest unsolved situations in this problem. This is a challenging task because the singular set is a continuum. The geometry of the objective function is also complicated so that the characterizations of the subgradients, minimum and descent direction are very difficult. We develop a q q -th-powered ℓ p \ell_{p} -norm Weiszfeld Algorithm without Singularity ( q q P p p NWAWS) for this problem, which ensures convergence and the descent property of the objective function. Extensive experiments on six real-world data sets demonstrate that q q P p p NWAWS successfully solves the singularity problem and achieves a linear computational convergence rate in practical scenarios. 1 College of Cyber Security, Jinan University 2 Department of Mathematics, College of Information Science and Technology, Jinan University 3 Department of Computer Science, College of Information Science and Technology, Jinan University 4 Pazhou Laboratory 5 Research Institute of Multiple Agents and Embodied Intelligence, Peng Cheng Laboratory {laizhr, wxiaotian, fangld}@jnu.edu.cn, [email protected], [email protected] 1 Introduction The Weber location problem is a fundamental problem that is extensively investigated in artificial intelligence ( Lai et al. 2024 ) , machine learning ( Li, Sahoo, and Hoi 2016 ; Lai et al. 2018c ; Lai et al. 2020 ) , financial engineering ( Lai and Yang 2023 ) , computer vision ( Aftab, Hartley, and Trumpf 2015 ) , and operations research ( Ostresh 1978 ) . For a general definition, it seeks a point \bm{x}_{*} that minimizes the weighted sum of the q -th power of the \ell_{p} distances to m fixed data points \{\bm{x}_{i}\}_{i=1}^{m}\subseteq\mathbb{R}^{d} ( Weber 1909 ; Morris 1981 ; Chen 1984 ; Brimberg and Love 1993 ) , defined as the q -th-powered \ell_{p} -norm Weber location problem ( q P p NWLP) : \bm{x}_{*}\in\argmin_{\bm{y}\in\mathbb{R}^{d}}C_{p,q}(\bm{y}):=\sum_{i=1}^{m}\xi_{i}\|\bm{y}-\bm{x}_{i}\|_{p}^{q}, (1) where \xi_{i} denotes the weight for the i -th data point, \|\cdot\|_{p} denotes the \ell_{p} norm, C_{p,q}(\cdot) denotes the cost function related to the q -th power of the \ell_{p} norm, 1\leqslant q\leqslant p and p\geqslant 1 . Due to the same reasons as ( Lai et al. 2024 ) , we can assume that the data points \{\bm{x}_{i}\}_{i=1}^{m} are distinct and non-collinear in the rest of the paper. 1.1 The Singularity Problem 7 7 footnotetext: The supplementary material and codes for this paper are available at https://github.com/laizhr/qPpNWAWS . There is no closed-form solution to ( 1 ), and the gradient-type method is an intuitive and tractable approach. This approach includes those do not explicitly show a gradient form, like the Weiszfeld algorithm ( Brimberg and Love 1993 ) . To take a glimpse of the singularity problem, we first compute the gradient of the objective function C_{p,q} as \displaystyle\big(\nabla C_{p,q}(\bm{y})\big)^{(t)} \displaystyle{:=} \displaystyle{\sum_{i=1}^{m}}q\xi_{i}\|\bm{y}-\bm{x}_{i}\|_{p}^{q-p}|{y}^{(t)}-{x}_{i}^{(t)}|^{p-2}(y^{(t)}-{x}_{i}^{(t)}), (2) where \big(\nabla C_{p,q}(\bm{y})\big)^{(t)} denotes the t -th dimension ( 1\leqslant t\leqslant d ) of the gradient. Note that if q<p or p<2 , the singularity problem can occur if \bm{y} hits the following singular set: \begin{cases}\mathcal{S}_{p}{:=}\bigl\{\bm{y}{\in}\mathbb{R}^{d}|\exists i{\in}\{1,\dots,m\},t{\in}\{1,\dots,d\}\text{ s.t. }y^{(t)}{=}x_{i}^{(t)}\bigr\}\\ \qquad\qquad\qquad\qquad\qquad\qquad\text{if }1\leqslant p<2,\\ \mathcal{S}_{2}{:=}\{\bm{x}_{i}\}_{i=1}^{m}\qquad\qquad\qquad\text{if }1\leqslant q<2,p=2.\end{cases} (3) This singularity problem occurs frequently and unexpectedly. Chandrasekaran and Tamir (1989) ; Vardi and Zhang (2000) indicate that the “bad” points that can yield such singularity in a gradient-type method may constitute a continuum set that can be dense in an open region of \mathbb{R}^{d} ( d\geqslant 2 ) or even the entire \mathbb{R}^{d} . Moreover, this problem cannot be circumvented by straightforward treatments like perturbations and random restarts. More details can be found in ( Lai et al. 2024 ) . If q\geqslant p or p\geqslant 2 , the term \|\bm{y}-\bm{x}_{i}\|_{p}^{q-p} or |{y}^{(t)}-{x}_{i}^{(t)}|^{p-2} in ( 2 ) will not be singular. For p\geqslant 2 but 1\leqslant q<p , the singularity problem can be solved by ( Lai et al. 2024 ) . Hence this paper mainly focuses on the rest unsolved singular cases with the two key hyperparameters 1\leqslant q\leqslant p and 1\leqslant p<2 . Users can select any values of p and q within this range to suit their specific needs. As p approaches 2 , the distance between data points becomes closer to the Euclidean distance. Conversely, as p approaches 1 , the distance between data points becomes closer to the Manhattan distance, representing a typical non-Euclidean geometry. On the other hand, as q approaches p , the distance between data points gets higher power, which can be advantageous in certain computer vision tasks ( Aftab, Hartley, and Trumpf 2015 ) . In summary, allowing for a range of values for p and q enhances the geometrical representation of the Weber location problem. 1.2 Continuum Singular Set for 1\leqslant p<2 ( 3 ) indicates that when p=2 , the singularity only occurs at the m fixed data points \{\bm{x}_{i}\}_{i=1}^{m} . This case has already been completely solved by ( Vardi and Zhang 2000 ; Lai et al. 2024 ) . However, when 1\leqslant p<2 , the singularity occurs in at most m\cdot d hyperplanes that encompass a continuum set of points, which is much more difficult than the p=2 case and no solutions have been developed (see Figure 1 ) . The difficulties lie in the following three aspects: 1. An effective gradient-type algorithm may visit each singular point for only once. But since there are infinite singular points when 1\leqslant p<2 , the algorithm may visit the singular set for infinite times. 2. Based on the first point, there is no unified step size for the escape from the singular set, which affects the convergence property. 3. The geometry of the objective function is complicated when 1\leqslant q\leqslant p and 1\leqslant p<2 so that the characterizations of the subgradients, minimum and descent direction are very difficult, which also affects the convergence property. (a) p=2 and 1\leqslant q<2 (b) 1\leqslant p<2 Figure 1: (a) When p=2 , the singular set \mathcal{S}_{2} (the red dots) is finite and an effective gradient-type algorithm visits each singular point for only once. Hence the iterate \bm{y}_{(k)} (the circle) can finally escape from all the singular points. (b) When 1\leqslant p<2 , the singular set \mathcal{S}_{p} is a continuum (the red dashed lines), hence the iterate \bm{y}_{(k)} may revisit \mathcal{S}_{p} for infinite times and may not escape from \mathcal{S}_{p} . To address the above difficulties, we develop a complete de-singularity subgradient methodology for q P p NWLP with 1\leqslant q\leqslant p and 1\leqslant p<2 , including all the rest unsolved situations in this problem. Our main contributions are summarized as follows. 1. We develop a

Read the complete text