HPR method for QP

In this section, we review HPR-LP, a Halpern-Peaceman-Rachford (HPR) method for solving linear programming problems. We first describe the base algorithm and then discuss its convergence guarntees and complexity properties, which motivate subsequent algorithmic enhancements.

Base algorithm

For any \((y, z, x) \in \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n\), the augmented Lagrangian of the dual problem is

\[L_\sigma(y, z; x) := \delta_{\mathcal{K}}^*(-y) + \delta_{\mathcal{C}}^*(-z) + \langle x, A^* y + z - c \rangle + \frac{\sigma}{2} \| A^* y + z - c \|^2,\]

where \(\sigma > 0\) is a penalty parameter. For notational convenience, let \(w := (y, z, x) \in \mathbb{W} := \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n\). Then, an HPR method with semi-proximal terms [40, 5] for solving problems (1.1) and (1.2) is summarized in Algorithm 2.1.

\[\begin{split}\begin{array}{|l|} \hline \textbf{Algorithm 2.1: An HPR method with semi-proximal terms for the problem (1.2)} \\ \hline \textbf{Input:}\ \text{Set the penalty parameter }\sigma>0.\ \\ \text{Let }\mathcal{T}_1:\mathbb{R}^m\to\mathbb{R}^m\ \text{be a self-adjoint positive semidefinite linear operator such that } \\ \mathcal{T}_1+\sigma A A^*\ \text{is positive definite. } \text{Denote } w=(y,z,x)\ \text{and }\bar{w}=(\bar{y},\bar{z},\bar{x}).\ \\ \text{Choose an initial point } w^0=(y^0,z^0,x^0)\in\mathbb{R}^m\times\mathbb{R}^n\times\mathbb{R}^n. \\ \textbf{for } k = 0,1,\ldots \ \textbf{do} \\ \quad \text{Step 1: } \ \bar{z}^{k+1} = \arg\min_{z \in \mathbb{R}^n} L_\sigma(y^k, z; x^k). \\ \quad \text{Step 2: } \ \bar{x}^{k+1} = x^k + \sigma(A^* y^k + \bar{z}^{k+1} - c). \\ \quad \text{Step 3: } \ \bar{y}^{k+1} = \arg\min_{y \in \mathbb{R}^m} \left\{ L_\sigma(y, \bar{z}^{k+1}; \bar{x}^{k+1}) + \tfrac{\sigma}{2}\|y-y^k\|_{\mathcal{T}_1}^2 \right\}. \\ \quad \text{Step 4: } \ \hat{w}^{k+1} = 2\bar{w}^{k+1} - w^k. \\ \quad \text{Step 5: } \ w^{k+1} = \tfrac{1}{k+2} w^0 + \tfrac{k+1}{k+2} \hat{w}^{k+1}. \\ \textbf{end for} \\ \textbf{Output:} \text{Iteration sequence } \{ \bar{w}^k \}. \\ \hline \end{array}\end{split}\]

Remark 2.1. Steps 1–3 correspond to the Douglas–Rachford (DR) method [17, 15]. Adding Step 4 (relaxation) yields the Peaceman–Rachford (PR) method, and Step 5 introduces Halpern iteration with step size \(1/(k+2)\) [20, 26]. Together, Algorithm 2.1 is an accelerated preconditioned ADMM (pADMM) with parameter \(\alpha = 2\) [40].

According to [37, Corollary 28.3.1], a pair \((y^*, z^*) \in \mathbb{R}^m \times \mathbb{R}^n\) is an optimal solution to problem (1.2) if there exists \(x^* \in \mathbb{R}^n\) such that \((y^*, z^*, x^*)\) satisfies the following KKT system:

\[\begin{split}\begin{aligned} 0 &\in A x^* - \partial \delta_{\mathcal{K}}^*(-y^*), \\ 0 &\in x^* - \partial \delta_{\mathcal{C}}^*(-z^*), \\ &\quad A^* y^* + z^* - c = 0. \end{aligned}\end{split}\]

We make the following assumption:

Assumption 2.2. There exists a vector \((y^*, z^*, x^*) \in \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n\) satisfying the KKT system (2.1).

Under Assumption 2.2, solving the primal–dual pair (1.1)–(1.2) is equivalent to finding a point \(w^* \in \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n\) such that \(0 \in \mathcal{T} w^*\), where the maximal monotone operator \(\mathcal{T}\) is defined as

\[\begin{split}\mathcal{T} w = \begin{pmatrix} - \partial \delta_{\mathcal{K}}^*(-y) + A x \\ - \partial \delta_{\mathcal{C}}^*(-z) + x \\ c - A^* y - z \end{pmatrix}, \quad \forall w = (y, z, x) \in \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n.\end{split}\]

The global convergence of Algorithm 2.1 is established in the following proposition.

Proposition 2.3 (Corollary 3.5 in [40]). Suppose that Assumption 2.2 holds.
Then the sequence \(\{\bar{w}^k\} = \{(\bar{y}^k, \bar{z}^k, \bar{x}^k)\}\) generated by the HPR method with semi-proximal terms in Algorithm 2.1 converges to a point \(w^* = (y^*, z^*, x^*)\), where \((y^*, z^*)\) solves the dual problem (1.2) and \(x^*\) solves the primal problem (1.1).

Next, consider the self-adjoint positive semidefinite linear operator \(\mathcal{M} : \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n\) defined by

\[\begin{split}\mathcal{M} = \begin{bmatrix} \sigma A A^* + \sigma T_1 & 0 & A \\ 0 & T_2 & I \\ A^* & I & \tfrac{1}{\sigma} I_n \end{bmatrix},\end{split}\]

where \(I_n\) denotes the \(n \times n\) identity matrix. To analyze the complexity of the HPR method with semi-proximal terms, we consider the KKT residual and the objective error. The residual mapping associated with the KKT system (2.1), as introduced in [21], is given by

\[\begin{split}\mathcal{R}(w) = \begin{pmatrix} A x - \Pi_{\mathcal{K}}(A x - y) \\ x - \Pi_{\mathcal{C}}(x - z) \\ c - A^* y - z \end{pmatrix}, \quad \forall w = (y, z, x) \in \mathbb{R}^m \times \mathbb{R}^n \times \mathbb{R}^n.\end{split}\]

Furthermore, let \(\{(\bar{y}^k, \bar{z}^k)\}\) be the sequence generated by Algorithm 2.1. We define

the objective error as

\[h(\bar{y}^{k+1}, \bar{z}^{k+1}) := \delta_{\mathcal{K}}^*(-\bar{y}^{k+1}) + \delta_{\mathcal{C}}^*(-\bar{z}^{k+1}) - \delta_{\mathcal{K}}^*(-y^*) - \delta_{\mathcal{C}}^*(-z^*), \quad \forall k \geq 0,\]

where \((y^*, z^*)\) is the limit point of the sequence \(\{(\bar{y}^k, \bar{z}^k)\}\).
The complexity of the HPR method with semi-proximal terms is summarized in Theorem 2.4.

Theorem 2.4 (Proposition 2.9 and Theorem 3.7 in [40]).
Suppose that Assumption 2.2 holds. Let \(\{w^k\} = \{(y^k, z^k, x^k)\}\) and \(\{\bar{w}^k\} = \{(\bar{y}^k, \bar{z}^k, \bar{x}^k)\}\) be two sequences generated by the HPR method with semi-proximal terms in Algorithm 2.1, and let \(w^* = (y^*, z^*, x^*)\) be its limit point. Define \(R_0 = \|w^0 - w^*\|_{\mathcal{M}}\). Then for all \(k \geq 0\), the following iteration complexity bounds hold:

\[\| w^k - \hat{w}^{k+1} \|_{\mathcal{M}} \leq \frac{R_0}{k+1},\]

\[\| \mathcal{R}(\bar{w}^{k+1}) \| \leq \left( \frac{\sigma(\|A\| + \| \sqrt{T_1} \|) + 1}{\sqrt{\sigma}} \right) \frac{R_0}{k+1},\]

\[- \frac{1}{\sqrt{\sigma}} \| x^* \| \frac{R_0}{k+1} \;\; \leq \;\; h(\bar{y}^{k+1}, \bar{z}^{k+1}) \;\; \leq \;\; \left( 3 R_0 + \frac{1}{\sqrt{\sigma}} \| x^* \| \right) \frac{R_0}{k+1}.\]

Remark 2.5. existing complexity results for LP

The results above establish that the HPR method enjoys global convergence and an \(O(1/k)\) complexity rate in terms of both KKT residuals and objective error. These properties motivate the use of restart strategies and adaptive parameter updates, which will be reviewed in the next subsection.