On the Convergence of Algorithms with Restart

Abstract

Global convergence properties are established for a class of point-to-set mathematical programming algorithms commonly termed "restart" methods. Well-known algorithms in this class include the "restart" versions of the Fletcher-Reeves conjugate gradient and Davidon-Fletcher-Powell methods. Under certain mild assumptions, it is shown that the entire sequence of iterates (as opposed to selected subsequences) generated by such algorithms converges to a "desirable" point. Some similar convergence results are also established for a related class of "inexact" algorithms, and for a class of algorithms motivated by cyclic coordinate descent methods.