Extragradient Sliding for Composite Non-Monotone Variational Inequalities
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_ | 1866912220103835648 |
|---|---|
| author | Emelyanov, Roman Tikhomirov, Andrey Beznosikov, Aleksandr Gasnikov, Alexander |
| author_facet | Emelyanov, Roman Tikhomirov, Andrey Beznosikov, Aleksandr Gasnikov, Alexander |
| contents | Variational inequalities offer a versatile and straightforward approach to analyzing a broad range of equilibrium problems in both theoretical and practical fields. In this paper, we consider a composite generally non-monotone variational inequality represented as a sum of $L_q$-Lipschitz monotone and $L_p$-Lipschitz generally non-monotone operators. We applied a special sliding version of the classical Extragradient method to this problem and obtain better convergence results. In particular, to achieve $\varepsilon$-accuracy of the solution, the oracle complexity of the non-monotone operator $Q$ for our algorithm is $O\left(L_p^2/\varepsilon^2\right)$ in contrast to the basic Extragradient algorithm with $O\left((L_p+L_q)^2/\varepsilon^2\right)$. The results of numerical experiments confirm the theoretical findings and show the superiority of the proposed method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_14981 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extragradient Sliding for Composite Non-Monotone Variational Inequalities Emelyanov, Roman Tikhomirov, Andrey Beznosikov, Aleksandr Gasnikov, Alexander Optimization and Control Variational inequalities offer a versatile and straightforward approach to analyzing a broad range of equilibrium problems in both theoretical and practical fields. In this paper, we consider a composite generally non-monotone variational inequality represented as a sum of $L_q$-Lipschitz monotone and $L_p$-Lipschitz generally non-monotone operators. We applied a special sliding version of the classical Extragradient method to this problem and obtain better convergence results. In particular, to achieve $\varepsilon$-accuracy of the solution, the oracle complexity of the non-monotone operator $Q$ for our algorithm is $O\left(L_p^2/\varepsilon^2\right)$ in contrast to the basic Extragradient algorithm with $O\left((L_p+L_q)^2/\varepsilon^2\right)$. The results of numerical experiments confirm the theoretical findings and show the superiority of the proposed method. |
| title | Extragradient Sliding for Composite Non-Monotone Variational Inequalities |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2403.14981 |