This paper presents new coordinate descent methods for solving large-scale optimization problems. The methods use random partial updates of decision variables, which are more efficient than traditional full-gradient methods for large problems. The authors prove global convergence rates for these methods and show that, for certain classes of objective functions, they outperform standard worst-case bounds for deterministic algorithms. The methods are presented in both constrained and unconstrained versions, with an accelerated variant. Numerical tests confirm the high efficiency of these methods on very large-scale problems. The paper also discusses the computational complexity of these methods and provides worst-case efficiency estimates. The methods are shown to be effective for problems with expensive coordinate derivatives, as their convergence rate depends on an upper bound for the average diagonal element of the Hessian of the objective function. The paper concludes with implementation details and numerical test results.This paper presents new coordinate descent methods for solving large-scale optimization problems. The methods use random partial updates of decision variables, which are more efficient than traditional full-gradient methods for large problems. The authors prove global convergence rates for these methods and show that, for certain classes of objective functions, they outperform standard worst-case bounds for deterministic algorithms. The methods are presented in both constrained and unconstrained versions, with an accelerated variant. Numerical tests confirm the high efficiency of these methods on very large-scale problems. The paper also discusses the computational complexity of these methods and provides worst-case efficiency estimates. The methods are shown to be effective for problems with expensive coordinate derivatives, as their convergence rate depends on an upper bound for the average diagonal element of the Hessian of the objective function. The paper concludes with implementation details and numerical test results.