A single-loop proximal-conditional-gradient penalty method
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911078797017088 |
|---|---|
| author | Zhang, Hao Zeng, Liaoyuan Pong, Ting Kei |
| author_facet | Zhang, Hao Zeng, Liaoyuan Pong, Ting Kei |
| contents | We consider the problem of minimizing a convex separable objective (as a separable sum of two proper closed convex functions $f$ and $g$) over a linear coupling constraint. We assume that $f$ can be decomposed as the sum of a smooth part having Hölder continuous gradient (with exponent $μ\in(0,1]$) and a nonsmooth part that admits efficient proximal mapping computations, while $g$ can be decomposed as the sum of a smooth part having Hölder continuous gradient (with exponent $ν\in(0,1]$) and a nonsmooth part that admits efficient linear oracles. Motivated by the recent works [1,49], we propose a single-loop variant of the standard penalty method, which we call a single-loop proximal-conditional-gradient penalty method (proxCG$^{\rm pen}_{1\ell}$), for this problem. In each iteration of proxCG$^{\rm pen}_{1\ell}$, we successively perform one proximal-gradient step involving $f$ and one conditional-gradient step involving $g$ on the quadratic penalty function, followed by an update of the penalty parameter. We present explicit rules for updating the penalty parameter and the stepsize in the conditional-gradient step in each iteration. Under a standard constraint qualification and domain boundedness assumption, we show that the objective value deviations (from the optimal value) along the sequence generated decay in the order of $t^{-\min\{μ,ν,1/2\}}$ with the associated feasibility violations decaying in the order of $t^{-1/2}$. Moreover, if the nonsmooth parts are indicator functions and the extended objective is a KL function with exponent $α\in[0,1)$, then the distances to the optimal solution set along the sequence generated by proxCG$^{\rm pen}_{1\ell}$ decay asymptotically at a rate of $t^{-(1-α)\min\{μ,ν,1/2\}}$. Finally, we illustrate numerically the behavior of proxCG$^{\rm pen}_{1\ell}$ on solving low rank Hankel matrix completion problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14957 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A single-loop proximal-conditional-gradient penalty method Zhang, Hao Zeng, Liaoyuan Pong, Ting Kei Optimization and Control We consider the problem of minimizing a convex separable objective (as a separable sum of two proper closed convex functions $f$ and $g$) over a linear coupling constraint. We assume that $f$ can be decomposed as the sum of a smooth part having Hölder continuous gradient (with exponent $μ\in(0,1]$) and a nonsmooth part that admits efficient proximal mapping computations, while $g$ can be decomposed as the sum of a smooth part having Hölder continuous gradient (with exponent $ν\in(0,1]$) and a nonsmooth part that admits efficient linear oracles. Motivated by the recent works [1,49], we propose a single-loop variant of the standard penalty method, which we call a single-loop proximal-conditional-gradient penalty method (proxCG$^{\rm pen}_{1\ell}$), for this problem. In each iteration of proxCG$^{\rm pen}_{1\ell}$, we successively perform one proximal-gradient step involving $f$ and one conditional-gradient step involving $g$ on the quadratic penalty function, followed by an update of the penalty parameter. We present explicit rules for updating the penalty parameter and the stepsize in the conditional-gradient step in each iteration. Under a standard constraint qualification and domain boundedness assumption, we show that the objective value deviations (from the optimal value) along the sequence generated decay in the order of $t^{-\min\{μ,ν,1/2\}}$ with the associated feasibility violations decaying in the order of $t^{-1/2}$. Moreover, if the nonsmooth parts are indicator functions and the extended objective is a KL function with exponent $α\in[0,1)$, then the distances to the optimal solution set along the sequence generated by proxCG$^{\rm pen}_{1\ell}$ decay asymptotically at a rate of $t^{-(1-α)\min\{μ,ν,1/2\}}$. Finally, we illustrate numerically the behavior of proxCG$^{\rm pen}_{1\ell}$ on solving low rank Hankel matrix completion problems. |
| title | A single-loop proximal-conditional-gradient penalty method |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.14957 |