De-singularity Subgradient for the q-th-Powered ℓp-Norm Weber Location Problem.

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

TL;DR

This paper introduces a novel algorithm, qPpNWAWS, that effectively solves the q-th-powered ℓp-norm Weber location problem (qPpNWLP), even in challenging scenarios where the objective function's gradient is undefined. By developing a "de-singularity subgradient," the authors overcome a critical limitation in existing methods, enabling more robust and efficient solutions for a wide range of applications.

What Problem Does This Paper Address?

The Weber location problem, a fundamental task in fields like facility location and operations research, aims to find an optimal point that minimizes the weighted sum of distances to several fixed locations. A common formulation involves the q-th power of the ℓp-norm distance. However, a significant challenge arises when the objective function's gradient is undefined at certain "singular points." While previous work addressed this for the ℓ2-norm case, the more general ℓp-norm (with 1 < p < 2) presented a much harder problem because the set of singular points forms a continuum, making standard gradient-based methods fail or become inefficient. This paper tackles this difficult problem by developing a method that can handle these continuous singular sets.

Methods

The core contribution of this paper is the development of a q-th-powered ℓp-norm de-singularity subgradient. This novel concept allows the algorithm to navigate singular points without losing the descent property of the objective function. The authors then integrate this into a new algorithm called the q-th-Powered ℓp-Norm Weiszfeld Algorithm without Singularity (qPpNWAWS).

Key aspects of their approach include:

  • De-singularity Subgradient: This technique effectively "removes" the problematic singular components from the gradient calculation, allowing the algorithm to proceed even when the standard gradient doesn't exist.
  • Weiszfeld-Style Update: For non-singular points, the algorithm uses a standard Weiszfeld-style update that ensures the objective function decreases.
  • Singular Point Handling: When the algorithm encounters a singular point, it switches to using the de-singularity subgradient to compute a descent direction, ensuring progress towards the minimum.
  • Convergence Proof: The authors provide a rigorous mathematical proof for the convergence of their qPpNWAWS algorithm, demonstrating its theoretical soundness.

Datasets

The authors evaluated their proposed qPpNWAWS algorithm on six real-world datasets:

  • CSI300: A dataset derived from the constituents of the Shanghai and Shenzhen Stock Exchanges.
  • NYSE(N): A dataset from the New York Stock Exchange.
  • FTSE100: A dataset from the Financial Times Stock Exchange 100 Index.
  • NASDAQ100: A dataset from the Nasdaq 100 Index.
  • FF100: A dataset based on the Kenneth R. French's Data Library.
  • FF100MEOP: Another dataset from Kenneth R. French's Data Library, focusing on specific financial factors.

These datasets cover various regions, frequencies (daily, weekly, monthly), and dimensions (23 to 100), providing a comprehensive testbed for the algorithm's performance.

Key Insights and Ideas

  • Singular Sets are a Major Hurdle: The paper clearly illustrates why continuous singular sets in the ℓp-norm Weber location problem (1 < p < 2) are significantly more challenging than finite singular sets (p=2). The algorithm's ability to handle this continuum is a major breakthrough.
  • De-singularity is Key: The introduction of the "de-singularity subgradient" is the core innovation. It's not just about avoiding division by zero; it's about reformulating the problem locally to maintain a descent direction.
  • Unified Approach: The qPpNWAWS algorithm provides a unified framework that handles both singular and non-singular points seamlessly, avoiding the need for separate strategies or complex case distinctions within the iteration.
  • Practical Relevance: The algorithm's effectiveness is demonstrated not only in solving the optimization problem but also in a practical application (online portfolio selection), showing improved performance metrics.

Key Results

  • Successful Singularity Resolution: Experiments show that qPpNWAWS successfully reduces the cost function at singular iterates in a small number of iterations, effectively solving the singularity problem.
  • Rapid Convergence: The algorithm demonstrates fast convergence, with average running times generally below 0.03 seconds and iteration counts not exceeding 36 on the tested datasets.
  • Linear Convergence Rate: The paper verifies that qPpNWAWS achieves a linear computational convergence rate, which is considered efficient for practical applications.
  • Improved Performance in Portfolio Selection: In the context of online portfolio selection, qPpNWAWS, particularly with specific (q, p) pairs, achieved better cumulative wealth and Sharpe ratios compared to the original setting (q=1, p=2).

Limitations and Future Work

  • Limitations: The paper notes that a general constant-step subgradient descent method might not guarantee convergence in objective value due to varying step sizes. They also point out that the gradient might not be Lipschitz continuous even at non-singular points, which can complicate convergence analysis.
  • Future Work: The authors suggest extending their de-singularity methodology to the multi-facility location problem, indicating a promising avenue for future research.

Summary updated

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$-th-powered $\ell_2$-norm case ($1\leqslant q<2$), which has only finite singular points. In this paper, we further establish the de-singularity subgradient for the $q$-th-powered $\ell_p$-norm case with $1\leqslant q\leqslant p$ and $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$-th-powered $\ell_p$-norm Weiszfeld Algorithm without Singularity ($q$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$P$p$NWAWS successfully solves the singularity problem and achieves a linear computational convergence rate in practical scenarios.
BibTeX
@misc{lai2024de,
  author = {Zhao-Rong Lai and Xiaotian Wu and Liangda Fang and Ziliang Chen and Cheng Li},
  title = {{De-singularity Subgradient for the q-th-Powered ℓp-Norm Weber Location Problem.}},
  year = {2024},
  eprint = {2412.15546},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.15546},
}
Figure