Cargando…
A general double-proximal gradient algorithm for d.c. programming
The possibilities of exploiting the special structure of d.c. programs, which consist of optimising the difference of convex functions, are currently more or less limited to variants of the DCA proposed by Pham Dinh Tao and Le Thi Hoai An in 1997. These assume that either the convex or the concave p...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer Berlin Heidelberg
2018
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6830843/ https://www.ncbi.nlm.nih.gov/pubmed/31762494 http://dx.doi.org/10.1007/s10107-018-1292-2 |
_version_ | 1783465844289830912 |
---|---|
author | Banert, Sebastian Boț, Radu Ioan |
author_facet | Banert, Sebastian Boț, Radu Ioan |
author_sort | Banert, Sebastian |
collection | PubMed |
description | The possibilities of exploiting the special structure of d.c. programs, which consist of optimising the difference of convex functions, are currently more or less limited to variants of the DCA proposed by Pham Dinh Tao and Le Thi Hoai An in 1997. These assume that either the convex or the concave part, or both, are evaluated by one of their subgradients. In this paper we propose an algorithm which allows the evaluation of both the concave and the convex part by their proximal points. Additionally, we allow a smooth part, which is evaluated via its gradient. In the spirit of primal-dual splitting algorithms, the concave part might be the composition of a concave function with a linear operator, which are, however, evaluated separately. For this algorithm we show that every cluster point is a solution of the optimisation problem. Furthermore, we show the connection to the Toland dual problem and prove a descent property for the objective function values of a primal-dual formulation of the problem. Convergence of the iterates is shown if this objective function satisfies the Kurdyka–Łojasiewicz property. In the last part, we apply the algorithm to an image processing model. |
format | Online Article Text |
id | pubmed-6830843 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2018 |
publisher | Springer Berlin Heidelberg |
record_format | MEDLINE/PubMed |
spelling | pubmed-68308432019-11-20 A general double-proximal gradient algorithm for d.c. programming Banert, Sebastian Boț, Radu Ioan Math Program Full Length Paper The possibilities of exploiting the special structure of d.c. programs, which consist of optimising the difference of convex functions, are currently more or less limited to variants of the DCA proposed by Pham Dinh Tao and Le Thi Hoai An in 1997. These assume that either the convex or the concave part, or both, are evaluated by one of their subgradients. In this paper we propose an algorithm which allows the evaluation of both the concave and the convex part by their proximal points. Additionally, we allow a smooth part, which is evaluated via its gradient. In the spirit of primal-dual splitting algorithms, the concave part might be the composition of a concave function with a linear operator, which are, however, evaluated separately. For this algorithm we show that every cluster point is a solution of the optimisation problem. Furthermore, we show the connection to the Toland dual problem and prove a descent property for the objective function values of a primal-dual formulation of the problem. Convergence of the iterates is shown if this objective function satisfies the Kurdyka–Łojasiewicz property. In the last part, we apply the algorithm to an image processing model. Springer Berlin Heidelberg 2018-05-23 2019 /pmc/articles/PMC6830843/ /pubmed/31762494 http://dx.doi.org/10.1007/s10107-018-1292-2 Text en © The Author(s) 2018 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
spellingShingle | Full Length Paper Banert, Sebastian Boț, Radu Ioan A general double-proximal gradient algorithm for d.c. programming |
title | A general double-proximal gradient algorithm for d.c. programming |
title_full | A general double-proximal gradient algorithm for d.c. programming |
title_fullStr | A general double-proximal gradient algorithm for d.c. programming |
title_full_unstemmed | A general double-proximal gradient algorithm for d.c. programming |
title_short | A general double-proximal gradient algorithm for d.c. programming |
title_sort | general double-proximal gradient algorithm for d.c. programming |
topic | Full Length Paper |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6830843/ https://www.ncbi.nlm.nih.gov/pubmed/31762494 http://dx.doi.org/10.1007/s10107-018-1292-2 |
work_keys_str_mv | AT banertsebastian ageneraldoubleproximalgradientalgorithmfordcprogramming AT botraduioan ageneraldoubleproximalgradientalgorithmfordcprogramming AT banertsebastian generaldoubleproximalgradientalgorithmfordcprogramming AT botraduioan generaldoubleproximalgradientalgorithmfordcprogramming |