Parallel Algorithms

Nonstationary Direct Policy Search for Risk-Averse Stochastic Optimization

  • Belgacem Bouzaiene-Ayari
  • Somayeh Moazeni
  • Boris Defourny
  • Warren B. Powell
    • Categories Dynamic Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    This paper presents an approach to non-stationary policy search for finite-horizon, discrete-time Markovian decision problems with large state spaces, constrained action sets, and a risk-sensitive optimality criterion. The methodology relies on modeling time variant policy parameters by a non-parametric response surface model for an indirect parametrized policy motivated by the Bellman equation. Through the interpolating … Read more

    Nonlinear Programming Strategies on High-Performance Computers

  • Naiyuan Chiang
  • Carl D. Laird
  • Victor M. Zavala
  • Jia Kang
    • Categories Constrained Nonlinear Optimization, Parallel Algorithms, Systems governed by Differential Equations Optimization

    We discuss structured nonlinear programming problems arising in control applications, and we review software and hardware capabilities that enable the efficient exploitation of such structures. We focus on linear algebra parallelization strategies and discuss how these interact and influence high-level algorithmic design elements required to enforce global convergence and deal with negative curvature in a … Read more

    Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs

  • Kibaek Kim
  • Victor M. Zavala
    • Categories Optimization Software and Modeling Systems, Parallel Algorithms, Stochastic Programming

    We develop algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide a parallel software implementation that we call DSP. Our innovations include the derivation of valid inequalities that tighten Lagrangian subproblems and that allow the guaranteed recovery of feasible solutions for problems without (relative) complete recourse. We … Read more

    ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

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

    We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex … Read more

    Parallelizing the dual revised simplex method

  • J. A. Julian Hall
  • Q. Huangfu
    • Categories Linear Programming, Parallel Algorithms

    This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational … Read more

    Object-Parallel Infrastructure for Implementing First-Order Methods, with an Example Application to LASSO

  • Jonathan Eckstein
  • Gyorgy Matyasfalvi
    • Categories Bound-constrained Optimization, Parallel Algorithms, Unconstrained Optimization Tags , ,

    We describe the design of a C++ vector-manipulation substrate that allows first-order optimization algorithms to be expressed in a concise and readable manner, yet still achieve high performance in parallel computing environments. We use standard object-oriented techniques of encapsulation and operator overloading, combined with a novel “symbolic temporaries” delayed-evaluation system that greatly reduces the overhead … Read more

    Coordinate descent algorithms

  • Stephen Wright
    • Categories Convex Optimization, Parallel Algorithms Tags , ,

    Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate … Read more

    PSMG-A Parallel Structured Model Generator for Mathematical Programming

  • Andreas Grothey
  • Feng Qiang
    • Categories Optimization Software and Modeling Systems, Parallel Algorithms

    In this paper, we present PSMG–Parallel Structured Model Generator–an efficient parallel implementation of a model generator for the structure conveying modelling language (SML[4]). Unlike the earlier proof-of-concept implementation presented with SML, PSMG does not depend on AMPL. The main purposes of PSMG are: to provide an easy to use framework for modelling and generating large … Read more

    A Parallel Line Search Subspace Correction Method for Composite Convex Optimization

  • Qian Dong
  • Xin Liu
  • Zaiwen Wen
  • Ya-xiang Yuan
    • Categories Convex and Nonsmooth Optimization, Parallel Algorithms Tags , , , ,

    In this paper, we investigate a parallel subspace correction framework for composite convex optimization. The variables are first divided into a few blocks based on certain rules. At each iteration, the algorithms solve a suitable subproblem on each block simultaneously, construct a search direction by combining their solutions on all blocks, then identify a new … Read more

    Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

  • Oleg A. Prokopyev
  • Andrew J. Schaefer
  • Gabriel L. Zenarosa
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller … Read more