zbMATH — the first resource for mathematics

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.

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