Greedy coordinate descent method on non-negative quadratic programming
Greedy coordinate descent method on non-negative quadratic programming
复制标题
DOI：
10.1109/sam48682.2020.9104264
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Chenyu Wu;Yangyang Xu
中科院分区：
文献类型：
--
作者：
Chenyu Wu;Yangyang Xu
坐标下降（CD）方法最近成为解决非常大规模问题的流行，部分原因是它的简单更新，低内存需求和快速收敛。本文研究了贪婪CD算法在求解非负二次规划问题中的应用。贪婪CD通常比其循环和随机对应物具有更昂贵的每次更新复杂度。然而，在NQP上，这三个CD具有几乎相同的每次更新成本，而贪婪CD可以具有显著更快的整体收敛速度。我们也将提出的贪婪CD作为子程序来求解线性约束NQP和非负矩阵分解。这两个问题的数值结果与合成数据和图像数据的实例观察。
The coordinate descent (CD) method has recently become popular for solving very large-scale problems, partly due to its simple update, low memory requirement, and fast convergence. In this paper, we explore the greedy CD on solving non-negative quadratic programming (NQP). The greedy CD generally has much more expensive per-update complexity than its cyclic and randomized counterparts. However, on the NQP, these three CDs have almost the same per-update cost, while the greedy CD can have significantly faster overall convergence speed. We also apply the proposed greedy CD as a subroutine to solve linearly constrained NQP and the non-negative matrix factorization. Promising numerical results on both problems are observed on instances with synthetic data and also image data.