Optimization Online


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

Yurii Nesterov(Yurii.Nesterov***at***uclouvain.be)
Sergey Shipirko(Shpirko***at***yahoo.com)

Abstract: 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.

Keywords: Convex optimization, subgradient methods, huge-scale problems, sublinear iteration cost

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 08/30/2012
Entry Accepted: 08/30/2012
Entry Last Modified: 08/30/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society