Complexity results and active-set identification of a derivative-free method for bound-constrained problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909871776989184 |
|---|---|
| author | Brilli, Andrea Cristofari, Andrea Liuzzi, Giampaolo Lucidi, Stefano |
| author_facet | Brilli, Andrea Cristofari, Andrea Liuzzi, Giampaolo Lucidi, Stefano |
| contents | In this paper, we analyze a derivative-free line search method designed for bound-constrained problems. Our analysis demonstrates that this method exhibits a worst-case complexity comparable to other derivative-free methods for unconstrained and linearly constrained problems. In particular, when minimizing a function with $n$ variables, we prove that at most ${\cal O(nε^{-2})}$ iterations are needed to drive a criticality measure below a predefined threshold $ε$, requiring at most ${\cal O(n^2ε^{-2})}$ function evaluations. We also show that the total number of iterations where the criticality measure is not below $ε$ is upper bounded by ${\cal O(n^2ε^{-2})}$. Moreover, we investigate the method capability to identify active constraints at the final solutions. We show that, after a finite number of iterations, all the active constraints satisfying the strict complementarity condition are correctly identified. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10801 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity results and active-set identification of a derivative-free method for bound-constrained problems Brilli, Andrea Cristofari, Andrea Liuzzi, Giampaolo Lucidi, Stefano Optimization and Control In this paper, we analyze a derivative-free line search method designed for bound-constrained problems. Our analysis demonstrates that this method exhibits a worst-case complexity comparable to other derivative-free methods for unconstrained and linearly constrained problems. In particular, when minimizing a function with $n$ variables, we prove that at most ${\cal O(nε^{-2})}$ iterations are needed to drive a criticality measure below a predefined threshold $ε$, requiring at most ${\cal O(n^2ε^{-2})}$ function evaluations. We also show that the total number of iterations where the criticality measure is not below $ε$ is upper bounded by ${\cal O(n^2ε^{-2})}$. Moreover, we investigate the method capability to identify active constraints at the final solutions. We show that, after a finite number of iterations, all the active constraints satisfying the strict complementarity condition are correctly identified. |
| title | Complexity results and active-set identification of a derivative-free method for bound-constrained problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.10801 |