On convergence of the maximum block improvement method

Zhening Li, André Uschmajew, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

The MBI (maximum block improvement) method is a greedy approach to solving 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 Łojasiewicz 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 (US)
Pages (from-to)210-233
Number of pages24
JournalSIAM Journal on Optimization
Volume25
Issue number1
DOIs
StatePublished - 2015

Keywords

  • Block coordinate descent
  • Convergence
  • Maximum block improvement
  • Nonconvex optimization
  • Rank-one tensor approximation
  • Łojasiewicz inequality

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

Cite this