A Near-optimal Method for Linearly Constrained Composite Non-convex Non-smooth Problems
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_ | 1866909557457944576 |
|---|---|
| author | Liu, Wei Lin, Qihang Xu, Yangyang |
| author_facet | Liu, Wei Lin, Qihang Xu, Yangyang |
| contents | We study first-order methods (FOMs) for solving \emph{composite nonconvex nonsmooth} optimization with linear constraints. Recently, the lower complexity bounds of FOMs on finding an ($\varepsilon,\varepsilon$)-KKT point of the considered problem is established in \cite{liu2025lowercomplexityboundsfirstorder}. However, optimization algorithms that achieve this lower bound had not been developed. In this paper, we propose an inexact proximal gradient method, where subproblems are solved using a recovering primal-dual procedure. Without making the bounded domain assumption, we establish that the oracle complexity of the proposed method, for finding an ($\varepsilon,\varepsilon$)-KKT point of the considered problem, matches the lower bounds up to a logarithmic factor. Consequently, in terms of the complexity, our algorithm outperforms all existing methods. We demonstrate the advantages of our proposed algorithm over the (linearized) alternating direction method of multipliers and the (proximal) augmented Lagrangian method in the numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22927 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Near-optimal Method for Linearly Constrained Composite Non-convex Non-smooth Problems Liu, Wei Lin, Qihang Xu, Yangyang Optimization and Control We study first-order methods (FOMs) for solving \emph{composite nonconvex nonsmooth} optimization with linear constraints. Recently, the lower complexity bounds of FOMs on finding an ($\varepsilon,\varepsilon$)-KKT point of the considered problem is established in \cite{liu2025lowercomplexityboundsfirstorder}. However, optimization algorithms that achieve this lower bound had not been developed. In this paper, we propose an inexact proximal gradient method, where subproblems are solved using a recovering primal-dual procedure. Without making the bounded domain assumption, we establish that the oracle complexity of the proposed method, for finding an ($\varepsilon,\varepsilon$)-KKT point of the considered problem, matches the lower bounds up to a logarithmic factor. Consequently, in terms of the complexity, our algorithm outperforms all existing methods. We demonstrate the advantages of our proposed algorithm over the (linearized) alternating direction method of multipliers and the (proximal) augmented Lagrangian method in the numerical experiments. |
| title | A Near-optimal Method for Linearly Constrained Composite Non-convex Non-smooth Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2503.22927 |