Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions
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_ | 1866911407703851008 |
|---|---|
| author | Huang, Yankun Lin, Qihang Xu, Yangyang |
| author_facet | Huang, Yankun Lin, Qihang Xu, Yangyang |
| contents | In this paper, we investigate how structural properties of the constraint system impact the oracle complexity of smooth non-convex optimization problems with convex inequality constraints over a simple polytope. In particular, we show that, under a local error bound condition with exponent $d\in[1,2]$ on constraint functions, an inexact Moreau envelope Lagrangian method can attain an $ε$-Karush--Kuhn--Tucker point with $\tilde O(ε^{-2d})$ gradient oracle complexity. When $d=1$, this result matches the best-known complexity in literature up to logarithmic factors. Importantly, the assumed error bound condition with any $d\in[1,2]$ is strictly weaker than the local linear independence constraint qualification that is required to achieve the best-known complexity. Our results clarify the interplay between error bound conditions of constraints and algorithmic complexity, and extend complexity guarantees to a broader class of constrained non-convex problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_19764 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions Huang, Yankun Lin, Qihang Xu, Yangyang Optimization and Control Machine Learning In this paper, we investigate how structural properties of the constraint system impact the oracle complexity of smooth non-convex optimization problems with convex inequality constraints over a simple polytope. In particular, we show that, under a local error bound condition with exponent $d\in[1,2]$ on constraint functions, an inexact Moreau envelope Lagrangian method can attain an $ε$-Karush--Kuhn--Tucker point with $\tilde O(ε^{-2d})$ gradient oracle complexity. When $d=1$, this result matches the best-known complexity in literature up to logarithmic factors. Importantly, the assumed error bound condition with any $d\in[1,2]$ is strictly weaker than the local linear independence constraint qualification that is required to achieve the best-known complexity. Our results clarify the interplay between error bound conditions of constraints and algorithmic complexity, and extend complexity guarantees to a broader class of constrained non-convex problems. |
| title | Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2502.19764 |