Optimization Online


A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

Ion Necoara (ion.necoara***at***acse.pub.ro)
Andrei Patrascu (andrei.patrascu***at***acse.pub.ro)

Abstract: In this paper we present a variant of random coordinate descent method for solving linearly constrained convex optimization problems with composite objective function. If the smooth part has Lipschitz continuous gradient, then the method terminates with an ϵ-optimal solution in O(N2/ϵ) iterations, where N is the number of blocks. For the class of problems with cheap coordinate derivatives we show that the new method is faster than methods based on full-gradient information. Analysis for rate of convergence in probability is also provided. For strongly convex functions our method converges linearly.

Keywords: Coordinate descent, composite objective function, linear coupled constraints, randomized algorithms, convergence rate O(1/ϵ).

Category 1: Convex and Nonsmooth Optimization

Category 2: Applications -- Science and Engineering

Category 3: Network Optimization

Citation: Technical Report, University Politehnica Bucharest, Spl. Independentei 313, pp. 1-20, June, 2012.

Download: [PDF]

Entry Submitted: 11/02/2012
Entry Accepted: 11/02/2012
Entry Last Modified: 02/13/2013

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