New Classes of Non-monotone Variational Inequality Problems Solvable via Proximal Gradient on Smooth Gap Functions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915553170423808 |
|---|---|
| author | Zhao, Lei Zhu, Daoli Zhang, Shuzhong |
| author_facet | Zhao, Lei Zhu, Daoli Zhang, Shuzhong |
| contents | In this paper, we study the local linear convergence behavior of proximal-gradient (PG) descent algorithm on a parameterized gap-function reformulation of a smooth but non-monotone variational inequality problem (VIP). The aim is to solve the non-monotone VI problem without assuming the existence of a Minty-type solution. We first introduce and study various error bound conditions for the gap functions in relation to the VI model. In particular, we show that uniform type error bounds imply level-set type error bounds for composite optimization, revealing a key hierarchical structure there. As a result, local linear convergence is established under some easy-verifiable conditions induced by level-set error bounds, the gradient Lipschitz condition and a suitable initialization condition. Furthermore, for non-monotone affine VIs we present a homotopy continuation scheme that achieves global convergence by dynamically tracing a solution path. Our numerical experiments show the efficacy of the proposed approach, leading to the solutions of a broad class of non-monotone VI problems resulting from the need to compute Nash equilibria, traffic controls, and the GAN models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12105 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Classes of Non-monotone Variational Inequality Problems Solvable via Proximal Gradient on Smooth Gap Functions Zhao, Lei Zhu, Daoli Zhang, Shuzhong Optimization and Control 90C33, 65K15, 90C26 In this paper, we study the local linear convergence behavior of proximal-gradient (PG) descent algorithm on a parameterized gap-function reformulation of a smooth but non-monotone variational inequality problem (VIP). The aim is to solve the non-monotone VI problem without assuming the existence of a Minty-type solution. We first introduce and study various error bound conditions for the gap functions in relation to the VI model. In particular, we show that uniform type error bounds imply level-set type error bounds for composite optimization, revealing a key hierarchical structure there. As a result, local linear convergence is established under some easy-verifiable conditions induced by level-set error bounds, the gradient Lipschitz condition and a suitable initialization condition. Furthermore, for non-monotone affine VIs we present a homotopy continuation scheme that achieves global convergence by dynamically tracing a solution path. Our numerical experiments show the efficacy of the proposed approach, leading to the solutions of a broad class of non-monotone VI problems resulting from the need to compute Nash equilibria, traffic controls, and the GAN models. |
| title | New Classes of Non-monotone Variational Inequality Problems Solvable via Proximal Gradient on Smooth Gap Functions |
| topic | Optimization and Control 90C33, 65K15, 90C26 |
| url | https://arxiv.org/abs/2510.12105 |