  We present an overlapping Schwarz decomposition algorithm for constrained
quadratic programs (QPs). Schwarz algorithms have been traditionally used to
solve linear algebra systems arising from partial differential equations, but
we have recently shown that they are also effective at solving structured
optimization problems. In the proposed scheme, we consider QPs whose algebraic
structure can be represented by graphs. The graph domain is partitioned into
overlapping subdomains (yielding a set of coupled subproblems), solutions for
the subproblems are computed in parallel, and convergence is enforced by
updating primal-dual information in the overlapping regions. We show that
convergence is guaranteed if the overlap is sufficiently large and that the
convergence rate improves exponentially with the size of the overlap.
Convergence results rely on a key property of graph-structured problems that is
known as exponential decay of sensitivity. Here, we establish conditions under
which this property holds for constrained QPs (as those found in network
optimization and optimal control), thus extending existing work that addresses
unconstrained QPs. The numerical behavior of the Schwarz scheme is demonstrated
by using a DC optimal power flow problem defined over a network with 9,241
nodes.
