Research map / Optimization / Nonconvex and smooth optimization
De-singularity Subgradient for the q-th-Powered lₚ-Norm Weber Location Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes qPpNWAWS, a de-singularity subgradient Weiszfeld-style algorithm for the q-th-powered lp-norm Weber location problem with 1<=q<=p<2, and applies it to online portfolio selection median computation on six financial datasets.
Problem
The q-th-powered lp-norm Weber location problem (qPpNWLP) has a gradient that does not exist on a continuum of singular points when 1<=p<2, so gradient-type methods such as the Weiszfeld algorithm can get stuck; prior de-singularity work only covered p=2.
Approach
Defines a de-singularity subgradient that removes the singular terms at each singular coordinate, characterizes subgradients and minima at singular points, and uses a line-searched descent step along this direction when the iterate is singular and a Weiszfeld-style update otherwise, guaranteeing monotone decrease of the cost.
Key results
- On CSI300, average iterations to reduce cost at a singular point range from 4.92 at (q,p)=(1,1) to 1.95 at (1.9,1.9).
- Average computational convergence rate decreases from about 0.8 to 0.09 on CSI300 as p and q increase, indicating at least linear convergence.
- In online portfolio selection, (q,p)=(1,1.6) gives the best cumulative wealth 2.0932 on CSI300 versus 1.7750 for the original (1,2) setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use q=1.0 and p=1.6 instead of the original q=1, p=2 setting (ablation) | qPpNWAWS in the OPS median-reversion strategy · CSI300 OPS | cumulative wealth: 1.7750 -> 2.0932 | Helped |
| Use q=1.0 and p=1.6 instead of the original q=1, p=2 setting (ablation) | qPpNWAWS in the OPS median-reversion strategy · CSI300 OPS | Sharpe ratio: 0.0479 -> 0.0574 | Helped |
| Use q=1.3 and p=1.9 instead of the original q=1, p=2 setting (ablation) | qPpNWAWS in the OPS median-reversion strategy · NYSE(N) OPS | cumulative wealth: 3.3183e+08 -> 8.5677E+08 | Helped |
| Use q=1.3 and p=1.9 instead of the original q=1, p=2 setting (ablation) | qPpNWAWS in the OPS median-reversion strategy · NYSE(N) OPS | Sharpe ratio: 0.1034 -> 0.1075 | Helped |
| Increase q and p from 1.0 to 1.9 (ablation) | qPpNWAWS · CSI300 | average iterations to reduce cost at a singular point: 4.92\pm 0.29 -> 1.95 \pm0.23 | Helped |
| Increase q and p from 1.0 to 1.9 (ablation) | qPpNWAWS · NYSE(N) | average iterations to reduce cost at a singular point: 3.91\pm0.60 -> 1.45 \pm0.50 | Helped |
| Increase q and p from 1.0 to 1.9 (ablation) | qPpNWAWS · CSI300 | average iterations to convergence: 35.93\pm15.04 -> 7.19 \pm0.41 | Helped |
| Increase q and p from 1.0 to 1.9 (ablation) | qPpNWAWS · NYSE(N) | average iterations to convergence: 26.71\pm15.93 -> 6.50 \pm0.89 | Helped |
| Increase q and p from 1.0 to 1.9 (ablation) | qPpNWAWS · CSI300 | computational convergence rate: 0.80 -> 0.09 | Helped |
Surprising findings
- Counterexample shows the gradient of the cost is not Lipschitz even at nonsingular points, so standard constant-step subgradient descent cannot achieve O(1/k) rates.
Limitations
- Theoretical convergence analysis for the 1<p<2 case; the p=1 case has only non-unique minima and is handled differently.
- Convergence rate is shown empirically rather than proven.
- Experiments are limited to portfolio-selection datasets.
Experimental setup
Datasets: CSI300 NYSE(N) FTSE100 NASDAQ100 FF100 FF100MEOP
Benchmarks: CSI300 NYSE(N) FTSE100 NASDAQ100 FF100 FF100MEOP
Metrics: iterations running time computational convergence rate cumulative wealth Sharpe ratio
Baselines: pNWA original setting (q,p)=(1,2)
Builds on: Weiszfeld algorithm qPWAWS
Closest papers by meaning
- Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints (ICML 2020 · similarity 0.84)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.82)
- Two-timescale Extragradient for Finding Local Minimax Points (ICLR 2024 · similarity 0.82)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.81)
- On the Convergence of Projected Bures-Wasserstein Gradient Descent under Euclidean Strong Convexity (ICML 2024 · similarity 0.81)
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.