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

Acceleration of block coordinate descent method achieves the O(1/k^2) rate of convergence for a convex function with block coordinate strong convexity

作　　者：宋恩彬[1] 史清江[2] 朱允民[1] 

机构地区：[1]四川大学数学学院,成都610065 [2]浙江理工大学信息学院,杭州310018

出　　处：《中国科学：数学》2016年第10期1499-1506,共8页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:61473197;61302076和61273074)资助项目

摘　　要：有很长发展历史的块坐标下降(block coordinate descent,BCD)算法是一种经典的优化方法,因其有诸多优点,如简单、速度快和稳定等而被广泛应用.本文在一种相对较弱的假设下,即当目标函数是分块强凸时,分析对于凸优化问题的块坐标下降算法的非渐近收敛率.本文证明,若k是迭代次数,则块坐标下降(BCD)算法可以由O(1/k)的收敛率被加速到O(1/k^2)的收敛率.Block coordinate descent method enjoys a long history and is a classic optimization method which has been extensively applied because it possesses some advantages,such as the simplicity,speed,and stability,etc.We prove that it can be accelerated and obtain an O（1/k2） rate of convergence for unconstrained convex optimization problem under a relatively mild assumption that the objective function is a convex function with block coordinate strong convexity.

关 键 词：循环块坐标最小化 交替最小化 凸优化 收敛率 

分 类 号：O174.13[理学—数学]