Parallel Algorithms

Efficient parallel coordinate descent algorithm for convex optimization problems with separable constraints: application to distributed MPC

  • Dragos Clipici
  • Ion Necoara
    • Categories Control Applications, Convex Optimization, Parallel Algorithms Tags , , , ,

    In this paper we propose a parallel coordinate descent algorithm for solving smooth convex optimization problems with separable constraints that may arise e.g. in distributed model predictive control (MPC) for linear network systems. Our algorithm is based on block coordinate descent updates in parallel and has a very simple iteration. We prove (sub)linear rate of … Read more

    On parallelizing dual decomposition in stochastic integer programming

  • Miles Lubin
  • Kipp Martin
  • Burhaneddin Sandikçi
  • Cosmin G. Petra
    • Categories Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming Tags , , , , ,

    For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more

    Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems

  • Ion Necoara
  • Valentin Nedelcu
    • Categories Convex Optimization, Distributed Control, Parallel Algorithms Tags , , , , ,

    In this paper we propose two dual decomposition methods based on inexact dual gradient information for solving large-scale smooth convex optimization problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first order methods based on approximate gradients and we prove sublinear rate of convergence … Read more

    Convergence and Perturbation Resilience of Dynamic String-Averaging Projection Methods

  • Yair Censor
  • Alexander J. Zaslavski
    • Categories Biomedical Applications, Convex Optimization, Parallel Algorithms Tags , , , , , , , , ,

    We consider the convex feasibility problem (CFP) in Hilbert space and concentrate on the study of string-averaging projection (SAP) methods for the CFP, analyzing their convergence and their perturbation resilience. In the past, SAP methods were formulated with a single predetermined set of strings and a single predetermined set of weights. Here we extend the … Read more

    Parallel distributed-memory simplex for large-scale stochastic LP problems

  • Mihai Anitescu
  • J. A. Julian Hall
  • Miles Lubin
  • Cosmin G. Petra
    • Categories Linear Programming, Parallel Algorithms, Stochastic Programming Tags , , ,

    We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal … Read more

    What Could a Million Cores Do To Solve Integer Programs?

  • Thorsten Koch
  • Ted K. Ralphs
  • Yuji Shinano
    • Categories Integer Programming, Parallel Algorithms Tags , ,

    Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise … Read more

    A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

  • Frank Fischer
  • Christoph Helmberg
    • Categories Convex Optimization, Parallel Algorithms Tags , ,

    An algorithmic approach is proposed for exploiting parallelization possibilities in large scale optimization models of the following generic type. Objects change their state over time subject to a limited availability of common resources. These are modeled by linear coupling constraints and result in few objects competing for the same resource at each point in time. … Read more

    Distributed Basis Pursuit

  • Pedro Aguiar
  • João Mota
  • Markus Püschel
  • João Xavier
    • Categories Convex Optimization, Network Optimization, Parallel Algorithms Tags , , ,

    We propose a distributed algorithm for solving the optimization problem Basis Pursuit (BP). BP finds the least L1-norm solution of the underdetermined linear system Ax = b and is used, for example, in compressed sensing for reconstruction. Our algorithm solves BP on a distributed platform such as a sensor network, and is designed to minimize … Read more

    Efficient Serial and Parallel Coordinate Descent Methods for Huge-Scale Truss Topology Design

  • Peter Richtarik
  • Martin Takac
    • Categories Civil and Environmental Engineering, Convex Optimization, Parallel Algorithms Tags , , ,

    In this work we propose solving huge-scale instances of the truss topology design problem with coordinate descent methods. We develop four efficient codes: serial and parallel implementations of randomized and greedy rules for the selection of the variable (potential bar) to be updated in the next iteration. Both serial methods enjoy an O(n/k) iteration complexity … Read more

    Scalable Stochastic Optimization of Complex Energy Systems

  • Mihai Anitescu
  • Victor M. Zavala
  • Miles Lubin
  • Cosmin G. Petra
    • Categories Parallel Algorithms, Stochastic Programming Tags , , , ,

    We present a scalable approach and implementation for solving stochastic programming problems, with application to the optimization of complex energy systems under uncertainty. Stochastic programming is used to make decisions in the present while incorporating a model of uncertainty about future events (scenarios). These problems present serious computational difficulties as the number of scenarios becomes … Read more