Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP Yingxin Zhou, Stefano Cipolla, Phan Tu Vuong Abstract We present the Anderson Accelerated Primal–Dual Hybrid Gradient (AA-PDHG), a fixed-point-based framework designed to overcome the slow convergence of the standard PDHG method for the solution of linear programming (LP) problems. We establish the global convergence of AA-PDHG under a safeguard condition. In addition, we propose a filtered variant (FAA-PDHG) that applies angle and length filtering to preserve the uniform boundedness of the coefficient matrix, a property crucial for guaranteeing convergence. Numerical results show that both AA-PDHG and FAA-PDHG deliver significant speedups over vanilla PDHG for large-scale LP instances. 1 Introduction In recent years, first-order methods have become increasingly popular for solving large-scale convex optimization problems, particularly due to their low per-iteration cost and favorable scalability. Among them, the Primal Dual Hybrid Gradient (PDHG) method has received considerable attention. If we consider a min-max problem in the form: \displaystyle\min_{x}\max_{z}\;f(x)+z^{{}^{\top}}Kx-g^{*}(z), where f and g are proper, closed, and convex functions, g^{*} denotes the conjugate function of g , and K is a linear operator, then the corresponding PDHG scheme can be written as \begin{split}x^{k+1}&=\arg\min_{x}\left\{f(x)+\frac{1}{2\tau}\left\|x-\left(x^{k}-\tau K^{{}^{\top}}z^{k}\right)\right\|^{2}\right\},\\ z^{k+1}&=\arg\min_{z}\left\{g^{*}(z)+\frac{1}{2\sigma}\left\|z-\left(z^{k}+\sigma K\left(2x^{k+1}-x^{k}\right)\right)\right\|^{2}\right\},\end{split} (1) being \tau,\;\sigma step-sizes. This algorithm is also commonly referred to as the Chambolle–Pock algorithm ChambollePDHG . When the updates in ( 1 ) are specialised for the solution of linear programs (LP), see ( 8 ), it is possible to observe a major advantage of PDHG when compared to other first or second-order optimization methods, that is, it requires only matrix-vector multiplications at each iteration, thereby avoiding solution of linear systems and related expensive matrix factorisations. Such a characteristic is often referred to as matrix-free in the literature, as also discussed in ChambollePDHG . This characteristic, combined with the fact that the matrix-vector product is a highly parallelizable task, makes PDHG particularly attractive for large-scale applications. And indeed, the use of PDHG for solving LP problems has recently gathered a lot of attention, see, e.g., PGLP87 ; SDLP89 ; AFOM-SPECIAL-LP11 ; ADMMLP17 ; AFOM-SPECIAL-LP19 ; fasterPDHG-23 , which have demonstrated that PDHG might offer a more scalable alternative to classical LP methods, such as interior-point or simplex methods. Nonetheless, when applied to LP problems, the PDHG method might still exhibit relatively slow convergence in practice. In particular, it often suffers from stagnation in the later stages of optimization, especially when approaching optimal solutions. This is because linear programming problems lack strong convexity, making PDHG achieve only sublinear convergence rates first-order-beck . As a result, obtaining high-precision solutions within a reasonable computational time remains difficult, especially in large-scale or ill-conditioned scenarios. Motivated by the above discussion, in this work, we explore the integration of acceleration techniques within the PDHG framework for solving large-scale linear programming problems. It is important to note that in some works it has been shown that LP problems possessing special properties, e.g., sharpness fasterPDHG-23 or error bounds QEB-FE2023 , can support faster convergence rates for first-order methods. These properties can be leveraged to theoretically establish faster convergence rates for first-order methods applied to LPs. Motivated by these insights, numerous accelerated variants of PDHG have been developed. Notable acceleration strategies include adaptive step sizes AdapPDHG15 , inertial techniques IPDHG-16 , line search strategies LINE-PDHG18 , coordinate updates ACPDHG21 , and refined primal-dual schemes google2022p ; fasterPDHG-23 ; PDLPnew2025 . While differing in implementation and used methodologies, these methods all aim to improve the rate of convergence of PDHG. Some of them leverage historical information and have demonstrated significant improvements across various application domains. And indeed, their success highlights the importance of incorporating past information into the update rules to guide the optimization process more effectively. Inspired by the success of these methods and their theoretical insights, in this work, we explore an acceleration approach that systematically leverages historical information. Specifically, we adopt a fixed-point perspective and investigate the use of Anderson Acceleration (AA) to enhance the convergence behaviour of PDHG. Our objective is to improve the overall efficiency and stability of PDHG when applied to large-scale linear programming (LP) problems. Anderson Acceleration (AA) is a technique originally introduced in AAoriginal to accelerate fixed-point iterations. Since then, it has been widely adopted as an effective tool in a variety of applications. For a broader overview of its theoretical development and practical uses, we refer the interested reader to AA-FPI-NI ; AA-CON-TAK ; AA-IMPROVE-PROOF-ECPRX ; MR3841161 ; MR4926317 . The core idea behind AA is to compute the next iterate as an affine combination of several previous iterates, thereby incorporating historical information to improve convergence. We summarized the standard version of the AA method in Algorithm 1 . Algorithm 1 Standard Anderson Acceleration with memory m for solving x=F(x) 1: Given F : \mathbb{R}^{n}\to\mathbb{R}^{n} , a initial point x^{0}\in\mathbb{R}^{n} , a damping paremater \beta , and a positive integer m . Set x^{1}=F(x^{0}) and G^{0}=F(x^{0})-x^{0}. 2: for k=0,1,\dots do 3: Set m_{k}=\min\{m,k\}. 4: Set \hat{G}^{k}=(G^{k-m_{k}},\ldots,G^{k}) , where G^{k}=F(x^{k})-x^{k} , and \alpha_{(k)}=(\alpha_{(k)}^{0},\ldots,\alpha_{(k)}^{m_{k}})^{{}^{\top}}. 5: Solve the problem: \displaystyle\min_{\alpha_{(k)}} \displaystyle\|\hat{G}^{k}\alpha_{(k)}\|, s.t. \displaystyle\sum_{i=0}^{m_{k}}\alpha^{i}_{(k)}=1. 6: Compute x^{k+1}=(1-\beta)\sum_{i=0}^{m_{k}}\alpha^{i}_{(k)}x^{k-m_{k}+i}+\beta\sum_{i=0}^{m_{k}}\alpha^{i}_{(k)}F(x^{k-m_{k}+i}). 7: end for In Algorithm 1 , the scalar 0<\beta\leq 1 is a damping (mixing) factor, which is often set as 1 in most cases. Some researches also show that the smaller choice of \beta would help improve the model stability and algorithm convergence in practice AACONTRACTIVE-21 ; AAMIXING19 ; dynamicBETAAA-25 . Anderson Acceleration (AA) has broad applicability. For instance, AA-FPI-NI demonstrates that, for linear problems, AA is essentially equivalent to the generalized minimal residual (GMRES) method; see also MR4711308 for connections among Krylov methods and AA. Furthermore, AA-QUASI-NEWTON interprets AA as a quasi-Newton method for nonlinear problems, thereby offering a theoretical basis for its acceleration properties. On top of that, although AA has demonstrated significant acceleration capability in practical applications, the theoretical analysis of its convergence has only been gradually developed in recent years. In AA-FPI-NI it was observed that when the fixed-point iteration is governed by a contractive operator, the algorithm can achieve local linear convergence rates. EDIIS-19 further considers the so-called EDIIS algorithm as a special case of AA requiring \alpha_{(k)}\geq 0, and proves its global convergence property under the case F is contractive on a convex set. In AA-IMPROVE-PROOF-ECPRX , the authors extended the result in AA-FPI-NI for AA with damping factors, and observed that AA is more effective for linearly convergent fixed-point methods, whereas for algorithms with quadratic convergence, it may actually reduce the acceleration effect. In anderson-type-I it was recently proposed a global convergence scheme for AA-I assuming the fixed point mapping is non-expansive. Based on this, the scheme was further applied in anderson-accelerated-operatorsplitting , where it served as a global convergence framework and was applied to splitting optimization methods. Inspired by these research results, we note that, as a member of the class of splitting methods, the PDHG algorithm can also be formulated as a fixed-point iteration. In particular, degenerate2021 investigated the convergence properties of PDHG in fixed point form under degenerate conditions. We also notice, though there are currently many papers showing that the AA algorithm can be applied to various first order algorithms AA-PG-21 ; EG-AA-24 ; anderson-accelerated-operatorsplitting , there has not yet been any work applying it to the PDHG method. To the best of our knowledge, this is the first work that integrates Anderson Acceleration into the PDHG framework. The main contributions of this paper are summarized as follows. First, we integrate Anderson Acceleration into the PDHG framework and establish its global convergence under a safeguard condition. Unlike existing works, we further incorporate a diagonal correction to enhance numerical stability. Moreover, we propose a novel approach to ensure the uniform boundedness of the matrix H_{k} , which plays a key role in guaranteeing convergence. This variant is referred to as the filtered AA-PDHG method. Second, to ensure feasibility when solving constrained problems, we introduce a projection step into the accelerated iteration to prevent infeasible iterates. The structure of this work is as follows, we first recall the preliminary knowledge that will be used throughout the work. In Section 2.1 , we present the formulation of the primal problem addressed in google2022p and explain how its corresponding dual form is derived. In Section 3 , we provide the specific formulation of the primal-dual problem in the form of a fixed point iteration tailored to the given problem. We provide a proof of the global convergence of our primal-dual fixed point iteration in Section 3.1 . In Section 4 , we also introduce a variant of AA-PDHG, FAA-PDHG, in which a filtering technique is employed. Numerical experiment results demonstrating the performance of our algorithm are presented in Section 5 . 2 Preliminaries Throughout this work, \mathbb{R}^{n} is the n -dimensional space whereas \mathbb{R}^{n}_{+}:=\{x\in\mathbb{R}^{n}\mid x_{i}\geq 0,\forall i=1,\dots,n\} and x^{\top} will denote the transpose of a vector x . Moreover, we define the distance of a point x from a closed set \Omega as \text{dist}(x,\Omega):=\min\{\,\|x-z\|,\;z\in\Omega\,\} . \|\cdot\| will be used to denote the {\ell}_{2} -norm with the inner product \langle\cdot,\cdot\rangle and the inner product induced by the operator \mathcal{M} is defined as \langle u,v\rangle_{\mathcal{M}}=\langle\mathcal{M}u,v\rangle , where \mathcal{M} is a bounded, semi-positive definite operator. The metric-induced norm \|u\|_{\mathcal{M}}=\sqrt{\langle\mathcal{M}u,u\rangle}=\sqrt{\langle u,u\rangle_{\mathcal{M}}} . Note that if \mathcal{M} is only semi-positive definte, it is possible that \|u\|_{\mathcal{M}}=0 while u\neq 0 . On the other hand, we will restrict our attention to the case where \mathcal{M} is positive definite. Besides, we call f:\mathbb{R}^{n}\to(-\infty,\infty) a proper function if f(x)<\infty for at least one x\in\mathbb{R}^{n} , and f(x)>-\infty for all x\in\mathbb{R}^{n} . We denote by \mathcal{I} the identity operator. Let \mathcal{C}\subseteq\mathbb{R}^{n} be a nonempty, closed, and convex set. The indicator function \mathcal{I}_{\mathcal{C}} of set \mathcal{C} is defined as: \mathcal{I}_{\mathcal{C}}(x)=\begin{cases}0,&x\in\mathcal{C},\\ +\infty,&x\notin\mathcal{C}.\end{cases} Definition 1 (Projection Operator first-order-beck ) . \mathcal{P}_{\mathcal{C}}:\mathbb{R}^{n}\to\mathcal{C} is a mapping that assigns to each x\in\mathbb{R}^{n} the closest point in \mathcal{C} , given by: \mathcal{P}_{\mathcal{C}}(x):=\arg\min_{y\in\mathcal{C}}\|x-y\|. This means that \mathcal{P}_{\mathcal{C}}(x) is the unique point in \mathcal{C} that minimizes the Euclidean distance to x . It is important to note that \mathcal{P}_{\mathcal{C}} is a non-expansive mapping that satisfies: \|\mathcal{P}_{\mathcal{C}}(x)-\mathcal{P}_{\mathcal{C}}(y)\|\leq\|x-y\|,\quad\forall x,\;y\in\mathbb{R}^{n}. Definition 2 (Proximal Operator first-order-beck ) . Given a function f:\mathbb{R}^{n}\to\mathbb{R}\cup\{+\infty\} , the proximal mapping of f is the operator given by {\text{Prox}}_{f}(x):=\arg\min_{u\in\mathbb{R}^{n}}\left\{f(u)+\frac{1}{2}\|u-x\|^{2}\right\},\text{ for any x}\in\mathbb{R}^{n}. Definition 3 (Subgradient and Subdifferential first-order-beck ) . Let a function f:\mathbb{R}^{n}\to(-\infty,\infty] be a proper function and let x\in\operatorname{dom}(f) . A vector g\in\mathbb{R}^{n} is called a subgradient of f at x if the following inequality holds: f(y)\geq f(x)+\langle g,y-x\rangle,\quad\text{for all }y\in\mathbb{R}^{n}. The set of all subgradients of a function f at a point x is called the subdifferential of f at x , and is denoted by \partial f(x) , i.e., \partial f(x)=\left\{g\in\mathbb{R}^{n}\;\middle|\;f(y)\geq f(x)+\langle g,y-x\rangle,\quad\text{for all }y\in\mathbb{R}^{n}\right\}. Notably, the subdifferential of the indicator function \mathcal{I}_{\mathcal{C}} is precisely the normal cone of \mathcal{C} at x ( variational-Rock , Cor. 12.18) , where the normal cone to \mathcal{C} at x is defined as: \mathcal{N}_{\mathcal{C}}(x)=\{v\in\mathbb{R}^{n}\mid\langle v,z-x\rangle\leq 0,\quad\forall z\in\mathcal{C}\}=\partial\mathcal{I}_{\mathcal{C}}(x). If the set \mathcal{C}=\mathbb{R}^{n}_{+} , then for v\in\mathcal{N}_{\mathcal{C}}(x) , we have v^{{}^{\top}}x=0 for any x\in\mathcal{C} , see ( variational-Rock , Example 6.10) . Lemma 1 ( first-order-beck Th. 6.39) . Given a function f:\mathbb{R}^{n}\to\mathbb{R}\cup\{+\infty\} , let x,\;u\in\mathbb{R}^{n} . Then u=\text{Prox}_{f}(x) if and only if x-u\in\partial f(u). Definition 4 (Conjugate Function first-order-beck ) . Let a function f:\mathbb{R}^{n}\to\mathbb{R}\cup\{+\infty\} be a proper function. The conjugate function f^{*}:\mathbb{R}^{n}\to\mathbb{R}\cup\{+\infty\} , is defined as: f^{*}(y)=\sup_{x\in\mathbb{R}^{n}}\big(\langle y,x\rangle-f(x)\big),\quad y\in\mathbb{R}^{n}. If f is the indicator function \mathcal{I}_{\mathcal{C}}(x) , then f^{*}(y)=\sup_{x\in\mathcal{C}}\langle y,x\rangle . Definition 5 (Quasi-Fejér Monotone quasi-Fejer ) . A sequence \{z^{k}\}\subset\mathbb{R}^{n} is quasi-Fejér monotone with respect to a non-empty target set C\subset\mathbb{R}^{n} , if for any z\in C , there exists a nonnegative and summable sequence \varepsilon^{k} , such that for any k\geq 0 , we have \|z^{k+1}-z\|^{2}\leq\|z^{k}-z\|^{2}+\varepsilon^{k}. The definition remains valid when \|\cdot\| is replaced by a metric-induced norm \|\cdot\|_{\mathcal{M}} , see ( quasi-Fejer , Definition 3.1) . Lemma 2 ( quasi-Fejer Th. 3.3) . Let \{z^{k}\} be a quasi-Fejér monotone sequence with respect to a non-empty target set C\subset\mathbb{R}^{n} . Then \{z^{k}\} converges to a point in C if and only if for any limit point z of \{z^{k}\} , we have z\in C . 2.1 Problem Statement In this section, we will present the particular form of the Linear Programming problem (LP) considered in this work including a brief explanation of how the specific form of the dual problem can be obtained. Among other things, the provided presentation allows a clearer theoretical foundation for the termination criteria introduced in Section 2 . In particular, the primal form of the LP problem here considered, see google2022p , has the form: \displaystyle\min \displaystyle\;\;c^{\top}x s.t. \displaystyle Gx\geq h, (2) \displaystyle Ax=b, \displaystyle l\leq x\leq u, where G\in\mathbb{R}^{m_{1}\times n},\;A\in\mathbb{R}^{m_{2}\times n},\;c\in\mathbb{R}^{n},\;h\in\mathbb{R}^{m_{1}},\;b\in\mathbb{R}^{m_{2}},\;l\in(\mathbb{R}\cup\{-\infty\})^{n},\;u\in(\mathbb{R}\cup\{\infty\})^{n}. In order to get its dual form, we first reformulate the problem by introducing appropriate auxiliary variables to decouple the constraints. Based on this, we first write down the Lagrangian of problem ( 2.1 ) as: \displaystyle\mathcal{L}(x,y_{1:m_{1}},y_{m_{1}+1:m},\lambda^{-},\lambda^{+}):= \displaystyle c^{\top}x+y_{1:m_{1}}^{\top}(-Gx+h)+y_{m_{1}+1:m}^{\top}(b-Ax)+(\lambda^{-})^{\top}(x-u)+(\lambda^{+})^{\top}(l-x), (3) where m=m_{1}+m_{2} and where the dual variables are given by y_{1:m_{1}}\in\mathbb{R}_{+}^{m_{1}},\;y_{m_{1}+1:m}\in{\mathbb{R}^{m_{2}}},\;\;\lambda^{-}\in\mathbb{R}_{+}^{n},\;\lambda^{+}\in\mathbb{R}_{+}^{n} . The corresponding dual function is then \displaystyle{\mathcal{K}(y_{1:m_{1}},y_{m_{1}+1:m},\lambda^{-},\lambda^{+})}:=\inf_{x}\mathcal{L}(x,y_{1:m_{1}},y_{m_{1}+1:m},\lambda^{-},\lambda^{+}) \displaystyle=\inf_{x}\{c^{\top}x+y_{1:m_{1}}^{\top}(-Gx)+y_{m_{1}+1:m}^{\top}(-Ax)+(\lambda^{-})^{\top}(x)+(\lambda^{+})^{\top}(-x)\} \displaystyle=\inf_{x}\{(c-G^{\top}y_{1:m_{1}}-A^{\top}y_{m_{1}+1:m}+\lambda^{-}-\lambda^{+})^{\top}x\}. Clearly, when c-G^{\top}y_{1:m_{1}}-A^{\top}y_{m_{1}+1:m}+\lambda^{-}-\lambda^{+}=0 , then {\mathcal{K}(y_{1:m_{1}},y_{m_{1}+1:m},\lambda^{-},\lambda^{+})} attains a finite value. Substituting this condition into ( 2.1 ), we get \displaystyle\mathcal{K}(y_{1:m_{1}},y_{m_{1}+1:m},\lambda^{-},\lambda^{+})=h^{\top}y_{1:m_{1}}+b^{\top}y_{m_{1}+1:m}+l^{\top}\lambda^{+}-u^{\top}\lambda^{-}, (4) when c-G^{\top}y_{1:m_{1}}-A^{\top}y_{m_{1}+1:m}+\lambda^{-}-\lambda^{+}=0 . Now, letting \displaystyle K^{\top} \displaystyle=\begin{bmatrix}G^{\top},A^{\top}\end{bmatrix},\quad q^{\top}:=\begin{bmatrix}h^{\top},b^{\top}\end{bmatrix},\;y^{\top}=\begin{bmatrix}y_{1:m_{1}}^{\top},y_{m_{1}+1:m}^{\top}\end{bmatrix},\;\lambda=\lambda^{+}-\lambda^{-}, \displaystyle\Lambda \displaystyle=\Lambda_{1}\times\cdots\times\Lambda_{n},\quad\Lambda_{i}=\begin{cases}\{0\},&l_{i}=-\infty,\quad u_{i}=\infty,\\ \mathbb{R}_{-},&l_{i}=-\infty,\quad u_{i}\in\mathbb{R},\\ \mathbb{R}^{+},&l_{i}\in\mathbb{R},\quad u_{i}=\infty,\\ \mathbb{R},&l_{i}\in\mathbb{R},\quad u_{i}\in\mathbb{R},\end{cases} (5) and using such definitions in ( 4 ), the dual problem of ( 2.1 ) can be formulated \displaystyle\max_{y,\lambda}\; \displaystyle q^{\top}y+l^{\top}\lambda^{+}-u^{\top}\lambda^{-} s.t. \displaystyle c-K^{\top}y=\lambda, (6) \displaystyle y_{1:m_{1}}\geq 0, \displaystyle\lambda\in\Lambda. For more details about the derivation of the constraint set \Lambda , see Appendix A . In conclusion, in this section, we have clarified the origin of the dual formulation ( 2.1 ) corresponding to the primal problem ( 2.1 ) in google2022p . 3 Anderson Accelerated PDHG As discussed in Section 1 , the goal of this work is to accelerate the convergence of PDHG using AA. On the other hand, in general, AA is designed to accelerate fixed point iterations; for this reason, in this section, we first show that the PDHG algorithm can be written in a fixed point fashion. Afterwards, in Algorithm 2 , we present the pseudo-code of the computational framework considered in this work. We begin by presenting the specific form of the PDHG method when applied to problem ( 2.1 ). To this aim, as in google2022p , we use min-max formulation of such problem: \displaystyle\min_{x\in X}\max_{y\in Y}L(x,y):=c^{\top}x-y^{\top}(Kx-q) where X:=\{x\mid l\leq x\leq u\} and Y:=\mathbb{R}_{+}^{m_{1}}\times\mathbb{R}^{m_{2}} . Through the use of indicator functions, it can be equivalently reformulated as: \displaystyle\min_{x\in X}\max_{y\in Y}L(x,y)=c^{\top}x-y^{\top}(Kx-q) \displaystyle=\min_{x\in\mathbb{R}^{n}}\max_{y\in\mathbb{R}^{m}}c^{{}^{\top}}x+y^{{}^{\top}}(q-Kx)+\mathcal{I}_{\{l\leq x\}}(x)+\mathcal{I}_{\{x\leq u\}}(x)-\mathcal{I}_{Y}(y) \displaystyle=\min_{x\in\mathbb{R}^{n}}\max_{y\in\mathbb{R}^{m}}c^{\top}x-y^{\top}(Kx-q)+\mathcal{I}_{{X}}(x)-\mathcal{I}_{{Y}}(y), (7) where the first equality holds because we performed a decomposition on the constraint X , i.e., X=\{x\mid l\leq x\}\cap\{x\mid x\leq u\} . From ( 7 ), we can write the PDHG iteration as: \displaystyle x^{k+1} \displaystyle=\mathcal{P}_{X}\left(x^{k}-\tau(c-K^{\top}y^{k})\right), (8a) \displaystyle y^{k+1} \displaystyle=\mathcal{P}_{Y}\left(y^{k}+\sigma(q-K(2x^{k+1}-x^{k}))\right). (8b) We will show, in the following, that the ieration ( 8 ) can be rewritten in fixed point form. This reformulation is inspired by the approach presented in ( degenerate2021 , Eq. (3.3)) where the authors show, indeed, that the PDHG method can be reformulated in a fixed-point fashion. However, in their analysis, the reformulation is stated for problems having the composite form \displaystyle\min_{x\in\mathbb{R}^{n}}f(x)+g(Kx), (9) where K is a generic bounded linear operator. Following this idea, we first rewrite ( 7 ) as a problem having the form ( 9 ). Indeed, ( 7 ) can be equivalently written as: \displaystyle\min_{x\in\mathbb{R}^{n}}\max_{y\in\mathbb{R}^{m}}c^{\top}x-y^{\top}(Kx-q)+\mathcal{I}_{{X}}(x)-\mathcal{I}_{{Y}}(y) \displaystyle= \displaystyle\min_{x\in\mathbb{R}^{n}}c^{\top}x+\mathcal{I}_{{X}}(x)+\max_{y\in\mathbb{R}^{m}}\Big\{\langle-Kx+q,y\rangle-\mathcal{I}_{Y}(y)\Big\} \displaystyle= \displaystyle\min_{x\in\mathbb{R}^{n}}c^{\top}x+\mathcal{I}_{{X}}(x)+\mathcal{I}^{*}_{Y}(-Kx+q) \displaystyle= \displaystyle\min_{x}c^{\top}x+\mathcal{I}_{{X}}(x)+\mathcal{I}_{Q}(Kx), (10) where \mathcal{I}^{*}_{Y}(y) is the conjugate function of \mathcal{I}_{Y}(y) , see Section 2 , and where Q is the set Q:=\{Kx\mid(Kx)_{i}=q_{i}\text{ for all }i=m_{1}+1,\dots,m_{1}+m_{2},\;(Kx)_{i}\geq q_{i}\text{ for }i=1,\dots,m_{1}\}. The full details about the last equality are provided in Appendix B . Hence, setting, f(x)=c^{{}^{\top}}x+\mathcal{I}_{X}(x) and g(Kx)=\mathcal{I}_{Q}(Kx) , we finally proved the equivalence of the formulation ( 9 ) and the formulation ( 10 ). Following degenerate2021 , we can finally write PDHG in the fixed point form: \displaystyle u^{k+1}=(\mathcal{M}+\mathcal{A})^{-1}\mathcal{M}u^{k}=(\mathcal{I}+\mathcal{M}^{-1}\mathcal{A})^{-1}u^{k}=\mathcal{T}(u^{k}), (11) where u=\begin{bmatrix}x\\ y\end{bmatrix},\quad\mathcal{A}:=\begin{bmatrix}\tau\bar{A}&-\tau K^{\top}\\ \sigma K&\sigma\bar{B}^{-1}\end{bmatrix},\quad\mathcal{M}:=\begin{bmatrix}I&\tau K^{\top}\\ \sigma K&I\end{bmatrix},\;\mathcal{T}=(\mathcal{I}+\mathcal{M}^{-1}\mathcal{A})^{-1} \bar{A}=c+\partial\mathcal{I}_{X} and \bar{B}=\partial\mathcal{I}_{Q} . Parameters \sigma,\;\tau are the same as in ( 8a ) and ( 8b ). Assumption 1 . In the remainder of this work, we assume that the step sizes \tau and \sigma are such that \sigma\tau\|K\|^{2}<1 . This ensures the positive definiteness of \mathcal{M} and that \mathcal{T} is an \mathcal{M} -firmly non-expansive operator. Moreover, in this case, the induced semi-norm \|\cdot\|_{\mathcal{M}} introduced in Section 2 becomes a norm. Remark 1 . The dual variable \lambda introduced in ( 2.1 ) can be characterised as an element of the subgradient set of the indicator function \mathcal{I}_{X} in ( 10 ). A simple explanation is shown in the appendix A . Please note that we will freely use this result in subsequent proofs. Before introducing our computational framework, we note that, in general, AA relies on affine combinations of multiple historical iterates, see Algorithm 1 . When applied to the fixed-point iterations defined in ( 11 ), such combinations do not necessarily preserve feasibility w.r.t. X and Y , whereas PDHG inherently produces feasible iterates – see also equations ( 8a ) and ( 8b ). In the context of PDHG, this issue is particularly undesirable. To address this problem and preserve feasibility in the AA-accelerated, considering \mathcal{P}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to X\times Y the projection operator onto the feasible set. Specifically, this projection can be decomposed into: \mathcal{P}=\begin{bmatrix}\mathcal{P}_{X}&0\\ 0&\mathcal{P}_{Y}\end{bmatrix}, where \mathcal{P}_{X}:\mathbb{R}^{n}\to X and \mathcal{P}_{Y}:\mathbb{R}^{m}\to Y . We are now ready to present, see Algorithm 2 , our proposed Anderson Accelerated Primal Dual Hybrid Gradient, denoted by AA-PDHG in the following. The specific structure of Algorithm 2 incorporates several key mechanisms to ensure soundness and convergence, see Section 3.1 . The core of such a mechanism is the safeguard step included at Line 10 . This step adopts the strategy introduced in ANDERSON-DRS-Fu_2020 ; anderson-accelerated-operatorsplitting ; anderson-type-I to guarantee global convergence. In particular, when the new fixed point residual norm \|g^{k}\| does not satisfy the safeguard condition, the algorithm defaults to a classical PDHG iteration to compute the next approximation, as detailed in Line 14 . To provide insight into the interplay between acceleration and fallback strategies, the algorithm tracks the number of times Anderson Acceleration (AA) and vanilla PDHG are used. Specifically, if up to iteration k , the AA step (see Line 17 ) has been invoked i^{k} times, and the PDHG step (see Line 14 ) has been applied j^{k} times, then at iteration k+1 , we increment either i^{k+1}=i^{k}+1 or j^{k+1}=j^{k}+1 . Concerning the embedded AA procedure, we observe that the AA memory, see Line 9 is updated also when the safeguard step is not used in order to ensure that any acceleration step is performed using the most updated information. It is important to note, moreover, that Line 12 does not represent a classical AA update, as the algorithm uses a regularisation technique originally proposed in AA-NONLINEAR-21 to update the accelerated iterate u^{k+1}_{\mathrm{AA}} . This step is particularly important when the matrix (\Delta\mathcal{G}^{k-m_{k}})^{T}\Delta\mathcal{G}^{k-m_{k}} is non-invertible or poorly conditioned. To further enhance numerical stability and performance, we also add a diagonal matrix \hat{D} is introduced in the same step. This matrix plays a role analogous to the preconditioning matrix discussed in diagonalPDHG-11 , helping to moderate the effect of scaling across different components of the update. Algorithm 2 Anderson Accelerated Primal-Dual Hybrid Gradient (AA-PDHG) 1: Given initial feasible point u^{0}:=(x^{0},y^{0}) , a projection operator \mathcal{P}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to X\times Y , and the fixed point iteration \mathcal{T} defined in ( 11 ). Select a scalar D>0 and a diagonal matrix \hat{D} . Let m\geq 1 , \varepsilon>0 , toll>0 . Set i^{1}=0 , j^{1}=0 . Set u_{1}=\mathcal{T}u^{0} , g^{0}:=u^{1}-u^{0} . 2: for k=1,\dots, do 3: Set \widehat{u}^{k+1}=\mathcal{T}u^{k} 4: Set g^{k}=\widehat{u}^{k+1}-u^{k} 5: if \|g^{k}\|\bar{K} , we only use the update at Line 14 in Algorithm 2 . Applying now Theorem 1 , we have \lim_{k\to\infty}\|{g}^{k}\|=\lim_{k\to\infty}\|\mathcal{T}(u^{k})-u^{k}\|=0 . Hence, \forall\;\delta>0 , there exists an index K>\bar{K} such that for all k\geq K , \|{g}^{k}\|\leq\delta . Letting \delta\leq D\|g^{0}\|(i^{{k}}+1)^{-(1+\varepsilon)}\leq D\|g^{0}\|(\bar{A}+1)^{-(1+\varepsilon)}, we have for all {k}\geq K , \|g^{k}\|\leq\delta\leq D\|g^{0}\|({\bar{A}+1})^{-(1+\varepsilon)} , i.e., that the safeguard condition is satisfied. This contradicts our assumption, as it implies that the safeguard check would be successful one more time. ∎ Let us introduce some necessary notation useful in the following. Regardless of how the algorithm alternates between AA and PDHG steps, for the sake of clarity, we divide the index set \mathbb{N}=\{0,1,\ldots\} of iterations into two subsets: K_{aa}:=\{a_{0},a_{1},a_{2},\ldots\} and K_{pd}=\{p_{0},p_{1},\ldots\} . So, K_{aa} represents the iteration indices where the safeguard condition is satisfied and Line 17 is applied, whereas K_{pd} represents the iteration indices where Line 14 is used. It is important to note by Lemma 3 we know that K_{aa} is an infinite set. In the next lemma, we prove that the sequence \{u^{k}\} generated by Algorithm 2 is a quasi-Fejér monotone sequence with respect to non-empty set Fix\mathcal{T} . Lemma 4 . Assume that matrix H^{k} generated by Algorithm 2 is uniformly bounded, i.e., \|H^{k}\|\leq M for all k . Consider \{u^{k}\} generated by Algorithm 2 and assume the point u^{*}\in Fix\mathcal{T} . Then \{u^{k}\} is a quasi-Fejér monotone sequence with respect to the set Fix\mathcal{T} . Proof. We divide the discussion into two cases. Firstly, assume the k -th iteration is an AA step, i.e., k=a_{l}\in K_{aa} . We have \displaystyle\|u^{k+1}-u^{*}\|_{\mathcal{M}} \displaystyle\leq\|u^{k}-u^{*}\|_{\mathcal{M}}+\|\mathcal{P}(u^{k}-H^{k}g^{k})-u^{k}\|_{\mathcal{M}} \displaystyle\leq\|u^{k}-u^{*}\|_{\mathcal{M}}+\|H^{k}g^{k}\|_{\mathcal{M}} \displaystyle\leq\|u^{k}-u^{*}\|_{\mathcal{M}}+M\lambda_{\max}(\mathcal{M})\|g^{k}\| \displaystyle\leq\|u^{k}-u^{*}\|_{\mathcal{M}}+M\lambda_{\max}(\mathcal{M})\|g^{0}\|(i^{k}+1)^{-(1+\varepsilon)}, (16) where the second inequality follows by the non-expansiveness of the projection, whereas the last inequality holds due to the safeguard strategy in Algorithm 2 . Analogously, if k=p_{l}\in K_{pd} , we have, \displaystyle\|u^{k+1}-u^{*}\|^{2}_{\mathcal{M}} \displaystyle=\|\mathcal{T}(u^{k})-\mathcal{T}(u^{*})\|^{2}_{\mathcal{M}} \displaystyle\leq\|u^{k}-u^{*}\|^{2}_{\mathcal{M}}-\|g^{k}\|^{2}_{\mathcal{M}}, (17) where the first inequality holds because \mathcal{T} is \mathcal{M} -firmly non-expansive and applying ( convex-monotone , Proposition 4.25(iii)) with \alpha=\frac{1}{2} . Then we have, \displaystyle\|u^{k+1}-u^{*}\|_{\mathcal{M}}-\|u^{0}-u^{*}\|_{\mathcal{M}} \displaystyle= \displaystyle\sum_{j=0}^{k}(\|u^{j+1}-u^{*}\|_{\mathcal{M}}-\|u^{j}-u^{*}\|_{\mathcal{M}}) \displaystyle= \displaystyle\sum_{j\in K_{aa},\;j\leq k}(\|u^{j+1}-u^{*}\|_{\mathcal{M}}-\|u^{j}-u^{*}\|_{\mathcal{M}})+\sum_{j\in K_{pb}\;j\leq k}(\|u^{j+1}-u^{*}\|_{\mathcal{M}}-\|u^{j}-u^{*}\|_{\mathcal{M}}) \displaystyle\leq \displaystyle\sum_{j\in K_{aa}\;j\leq k}(\|u^{j+1}-u^{*}\|_{\mathcal{M}}-\|u^{j}-u^{*}\|_{\mathcal{M}}) \displaystyle\leq \displaystyle M{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|\sum_{j\in K_{aa}}^{k}(i^{j}+1)^{-(1+\varepsilon)} \displaystyle\leq \displaystyle M{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|\sum_{j=0}^{+\infty}(j+1)^{-(1+\varepsilon)}<+\infty, (18) where the first inequality holds from ( 3.1 ) and the second inequality holds from ( 3.1 ). Hence, we get \{\|u^{k}-u^{*}\|_{\mathcal{M}}\} is bounded, and we denote this bound by E:=\|u^{0}-u^{*}\|_{\mathcal{M}}+M{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|\sum_{m=0}^{+\infty}(m+1)^{-(1+\varepsilon)}, i.e., \|u^{k}-u^{*}\|_{\mathcal{M}}\leq E for all k\geq 0 . Clearly, this implies that \{\|u^{k}-u^{*}\|\} is also bounded. Squaring both sides of equation ( 3.1 ), we have \displaystyle\|u^{{k+1}}-u^{*}\|^{2}_{\mathcal{M}}-\|u^{k}-u^{*}\|^{2}_{\mathcal{M}} \displaystyle\leq 2\|u^{k}-u^{*}\|_{\mathcal{M}}M{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|(i^{k}+1)^{-(1+\varepsilon)} \displaystyle\quad+M^{2}D^{2}{\lambda_{\max}^{2}(\mathcal{M})}\|g^{0}\|^{2}(i^{k}+1)^{-2(1+\varepsilon)} \displaystyle\leq 2EM\lambda_{\max}(\mathcal{M})D\|g^{0}\|(i^{k}+1)^{-(1+\varepsilon)} \displaystyle\quad+M^{2}D^{2}{\lambda^{2}_{\max}(\mathcal{M})}\|g^{0}\|^{2}(i^{k}+1)^{-2(1+\varepsilon)}. (19) Let us now define the sequence \begin{cases}\varepsilon^{k}:=2EM\lambda_{\max}(\mathcal{M})D\|g^{0}\|(i^{k}+1)^{-(1+\varepsilon)}+M^{2}D^{2}{\lambda^{2}_{\max}(\mathcal{M})}\|g^{0}\|^{2}(i^{k}+1)^{-2(1+\varepsilon)}\hbox{ if }k\in K_{aa}\\ \varepsilon^{k}=0\hbox{ if }k\not\in K_{aa}.\end{cases} Using ( 3.1 ) and ( 3.1 ), by the definition of \varepsilon^{k} , it holds \|u^{{k+1}}-u^{*}\|^{2}_{\mathcal{M}}\leq\|u^{k}-u^{*}\|^{2}_{\mathcal{M}}+\varepsilon^{k} for all k\geq 0 . Moreover, we have \displaystyle\sum_{j=0}\varepsilon^{j}=\sum_{j\in K_{pb}}\varepsilon^{j}+\sum_{j\in K_{aa}}\varepsilon^{j} \displaystyle= \displaystyle\sum_{{j}\in K_{aa}}\Big(2EM\lambda_{\max}(\mathcal{M})D\|g^{0}\|(i^{j}+1)^{-(1+\varepsilon)} \displaystyle\quad+M^{2}D^{2}{\lambda^{2}_{\max}(\mathcal{M})}\|g^{0}\|^{2}(i^{j}+1)^{-2(1+\varepsilon)}\Big) \displaystyle\leq \displaystyle\sum_{j=0}^{+\infty}\Big(2EM\lambda_{\max}(\mathcal{M})D\|g^{0}\|(j+1)^{-(1+\varepsilon)} \displaystyle\quad+M^{2}D^{2}{\lambda^{2}_{\max}(\mathcal{M})}\|g^{0}\|^{2}(j+1)^{-2(1+\varepsilon)}\Big)<+\infty, (20) where the second equality holds due to the definition of \varepsilon^{k} . Hence, the \{\varepsilon^{k}\} is a summable sequence, which proves, looking at Definition 5 , that \{u^{k}\} is a \mathcal{M} -quasi-Fejér monotone sequence. ∎ We are finally able to show that the sequence generated by Algorithm 2 converges globally. Theorem 2 . Assume that the sequence \{u^{k}\} is generated by Algorithm 2 , where H^{k} satisfies \|H^{k}\|\leq M . Then \{u^{k}\} converges globally to a fixed point u^{*}\in Fix\mathcal{T} . Proof. Let us recall, that by ( 3.1 ), for k=a_{l}\in K_{aa} , we have \displaystyle\|u^{k+1}-u^{*}\|_{\mathcal{M}}^{2}-\|u^{k}-u^{*}\|_{\mathcal{M}}^{2} \displaystyle\leq M^{2}D^{2}{\lambda_{\max}^{2}(\mathcal{M})}\|g^{0}\|^{2}(i^{k}+1)^{-2(1+\varepsilon)} \displaystyle+2EM\lambda_{\max}(\mathcal{M})D\|g^{0}\|(i^{k}+1)^{-(1+\varepsilon)}. (21) Similarly, by ( 3.1 ), for k=p_{l}\in K_{pd} , we have \displaystyle\|u^{k+1}-u^{*}\|_{\mathcal{M}}^{2}-\|u^{k}-u^{*}\|_{\mathcal{M}}^{2}\leq-\|g^{k}\|^{2}_{\mathcal{M}}. (22) Let us considered the sequences \{g^{p_{l}}\} and \{g^{a_{l}}\} , extracted from the full sequence \{g^{k}\} . Observing that AA is used infinitely many times in Algorithm 2 , see Lemma 3 , if we can prove that the subsequences satisfy one of the following two cases: \displaystyle\lim_{l\to\infty}\|g^{p_{l}}\|=0=\lim_{l\to\infty}\|g^{a_{l}}\|, (23) or \displaystyle\lim_{l\to\infty}\|g^{a_{l}}\|=0,\text{\; and the number of elements in $K_{pd}$ is finite,} (24) then, we can conclude that \lim_{k\to\infty}\|g^{k}\|=0. Next, we prove, indeed, ( 23 ) and ( 24 ) hold. Using ( 3.1 ) and ( 22 ) over all j\leq k , we have, \displaystyle\|u^{k+1}-u^{*}\|^{2}_{\mathcal{M}}-\|u^{0}-u^{*}\|^{2}_{\mathcal{M}} \displaystyle=\sum_{j\in K_{pd},\;j\leq k}\Big(\|u^{j+1}-u^{*}\|_{\mathcal{M}}^{2}-\|u^{j}-u^{*}\|_{\mathcal{M}}^{2}\Big) \displaystyle\quad+\sum_{j\in K_{aa},\;j\leq k}\Big(\|u^{j+1}-u^{*}\|_{\mathcal{M}}^{2}-\|u^{j}-u^{*}\|_{\mathcal{M}}^{2}\Big) (25) \displaystyle\leq-\sum_{j\in K_{pd},\;j\leq k}\|g^{j}\|_{\mathcal{M}}^{2}+M^{2}D^{2}{\lambda^{2}_{\max}(\mathcal{M})}\|g^{0}\|^{2}\sum_{j\in K_{aa},\;j\leq k}(i^{j}+1)^{-2(1+\varepsilon)} \displaystyle\quad+2EM{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|\sum_{j\in K_{aa},\;j\leq k}(i^{j}+1)^{-(1+\varepsilon)}. From the above, we obtain \displaystyle\sum_{j\in K_{pd},\;j\leq k}\|g^{j}\|_{\mathcal{M}}^{2} \displaystyle\leq M^{2}D^{2}{\lambda^{2}_{\max}(\mathcal{M})}\|g^{0}\|^{2}\sum_{j\in K_{aa},\;j\leq k}(i^{j}+1)^{-2(1+\varepsilon)} \displaystyle\quad+2EM{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|\sum_{j\in K_{aa},\;j\leq k}(i^{j}+1)^{-(1+\varepsilon)} \displaystyle\quad-\|u^{k+1}-u^{*}\|^{2}_{\mathcal{M}}+\|u^{0}-u^{*}\|^{2}_{\mathcal{M}} \displaystyle\leq M^{2}D^{2}{\lambda^{2}_{\max}(\mathcal{M})}\|g^{0}\|^{2}\sum_{j\in K_{aa},\;j\leq k}(i^{j}+1)^{-2(1+\varepsilon)} \displaystyle\quad+2EM{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|\sum_{j\in K_{aa},\;j\leq k}(i^{j}+1)^{-(1+\varepsilon)} \displaystyle\quad+\|u^{0}-u^{*}\|^{2}_{\mathcal{M}} Now letting k\to\infty , due to the summability of the series M^{2}D^{2}{\lambda_{\max}(\mathcal{M})}\|g^{0}\|^{2}\sum_{j=0}^{\infty}(i^{j}+1)^{-2(1+\varepsilon)}+2EM{\lambda_{\max}(\mathcal{M})}D\|g^{0}\|\sum_{j=0}^{\infty}(i^{j}+1)^{-(1+\varepsilon)}+\|u^{0}-u^{*}\|^{2}_{\mathcal{M}}, we obtain that \sum_{j\in K_{pd}}\|g^{j}\|_{\mathcal{M}}^{2}<+\infty , i.e., either K_{pd} is finite, or \lim_{\begin{subarray}{c}j\to\infty\\ j\in K_{pd}\end{subarray}}\|g^{j}\|=0 . Moreover, from safeguard condition, we have for any j\in K_{aa} , 0\leq\lim_{\begin{subarray}{c}j\to\infty\\ j\in K_{aa}\end{subarray}}\|g^{j}\|\leq D\|g^{0}\|\lim_{j\to\infty}(j+1)^{-(1+\varepsilon)}=0. Hence, we conclude that \lim_{k\to\infty}\|g^{k}\|=0 . By ( 3.1 ), we already know that the sequence \{\|u^{k}-u^{*}\|\} is bounded, and hence, we can conclude that \{u^{k}\} is bounded. Then for any convergent subsequence of \{u^{k}\} , i.e., u^{k_{n}}\to u^{\prime} , combined with \lim_{n\to\infty}g^{k_{n}}=\lim_{n\to\infty}\mathcal{T}u^{k_{n}}-u^{k_{n}}=0 , we know that \mathcal{T}u^{\prime}=\lim_{n\to\infty}\mathcal{T}u^{k_{n}}=\lim_{n\to\infty}u^{k_{n}}=u^{\prime}, and hence u^{\prime}\in Fix\mathcal{T} . We can then conclude that the limit point of any convergent subsequence of \{u_{k}\} is a fixed point of \mathcal{T} . Moreover, we have already shown that \{u^{k}\} is a \mathcal{M} -quasi-Fejér monotone sequence with respect to Fix\,\mathcal{T} in Lemma 4 , i.e., \|u^{k+1}-u^{\prime}\|_{\mathcal{M}}\leq\|u^{k}-u^{\prime}\|_{\mathcal{M}}+\varepsilon^{k}, and hence, from Lemma 2 , we conclude that \{u^{k}\} converges to some u^{\prime}\in Fix\mathcal{T} . ∎ 4 Filtered Anderson Accelerated PDHG (FAA-PDHG) In this section, we will address the issue concerning the uniform boundedness of the matrices \|H_{k}\| . The results here presented are mainly inspired by the developments in PRFAA-2023 , and extend the techniques there presented to the safeguard framework in Algorithm 2 . To this aim, we will consider the following Algorithm 3 , a modification of Algorithm 2 , see Lines 12 and 13 , that enforces algorithmically the uniform boundedness of the matrices H_{k} using the procedure described in Algorithms 4 and 5 . We explicitly note, that the other main difference w.r.t. Algorithm 2 , is represented by Lines 11 and 14 . The auxiliary function reverse simply swaps the columns of the input matrices, as illustrated in Algorithm 6 . Its use is motivated by the choice to leverage existing results from PRFAA-2023 , where the most recent information is stored to the left of the matrices \Delta\mathcal{U}^{k-m_{k}} and \Delta\mathcal{G}^{k-m_{k}} , in contrast to our convention, where the most updated columns are placed at the right. While the application of the reverse function is not strictly necessary, omitting it would require the underlying theoretical results, see, e.g., Lemma 5 , to be carefully reformulated to accommodate our indexing scheme. Algorithm 3 Filtered Anderson Accelerated PDHG (FAA-PDHG) 1: Given initial feasible point u^{0}:=(x^{0},y^{0}) , a projection operator \mathcal{P}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to X\times Y , and the fixed point iteration \mathcal{T} defined in ( 11 ). Select a scalar D>0 and a diagonal matrix \hat{D} . Let m\geq 1 , \varepsilon>0 , toll>0 . Set i^{1}=0 , j^{1}=0 . Set u^{1}=\mathcal{T}u^{0} , g^{0}:=u^{1}-u^{0} . 2: for k=1,\dots, do 3: Set \widehat{u}^{k+1}=\mathcal{T}u^{k} 4: Set g^{k}=\widehat{u}^{k+1}-u^{k} 5: if \|g^{k}\|0 such that \displaystyle c_{1}\|\Delta g^{k-j-1}\| \displaystyle\leq\|g^{k-j}-g^{k-j-1}\|_{\mathcal{M}} \displaystyle=\|\mathcal{T}u^{k-j}-u^{k-j}-\mathcal{T}u^{k-j-1}+u^{k-j-1}\|_{\mathcal{M}} \displaystyle\leq 2\|u^{k-j}-u^{k-j-1}\|_{\mathcal{M}}\leq 2c_{2}\|\Delta u^{k-j-1}\|, (29) i.e., \|\Delta\mathcal{G}^{k-m_{k}}\|_{F}\leq\dfrac{2c_{2}}{c_{1}}\|\Delta\mathcal{U}^{k-m_{k}}\|_{F}. Thus the claim follows by the inequalities \begin{split}\|H^{k}\|&\leq\beta\|\hat{D}\|+\|\Delta\mathcal{U}^{k-m_{k}}\|\|R_{k}^{-1}\|+\beta\|\hat{D}\|\|\Delta\mathcal{G}^{k-m_{k}}\|\|R_{k}^{-1}\|\\ &\leq\beta\|\hat{D}\|+\|\Delta\mathcal{U}^{k-m_{k}}\|_{F}\|R_{k}^{-1}\|_{F}+\beta\|\hat{D}\|\|\Delta\mathcal{G}^{k-m_{k}}\|_{F}\|R_{k}^{-1}\|_{F}\\ &\leq\beta\|\hat{D}\|+{\bar{\kappa}}+\dfrac{2c_{2}}{c_{1}}\beta\|\hat{D}\|{\bar{\kappa}}=:M,\end{split} where the last inequality follows from Lemma 7 . ∎ 5 Numerical Experiment In order to showcase the computational advantages of the approach proposed here, in this section, we compare AA-PDHG (Algorithm 2 ), FAA-PDHG (Algorithm 3 ) with vanilla PDHG when solving selected large-scale LP problems. All the presented experiments are carried out in Python 3.9.16 and run on the University of Southampton’s Iridis 6 high-performance computing cluster and the relative code is publicly available at https://github.com/ZYXYJS/AA-PD . Before presenting the numerical results, we note that the implemented version of Algorithm 3 , still referred to as FAA-PDHG in the following, employs a slightly different update strategy for the matrices \Delta\mathcal{U}^{k-m_{k}} and \Delta\mathcal{G}^{k-m_{k}} compared to the description in Section 4 . Specifically, rather than fully recomputing these matrices as in Line 9 , the implementation appends the most recent vectors \Delta u^{k-1} and \Delta g^{k-1} to the matrices obtained after applying the filtering procedures, as returned in Lines 12 and 13 . To ensure that the number of columns does not exceed the prescribed memory size m , the matrices produced by the filtering procedures may discard the oldest information. This modification can be regarded as an adaptive memory selection mechanism, prioritising the most recent and relevant information gathered through the fixed-point iteration. Remark 2 . (Termination conditions) At Line 4 of Algorithms 2 and 3 , we used a stopping criterion based on the fixed point residual. In our numerical results, we will experimentally show that such a stopping criterion is indeed compatible with more traditional stopping criteria used for LP problems, as those proposed, e.g., in google2022p . In particular, for x\in X,\;y\in Y,\;\lambda\in\Lambda, such conditions are given as follows: \displaystyle|q^{T}y+l^{T}\lambda^{+}-u^{T}\lambda^{-}-c^{T}x| \displaystyle\leq\epsilon(1+|q^{T}y+l^{T}\lambda^{+}-u^{T}\lambda^{-}|+|c^{T}x|), (30) \displaystyle\left\|\begin{pmatrix}b-Ax\\ (h-Gx)_{+}\end{pmatrix}\right\|_{2} \displaystyle\leq\epsilon(1+\|q\|_{2}), (31) \displaystyle\|c-K^{T}y-\lambda\|_{2} \displaystyle\leq\epsilon(1+\|c\|_{2}). (32) In general, equation ( 30 ) measures the relative duality gap, ( 31 ) the relative primal infeasibility, whereas ( 32 ) is the relative dual infeasibility, where \epsilon controls the quality of the sought approximate solution. It is important to note that, since the PDHG algorithm does not explicitly include reduced-cost variable \lambda , to evaluate ( 32 ), \lambda=\mathcal{P}_{\Lambda}(c-K^{T}y) is used. This is because c-K^{\top}y=\lambda with \lambda\in\Lambda represent the feasibility conditions of the dual formulation ( 2.1 ). Moreover, using Remark 1 , we can easily see that if we consider \lambda=\mathcal{P}_{\Lambda}(c-K^{T}y) , defining \varsigma:=-\lambda , we have \varsigma\in\partial\mathcal{I}_{X} . The first experiment showcases the acceleration effect of AA-PDHG when used to solve a simple linear feasibility problem, i.e., \displaystyle\min_{x}0\cdot x, (33) \displaystyle\text{s.t. }x=3,\;x\geq 0. In Figure 1 we compare the iterates produced by the vanilla PDHG with those produced by AA-PDHG to solve ( 33 ). The figure highlights how, despite the initial iterations of the of two methods are similar, AA-PDHG is able to avoid the spiraling behaviour of vanilla PDHG toward the end. Besides, for this problem, vanilla PDHG stops after 1000 maximum iterations while AA-PDHG with memory size 5 converges after only 60 iteration. Figure 1: Comparison of the iterates produced by AA-PDHG (in red) and by Vanilla PDHG (blue) for solving ( 33 ). The optimal value is (3,0) . We use the same step-size 0.25 for both. For the second class of experiments, we propose compare the residual history of AA-PDHG and vanilla PDHG on selected instances the MIPLIB 2017 dataset, which is a widely used collection of mixed integer programming (MIP) problems. The tested instances have between 10,000 and 10,000,000 nonzero coefficients, falling hence within the category of large-scale problems. To preserve the original structure of the problems and to ensure the comparability of results, we did not apply any presolve procedures to these instances. Moreover, for both algorithms, we apply the same step size, which is estimated using a power iteration power-iter-96 to compute. We also evaluate the performance with different choices of memory size m_{k} for AA-PDHG. As reported in most of the existing literature AA-CON-TAK ; AA-FPI-NI ; AA-IMPROVE-PROOF-ECPRX , it has been observed that selecting m_{k} in the range of 5 to 20 yields the best performance, and in general, a larger m_{k} tends to reduce the number of iterations required for convergence at the price of an increase of the computational time due to the computational footprint related to the computation of AA steps incorporating longer iteration history. For those reasons, we report the numerical results relative to m_{k}=5,10,15 . Concerning the hyper-parameters selection in Line 3 of Algorithm 2 , the pair (\varepsilon,D) is selected from the set \mathcal{H}:=\{0.01,0.1,1\}\times\{0.1,1,10,100\} individually for each problem instance, with the goal of maximising the acceleration performance. In our numerical experimentation, we found out indeed that this choice has a notable impact on the effectiveness of Anderson Acceleration. The importance of this selection is further illustrated in Figure 2 , which reports the residual history for the instance neos-933966 , with fixed \varepsilon=1 and m_{k}=5 , and varying values of D . As evidenced by the figure, setting D too small or too large may result in an imbalanced interplay between the vanilla PDHG update and the AA step, ultimately impairing, in both cases, the acceleration effect. Finally, we set toll=1e-4 in Algorithm 2 . Figure 2: AA-PDHG with m_{k}=5 for different values of the safeguard parameter D . In the case D=100 , we observe extended stagnation in the residual history, indicating that, despite the more frequent use of AA iterations, the fixed-point residual does not decrease, resulting in a substantial number of ineffective iterations. Conversely, when D is too small, e.g., D=0.01 , the algorithm relies predominantly on vanilla PDHG updates in the initial stages. As a consequence, AA is activated too late, leading to inferior performance compared to configurations that maintain a more balanced interplay between AA and vanilla PDHG throughout the process, e.g., D\in\{0.1,1,10\} . In Figures 3 and 4 we present the experimental results for the selected LP instances. In particular, in Figure 3 , we first present the evolution of the fixed point residual for all algorithms, vanilla PDHG, AA-PDHG and FAA-PDHG, when using different memory sizes m_{k} . To ensure a fair comparison of the impact of different values of m_{k} on algorithmic performance, we set the same D and \varepsilon for each instance and vary only the value of m_{k} . In the case of the filtered method, the c_{s} is set as 0.2, while \bar{\kappa} is selected from the set \{10^{8},\;10^{9},\;10^{10}\} as the one delivering better acceleration performance. We observe from Figure 3 that at the beginning AA-PDHG, FAA-PDHG exhibits the same fluctuating behavior as Vanilla PDHG, while when AA-PDHG, FAA-PDHG gather enough historical information about the problem, it is able to reduce the fixed point residual at a much more rapid rate. Moreover, for these instances, setting m_{k}=10 or 15 yields better performance than using m_{k}=5 in most cases. This observation is in accordance to the general intuition behind every limited memory Quasi-Newton method. In addition, it should be noted that, for the brazil3,rocll-10-11 instances, the vanilla PDHG failed to reach the required fixed point residual, reaching the maximum allowed wall-time limit of 1 hour, further demonstrating the power of the acceleration effect delivered by AA. Moreover, we observe with m_{k}=5,10 , in most cases, the filtered AA method outperforms Algorithm 2 in terms of convergence behaviour. Figure 3: The fixed point residual trajectory over iterations. Figure 4: The primal and dual residual trajectory over iterations. Finally, in Figure 4 , we report the history convergence of r^{k}_{primal} and r^{k}_{dual} (primal and dual residuals) as defined in ( 31 ) and ( 32 ) when m_{k}=5 . Similar observations to those carried out for the fixed point residual also apply in this case, with filtered AA-PDHG able to consistently speed up the reduction of the primal and dual residuals when compared to the vanilla PDHG. Moreover, from the comparison of Figures 3 and 4 , we observe how, in general, r^{k}_{primal} and r^{k}_{dual} remain roughly of the same order of magnitude when compared to the fixed point residual \|g^{k}\| . It is worth noting that we do not report the primal and dual residuals for Algorithm 2 , i.e., AA-PDHG, as its behaviour is very similar to that of FAA-PDHG. As a final comment, we observe that in Figure 4 , the erratic behaviour of the dual residuals with values very close to zero at certain iteration, depends on the fact that when computing the variable \lambda=\mathcal{P}_{\Lambda}(c-K^{{}^{\top}}(\mathcal{P}_{Y}y)) and r_{dual}=\|c-K^{{}^{\top}}(\mathcal{P}_{Y}y)-\lambda\| , it might happen that c-K^{{}^{\top}}(\mathcal{P}_{Y}y) lies within the set \Lambda , i.e., \lambda=c-K^{{}^{\top}}(\mathcal{P}_{Y}y) , and thus r^{k}_{dual}=0 . 6 Conclusion In this work, we propose a novel application of Anderson Acceleration (AA) to the Primal-Dual Hybrid Gradient (PDHG) method for solving linear programming (LP) problems. Since AA was originally developed for fixed-point iterations, we begin by reformulating the PDHG algorithm for LPs into a fixed-point framework. To ensure that the AA-accelerated iterates remain within the feasible set, we introduce an additional projection step. By incorporating a safeguard mechanism, we establish the global convergence of the proposed algorithm. For the numerical experiments, we consider large-scale LP instances derived from the MIPLIB 2017 dataset, where integer constraints are relaxed. Our results show that the AA-PDHG method outperforms, on selected instances, the vanilla PDHG algorithm in terms of convergence rate. We further investigate the impact of different AA memory sizes and observe trends consistent with findings in the existing literature. Importantly, our method enhances the vanilla PDHG algorithm using AA alone, without introducing any additional acceleration techniques. This simplicity suggests that, in future work, combining AA with other advanced strategies could yield variants of AA-PDHG capable of achieving performance comparable to that of state-of-the-art solvers such as PDLP google2022p . Appendix A Explicit expression of \Lambda and Proof of Remark 1 Proof. From ( 2.1 ), we know the variable \lambda=\lambda^{+}-\lambda^{-} , where \lambda^{+} corresponding to the constraint l\leq x , and \lambda^{-} corresponding to the constraint x\leq u . We analyse the different cases below, with the variables characterised component-wise as follows: (1) If l_{i}=-\infty , u_{i}=\infty , then \lambda_{i}=0 . (2) If l_{i}=-\infty , u_{i}\in\mathbb{R} , then \lambda_{i}^{+}=0 , \lambda_{i}^{-}\geq 0 , and hence \lambda_{i}=-\lambda_{i}^{-}\in\mathbb{R}_{-} . (3) If u_{i}=\infty , l_{i}\in\mathbb{R} , then \lambda_{i}^{+}\geq 0 , \lambda_{i}^{-}=0 , and hence \lambda_{i}=\lambda_{i}^{+}\in\mathbb{R}_{+} . (4) If l_{i},u_{i}\in\mathbb{R} , then \lambda_{i}^{+}\geq 0 , \lambda_{i}^{-}\geq 0 , and \lambda_{i}=\lambda_{i}^{+}-\lambda_{i}^{-}\in\mathbb{R} . Moreover, writing X:=X_{1}\times\dots\times X_{n} where X_{i}\in\{\mathbb{R},\;(-\infty,u_{i}],[l_{i},+\infty),[l_{i},u_{i}]\} , we have, \displaystyle\partial I_{X}(x)=\begin{cases}\{0\},&l_{i}=-\infty,\quad u_{i}=\infty,\\ \mathbb{R}_{+},&l_{i}=-\infty,\quad u_{i}\in\mathbb{R},\\ \mathbb{R}_{-},&l_{i}\in\mathbb{R},\quad u_{i}=\infty,\\ \mathbb{R},&l_{i}\in\mathbb{R},\quad u_{i}\in\mathbb{R},\end{cases} (34) and hence -\Lambda=\partial I_{X}(x) for all x\in\mathbb{R}^{n} . ∎ Appendix B Proof of \mathcal{I}_{Q}(Kx) = \mathcal{I}^{*}_{Y}(-Kx+q) Proof. The definition of \mathcal{I}^{*}_{Y}(-Kx+q) , yields, \displaystyle\mathcal{I}^{*}_{Y}(-Kx+q)= \displaystyle\sup_{y\in\mathbb{R}^{m}}\ \Big\{\langle-Kx+q,y\rangle-\mathcal{I}_{Y}(y)\Big\} \displaystyle= \displaystyle\sup_{y\in Y}\Big\{\langle-Kx+q,y\rangle\Big\} \displaystyle= \displaystyle\sup_{y\in Y}\sum_{i=1}^{m_{1}+m_{2}}(-Kx_{i}+q_{i})^{\top}y_{i}. Recall that Y:=\mathbb{R}_{+}^{m_{1}}\times\mathbb{R}^{m_{2}} , which means the dual variable y has non-negativity constraints on its first m_{1} components, and is unconstrained on the remaining m_{2} components. Analyzing the summation in the \sup component-wise: (a) For index i\in[1,m_{1}] , where y_{i}\geq 0 , (1) If -Kx_{i}+q_{i}<0 , then we would get \sup_{y\in Y}\sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=0. (2) If -Kx_{i}+q_{i}=0 , then we would get \sup_{y\in Y}\sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=0. (3) If -Kx_{i}+q_{i}>0 , then we would get \sup_{y\in Y}\sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=+\infty. (b) For index i\in[m_{1}+1,m_{1}+m_{2}] , where y_{i} is free, (1) If -Kx_{i}+q_{i}<0 , then we would get \sup_{y\in Y}\sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=+\infty. (2) If -Kx_{i}+q_{i}=0 , then we would get \sup_{y\in Y}\sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=0. (3) If -Kx_{i}+q_{i}>0 , then we would get \sup_{y\in Y}\sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=+\infty. In summary, for all i\in[1,m_{1}+m_{2}] , when -Kx_{i}+q_{i}=0 or when -Kx_{i}+q_{i}<0 for i\in[1:m_{1}] , the supremum of \sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=0 , otherwise, \sup_{y\in Y}\sum_{i}(-Kx_{i}+q_{i})^{\top}y_{i}=+\infty . We obtained, hence, \mathcal{I}^{*}_{Y}(-Kx+q)=\begin{cases}0,&\text{if }(Kx)_{i}\geq q_{i}\text{ for }i=1,\dots,m_{1}\\ &\text{ and }(Kx)_{i}=q_{i}\text{ for }i=m_{1}+1,\dots,m_{1}+m_{2},\\ +\infty,&\text{otherwise}\end{cases}=:\mathcal{I}_{Q}(Kx), where Q is the set Q:=\{Kx\mid(Kx)_{i}=q_{i}\text{ for all }i=m_{1}+1,\dots,m_{1}+m_{2},\;(Kx)_{i}\geq q_{i}\text{ for }i=1,\dots,m_{1}\}. ∎