Parallel Polyhedral Projection Method for the Convex Feasibility Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916811455332352 |
|---|---|
| author | Barros, Pablo Behling, Roger Guigues, Vincent |
| author_facet | Barros, Pablo Behling, Roger Guigues, Vincent |
| contents | In this paper, we introduce and study the Parallel Polyhedral Projection Method (3PM) and the Approximate Parallel Polyhedral Projection Method (A3PM) for finding a point in the intersection of finitely many closed convex sets. Each iteration has two phases: parallel projections onto the target sets (exact in 3PM, approximate in A3PM), followed by an exact or approximate projection onto a polyhedron defined by supporting half-spaces. These strategies appear novel, as existing methods largely focus on parallel schemes like Cimmino's method. Numerical experiments demonstrate that A3PM often outperforms both classical and recent projection-based methods when the number of sets is greater than two. Theoretically, we establish global convergence for both 3PM and A3PM without regularity assumptions. Under a Slater condition or error bound, we prove linear convergence, even with inexact projections. Additionally, we show that 3PM achieves superlinear convergence under suitable geometric assumptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15895 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parallel Polyhedral Projection Method for the Convex Feasibility Problem Barros, Pablo Behling, Roger Guigues, Vincent Optimization and Control 49M27, 65K05, 65B99, 90C25 In this paper, we introduce and study the Parallel Polyhedral Projection Method (3PM) and the Approximate Parallel Polyhedral Projection Method (A3PM) for finding a point in the intersection of finitely many closed convex sets. Each iteration has two phases: parallel projections onto the target sets (exact in 3PM, approximate in A3PM), followed by an exact or approximate projection onto a polyhedron defined by supporting half-spaces. These strategies appear novel, as existing methods largely focus on parallel schemes like Cimmino's method. Numerical experiments demonstrate that A3PM often outperforms both classical and recent projection-based methods when the number of sets is greater than two. Theoretically, we establish global convergence for both 3PM and A3PM without regularity assumptions. Under a Slater condition or error bound, we prove linear convergence, even with inexact projections. Additionally, we show that 3PM achieves superlinear convergence under suitable geometric assumptions. |
| title | Parallel Polyhedral Projection Method for the Convex Feasibility Problem |
| topic | Optimization and Control 49M27, 65K05, 65B99, 90C25 |
| url | https://arxiv.org/abs/2506.15895 |