AbstractChebyshev Greedy Algorithm is a generalization of the well knownOrthogonal Matching Pursuit defined in a Hilbert space to the caseof Banach spaces. We apply this algorithm for constructing sparseapproximate solutions (with respect to a given dictionary) to convexoptimization problems. Rate of convergence results in a style of theLebesgue-type inequalities are proved. 1 Introduction We study sparse approximate solutions to convex optimization problems. Weapply the technique developed in nonlinear approximation known under thename of greedy approximation. A typical problem of convex optimization isto find an approximate solution to the probleminf x E(x) (1.1)under assumption that E is a convex function. Usually, in convex optimiza-tion function E is defined on a finite dimensional space R n (see [1], [3]).Recent needs of numerical analysis call for consideration of the above opti-mization problem on an infinite dimensional space, for instance, a space of ∗ University of South Carolina and Steklov Institute of Mathematics. Research wassupported by NSF grant DMS-1160841