On convergence of the maximum block improvement method

Zhening Li, André Uschmajew, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

265 Downloads (Pure)

Abstract

The MBI (maximum block improvement) method is a greedy approach to solve optimization problems where the decision variables can be grouped into a finite number of blocks. Assuming that optimizing over one block of variables while fixing all others is relatively easy, the MBI method updates the block of variables corresponding to the maximally improving block at each iteration, which is arguably a most natural and simple process to tackle block-structured problems with great potentials for engineering applications. In this paper we establish global and local linear convergence results for this method. The global convergence is established under the Lojasiewicz inequality assumption, while the local analysis invokes second-order assumptions. We study in particular the tensor optimization model with spherical constraints. Conditions for linear convergence of the famous power method for computing the maximum eigenvalue of a matrix follow in this framework as a special case. The condition is interpreted in various other forms for the rank-one tensor optimization model under spherical constraints. Numerical experiments are shown to support the convergence property of the MBI method.
Original languageEnglish
Pages (from-to)210-233
JournalSIAM Journal on Optimization
Volume25
Issue number1
Early online date15 Jan 2015
DOIs
Publication statusPublished - Mar 2015

Keywords

  • maximum block improvement
  • block coordinate descent
  • nonconvex optimization
  • rank-one tensor approximation
  • convergence
  • Lojasiewicz inequality

Fingerprint

Dive into the research topics of 'On convergence of the maximum block improvement method'. Together they form a unique fingerprint.

Cite this