Polling Set Construction and Worst-Case Complexity for Direct Search under Polyhedral Convex Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914606789689344 |
|---|---|
| author | Roberts, Lindon Royer, Clément W. |
| author_facet | Roberts, Lindon Royer, Clément W. |
| contents | Direct search is one of the most popular derivative-free optimization paradigms, that relies on exploring the variable space using polling directions. To analyze and implement direct search, one typically relies on positive spanning sets. This concept is somewhat decorrelated from interpolation-based sets used in model-based algorithms, another class of derivative-free optimization methods. This discrepancy is even more pronounced for constrained problems, where recent advances in the interpolation-based setting have produced a unified picture that is still lacking in the direct-search case. In this paper, we introduce a new theoretical underpinning for direct-search methods, that can be defined for general convex constraints and lead to complexity guarantees, as in the model-based setting. By focusing on polyhedral convex constraints, we are able to construct polling sets that meet our new theoretical requirements. In particular, our polling sets necessarily include directions outside of the approximate tangent cone, giving theoretical justification to existing practical heuristics which incorporate this idea. Our numerical results confirm that adding these extra directions significantly improves practical performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_27814 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polling Set Construction and Worst-Case Complexity for Direct Search under Polyhedral Convex Constraints Roberts, Lindon Royer, Clément W. Optimization and Control Direct search is one of the most popular derivative-free optimization paradigms, that relies on exploring the variable space using polling directions. To analyze and implement direct search, one typically relies on positive spanning sets. This concept is somewhat decorrelated from interpolation-based sets used in model-based algorithms, another class of derivative-free optimization methods. This discrepancy is even more pronounced for constrained problems, where recent advances in the interpolation-based setting have produced a unified picture that is still lacking in the direct-search case. In this paper, we introduce a new theoretical underpinning for direct-search methods, that can be defined for general convex constraints and lead to complexity guarantees, as in the model-based setting. By focusing on polyhedral convex constraints, we are able to construct polling sets that meet our new theoretical requirements. In particular, our polling sets necessarily include directions outside of the approximate tangent cone, giving theoretical justification to existing practical heuristics which incorporate this idea. Our numerical results confirm that adding these extra directions significantly improves practical performance. |
| title | Polling Set Construction and Worst-Case Complexity for Direct Search under Polyhedral Convex Constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.27814 |