A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908603032535040 |
|---|---|
| author | Davar, Dânâ Grapiglia, Geovani Nunes |
| author_facet | Davar, Dânâ Grapiglia, Geovani Nunes |
| contents | We propose a derivative-free trust-region method based on finite-difference gradient approximations for smooth optimization problems with convex constraints. The proposed method does not require computing an approximate stationarity measure. For nonconvex problems, we establish a worst-case complexity bound of $\mathcal{O}\!\left(n\left(\tfrac{L}σε\right)^{-2}\right)$ function evaluations for the method to reach an $\left(\tfrac{L}σε\right)$-approximate stationary point, where $n$ is the number of variables, $L$ is the Lipschitz constant of the gradient, and $σ$ is a user-defined estimate of $L$. If the objective function is convex, the complexity to reduce the functional residual below $(L/σ)ε$ is shown to be of $\mathcal{O}\!\left(n\left(\tfrac{L}σε\right)^{-1}\right)$ function evaluations, while for Polyak-Lojasiewicz functions on unconstrained domains, the bound further improves to $\mathcal{O}\left(n\log\left(\left(\frac{L}σε\right)^{-1}\right)\right)$. Numerical experiments on benchmark problems and a model-fitting application demonstrate the method's efficiency relative to state-of-the-art derivative-free solvers for both unconstrained and bound-constrained problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17366 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization Davar, Dânâ Grapiglia, Geovani Nunes Optimization and Control We propose a derivative-free trust-region method based on finite-difference gradient approximations for smooth optimization problems with convex constraints. The proposed method does not require computing an approximate stationarity measure. For nonconvex problems, we establish a worst-case complexity bound of $\mathcal{O}\!\left(n\left(\tfrac{L}σε\right)^{-2}\right)$ function evaluations for the method to reach an $\left(\tfrac{L}σε\right)$-approximate stationary point, where $n$ is the number of variables, $L$ is the Lipschitz constant of the gradient, and $σ$ is a user-defined estimate of $L$. If the objective function is convex, the complexity to reduce the functional residual below $(L/σ)ε$ is shown to be of $\mathcal{O}\!\left(n\left(\tfrac{L}σε\right)^{-1}\right)$ function evaluations, while for Polyak-Lojasiewicz functions on unconstrained domains, the bound further improves to $\mathcal{O}\left(n\log\left(\left(\frac{L}σε\right)^{-1}\right)\right)$. Numerical experiments on benchmark problems and a model-fitting application demonstrate the method's efficiency relative to state-of-the-art derivative-free solvers for both unconstrained and bound-constrained problems. |
| title | A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.17366 |