Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2508.16561 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914001068228608 |
|---|---|
| author | Cao, Liyuan Hu, Wei Wang, Jinxin |
| author_facet | Cao, Liyuan Hu, Wei Wang, Jinxin |
| contents | Simplex-type methods, such as the well-known Nelder-Mead algorithm, are widely used in derivative-free optimization (DFO), particularly in practice. Despite their popularity, the theoretical understanding of their convergence properties has been limited, and until very recently essentially no worst-case complexity bounds were available. Recently, Cao et al. provided a sharp error bound for linear interpolation and extrapolation and derived a worst-case complexity result for a basic simplex-type method. Motivated by this, we propose a practical and provable algorithm -- the regular simplicial search method (RSSM), that incorporates reflection and shrinking steps, akin to the original method of Spendley et al. We establish worst-case complexity bounds in nonconvex, convex, and strongly convex cases. These results provide guarantees on convergence rates and lay the groundwork for future complexity analysis of more advanced simplex-type algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_16561 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity Analysis of the Regular Simplicial Search Method with Reflection and Shrinking Steps for Derivative-Free Optimization Cao, Liyuan Hu, Wei Wang, Jinxin Optimization and Control Simplex-type methods, such as the well-known Nelder-Mead algorithm, are widely used in derivative-free optimization (DFO), particularly in practice. Despite their popularity, the theoretical understanding of their convergence properties has been limited, and until very recently essentially no worst-case complexity bounds were available. Recently, Cao et al. provided a sharp error bound for linear interpolation and extrapolation and derived a worst-case complexity result for a basic simplex-type method. Motivated by this, we propose a practical and provable algorithm -- the regular simplicial search method (RSSM), that incorporates reflection and shrinking steps, akin to the original method of Spendley et al. We establish worst-case complexity bounds in nonconvex, convex, and strongly convex cases. These results provide guarantees on convergence rates and lay the groundwork for future complexity analysis of more advanced simplex-type algorithms. |
| title | Complexity Analysis of the Regular Simplicial Search Method with Reflection and Shrinking Steps for Derivative-Free Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.16561 |