Enforcing Convergence in Sensitivity-based Distributed Programming via Transformed Primal-Dual Updates

Maximilian Pierer von Esch, Andreas Völz, Knut Graichen · 2025

Read Enforcing Convergence in Sensitivity-based Distributed Programming via Transformed Primal-Dual Updates by Maximilian Pierer von Esch, Andreas Völz, Knut Graichen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15938.txt.

Introduction

Maximilian Pierer von Esch, Andreas Völz, and Knut Graichen fix a distributed solver for coupled problems. Their base method splits a large nonlinear program across a network of subsystems. Each part uses sensitivity facts and talks to neighbors. Whether the base method converges hinges on how strongly the parts couple, a real limit in practice.

Their upgrade, SBDP+, reshapes the joint update of the core variables and their dual partners. Local subproblems stay small and run in parallel. They prove the method settles at a linear rate near a solution, for general coupling shapes and for non convex problems that meet standard conditions. Tests in statistical learning and beyond show stronger robustness than the base method and peer solvers. The design keeps communication neighbor to neighbor.

Catalog record

CREATORMaximilian Pierer von Esch, Andreas Völz, Knut Graichen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-15938

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Enforcing Convergence in Sensitivity-based Distributed Programming via Transformed Primal-Dual Updates Thanks: This work is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under project no. 464391622. Maximilian Pierer von Esch, Andreas Völz, Knut Graichen Abstract Sensitivity-based distributed programming (SBDP) is an algorithm for solving large-scale, nonlinear programs over graph-structured networks. However, its convergence depends on the coupling strength and structure between subsystems. To address this limitation, we develop an algorithmic variant: SBDP+. The proposed method utilizes first-order sensitivities and primal decomposition to formulate low-dimensional, decoupled subproblems, which are solved in parallel with neighbor-to-neighbor communication. SBDP+ differs from SBDP by enforcing convergence for all coupling structures through a carefully designed primal-dual update. It retains a low communication effort and handles couplings in the objective and constraints. We establish sufficient conditions for local convergence in the non-convex case. The effectiveness of the method is shown by solving various distributed optimization problems, including statistical learning, with a comparison to state-of-the-art algorithms. keywords Distributed optimization, non-convex optimization, large-scale problems, statistical learning † † runningheads: Sensitivity-based Distributed Programming / M. Pierer v. Esch, A. Völz, and K. Graichen MSC 90C06, 90C30, 68W15 1 Introduction Large-scale nonlinear optimization problems arise in a wide range of applications, including statistical learning with high-dimensional data or features [ 3 ] , economical optimization problems [ 30 ] , electrical power systems [ 17 ] , and distributed nonlinear predictive control (DMPC) [ 4 ] . These problems often feature separable objectives and structured couplings, which distributed optimization techniques can exploit by decomposing the global problem into smaller, parallelizable subproblems. This enables local computation with limited communication, offering significant advantages over centralized methods in terms of scalability, flexibility, and robustness. Therefore, a wide range of distributed algorithms have been developed. Popular approaches for constrained, convex problems include distributed projected gradient descent [ 31 ] , dual decomposition [ 9 ] , distributed non-smooth Newton methods [ 12 ] or the alternating direction method of multipliers (ADMM) [ 3 ] . However, a large share of relevant applications requires to solve non-convex problems for which the algorithms mentioned above might diverge or only find a suboptimal solution in terms of a non-vanishing duality gap. Consequently, research has shifted towards distributed non-convex optimization techniques. A straightforward approach is to distribute the internal operations of standard nonlinear programming methods such as sequential quadratic programming (SQP), interior point methods (IPM) or augmented Lagrangian schemes. Examples include using ADMM to solve the quadratic programs (QP) arising in SQP [ 26 ] , distributing the Newton step in IPMs via ADMM [ 8 ] or exploiting the locally convex structure of augmented Lagrangian functions to apply dual decomposition [ 1 ] or distributed proximal minimization techniques [ 13 ] . The augmented Lagrangian alternating direction inexact Newton (ALADIN) method aims at combining SQP and ADMM and is a well-established approach for non-convex problems [ 14 ] , but relies on a central coordination step which may jeopardize scalability. This issue can be addressed with a bi-level scheme by distributing the coordination step using methods such as ADMM [ 7 ] . These algorithms often rely on a generalized consensus formulation [ 3 ] , where additional optimization variables are introduced for shared components for which consistency is enforced via consensus constraints. Then, the dual formulation of the problem is used to solve the problem in distributed fashion. In contrast, primal decomposition methods iterate directly on the shared variables, avoiding the need for strong duality and resulting in smaller subproblem dimensions. Next to Jacobi iterations [ 5 ] and forward-backward splitting [ 27 ] , sensitivity-based distributed programming (SBDP) has recently become a promising alternative. Prior work demonstrates its effectiveness in linear-quadratic settings [ 23 , 25 , 24 ] , for optimal control [ 20 ] , general NLPs [ 22 ] or real-time DMPC [ 21 ] . However, existing convergence results for SBDP depend on the coupling structure and require a generalized diagonal dominance (GDD) condition [ 23 , 25 , 22 ] or a sufficiently short prediction horizon [ 20 , 22 ] . This motivates the development of SBDP+, an algorithmic variant of SBDP to solve general, non-convex NLPs over graph-structured networks in a distributed fashion via neighbor-to-neighbor communication. Hereby, non-convexity is understood in the same sense as in e.g. [ 14 , 7 , 26 ] , that is, we assume the existence of regular local minima, while allowing the objective and constraint functions to be non-convex, and provide local convergence guarantees to these minima. Building upon the original idea of SBDP, the method uses first-order sensitivities to capture the interaction between subsystems and applies primal decomposition to construct lower-dimensional, decoupled NLPs. We formulate the local NLPs in terms of a search direction which, together with the local Lagrange multipliers, is used to update the original primal and dual variables. In this sense, we first decompose and then optimize with classical NLP algorithms. This is in contrast to first applying NLP solvers and then decomposing their internal operations. We argue that this reduces the time-expensive communication by limiting it to the algorithm’s upper layer and allows for greater flexibility in choosing suitable NLP solvers. Furthermore, we rigorously investigate the convergence properties of SBDP+ and show linear convergence under appropriate assumptions. We compare the scheme to state-of-the-art algorithms for (non-)convex optimization such as ADMM [ 3 ] , ALADIN [ 14 ] and bi-level ALADIN [ 7 ] . The paper is structured as follows: Section 2 states the problem formulation, for which the distributed solution via SBDP+ is given in Section 3 . Local convergence is analyzed in Section 4 , before algorithmic extensions are presented in Section 5 . The numerical evaluation is given in Section 6 . Afterward, the findings are summarized in Section 7 . Notation: For a vector \boldsymbol{v}\in\mathbb{R}^{n} and matrix \boldsymbol{M}\in\mathbb{R}^{n\times m} , the notations [\boldsymbol{v}]_{i} and [\boldsymbol{M}]_{i} refer to the i -th component and i -th row of \boldsymbol{v} and \boldsymbol{M} , respectively. Given an ordered index set \mathcal{S}\subset\mathbb{N} , [\boldsymbol{M}]_{\mathcal{S}} denotes the sub-matrix of rows [\boldsymbol{M}]_{i} , i\in\mathcal{S} and [\boldsymbol{v}_{i}]_{i\in\mathcal{S}} denotes the stacked vector of all \boldsymbol{v}_{i}\in\mathbb{R}^{n_{i}} . Norms without subscript, i.e., \|\cdot\| , refer to the Euclidean or induced spectral norm. The maximum and minimum eigenvalues of a square matrix are denoted by \bar{\lambda}(\cdot) and \underline{\lambda}(\cdot) . The integer set from 0 to N is \mathbb{N}_{[0,N]} . An open r -neighborhood of a point \boldsymbol{v}_{0}\in\mathbb{R}^{n} is defined as \mathcal{B}_{r}(\boldsymbol{v}_{0}):=\{\boldsymbol{v}\in\mathbb{R}^{n}\,|\,\|\boldsymbol{v}-\boldsymbol{v}_{0}\|<r\} . For a vector-valued function \boldsymbol{f}(\boldsymbol{x}):\mathbb{R}^{n}\rightarrow\mathbb{R}^{m} , the Jacobian is \nabla\boldsymbol{f}(\boldsymbol{x})=[\nabla f_{1}(\boldsymbol{x}),\dots,\nabla f_{m}(\boldsymbol{x})]^{\top}\in\mathbb{R}^{m\times n} , whereby \nabla f_{i} is the gradient of the i -th component and \nabla^{\top}f_{i} its transpose. 2 Problem Statement We consider NLPs structured over an undirected, connected graph \mathcal{G}=(\mathcal{V},\mathcal{E}) , where the node set \mathcal{V}=\{1,\dots,M\} represents a collection of subsystems, referred to as agents. The edge set \mathcal{E}\subset\mathcal{V}\times\mathcal{V} encodes the coupling between them. The agents cooperatively solve the central NLP \displaystyle\min_{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{M}} \displaystyle\quad\sum_{i\in\mathcal{V}}f_{i}(\boldsymbol{x}_{i},\boldsymbol{x}_{\mathcal{N}_{i}}) (1a) \displaystyle~\operatorname{s.\!t.}\quad \displaystyle\quad\boldsymbol{g}_{i}(\boldsymbol{x}_{i},\boldsymbol{x}_{\mathcal{N}_{i}})=\boldsymbol{0} \displaystyle\quad|\,\, \displaystyle\boldsymbol{\lambda}_{i}\,, \displaystyle i\in\mathcal{V} (1b) \displaystyle\quad\boldsymbol{h}_{i}(\boldsymbol{x}_{i},\boldsymbol{x}_{\mathcal{N}_{i}})\leq\boldsymbol{0} \displaystyle\quad|\,\, \displaystyle\boldsymbol{\mu}_{i}\,, \displaystyle i\in\mathcal{V} (1c) with the local decision variables \boldsymbol{x}_{i}\in\mathbb{R}^{n_{i}} , i\in\mathcal{V} . The notation after the constraints in ( 1 ) highlights that the quantities \boldsymbol{\lambda}_{i}\in\mathbb{R}^{n_{gi}} and \boldsymbol{\mu}_{i}\in\mathbb{R}^{n_{hi}} represent the Lagrange multipliers associated with the constraints

Read the complete text