We develop a new proximal--gradient method for minimizing the sum of a differentiable, possibly nonconvex, function plus a convex, possibly non differentiable, function. The key features of the proposed method are the definition of a suitable descent direction, based on the proximal operator associated to the convex part of the objective function, and an Armijo--like rule to determine the step size along this direction ensuring the sufficient decrease of the objective function. In this frame, we especially address the possibility of adopting a metric which may change at each iteration and an inexact computation of the proximal point defining the descent direction. For the more general nonconvex case, we prove that all limit points of the iterates sequence are stationary, while for convex objective functions we prove the convergence of the whole sequence to a minimizer, under the assumption that a minimizer exists. In the latter case, assuming also that the gradient of the smooth part of the objective function is Lipschitz, we also give a convergence rate estimate, showing the O(1/k) complexity with respect to the function values. We also discuss verifiable sufficient conditions for the inexact proximal point and we present the results of two numerical tests on total variation based image restoration problems, showing that the proposed approach is competitive with other state-of-the-art methods.

Variable metric inexact line-search based methods for nonsmooth optimization / Bonettini, Silvia; Loris, Ignace; Porta, Federica; Prato, Marco. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 26:(2016), pp. 891-921. [10.1137/15M1019325]

Variable metric inexact line-search based methods for nonsmooth optimization

BONETTINI, Silvia;Porta, Federica;PRATO, Marco
2016

Abstract

We develop a new proximal--gradient method for minimizing the sum of a differentiable, possibly nonconvex, function plus a convex, possibly non differentiable, function. The key features of the proposed method are the definition of a suitable descent direction, based on the proximal operator associated to the convex part of the objective function, and an Armijo--like rule to determine the step size along this direction ensuring the sufficient decrease of the objective function. In this frame, we especially address the possibility of adopting a metric which may change at each iteration and an inexact computation of the proximal point defining the descent direction. For the more general nonconvex case, we prove that all limit points of the iterates sequence are stationary, while for convex objective functions we prove the convergence of the whole sequence to a minimizer, under the assumption that a minimizer exists. In the latter case, assuming also that the gradient of the smooth part of the objective function is Lipschitz, we also give a convergence rate estimate, showing the O(1/k) complexity with respect to the function values. We also discuss verifiable sufficient conditions for the inexact proximal point and we present the results of two numerical tests on total variation based image restoration problems, showing that the proposed approach is competitive with other state-of-the-art methods.
2016
26
891
921
Variable metric inexact line-search based methods for nonsmooth optimization / Bonettini, Silvia; Loris, Ignace; Porta, Federica; Prato, Marco. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 26:(2016), pp. 891-921. [10.1137/15M1019325]
Bonettini, Silvia; Loris, Ignace; Porta, Federica; Prato, Marco
File in questo prodotto:
File Dimensione Formato  
VOR_VARIABLE METRIC INEXACT LINE-SEARCH-BASED METHODS.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 743.67 kB
Formato Adobe PDF
743.67 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
POST PRINT_VARIABLE METRIC INEXACT LINE.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 826.94 kB
Formato Adobe PDF
826.94 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1081761
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 64
  • ???jsp.display-item.citation.isi??? 60
social impact