AN O(1/k) CONVERGENCE RATE FOR THE VARIABLE STEPSIZE BREGMAN OPERATOR SPLITTING ALGORITHM

作者：Hager William W^*; Yashtini Maryam; Zhang Hongchao

来源：SIAM Journal on Numerical Analysis, 2016, 54(3): 1535-1556.

DOI：10.1137/15100401X

• nonsmooth optimization
• convex optimization
• BOSVS
• ergodic convergence
• saddle point problem
• variational inequality

An earlier paper proved the convergence of a variable stepsize Bregman operator splitting algorithm (BOSVS) for minimizing phi(Bu) + H(u), where H and phi are convex functions, and phi is possibly nonsmooth. The algorithm was shown to be relatively efficient when applied to partially parallel magnetic resonance image reconstruction problems. In this paper, the convergence rate of BOSVS is analyzed. When H(u) = parallel to Au -f parallel to(2), where A is a matrix, it is shown that for an ergodic approximation u(k) obtained by averaging k BOSVS iterates, the error in the objective value phi(Bu-k)+ H(u(k)) is O(1/k). When the optimization problem has a unique solution u*, we obtain the estimate parallel to u(k) -u*parallel to = O(1/root k). The theoretical analysis is compared to observed convergence rates for partially parallel magnetic resonance image reconstruction problems where A is a large dense ill-conditioned matrix.

• 出版日期2016