Optimization Online


Coordinate Friendly Structures, Algorithms and Applications

Zhimin Peng (zhimin.peng***at***math.ucla.edu)
Tianyu Wu (wuty11***at***math.ucla.edu)
Yangyang Xu (yangyang***at***ima.umn.edu)
Ming Yan (yanm***at***math.msu.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize. The great performance of coordinate update methods depends on solving simple subproblems. To derive simple subproblems for several new classes of applications, this paper systematically studies coordinate friendly operators that perform low-cost coordinate updates. Based on the discovered coordinate friendly operators, as well as operator splitting techniques, we obtain new coordinate update algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history. The obtained algorithms are scalable to large instances through parallel and even asynchronous computing. We present numerical examples to illustrate how effective these algorithms are.

Keywords: coordinate update, fixed-point, operator splitting, parallel, asynchronous

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 03/07/2016
Entry Accepted: 03/07/2016
Entry Last Modified: 08/16/2016

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