A Zeroth-Order Extra-Gradient Method for Black-Box Constrained Optimization
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915390651629568 |
|---|---|
| author | Zhou, Yuke Jin, Ruiyang Gao, Siyang Wang, Jianxiao Song, Jie |
| author_facet | Zhou, Yuke Jin, Ruiyang Gao, Siyang Wang, Jianxiao Song, Jie |
| contents | Non-analytical objectives and constraints often arise in control systems, particularly in problems with complex dynamics, which are challenging yet lack efficient solution methods. In this work, we consider general constrained optimization problems involving black-box objectives and constraints. To solve it, we reformulate it as a min-max problem and propose a zeroth-order extra gradient (ZOEG) algorithm that combines the extra gradient method with a feedback-based stochastic zeroth-order gradient estimator. Then, we apply another coordinate gradient estimator to design the zeroth-order coordinate extra gradient algorithm (ZOCEG) to further improve efficiency. The theoretical analysis shows that ZOEG can achieve the best-known oracle complexity of $\mathcal{O}(dε^{-2})$ to get an $ε$-optimal solution ($d$ is the dimension of decision space), and ZOCEG can improve it to $\mathcal{O}(dε^{-1})$. Furthermore, we develop a variant of ZOCEG, which applies block coordinate updates to enhance the efficiency of single-step gradient estimation. Finally, numerical experiments on a load tracking problem validate our theoretical results and the effectiveness of the proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_20546 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Zeroth-Order Extra-Gradient Method for Black-Box Constrained Optimization Zhou, Yuke Jin, Ruiyang Gao, Siyang Wang, Jianxiao Song, Jie Optimization and Control Non-analytical objectives and constraints often arise in control systems, particularly in problems with complex dynamics, which are challenging yet lack efficient solution methods. In this work, we consider general constrained optimization problems involving black-box objectives and constraints. To solve it, we reformulate it as a min-max problem and propose a zeroth-order extra gradient (ZOEG) algorithm that combines the extra gradient method with a feedback-based stochastic zeroth-order gradient estimator. Then, we apply another coordinate gradient estimator to design the zeroth-order coordinate extra gradient algorithm (ZOCEG) to further improve efficiency. The theoretical analysis shows that ZOEG can achieve the best-known oracle complexity of $\mathcal{O}(dε^{-2})$ to get an $ε$-optimal solution ($d$ is the dimension of decision space), and ZOCEG can improve it to $\mathcal{O}(dε^{-1})$. Furthermore, we develop a variant of ZOCEG, which applies block coordinate updates to enhance the efficiency of single-step gradient estimation. Finally, numerical experiments on a load tracking problem validate our theoretical results and the effectiveness of the proposed algorithms. |
| title | A Zeroth-Order Extra-Gradient Method for Black-Box Constrained Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2506.20546 |