论文标题
非负二次编程的贪婪协调下降法
Greedy coordinate descent method on non-negative quadratic programming
论文作者
论文摘要
坐标下降（CD）方法最近在解决非常大规模的问题方面变得很流行，部分原因是它的简单更新，低内存需求和快速收敛。在本文中，我们探讨了解决非负二次编程（NQP）的贪婪CD。贪婪的CD通常比其循环和随机对应物的每上更复杂性要昂贵得多。但是，在NQP上，这三个CD的每上新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.
