A proximal difference-of-convex algorithm with extrapolation
A proximal difference-of-convex algorithm with extrapolation
复制标题
DOI：
10.1007/s10589-017-9954-1
复制
发表时间：
2016-12
影响因子：
2.2
通讯作者：
Bo Wen;Xiaojun Chen;Ting Kei Pong
中科院分区：
文献类型：
--
作者：
Bo Wen;Xiaojun Chen;Ting Kei Pong
考虑一类目标为水平有界的凸差(DC)优化问题，其目标是具有Lipschitz梯度的光滑凸函数、真闭凸函数和连续凹函数之和。而这类问题可以用经典的凸差算法(DCA)来解决(Pham et al.越南数学学报22：289-355,1997)，这个算法的子问题的难度在很大程度上取决于DC分解的选择。更简单的子问题可以通过使用Pham等人描述的特定DC分解来获得。(暹罗杂志Optim8：476-505,1998)。这种分解在Gotoh等人的许多工作中都提出了。(稀疏优化问题的DC公式和算法，2017)，我们将产生的DCA称为近端DCA。虽然子问题比较简单，但当目标的凹面部分是空的时，近端DCA算法与近端梯度算法是相同的，因此在实际应用中可能会很慢。在本文中，受在凸环境下加速近邻梯度算法的外推技术的启发，我们考虑了一种可能加速近邻DCA的外插的近邻凸差算法。我们证明了由我们的算法生成的序列的任何聚类点都是DC优化问题的固定点，对于相当一般的外推参数的选择：特别地，参数可以像Fista中固定重新开始的那样选择(O‘Donoghue和CandèS在Found Comput Math 15715-732中，2015)。此外，通过假设目标的Kurdyka-Łojasiewicz性质和凹部分的可微性，我们建立了算法生成的序列的全局收敛，并分析了它的收敛速度。我们在两个凸差正则最小二乘模型上的数值实验表明，我们的算法的性能通常优于最近的DCA和Gong等人提出的一般迭代收缩和阈值算法。(非凸正则优化问题的通用迭代收缩和阈值算法，2013)。
We consider a class of difference-of-convex (DC) optimization problems whose objective is level-bounded and is the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function and a continuous concave function. While this kind of problems can be solved by the classical difference-of-convex algorithm (DCA) (Pham et al. Acta Math Vietnam 22:289–355, 1997), the difficulty of the subproblems of this algorithm depends heavily on the choice of DC decomposition. Simpler subproblems can be obtained by using a specific DC decomposition described in Pham et al. (SIAM J Optim 8:476–505, 1998). This decomposition has been proposed in numerous work such as Gotoh et al. (DC formulations and algorithms for sparse optimization problems, 2017), and we refer to the resulting DCA as the proximal DCA. Although the subproblems are simpler, the proximal DCA is the same as the proximal gradient algorithm when the concave part of the objective is void, and hence is potentially slow in practice. In this paper, motivated by the extrapolation techniques for accelerating the proximal gradient algorithm in the convex settings, we consider a proximal difference-of-convex algorithm with extrapolation to possibly accelerate the proximal DCA. We show that any cluster point of the sequence generated by our algorithm is a stationary point of the DC optimization problem for a fairly general choice of extrapolation parameters: in particular, the parameters can be chosen as in FISTA with fixed restart (O’Donoghue and Candès in Found Comput Math 15, 715–732, 2015). In addition, by assuming the Kurdyka-Łojasiewicz property of the objective and the differentiability of the concave part, we establish global convergence of the sequence generated by our algorithm and analyze its convergence rate. Our numerical experiments on two difference-of-convex regularized least squares models show that our algorithm usually outperforms the proximal DCA and the general iterative shrinkage and thresholding algorithm proposed in Gong et al. (A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems, 2013).