A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima
A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima
复制标题
DOI：
10.1137/19m1264783
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Masoud Ahookhosh;Andreas Themelis;Panagiotis Patrinos
中科院分区：
文献类型：
--
作者：
Masoud Ahookhosh;Andreas Themelis;Panagiotis Patrinos
介绍了一种局部超线性收敛的Bregman向前向后分裂方法Bella，用于最小化两个非凸函数之和，其中一个函数满足相对光滑性条件，另一个可能不光滑性。我们方法的一个关键工具是Bregman前向后向包络(BFBE)，它是一种精确的连续罚函数，具有良好的一阶和二阶性质，当目标函数满足Lojasiewicz型性质时，它享有一个非线性误差界。该算法在BFBE上沿着候选更新方向在线搜索，并在KL条件下全局收敛到平稳点，并且由于给定的非线性误差界，即使当极限点是非孤立最小值时，只要方向选择适当，也可以获得超线性收敛速度。
We introduce Bella, a locally superlinearly convergent Bregman forward backward splitting method for minimizing the sum of two nonconvex functions, one of which satisfying a relative smoothness condition and the other one possibly nonsmooth. A key tool of our methodology is the Bregman forward-backward envelope (BFBE), an exact and continuous penalty function with favorable first- and second-order properties, and enjoying a nonlinear error bound when the objective function satisfies a Lojasiewicz-type property. The proposed algorithm is of linesearch type over the BFBE along candidate update directions, and converges subsequentially to stationary points, globally under a KL condition, and owing to the given nonlinear error bound can attain superlinear convergence rates even when the limit point is a nonisolated minimum, provided the directions are suitably selected.