A Hybrid Subgradient Method for Nonsmooth Nonconvex Bilevel Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911617483014144 |
|---|---|
| author | Xiao, Nachuan Hu, Xiaoyin Liu, Xin Toh, Kim-Chuan |
| author_facet | Xiao, Nachuan Hu, Xiaoyin Liu, Xin Toh, Kim-Chuan |
| contents | In this paper, we focus on the nonconvex-nonconvex bilevel optimization problem (BLO), where both upper-level and lower-level objectives are nonconvex, with the upper-level problem potentially being nonsmooth. We develop a two-timescale momentum-accelerated subgradient method (TMG) that employs two-timescale stepsizes, and establish its local convergence when initialized within a sufficiently small neighborhood of the feasible region. To develop a globally convergent algorithm for (BLO), we introduce a feasibility restoration scheme (FRG) that drives iterates toward the feasible region. Both (TMG) and (FRG) only require the first-order derivatives of the upper-level and lower-level objective functions, ensuring efficient computations in practice. We then develop a novel hybrid method that alternates between (TMG) and (FRG) and adaptively estimates its hyperparameters. Under mild conditions, we establish the global convergence properties of our proposed algorithm. Preliminary numerical experiments demonstrate the high efficiency and promising potential of our proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22040 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Hybrid Subgradient Method for Nonsmooth Nonconvex Bilevel Optimization Xiao, Nachuan Hu, Xiaoyin Liu, Xin Toh, Kim-Chuan Optimization and Control In this paper, we focus on the nonconvex-nonconvex bilevel optimization problem (BLO), where both upper-level and lower-level objectives are nonconvex, with the upper-level problem potentially being nonsmooth. We develop a two-timescale momentum-accelerated subgradient method (TMG) that employs two-timescale stepsizes, and establish its local convergence when initialized within a sufficiently small neighborhood of the feasible region. To develop a globally convergent algorithm for (BLO), we introduce a feasibility restoration scheme (FRG) that drives iterates toward the feasible region. Both (TMG) and (FRG) only require the first-order derivatives of the upper-level and lower-level objective functions, ensuring efficient computations in practice. We then develop a novel hybrid method that alternates between (TMG) and (FRG) and adaptively estimates its hyperparameters. Under mild conditions, we establish the global convergence properties of our proposed algorithm. Preliminary numerical experiments demonstrate the high efficiency and promising potential of our proposed algorithm. |
| title | A Hybrid Subgradient Method for Nonsmooth Nonconvex Bilevel Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.22040 |