Parallel Algorithms

The Decentralized Trust-Region Method with Second-Order Approximations

  • Hong Wang
    • Categories Parallel Algorithms Tags , ,

    This paper presents a novel decentralized trust-region framework that systematically incorporates second-order information to solve general nonlinear optimization problems in multi-agent networks. Our approach constructs local quadratic models that simultaneously capture objective curvature and enforce consensus through penalty terms, while supporting multiple Hessian approximation strategies including exact Hessians, limited-memory quasi-Newton methods, diagonal preconditioners, and matrix-free … Read more

    GFORS: GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs

  • Ningji Wei
  • Jiaming Liang
    • Categories 0-1 Programming, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

    We present GFORS, a GPU-accelerated framework for large binary integer programs. It couples a first-order (PDHG-style) routine that guides the search in the continuous relaxation with a randomized, feasibility-aware sampling module that generates batched binary candidates. Both components are designed to run end-to-end on GPUs with minimal CPU–GPU synchronization. The framework establishes near-stationary-point guarantees for … Read more

    Smoothie: Mixing the strongest MIP solvers to solve hard MIP instances on supercomputers – Phase I development

  • Yuji Shinano
  • Stefan Vigerske
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

    Mixed-Integer Linear Programming (MIP) is applicable to such a wide range of real-world decision problems that the competition for the best code to solve such problems has lead to tremendous progress over the last decades. While current solvers can solve some of the problems that seemed completely out-of-reach just 10 years ago, there are always … Read more

    A note on asynchronous Projective Splitting in Julia

  • Utkarsh Sharma
  • Kashish Goel
  • Aryan Dua
  • Sebastian Pokutta
  • Zev Woodstock
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Parallel Algorithms

    While it has been mathematically proven that Projective Splitting (PS) algorithms can converge in parallel and distributed computing settings, to-date, it appears there were no open-source implementations of the full algorithm with asynchronous computing capabilities. This note fills this gap by providing a Julia implementation of the asynchronous PS algorithm of Eckstein and Combettes for … Read more

    New results related to cutters and to an extrapolated block-iterative method for finding a common fixed point of a collection of them

  • Yair Censor
  • Daniel Reem
  • Maroun Zaknoon
    • Categories Convex Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    Given a Hilbert space and a finite family of operators defined on the space, the common fixed point problem (CFPP) is to find a point in the intersection of the fixed point sets of these operators.  Instances of the problem have numerous applications in science and engineering. We consider an extrapolated block-iterative method with dynamic … Read more

    Fully First-Order Methods for Decentralized Bilevel Optimization

  • Xiaoyu Wang
  • Xuxing Chen
  • Shiqian Ma
  • Tong Zhang
    • Categories Nonlinear Optimization, Parallel Algorithms, Stochastic Programming Tags , , ,

    This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis … Read more

    MUSE-BB: A Decomposition Algorithm for Nonconvex Two-Stage Problems using Strong Multisection Branching

  • Marco Langiu
  • Manuel Dahmen
  • Dominik Bongartz
  • Alexander Mitsos
    • Categories Global Optimization, Parallel Algorithms, Stochastic Programming Tags , , , ,

    We present MUSE-BB, a branch-and-bound (B&B) based decomposition algorithm for the deterministic global solution of nonconvex two-stage stochastic programming problems. In contrast to three recent decomposition algorithms, which solve this type of problem in a projected form by nesting an inner B&B in an outer B&B on the first-stage variables, we branch on all variables … Read more

    Edge expansion of a graph: SDP-based computational strategies

  • Akshay Gupte
  • Melanie Siebenhofer
  • Angelika Wiegele
    • Categories Combinatorial Optimization, Parallel Algorithms, Semi-definite Programming Tags , , , ,

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relaxation first to reduce the search space considerably. The problem … Read more

    Similarity-based Decomposition Algorithm for Two-stage Stochastic Scheduling

  • Daniel Montes
  • José Luis Pitarch
  • Cesar de Prada
    • Categories Parallel Algorithms, Scheduling, Stochastic Programming Tags , ,

    This paper presents a novel decomposition method for two-stage stochastic mixed-integer optimization problems. The algorithm builds upon the idea of similarity between finite sample sets to measure how similar the first-stage decisions are among the uncertainty realization scenarios. Using such a Similarity Index, the non-anticipative constraints are removed from the problem formulation so that the … Read more

    Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees

  • Hamid Reza Feyzmahdavian
  • Mikael Johansson
    • Categories Convex Optimization, Global Optimization, Parallel Algorithms Tags , , , ,

    We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous optimization … Read more