Metraipolis › archive › dc_893d38e885cf
Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization — arXiv:2609.11567
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.11567
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T06:01:04.986Z
- SHA-256 of the archived text
8fd80a9c7e37a07a2dc1fd28c7a9e25b8ee1d629400003426aadc3695dcc293c- Stable URL of this page
https://metraipolis.com/documento/dc_893d38e885cf
How to cite
Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization — arXiv:2609.11567 — arXiv (en), https://arxiv.org/abs/2609.11567 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_893d38e885cf (Metraipolis archive dc_893d38e885cf, sha256 8fd80a9c7e37a07a2dc1fd28c7a9e25b8ee1d629400003426aadc3695dcc293c)
BibTeX
@misc{dc893d38e885cf,
title = {Non-monotone direct-search methods for deterministic and stochastic derivative-free optimization — arXiv:2609.11567},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.11567},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_893d38e885cf; sha256 8fd80a9c7e37a07a2dc1fd28c7a9e25b8ee1d629400003426aadc3695dcc293c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11567. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In derivative-free optimization (DFO), one minimizes functions for which the gradient is unavailable or expensive to compute. In many applications, objective function values and gradients are noisy due to simulations or system randomness. A class of standard direct-search methods for DFO accept a trial point when it decreases the objective function by an amount proportional to the squared stepsize. However, when applied to complex landscapes, such a requirement may trap the algorithm in a neighborhood of sub-optimal solutions. We study a non-monotone direct-search alternative where the trial function value is compared with the largest objective function obtained through the $M$ most recent distinct iterates. This max-$M$ non-monotone condition permits temporary increases in the objective function and can help navigate narrow curved valleys; however, its theoretical analysis is significantly more challenging due to the lack of monotonic decrease. In this paper, we develop a comprehensive complexity theory for the max-$M$ non-monotone direct-search in both deterministic and stochastic DFO problems. For deterministic objectives, we establish a worst-case iteration bound for a complete poll based on a positive spanning set and an expected iteration bound for a probabilistic-descent poll. We then analyze a stochastic variant using independent function estimates and show the expected iteration complexity under tail-bound assumptions of the stochastic errors. All three results have the standard complexity of $\mathcal{O}(\epsilon^{-2})$, which matches the iteration complexity of monotone direct-search methods. Our theory is enabled by a new family of merit functions that correct the stored objective values by ordered multiples of the squared stepsize, together with a renewal-reward stopping-time argument for the probabilistic methods.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-11 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.11567 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T05:52:41.417Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).