- Primal-dual subgradient method for Huge-Scale Linear Conic Problems Yurii Nesterov(Yurii.Nesterovuclouvain.be) Sergey Shipirko(Shpirkoyahoo.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 Citation: Download: [PDF]Entry Submitted: 08/30/2012Entry Accepted: 08/30/2012Entry Last Modified: 08/30/2012Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.