Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
Primal-Dual Subgradient Method for Huge-Scale Linear Conic Problems
In this paper we develop a 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
uniformly sparse.
In this case, our method can
approximate the primal-dual optimal solution with accuracy ε in O(1/ε^2) iterations.
the same time, complexity of each iteration of this scheme does not exceed O(rq 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.

Авторы: Nesterov Yurii , Shpirko Sergei

Дата: 30 декабря 2014

Статус: опубликована

Журнал: SIAM Journal on Optimization

Том: 24

Выпуск: 3

Страницы: 1444-1457

Год: 2014

Google scholar:

Направления исследований

Primal-dual subgradient methods

Huge-scale problems