RATES OF CONVERGENCE FOR CONDITIONAL GRADIENT ALGORITHMS NEAR SINGULAR AND NONSINGULAR EXTREMALS

Two conditional gradient algorithms are considered for the problem min// OMEGA F, with OMEGA a bounded convex subset of a Banach space. Neither method requires line search; one method needs no Lipschitz constants. Convergence rate estimates are similar in the two cases, and depend critically on the continuity properties of a set valued operator T whose fixed points, xi , are the extremals of F in OMEGA . The continuity properties of T at xi are determined by the way the function a( sigma ) grows with increasing sigma . It is shown that for convex F and Lipschitz continuous F prime , the algorithms converge like o(1/n), geometrically, or in finitely many steps, according to whether a( sigma ) greater than 0 for sigma greater than 0, or a( sigma ) greater than equivalent to A sigma **2 with A greater than 0, or a( sigma ) greater than equivalent to A sigma with A greater than 0. These three abstract conditions are closely related to established notions of nonsingularity for an important class of optimal control problems with bounded control inputs.