This paper proposes a novel approach for constructing efficient schemes to solve non-smooth convex optimization problems. The method involves a special smoothing technique that can be applied to functions with explicit max-structure, improving the traditional efficiency bounds from \(O(\frac{1}{\epsilon^2})\) to \(O(\frac{1}{\epsilon})\) while maintaining the complexity of each iteration. The approach is an alternative to black-box minimization and leverages the structure of the problem to enhance convergence rates. The paper is organized into several sections. Section 2 introduces the problem and presents a method to create smooth approximations of non-smooth functions. Section 3 discusses an efficient scheme for minimizing smooth convex functions, which uses a specific norm to measure the curvature of the objective function. Section 4 applies the results to specific problem instances, including matrix games, continuous location problems, variational inequalities, and piece-wise linear function minimization, providing upper bounds on the complexity of finding \(\epsilon\)-solutions. Section 5 addresses implementation issues and modifications to the proposed algorithm, while Section 6 presents preliminary computational results comparing the proposed method with other techniques. The key contributions of the paper include a systematic way to approximate non-smooth functions with smooth ones, an efficient gradient scheme for minimizing these smooth functions, and a detailed analysis of the complexity and performance of the proposed method.This paper proposes a novel approach for constructing efficient schemes to solve non-smooth convex optimization problems. The method involves a special smoothing technique that can be applied to functions with explicit max-structure, improving the traditional efficiency bounds from \(O(\frac{1}{\epsilon^2})\) to \(O(\frac{1}{\epsilon})\) while maintaining the complexity of each iteration. The approach is an alternative to black-box minimization and leverages the structure of the problem to enhance convergence rates. The paper is organized into several sections. Section 2 introduces the problem and presents a method to create smooth approximations of non-smooth functions. Section 3 discusses an efficient scheme for minimizing smooth convex functions, which uses a specific norm to measure the curvature of the objective function. Section 4 applies the results to specific problem instances, including matrix games, continuous location problems, variational inequalities, and piece-wise linear function minimization, providing upper bounds on the complexity of finding \(\epsilon\)-solutions. Section 5 addresses implementation issues and modifications to the proposed algorithm, while Section 6 presents preliminary computational results comparing the proposed method with other techniques. The key contributions of the paper include a systematic way to approximate non-smooth functions with smooth ones, an efficient gradient scheme for minimizing these smooth functions, and a detailed analysis of the complexity and performance of the proposed method.