The convergence properties of infeasible inexact proximal alternating linearized minimization

Highlights

We study the theoretical properties of proximal alternating linearized minimization (PALM) method, which is a popular unified framework for multi-block nonconvex optimization.

Setting

The subproblems are solved by infeasible subsolvers, yielding infeasible iterates. Examples are ubiquitous; for example, consider a feasible set described by a severely under-determined linear system. However, there are few existing works in this aspect.

Theoretical results

• Implementable inexact criterion for solving subproblems based on error bounds.
• Global convergence to stationarity and novel asymptotic convergence rates.

Abstract (in case you want a formal version)

The proximal alternating linearized minimization (PALM) method suits well for solving block-structured optimization problems, which are ubiquitous in real applications. In the cases where subproblems do not have closed-form solutions, e.g., due to complex constraints, infeasible subsolvers are indispensable, giving rise to an infeasible inexact PALM (PALM-I). Numerous efforts have been devoted to analyzing the feasible PALM, while little attention has been paid to the PALM-I. The usage of the PALM-I thus lacks a theoretical guarantee. The essential difficulty of analysis consists in the objective value nonmonotonicity induced by the infeasibility. We study in the present work the convergence properties of the PALM-I. In particular, we construct a surrogate sequence to surmount the nonmonotonicity issue and devise an implementable inexact criterion. Based upon these, we manage to establish the stationarity of any accumulation point, and moreover, show the iterate convergence and the asymptotic convergence rates under the assumption of the Łojasiewicz property. The prominent advantages of the PALM-I on CPU time are illustrated via numerical experiments on problems arising from quantum physics and 3-dimensional anisotropic frictional contact.