This paper is concerned with the cyclic block coordinate descent method, also known as the nonlinear Gauss-Seidel (GS) method, where the solution of an optimization problem is achieved by partitioning the variables in blocks and successively minimizing with respect to each block. The properties of the objective function that guarantee the convergence of such alternating scheme have been widely investigated in the literature and it is well known that without suitable convexity hypotheses, the method may fail to locate the stationary points when more than two blocks of variables are employed. In this paper the general constrained nonconvex case is considered, presenting three contributions. First, a general method allowing an approximate solution of each block minimization subproblem is devised and the related convergence analysis is developed, showing that the proposed inexact method has the same convergence properties as the standard nonlinear GS method. Then a cyclic block gradient projection method is analysed, proving that it leads to stationary points for every number of blocks. Finally, the cyclic block gradient method is applied to large-scale problems arising from the non-negative matrix factorization approach. The results of a numerical experimentation on image recognition problems are also reported.

Inexact block coordinate descent methods with application to the nonnegative matrix factorization

BONETTINI, Silvia
2011

Abstract

This paper is concerned with the cyclic block coordinate descent method, also known as the nonlinear Gauss-Seidel (GS) method, where the solution of an optimization problem is achieved by partitioning the variables in blocks and successively minimizing with respect to each block. The properties of the objective function that guarantee the convergence of such alternating scheme have been widely investigated in the literature and it is well known that without suitable convexity hypotheses, the method may fail to locate the stationary points when more than two blocks of variables are employed. In this paper the general constrained nonconvex case is considered, presenting three contributions. First, a general method allowing an approximate solution of each block minimization subproblem is devised and the related convergence analysis is developed, showing that the proposed inexact method has the same convergence properties as the standard nonlinear GS method. Then a cyclic block gradient projection method is analysed, proving that it leads to stationary points for every number of blocks. Finally, the cyclic block gradient method is applied to large-scale problems arising from the non-negative matrix factorization approach. The results of a numerical experimentation on image recognition problems are also reported.
File in questo prodotto:
File Dimensione Formato  
Bonettini_2011.pdf

solo gestori archivio

Descrizione: versione editoriale
Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 270.74 kB
Formato Adobe PDF
270.74 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11392/1399127
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 55
  • ???jsp.display-item.citation.isi??? 54
social impact