Domain decomposition preconditioners for Schur complement systems arising in structured nonlinear optimization problems

Laurens R. Lueg, Michael Bynum, Carl D. Laird, Lorenz T. BieglerOptimization 2025 · DOI

TL;DR

This paper introduces a parallel framework for solving massive, structured nonlinear optimization problems by applying domain decomposition techniques directly to the underlying linear algebra. By using novel distributed preconditioners—specifically a "diagonally-assembled" Additive Schwarz method—the authors demonstrate that we can solve complex engineering and public health models across thousands of processor cores with excellent scaling performance.

What Problem Does This Paper Address?

Many real-world challenges, from managing power grids to predicting the spread of a virus, are modeled as large-scale Nonlinear Programs (NLPs). These problems are often "structured," meaning variables are tied to specific locations or time points, and they only interact with their immediate neighbors (a "sparse graph" structure).

The gold standard for solving these is the Interior Point Method (IPM). However, as these problems grow to include millions of variables, the linear algebra at the heart of the IPM becomes a massive computational bottleneck. Specifically, the "Schur complement system"—the part of the math that coordinates interactions between different parts of the problem—is traditionally solved serially or with limited parallelism. This paper tackles the challenge of making that step truly distributed and scalable.

Methods

The authors implement an internal decomposition approach within the IPM. Instead of solving the entire massive system at once, they break it into partitions. The key steps include:

  1. Schur Complement Decomposition: They isolate the "complicating variables" (the ones that link different partitions) into a smaller but often dense system.
  2. Iterative Solving with PCG: Instead of factorizing the Schur matrix (which is slow and memory-intensive), they use the Preconditioned Conjugate Gradient (PCG) method.
  3. Novel Preconditioners: To make PCG converge quickly, they propose and compare several algebraic preconditioners:
  4. Block-Jacobi (BJ): A simple approach that ignores interactions between partitions during preconditioning.
  5. Additive Schwarz (AS): A more complex method that accounts for overlapping interactions but requires high communication.
  6. Diagonally-Assembled Additive Schwarz (ASd): A "middle ground" innovation that shares only the diagonal elements of the Schur complement across processors. This captures essential linking information with much lower communication overhead.

The methods were implemented in the open-source software package PARAPINT, which works with the Pyomo modeling language.

Datasets

The researchers evaluated their methods on two high-dimensional synthetic benchmarks:

  • Infectious Disease Model: A parameter estimation problem based on a 2D grid of 4,096 counties (64x64) over 200 time steps. This creates a spatio-temporal graph where each county interacts with its neighbors.
  • PDE-Constrained Optimal Control: A problem involving a parabolic partial differential equation (similar to Burgers’ equation) discretized into 200 points in space and 1,024 points in time, decomposed along the temporal axis.

Key Insights and Ideas

  • The "Sparsity" Advantage: In spatio-temporal problems, the Schur complement isn't just a random matrix; its structure mirrors the physical connections of the problem. The authors realized that for very sparse grids, the diagonal of the Schur complement contains the most critical "coupling" information.
  • Super-linear Scaling: For the disease model, the authors observed super-linear scaling (where doubling processors more than doubles speed) between 64 and 256 ranks. This happens because as partitions get smaller, the local work decreases super-linearly, and the local data fits better into the processor's cache.
  • Communication vs. Convergence: While the full Additive Schwarz (AS) preconditioner required the fewest iterations to converge, it wasn't always the fastest in "wall-clock" time because of the time spent moving data between processors. The ASd variant proved to be the "sweet spot" for performance.

Key Results

  • Strong Scaling: The methods demonstrated successful scaling up to 1,024 MPI ranks on the Bridges-2 supercomputer.
  • Superiority over Serial Methods: The distributed preconditioners (BJ, AS, ASd) significantly outperformed the standard serial Incomplete Cholesky (spIC) approach as the number of partitions increased.
  • Direct Solver Comparison: On a medium-scale instance, the proposed decomposition approach scaled much better than the industry-standard MKL PARDISO direct solver as the number of parallel threads increased.
  • Efficiency: For the PDE problem, the ASd method spent over 80% of its time on parallelizable local tasks, suggesting it could scale even further beyond 1,024 cores.

Limitations and Future Work

  • Global Convergence: The current implementation in PARAPINT lacks a "filter line search," which is technically required to guarantee the solver finds a solution for any starting point.
  • Tight Tolerances: To ensure accuracy, the authors had to solve the linear systems to a very tight tolerance ($10^{-9}$), which increases the number of PCG iterations.
  • "Other" Time Bottlenecks: As the linear algebra becomes faster through parallelization, other parts of the code (like evaluating the objective function or checking convergence) start to become the new bottlenecks.
  • Future Directions: The authors suggest exploring "two-level" preconditioners (adding a coarse-grid correction) and using batched linear solvers like PARDISO to speed up the formation of local Schur components.

Summary updated

Abstract

Abstract Large-scale nonlinear, nonconvex optimization problems arise in many relevant engineering applications, such as integrated energy systems, public health, or supply-chain logistics. Their solution is often challenging due to problem scale, significant spatio-temporal interactions, or time constraints (e.g. for real-time operations). This work focuses on decomposition strategies for nonlinear problems with distributed structure, where interactions between problem partitions can be defined over sparse graphs. Parallelization is achieved on the linear algebra level within an interior point algorithm using the Schur complement method, and we propose several distributed algebraic preconditioners for the Schur complement system, based on approaches from the field of domain decomposition. We demonstrate promising strong scaling results on large-scale problem instances for parameter estimation of infectious disease models and PDE-constrained optimal control.
BibTeX
@inproceedings{lueg2025domain,
  author = {Laurens R. Lueg and Michael Bynum and Carl D. Laird and Lorenz T. Biegler},
  title = {{Domain decomposition preconditioners for Schur complement systems arising in structured nonlinear optimization problems}},
  booktitle = {Optimization},
  year = {2025},
  doi = {10.1007/s11081-025-10020-1},
}
Figure