huge-scale problems

Primal-dual subgradient method for Huge-Scale Linear Conic Problems

  • Yurii Nesterov
  • Sergey Shipirko
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    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 … Read more

    Subgradient methods for huge-scale optimization problems

  • Yurii Nesterov
    • Categories Nonsmooth Optimization Tags , , , ,

    We consider a new class of huge-scale problems, the problems with {\em sparse subgradients}. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends {\em logarithmically} in the dimension. This technique is … Read more