分块强凸函数的加速块坐标下降算法的O(1/k~2)收敛率

宋恩彬史清江朱允民 · 2016

阅读量：444

循环块坐标最小化

交替最小化

凸优化

收敛率

期刊名称：

中国科学:数学 2016 年 10 期

摘要：

有很长发展历史的块坐标下降(block coordinate descent,BCD)算法是一种经典的优化方法,因其有诸多优点,如简单、速度快和稳定等而被广泛应用.本文在一种相对较弱的假设下,即当目标函数是分块强凸时,分析对于凸优化问题的块坐标下降算法的非渐近收敛率.本文证明,若k是迭代次数,则块坐标下降(BCD)算法可以由O(1/k)的收敛率被加速到O(1/k~2)的收敛率.