Global Convergence of Splitting Methods for Nonconvex Composite Optimization

Guoyin Li University of New South Wales Ting Kei Pong The Hong Kong Polytechnic University

Optimization and Control mathscidoc:1903.25003

Best Paper Award in 2019

SIAM Journal on Optimization , 25, (4), 2434-2460, 2015
We consider the problem of minimizing the sum of a smooth function h with a bounded Hessian and a nonsmooth function. We assume that the latter function is a composition of a proper closed function P and a surjective linear map M. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: the alternating direction method of multipliers and the proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions h and P are semialgebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the 1/2 regularization. Finally, when M is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex h. We illustrate our theoretical finding with a variety of applications such as signal denoising and sparse optimisation problems.
global convergence, nonconvex composite optimization, alternating direction method of multipliers, proximal gradient algorithm, Kurdyka–Lojasiewicz property
[ Download ] [ 2019-03-20 16:33:38 uploaded by gyli ] [ 547 downloads ] [ 0 comments ]
@inproceedings{guoyin2015global,
  title={ Global Convergence of Splitting Methods for Nonconvex Composite Optimization},
  author={Guoyin Li, and Ting Kei Pong},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20190320163338454037217},
  booktitle={SIAM Journal on Optimization },
  volume={25},
  number={4},
  pages={2434-2460},
  year={2015},
}
Guoyin Li, and Ting Kei Pong. Global Convergence of Splitting Methods for Nonconvex Composite Optimization. 2015. Vol. 25. In SIAM Journal on Optimization . pp.2434-2460. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20190320163338454037217.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved