Parallel Algorithms

DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization

  • Weizhu Chen
  • Qihang Lin
  • Lin Xiao
  • Wei Yu
    • Categories Convex and Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    Machine learning with big data often involves large optimization models. For distributed optimization over a cluster of machines, frequent communication and synchronization of all model parameters (optimization variables) can be very costly. A promising solution is to use parameter servers to store different subsets of the model parameters, and update them asynchronously at different machines … Read more

    Parallel Solvers for Mixed Integer Linear Optimization

  • Timo Berthold
  • Thorsten Koch
  • Ted K. Ralphs
  • Yuji Shinano
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Parallel Algorithms Tags , , ,

    In this article, we provide an overview of the current state of the art with respect to solution of mixed integer linear optimization problems (MILPS) in parallel. Sequential algorithms for solving MILPs have improved substantially in the last two decades and commercial MILP solvers are now considered effective off-the-shelf tools for optimization. Although concerted development … Read more

    FiberSCIP – A shared memory parallelization of SCIP

  • Stefan Heinz
  • Yuji Shinano
  • Stefan Vigerske
  • Michael Winkler
    • Categories Integer Programming, Parallel Algorithms

    Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There … Read more

    Symmetric ADMM with Positive-Indefinite Proximal Regularization for Linearly Constrained Convex Optimization

  • Bin Gao
  • Feng Ma
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Parallel Algorithms Tags , , ,

    The proximal ADMM which adds proximal regularizations to ADMM’s subproblems is a popular and useful method for linearly constrained separable convex problems, especially its linearized case. A well-known requirement on guaranteeing the convergence of the method in the literature is that the proximal regularization must be positive semidefinite. Recently it was shown by He et … Read more

    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