Abstract
The Weber location problem is a fundamental optimization task with applications ranging from facility location to machine learning. However, when generalized using the $q$-th powered $\ell_p$-norm, the problem encounters "singularities" where traditional gradient-based algorithms fail. This is particularly problematic for $1 \le p < 2$, where singular points form an infinite continuum. This paper introduces a novel de-singularity subgradient and a robust version of the Weiszfeld algorithm ($qPpNWAWS$) designed to navigate these regions. We demonstrate that our approach achieves linear convergence and enhances financial portfolio selection strategies on real-world datasets.
Introduction: The Singularity Challenge
The Weber location problem involves finding a central point $x_*$ that minimizes the weighted sum of distances to a set of $m$ data points. While conceptually straightforward, the problem becomes mathematically complex when using the $q$-th powered $\ell_p$-norm.
For $1 \le p < 2$, the objective function's gradient becomes singular—either non-existent or infinite—at certain points. In the standard Euclidean case ($p=2$), these singularities are isolated points. However, for $p < 2$, they form a dense, infinite continuum of hyperplanes. Standard optimization methods often "get stuck" or fail to converge when encountering these singular regions.
Methodology: The qPpNWAWS Algorithm
To address these challenges, we propose a two-part solution:
- De-singularity Subgradient: We derive a new subgradient that mathematically isolates and "removes" singular components. This allows for the calculation of a valid descent direction even when the current estimate lies on a singular hyperplane.
- qPpNWAWS Algorithm: The "$q$-th-powered $\ell_p$-norm Weiszfeld Algorithm without Singularity" adaptively switches between standard fixed-point updates and de-singularity subgradient steps. If a singular point is reached, the algorithm uses the subgradient to find a descent direction and a line search to "escape" the singularity.
We provide a rigorous proof of convergence, ensuring that the algorithm reaches the global minimum even after multiple encounters with singular regions.
Experimental Setup and Datasets
The algorithm's performance was evaluated using six real-world financial datasets. The Weber location problem was applied to calculate "median" asset prices for Online Portfolio Selection (OPS):
- CSI300: 47 assets from the Chinese market (Daily).
- NYSE(N): 23 assets from the US market (Daily).
- FTSE100: 83 assets from the UK market (Weekly).
- NASDAQ100: 82 assets from the US market (Weekly).
- FF100 & FF100MEOP: 100 assets from US portfolios (Monthly).
Key Results
The $qPpNWAWS$ algorithm demonstrated high efficiency and robustness across all test cases.
- Singularity Resolution: The algorithm successfully reduced the cost function at singular points where traditional methods failed. In practice, it typically required fewer than 5 iterations to escape a singularity.
- Computational Efficiency: Average running times remained under 0.03 seconds, with most problems converging in under 36 iterations, confirming the algorithm's suitability for high-frequency financial data.
- Portfolio Performance: By optimizing $p$ and $q$ values, we identified configurations that significantly outperformed traditional Euclidean medians. For example, on the CSI300 dataset, the setting $(q=1, p=1.6)$ yielded higher Cumulative Wealth and Sharpe Ratios.
Discussion and Insights
The core insight of this work is that the infinite singular continuum present when $p < 2$ is manageable through precise subgradient characterization. By mapping out the geometric complexity of the $q$-th powered $\ell_p$ norm for $1 \le q \le p$ and $1 \le p < 2$, we proved that random "jumps" are unnecessary; a calculated path through singularities is possible. Despite the lack of Lipschitz continuity at singular points, the algorithm maintains a linear computational convergence rate in real-world scenarios.
Limitations and Future Work
Currently, this research focuses on the single-facility location problem. Many logistics and network design applications require finding multiple optimal locations simultaneously. Future work will extend the de-singularity methodology to the multi-facility location problem, which involves even more complex singular set interactions. Additionally, developing automated methods for hyperparameter ($p, q$) selection remains an open area for investigation.
Summary updated