• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Primal-dual subgradient methods for huge-scale linear conic problems. SIOPT

SIAM Journal on Optimization. 2014. Vol. 24. No. 3. P. 1444-1457.
Nesterov Y., Shpirko S.

In this paper we develop a {\em primal-dual} subgradient method for solving huge-scale Linear Conic Optimization Problems. Our main assumption is that the primal cone is formed as a direct product of many small-dimensional convex cones, and that the matrix $A$ of corresponding linear operator is {\em uniformly sparse}. In this case, our method can approximate the primal-dual optimal solution with accuracy $\epsilon$ in $O\left({1 \over \epsilon^2}\right)$ iterations. At the same time, complexity of each iteration of this scheme does not exceed $O(r q \log_2 n)$ operations, where $r$ and $q$ are the maximal numbers of nonzero elements in the rows and columns of matrix $A$, and $n$ is the number variables.