Beck, Amir; Teboulle, Marc A conditional gradient method with linear rate of convergence for solving convex linear systems. (English) Zbl 1138.90440 Math. Methods Oper. Res. 59, No. 2, 235-247 (2004). Summary: We consider the problem of finding a point in the intersection of an affine set with a compact convex set, called a convex linear system (CLS). The conditional gradient method is known to exhibit a sublinear rate of convergence. Exploiting the special structure of (CLS), we prove that the conditional gradient method applied to the equivalent minimization formulation of (CLS), converges to a solution at a linear rate, under the sole assumption that Slater’s condition holds for (CLS). The rate of convergence is measured explicitly in terms of the problem’s data and a Slater point. Application to a class of conic linear systems is discussed. Cited in 28 Documents MSC: 90C25 Convex programming 90C60 Abstract computational complexity for mathematical programming problems 65K05 Numerical mathematical programming methods 90C05 Linear programming 90C20 Quadratic programming Keywords:Conic linear systems; Slater’s condition; conditional gradient; efficiency and rate of convergence analysis PDFBibTeX XMLCite \textit{A. Beck} and \textit{M. Teboulle}, Math. Methods Oper. Res. 59, No. 2, 235--247 (2004; Zbl 1138.90440) Full Text: DOI