Fast projection onto the top-k-sum constraint
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915668316651520 |
|---|---|
| author | Pan, Jianting Yan, Ming |
| author_facet | Pan, Jianting Yan, Ming |
| contents | This paper develops an efficient algorithm for computing the Euclidean projection onto the top-k-sum constraint, a key operation in financial risk management and matrix optimization problems. Existing projection methods rely on sorting and therefore incur an initial O(nlogn) complexity, which limits their scalability in high-dimensional settings. To address this difficulty, we revisit the Karush-Kuhn-Tucker (KKT) conditions of the projection problem and introduce relaxed conditions that remain sufficient for characterizing the solution. These conditions lead to a simple geometric interpretation: finding the solutions is equivalent to locating the intersection of two monotone piecewise linear functions. Building on this insight, we propose an iterative and highly efficient algorithm that searches directly for the intersection point and completely avoids all sorting procedures. We prove that the algorithm converges globally and reaches the exact solution in a finite number of iterations. Extensive numerical experiments further demonstrate that the proposed algorithm substantially outperforms existing algorithms and exhibits empirical O(n) complexity across a broad range of problem instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_10255 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast projection onto the top-k-sum constraint Pan, Jianting Yan, Ming Optimization and Control 65K10, 90-04, 90-08, 90C06, 90C25 This paper develops an efficient algorithm for computing the Euclidean projection onto the top-k-sum constraint, a key operation in financial risk management and matrix optimization problems. Existing projection methods rely on sorting and therefore incur an initial O(nlogn) complexity, which limits their scalability in high-dimensional settings. To address this difficulty, we revisit the Karush-Kuhn-Tucker (KKT) conditions of the projection problem and introduce relaxed conditions that remain sufficient for characterizing the solution. These conditions lead to a simple geometric interpretation: finding the solutions is equivalent to locating the intersection of two monotone piecewise linear functions. Building on this insight, we propose an iterative and highly efficient algorithm that searches directly for the intersection point and completely avoids all sorting procedures. We prove that the algorithm converges globally and reaches the exact solution in a finite number of iterations. Extensive numerical experiments further demonstrate that the proposed algorithm substantially outperforms existing algorithms and exhibits empirical O(n) complexity across a broad range of problem instances. |
| title | Fast projection onto the top-k-sum constraint |
| topic | Optimization and Control 65K10, 90-04, 90-08, 90C06, 90C25 |
| url | https://arxiv.org/abs/2512.10255 |