Modern large-scale optimization faces a fundamental computational wall: as datasets and system complexities grow, the cost of finding a global solution often increases polynomially. A centralized solver attempting to process billions of variables or constraints simultaneously will eventually exceed the memory and processing limits of any single machine.
To overcome this, researchers have developed a family of techniques centered on parallel subproblem decomposition. The core intuition is simple: rather than solving one massive, monolithic problem, we can break it into many smaller, independent subproblems that can be solved simultaneously across multiple processors.
The Logic of Decomposition
The primary driver for decomposition is the non-linear scaling of optimization solvers. As Narayanan et al. observe, the computational cost of mathematical programming typically grows much faster than the problem size. By partitioning a massive resource allocation task into smaller chunks, the sum of the time taken to solve these subproblems is often orders of magnitude less than solving the original whole—a phenomenon known as super-linear speedup.
This partitioning can happen in several ways:
- Data Partitioning: Collobert et al. demonstrate this by training a "Mixture of SVMs," where a massive dataset is divided among local "expert" learners.
- Spatial Partitioning: In physical simulations, Qiao et al. show that partitioning collisions into independent impact zones linearizes the complexity of contact resolution.
- Scenario Partitioning: For problems involving uncertainty, Hemmi et al. and Andrade et al. decompose multistage stochastic programs into individual scenarios that are evaluated in parallel.
Coordination through Duality and Consensus
If subproblems are solved in total isolation, the resulting "global" solution might be inconsistent—for example, two agents might both try to use the same limited resource. The challenge is achieving consensus without re-introducing a centralized bottleneck.
The most common mechanism for this is Dual Decomposition. As explained by Nikos Komodakis, this framework uses "dual variables" (which act like prices) to coordinate subproblems. A master process updates these prices based on how much the subproblems disagree, driving them toward a global optimum.
A popular implementation of this is the Alternating Direction Method of Multipliers (ADMM). The authors of Moehle et al. use ADMM to break massive network flow problems into parallel single-scenario tasks. Similarly, Saravanos et al. utilize consensus ADMM to allow robotic agents to satisfy collision constraints by communicating only with their immediate neighbors, rather than a central controller.
Exploiting Problem Structure
Decomposition is most effective when the underlying problem has a specific mathematical "shape." Many real-world systems in chemical engineering and power grids exhibit a block-diagonal structure. Li and Grossmann highlight that this structure is the primary enabler for high-performance computing in stochastic optimization, as it allows the problem to be naturally uncoupled into parallel blocks.
In geometric processing, Stein et al. show that mesh optimization can be split into independent local updates for each element and a single global linear solve. This "splitting" allows the most computationally expensive parts of the task to be executed in an embarrassingly parallel fashion.
Scaling to Billion-Variable Problems
The ultimate goal of these methods is to leverage modern hardware like GPUs and distributed clusters. By decomposing problems into thousands of tiny, independent tasks, researchers can bypass the sequential bottlenecks of traditional solvers.
For instance, Kim and Kim achieved real-time tracking of massive power grids by solving thousands of subproblems in parallel on a GPU. At an even larger scale, Zhang et al. developed a framework that uses dual decomposition to solve resource allocation problems with one billion variables, a feat that would be impossible for any centralized, single-machine solver.
Through decomposition, the complexity of a problem is no longer defined by its total size, but by the size of its largest sub-component and the efficiency of the coordination mechanism.
Key Foundational Work
Local matching indicators for concave transport costs (2010) — contributed 1 concept elements to this direction.
A Parallel Mixture of SVMs for Very Large Scale Problems (2002) — contributed 1 concept elements to this direction.