Parallel Algorithms

Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part I: Model and Convergence

  • Loris Cannelli
  • Francisco Facchinei
  • Vyacheslav Kungurtsev
  • Gesualdo Scutari
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , ,

    We propose a novel asynchronous parallel algorithmic framework for the minimization of the sum of a smooth nonconvex function and a convex nonsmooth regularizer, subject to both convex and nonconvex constraints. The proposed framework hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of modern computational architectures and asynchronous … Read more

    Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part II: Complexity and Numerical Results

  • Loris Cannelli
  • Francisco Facchinei
  • Vyacheslav Kungurtsev
  • Gesualdo Scutari
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , ,

    We present complexity and numerical results for a new asynchronous parallel algorithmic method for the minimization of the sum of a smooth nonconvex function and a convex nonsmooth regularizer, subject to both convex and nonconvex constraints. The proposed method hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of … Read more

    On the Convergence of Asynchronous Parallel Iteration with Arbitrary Delays

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
    • Categories Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call \emph{delay}, is the number of times it has been … Read more

    A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems

  • Natashia Boland
  • Brian Dandurand
  • Andrew C. Eberhard
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. The dual solution approach needs … Read more

    Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server

  • Arda Aytekin
  • Hamid Reza Feyzmahdavian
  • Mikael Johansson
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    This paper presents an asynchronous incremental aggregated gradient algorithm and its implementation in a parameter server framework for solving regularized optimization problems. The algorithm can handle both general convex (possibly non-smooth) regularizers and general convex constraints. When the empirical data loss is strongly convex, we establish linear convergence rate, give explicit expressions for step-size choices … Read more

    On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms

  • Robert Hannah
  • Wotao Yin
    • Categories Convex Optimization, Parallel Algorithms Tags , , , ,

    The need for scalable numerical solutions has motivated the development of asynchronous parallel algorithms, where a set of nodes run in parallel with little or no synchronization, thus computing with delayed information. This paper studies the convergence of the asynchronous parallel algorithm ARock under potentially unbounded delays. ARock is a general asynchronous algorithm that has … Read more

    TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods

  • Brent Edmunds
  • Zhimin Peng
  • Wotao Yin
    • Categories Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    TMAC is a toolbox written in C++11 that implements algorithms based on a set of mod- ern methods for large-scale optimization. It covers a variety of optimization problems, which can be both smooth and nonsmooth, convex and nonconvex, as well as constrained and unconstrained. The algorithms implemented in TMAC, such as the coordinate up- date … Read more

    Alternating Criteria Search: A Parallel Large Neighborhood Search Algorithm for Mixed Integer Programs

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • David A. Bader
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

    We present a parallel large neighborhood search framework for finding high quality primal solutions for generic Mixed Integer Programs (MIPs). The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary … Read more

    Coordinate Friendly Structures, Algorithms and Applications

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
  • Tianyu Wu
    • Categories Convex Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    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 … Read more

    A Distributed Interior-Point KKT Solver for Multistage Stochastic Optimization

  • Hübner Jens
  • Martin Schmidt
  • Marc C. Steinbach
    • Categories Finance and Economics, Parallel Algorithms, Stochastic Programming Tags , , , ,

    Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate … Read more