×

A conditional gradient method with linear rate of convergence for solving convex linear systems. (English) Zbl 1138.90440

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.

MSC:

90C25 Convex programming
90C60 Abstract computational complexity for mathematical programming problems
65K05 Numerical mathematical programming methods
90C05 Linear programming
90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI