  


Primaldual subgradient method for HugeScale Linear Conic Problems
Yurii Nesterov(Yurii.Nesterovuclouvain.be) Abstract: In this paper we develop a {\em primaldual} subgradient method for solving hugescale Linear Conic Optimization Problems. Our main assumption is that the primal cone is formed as a direct product of many smalldimensional convex cones, and that the matrix $A$ of corresponding linear operator is {\em uniformly sparse}. In this case, our method can approximate the primaldual 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, hugescale problems, sublinear iteration cost Category 1: Convex and Nonsmooth Optimization Category 2: Linear, Cone and Semidefinite Programming Citation: Download: [PDF] Entry Submitted: 08/30/2012 Modify/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  