distributed computing

Mind the \(\tilde{O}\): asymptotically better, but still impractical, quantum distributed algorithms

  • David E. Bernal Neira
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , , ,

    The CONGEST and CONGEST-CLIQUE models have been carefully studied to represent situations where the communication bandwidth between processors in a network is severely limited. Messages of only \( O(log(n)) \) bits of information each may be sent between processors in each round. The quantum versions of these models allow the processors instead to communicate and … Read more

    Compromise Policy for Multi-stage Stochastic Linear Programming: Variance and Bias Reduction

  • Jiajun Xu
  • Suvrajeet Sen
    • Categories Applications - Science and Engineering, Dynamic Programming, Stochastic Programming Tags , , , , ,

    This paper focuses on algorithms for multi-stage stochastic linear programming (MSLP). We propose an ensemble method named the “compromise policy”, which not only reduces the variance of the function approximation but also reduces the bias of the estimated optimal value. It provides a tight lower bound estimate with a confidence interval. By exploiting parallel computing, … Read more

    A Distributed and Secure Algorithm for Computing Dominant SVD Based on Projection Splitting

  • Xin Liu
  • Lei Wang
  • Yin Zhang
    • Categories Constrained Nonlinear Optimization, Parallel Algorithms Tags , , ,

    In this paper, we propose and study a distributed and secure algorithm for computing dominant (or truncated) singular value decompositions (SVD) of large and distributed data matrices. We consider the scenario where each node privately holds a subset of columns and only exchanges “safe” information with other nodes in a collaborative effort to calculate a … 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

    Block-wise Alternating Direction Method of Multipliers with Gaussian Back Substitution for Multiple-block Convex Programming

  • Xiaoling Fu
  • Bingsheng He
  • Xiangfeng Wang
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , , ,

    We consider the linearly constrained convex minimization model with a separable objective function which is the sum of m functions without coupled variables, and discuss how to design an efficient algorithm based on the fundamental technique of splitting the augmented Lagrangian method (ALM). Our focus is the specific big-data scenario where m is huge. A … Read more

    NLPQLP: A New Fortran Implementation of a Sequential Quadratic Programming Algorithm

  • Klaus Schittkowski
    • Categories Constrained Nonlinear Optimization, Optimization Software Benchmark, Parallel Algorithms Tags , , , , , ,

    The Fortran subroutine NLPQLP solves smooth nonlinear programming problems and is an extension of the code NLPQL. The new version is specifically tuned to run under distributed systems. A new input parameter l is introduced for the number of parallel machines, that is the number of function calls to be executed simultaneously. In case of … Read more