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