{"ID":2879541,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.16561","arxiv_id":"2508.16561","title":"Complexity Analysis of the Regular Simplicial Search Method with Reflection and Shrinking Steps for Derivative-Free Optimization","abstract":"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.","short_abstract":"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 boun...","url_abs":"https://arxiv.org/abs/2508.16561","url_pdf":"https://arxiv.org/pdf/2508.16561v1","authors":"[\"Liyuan Cao\",\"Wei Hu\",\"Jinxin Wang\"]","published":"2025-08-22T17:29:21Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}