The efficient solution of huge-scale sparse systems of linear or linearized equations poses a pivotal question in many applications of optimization and, with that, in numerical linear algebra. In particular, the design of bespoke iterative solvers is often invaluable, in order to mitigate the large storage requirements that may be required by off-the-shelf methods for systems of very high dimensions. In order to make a numerical solver feasible and effective, information about the linear system and the structure of the optimization problem from which it is obtained must frequently be taken into account when designing the solver.

A broad class of optimization problems with numerous applications involves sparsely-connected optimization problems. These consist of a series of constrained subproblems linked through a relatively small subset of variables. A general form of such problems can be written as

\begin{equation} \begin{alignedat}{3} \min _{\zeta _1, \dots , \zeta _N}\quad & \sum _{i=1}^N \phi _i\left (\zeta _i\right )\span \span \\ \text {s.t.}\quad && C_{i, j}^+ \zeta _i + C_{i, j}^- \zeta _j &= 0 \text { for all } (i, j) \in \mathbb {A}, \\ && c_i\left (\zeta _i\right ) &= 0 \text { for all } i \in \mathbb {V}, \end {alignedat} \label {eq:nlp} \end{equation}

where \(\mathbb {V} = \{1, \dots , N\}\) with \(N \in \mathbb {N}\) is an index set for the subproblems, and \(\mathbb {A} \subseteq \mathbb {V} \times \mathbb {V}\) represent the connecting graph. The functions \(\phi _i\) denote the optimization functionals, \(c_i\) the constraint for each subproblem, and the vectors \(\zeta _i \in \mathbb {R}^{n_i}\) are to be determined. These problems play a crucial role in engineering applications, including stochastic programming, robust nonlinear model predictive control, and optimal control of networks (e.g., gas pipelines). They are also relevant in domain decomposition methods for partial differential equations (PDEs) and parallel-in-time approaches. Upon discretization and linearization, problem (1) reduces to a large-scale sparse linear system of saddle-point structure of which the efficient solution is desirable.

In this talk, we derive a suite of direct and (in particular) iterative solvers for saddle-point systems with a tree-coupled structure [2], corresponding to a special case of a linearization of (1). Specifically, we extend well-studied structure-exploiting approaches for saddle-point systems [1] by incorporating the graph-based coupling structure, where interactions between the individual and otherwise isolated subsystems are expressed via generic coupling constraints. This allows us to make use of the special, sparse structure of the resulting Schur complement. We develop a range of structured preconditioners which may be embedded within suitable Krylov subspace methods, including block preconditioners, recursive preconditioners, and multi-level approaches. The majority of these methods are vastly parallelizable, allowing them to be applied in a real-time fashion. We prove a range of results relating to the convergence, complexity, and spectral properties of our algorithms. The performance of the preconditioners is showcased by applying them to an array of model problems. This includes model predictive control, multiple shooting for optimal control, and domain decomposition for PDEs. The numerical experiments validate our theoretical results and show improved performance over direct methods. Additionally, the experiments show that our methods are capable of coping with very large regimes of \(N\).

We, furthermore, outline future work on the analysis of coupled systems with an even more general graph-based structure, including cyclic dependencies and the derivation of methods to automatically detect this exploitable structure within given linear systems. There is also the potential to combine this with parallel-in-time methodologies derived by the author for fluid flow control problems [3]. Moreover, we discuss the potential of this method to be embedded within the sequential homotopy method [4], which leads to global convergence for a number of nonlinear optimization problems.

References

• [1]  Jacek Gondzio and Andreas Grothey. Parallel interior-point solver for structured quadratic programs: Application to financial planning problems. Annals of Operations Research, 152:319–339, 2007.

• [2]  Christoph Hansknecht, Bernhard Heinzelreiter, John W. Pearson, and Andreas Potschka. A framework for the solution of tree-coupled saddle-point systems. arXiv:2410.23385. 2024.

• [3]  Bernhard Heinzelreiter and John W. Pearson. Diagonalization-based parallel-in-time preconditioners for instationary fluid flow control problems. arXiv:2405.18964. 2024.

• [4]  Andreas Potschka and Hans Georg Bock. A sequential homotopy method for mathematical programming problems. Mathematical Programming, Series A, 187(1–2):459–486, 2021.