Abstract.
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.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Additional information
Acknowldegements. We thank two referees for their constructive comments which has led to improve the presentation.
Rights and permissions
About this article
Cite this article
Beck, A., Teboulle, M. A conditional gradient method with linear rate of convergence for solving convex linear systems. Math Meth Oper Res 59, 235–247 (2004). https://doi.org/10.1007/s001860300327
Issue Date:
DOI: https://doi.org/10.1007/s001860300327