期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2010
卷号：2010
期号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：In this paper we propose new methods for solving huge-scale optimization problems. For problems of this
size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply
an optimization technique based on random partial update of decision variables. For these methods, we
prove the global estimates for the rate of convergence. Surprisingly enough, for certain classes of
objective functions, our results are better than the standard worst-case bounds for deterministic
algorithms. We present constrained and unconstrained versions of the method, and its accelerated variant.
Our numerical test confirms a high efficiency of this technique on problems of very big size.
关键词：Convex optimization, coordinate relaxation, worst-case efficiency estimates, fast gradient
schemes, Google problem.
