# Companion Report of PROXQP: an Efficient and Versatile Quadratic Programming Solver for Real-Time Robotics Applications and Beyond

Antoine Bambade, Fabian Schramm, Sarah El Kazdadi, Stéphane Caron, Adrien Taylor, Justin Carpentier

► To cite this version:

Antoine Bambade, Fabian Schramm, Sarah El Kazdadi, Stéphane Caron, Adrien Taylor, et al. Companion Report of PROXQP: an Efficient and Versatile Quadratic Programming Solver for Real-Time Robotics Applications and Beyond. INRIA. 2023. hal-04196897

HAL Id: hal-04196897

https://inria.hal.science/hal-04196897v1

Submitted on 5 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# — Companion Report —
PROXQP: an Efficient and Versatile Quadratic
Programming Solver for Real-Time Robotics
Applications and Beyond

Antoine Bambade*,<fnref n="1" />,<fnref n="2" />, Fabian Schramm<fnref n="1" />, Sarah El-Kazdadi<fnref n="1" />,
Stéphane Caron<fnref n="1" />, Adrien Taylor<fnref n="1" /> and Justin Carpentier<fnref n="1" />

## A. Companion report organisation

This companion report provides the proof associated to the PROXQP algorithm introduced in [1]. It is organized as follows.

Section -B provides more details about which properties motivate the update rule presented in Section VI-B. Section -D establishes the global convergence of PROXQP (Theorem 1). It illustrates that BCL algorithm [2] finds appropriate proximal steps to match a desired convergence speed for primal feasibility $p^k$. More precisely, BCL decreases $\mu^k$ until the inequality $p^k \le \epsilon_{bcl}^k$ holds for all iteration starting from $k$. At this stage of the algorithm, PROXQP amounts to a primal-dual proximal point algorithm, and we rely on [3, Proposition 1.2] to ensure the global convergence of PROXQP. We study the simplified Algorithm 2, which assumes that at each iteration $k$ of the algorithm $\rho^k = \mu^k$ compared to Algorithm 1, where $\rho$ is fixed. Updating $\rho$ is not desirable in practice since it would require a numerical factorization at each iteration.

<table><caption>TABLE I: Organization of the companion report.</caption><thead><tr><th>Section</th><th>Content</th></tr></thead><tbody><tr><td>Section -B</td><td>More details about Section VI-B update rule</td></tr><tr><td>Section -C</td><td>Notations and technical properties</td></tr><tr><td>Section -D<br>Missing technical<br>elements.</td><td>Proof of Lemma 1<br>Proof of Lemma 2<br>Proof of Lemma 3</td></tr><tr><td>Section -E</td><td>Proof of Theorem 1</td></tr><tr><td>Section -F</td><td>Proof of Lemma 1</td></tr></tbody></table>

## B. Details about the update rule presented in Section VI-B

The update rule presented in Section VI-B is motivated by the following intuition. Assume the steady state $x_{goal}$ is still

reachable by an unconstrained LQR scheme (see the grey line in Figure 1)

$$ 
\begin{array}{l}
\min_{x_t \in \mathbb{R}^{n_x}, u_t \in \mathbb{R}^{n_u}} x_T^\top Q_T x_T + \sum_{t=0}^{T-1} x_t^\top Q x_t + u_t^\top R u_t, \qquad (1) \\
\text{s.t. } x_{t+1} = Ax_t + Bu_t, \quad x_0 = x_{\text{init}},
\end{array}
$$

with a solution sequence {$x_t^{LQR}$}$_t$, {$u_t^{LQR}$}$_t$. As the constraints are linear, strong duality holds, and the primal of problem (1) $p^{LQR}$ equals its dual $\delta^{LQR}$ for some dual multipliers {$y_t^{LQR}$}$_t$. Noting $\mathcal{L}^{LQR}$ the Lagrangian of problem (1), we have

$$ 
\begin{aligned}
-\infty < \delta^{LQR} &= \mathcal{L}^{LQR}(\{x_t^{LQR}\}_t, \{u_t^{LQR}\}_t, \{y_t^{LQR}\}_t) \\
&= \mathcal{L}(\{x_t^{LQR}\}_t, \{u_t^{LQR}\}_t, \{y_t^{LQR}\}_t, 0, 0), \\
&= \inf_{x_t, u_t} \mathcal{L}(\{x_t\}_t, \{u_t\}_t, \{y_t^{LQR}\}_t, 0, 0),
\end{aligned}
$$

with $\mathcal{L}$ the Lagrangian of the original problem (16), and 0 corresponds to the value of the dual multipliers associated with the box constraints with respect to $x_t$ and $u_t$. It thus guarantees the dual of the original problem has a non-empty domain and that there exists a closest feasible solution sequence {$\hat{x}_t$}$_t$, {$\hat{u}_t$}$_t$ (see the orange line in Figure 1) with associated optimal shifts {$\hat{s}_t^e$}$_t$, {$\hat{s}_t^x$}$_t$, {$\hat{s}_t^u$}$_t$.

If we compare now $\|x_1^{LQR} - x_{goal}\|_2^2$ with $\|x_1 - x_{goal}\|_2^2$ assuming that both $x_1^{LQR} > \bar{x}$ and $\hat{x}_1 > \bar{x}$ we see

$$ 
\begin{aligned}
\|x_1^{LQR} - x_{goal}\|_2^2 &= \|x_1^{LQR} - \bar{x}\|_2^2 + \|\bar{x} - x_{goal}\|_2^2 + \\
&\quad 2(x_1^{LQR} - \bar{x})^{\top}(\bar{x} - x_{goal}),
\end{aligned}
$$

and

$$ 
\begin{aligned}
\|x_1 - x_{goal}\|_2^2 &= \|x_1 - \bar{x}\|_2^2 + \|\bar{x} - x_{goal}\|_2^2 + 2(x_1 - \bar{x})^{\top}(\bar{x} - x_{goal}), \\
&= \|\hat{x}_1 - B\hat{s}_0^u - \bar{x}\|_2^2 + \|\bar{x} - x_{goal}\|_2^2 + \\
&\quad 2(\hat{x}_1 - B\hat{s}_0^u - \bar{x})^{\top}(\bar{x} - x_{goal}) \\
&= \|\underbrace{\hat{x}_1 - \bar{x}}_{=\hat{s}_1^x}\|_2^2 + \|B\hat{s}_0^u\|_2^2 - 2(B\hat{s}_0^u)^{\top}(\hat{s}_1^x) + \\
&\quad \|\bar{x} - x_{goal}\|_2^2 + 2(\hat{s}^x - B\hat{s}_0^u)^{\top}(\bar{x} - x_{goal}).
\end{aligned}
$$

Thus we have:

$$ 
\begin{aligned}
& \|x_1^{LQR} - x_{goal}\|_2^2 - \|x_1 - x_{goal}\|_2^2 = \|x_1^{LQR} - \bar{x}\|_2^2 + \\
& 2(x_1^{LQR} - \bar{x})^{\top}(\bar{x} - x_{goal}) - \|\hat{s}_1^x\|_2^2 - \|B\hat{s}_0^u\|_2^2 - \\
& 2(\hat{s}_1^x - B\hat{s}_0^u)^{\top}(\bar{x} - x_{goal}) + 2(B\hat{s}_0^u)^{\top}(\hat{s}_1^x).
\end{aligned}
\qquad (2)
$$

<footnote>*Corresponding author. bambade.antoine@gmail.com</footnote>

<footnote n="1">¹Inria - Département d'Informatique de l'École normale supérieure, PSL Research University.</footnote>

<footnote n="2">²École des Ponts, Marne-la-Vallée, France.</footnote>
Since $x_1^{\text{LQR}} > \bar{x}$ and $\bar{x} > x_{\text{goal}}$, then $(x_1^{\text{LQR}} - \bar{x})^{\top}(\bar{x} - x_{\text{goal}}) > 0$. Hence, if the optimal shifts $\hat{s}_0^u$ and $\hat{s}_1^x$ are sufficiently small, Equation (2) shows that $\|x_1^{\text{LQR}} - x_{\text{goal}}\|_2 > \|x_1 - x_{\text{goal}}\|_2$. The same calculus shows in this setting that $\|x_1^{\text{LQR}} - \bar{x}\|_2 > \|x_1 - \bar{x}\|_2$. Consequently, this update rule guarantees in this setting that if $x_{\text{init}}$ is not too far in the sense that the optimal shifts are small enough, then the update rule provides a point from which the feasible target $x_{\text{goal}}$ is both closer to reach and closer of the feasible frontier. Our intuition is that the property of this update rule may eventually lead to a feasible update, with demonstration further investigated in future work.

### C. Further notations and technical properties

This section provides a few additional technical ingredients that are necessary for establishing PROXQP convergence proof. The Fenchel convex conjugate of a function $\phi: \mathbb{R}^m \mapsto \mathbb{R} \cup \{\infty\}$ is defined as $\phi^*: \mathbb{R}^m \mapsto \mathbb{R} \cup \{\infty\}$ though

$$ \phi^*(y) \stackrel{\text{def}}{=} \sup_{z \in \mathbb{R}^m} \{y^\top z - \phi(z)\} = - \inf_{z \in \mathbb{R}^m} \{\phi(x) - y^\top z\}. \quad (3) $$

We introduce a maximal monotone operator $T_L^{-1}(v, t)$ (see for more details [4]), that encodes the set of solutions of the shifted problem (QP) by $(t, v)$:

$$ \begin{aligned} T_L(x, z) &\stackrel{\text{def}}{=} \{(v, t)| (v, -t) \in \partial \mathcal{L}(x, z)\}, \\ T_L^{-1}(v, t) &\stackrel{\text{def}}{=} \arg \min_{x \in \mathbb{R}^n} \max_{z \in \mathbb{R}^m} \{\mathcal{L}(x, z) - x^\top v + z^\top t\}, \end{aligned} $$

where $\partial \mathcal{L}$ refers to

$$ \partial \mathcal{L}(x, z) \stackrel{\text{def}}{=} \begin{pmatrix} \nabla f(x) + C^\top z \\ Cx - \partial I_u^*(z) \end{pmatrix}, \quad (4) $$

where $I_u$ denotes the indicator function of the constraint set $Cx \le u$. The Lagrangian function and $T_L(x, z)$ encodes the saddle sub-differential for (QP) [5, Section 4.3]. $T_L$ and $T_L^{-1}$ are generally "point to set" operators. From $T_L$ and for $\mu > 0$ we also introduce the resolvent of $T_L$ and $T_L^{-1}$

* the resolvent of $T_L$ [4]:

$$ P_{\mu} \stackrel{\text{def}}{=} \left(I + \frac{1}{\mu} T_L\right)^{-1}, \quad (5) $$

* the resolvent of $T_L^{-1}$ [4]:

$$ Q_{\mu} \stackrel{\text{def}}{=} (I + \mu T_L^{-1})^{-1} = I - P_{\mu}. \quad (6) $$

More precisely, when $T_L^{-1}(0, 0)$ is non-empty, it encodes the set of solutions to (QP). When (QP) is feasible, the KKT conditions for (QP) form a polyhedral variational inequality [6, Section 3D]. Hence, $\exists a \ge 0, \tau > 0$, such that $\forall (u, v) \in \mathbb{R}^{n+m}$:

$$ \begin{aligned} & \|(u, v)\| \le \tau \\ & \implies \operatorname{dist}_{T_L^{-1}(0,0)}(x, z) \le a \|(u, v)\|, \forall (x, z) \in T_L^{-1}(u, v) \end{aligned} \quad (7) $$

$a$ and $\tau$ are constants describing the geometry of the QP. Rockafellar [7, Thm. 2] has established that it holds as soon as $T_L(0, 0)^{-1} \ne \emptyset$. That is, $\forall \mu > 0, \forall (x, z) \in \mathbb{R}^n \times \mathbb{R}^m$:

$$ \mu \|Q_{\mu}(x, z)\| \le \tau \quad (8) $$

$$ \operatorname{dist}_{T_L(0,0)^{-1}}(P_{\mu}(x, z)) \le \frac{a\mu}{\sqrt{1+a^2\mu^2}} \operatorname{dist}_{T_L(0,0)^{-1}}(x, z). $$

### D. Convergence of PROXQP

The main convergence result for PROXQP is provided by Theorem 1. For proving this theorem (in Section -E), we proceed with the following strategy. This strategy relies on a slightly different formulation of ProxQP provided by Algorithm 2 (it is necessary for the proof to consider the conceptual infinite sequence of iterates generated by the algorithm).

* First, subsubsection -D1 shows that the “if condition” of ProxQP (see Algorithm 2) is satisfied at infinitely many iterations.

* Second, subsubsection -D2 is more accurate and shows that the “else condition” of ProxQP (see Algorithm 2) is entered only for a finite number of iterations.

* It follows from the second point that ProxQP corresponds to an appropriate type of approximate primal-dual proximal point method, and hence inherits all its nice convergence properties. This is formally stated in Section -E.

* Finally, one can conveniently deduce from this construction that ProxQP asymptotically corresponds to a fixed-step proximal method of multiplier (PMM, i.e., there exists $K > 0$ such that for all $k \ge K$, $\mu^k$ is constant). This is formally stated in Section -F.

1) We enter the “if” of Algorithm 2 an infinite number of times

**Lemma 1.** Under Assumption 1 and Assumption 2, $\forall k \in \mathbb{N}, \exists K \ge 0$ such that the condition $\|[Cx^{k+K+1} - u]_+\|_{\infty} \le \epsilon_{bcl}^{k+K}$ of Algorithm 2 is satisfied.

*Proof.* The following proof proceeds by contradiction. That is, we show that there cannot exist a $k \ge 0$ such that $\forall K > 0$ it holds that $p^{k+K} \stackrel{\text{def}}{=} \|[Cx^{k+K+1} - u]_+\|_{\infty} > \epsilon_{bcl}^{k+K}$ (as defined in (8)). For convenience, and without loss of generality, we assume $k = 0$.

By contradiction hypothesis, we thus have that $p^K > \epsilon_{bcl}^K$ holds $\forall K \ge 0$. Therefore, $\mu^K = \mu^0(\mu_f)^K$ and $\epsilon_{bcl}^K = \epsilon_{bcl}^0(\mu^0)^{\alpha_{bcl}}(\mu_f)^{\alpha_{bcl}K}$ and hence $\mu^K \to 0$ and $\epsilon_{bcl}^K \to 0$ as $K \to \infty$, since $\mu_f \in (0, 1)$ and $\alpha_{bcl} \in (0, 1/2)$. For establishing the desired statement, we show that under the contradiction hypothesis, one has

$$ \epsilon_{bcl}^K < \|[Cx^{K+1} - u]_+\|_{\infty} \le A\sqrt{\mu^K}, \quad (9) $$

for all $K \ge 0$, thereby reaching a contradiction. Indeed, with $\alpha_{bcl} \in (0, 1/2)$, the term $\sqrt{\mu^K}$ goes faster to zero (as a function of $K$) than $\epsilon_{bcl}^K$. More precisely, the hyperparameter choices within PROXQP ensure that $\exists K_0 \ge 0$ such that $\forall K \ge K_0$, $\epsilon_{bcl}^K > A\sqrt{\mu^K}$.

For proving our claim, we, therefore, focus on proving (9) in the following lines.

First, at iteration $K + 1$, the pair $(x^{K+1}, \hat{z}^{K+1})$ is an approximate solution to (10). In other words, by defining intermediary variables, we have:

$$ u^K \stackrel{\text{def}}{=} \nabla f(x^{K+1}) + C^\top \hat{z}^{K+1} + \mu^K (x^{K+1} - x^K), $$

$$ v^K \stackrel{\text{def}}{=} [Cx^{K+1} - u + \mu^K (z^0 + (\alpha - 1) \hat{z}^{K+1}]_+ - \hat{z}^{K+1} \alpha \mu^K, $$
with $\|(u^K, v^K)\|_\infty \le \epsilon^K$. Following [8, Section 3.1], one can equivalently look at $(x^{k+1}, \hat{z}^{k+1})$ as the unique minimum of the strongly convex function $\hat{M}_{\rho, \mu^K, \alpha}^K$:

$$ \hat{M}_{\rho, \mu^K, \alpha}^K (x, z) \stackrel{\text{def}}{=} f(x) + \frac{\mu^K}{2} \|x - (x^K + \frac{1}{\mu^K} u^K)\|_2^2 \\ + \frac{1}{2\alpha \mu^K} \|[Cx - u + \mu^K(z^K + (\alpha - 1)z)]_+\|_2^2 \\ + \frac{(1-\alpha)\mu^K}{2} \|z + \frac{1}{\alpha \mu^K} v^K\|_2^2. $$

Therefore, for any $x \in \mathbb{R}^n$ satisfying $Cx - u \le 0$ (such a feasible $x$ exists by Assumption 2), we get:

$$ \hat{M}_{\rho, \mu^K, \alpha}^K (x^{K+1}, \hat{z}^{K+1}) \le \hat{M}_{\rho, \mu^K, \alpha}^K (x, 0). $$

As $\{x^K\}$ is bounded by Assumption 2, then $\exists M > 0$ independent of $K$ such that

$$ \hat{M}_{\rho, \mu^K, \alpha}^K (x^{K+1}, \hat{z}^{K+1}) \le f(x) + M\mu^K, \quad (10) $$

where we used the facts that for a feasible point $x$, $[Cx - u + z^0\mu^K]_+ \le [z^0]_+\mu^K$ (as $Cx - u \le 0$), and that $\|(u^K, v^K)\|_\infty \le \epsilon^K$ implies that $\|u^K\|_\infty/\mu^K \le \epsilon^0$ and that $\|v^K\|_\infty/\mu^K$.

It follows from the definition of $\hat{M}_{\rho, \mu^K, \alpha}^K$ (and nonnegativity of the $\|\cdot\|_2$ terms) that:

* we can bound

$$ \hat{M}_{\rho, \mu^K, \alpha}^K (x^{K+1}, \hat{z}^{K+1}) \ge f(x^{K+1}) \\ + \frac{1}{2\alpha\mu^K} \|[Cx^{K+1} - u + \mu^K(z^0 + (\alpha - 1)\hat{z}^{K+1})]_+\|_2^2 $$

which, using (10), can be used to reach

$$ \|[Cx^{K+1} - u + \mu^K(z^0 + (\alpha - 1)\hat{z}^{K+1})]_+\|_2 \le \sqrt{2\mu^K\alpha(f(x) - f(x^{K+1}) + M\mu^K)}. \quad (11) $$

From (11), since $\{x^K\}_K$ is bounded and $f$ is a quadratic, we deduce that there exists some $M_1 > 0$ independent of $K$ such that

$$ \|[Cx^{K+1} - u + \mu^K(z^0 + (\alpha - 1)\hat{z}^{K+1})]_+\|_2 \le \sqrt{\mu^K} M_1. \quad (12) $$

* We can bound

$$ \hat{M}_{\rho, \mu^K, \alpha}^K (x^{K+1}, \hat{z}^{K+1}) \ge f(x^{K+1}) \\ + \frac{(1-\alpha)\mu^K}{2} \|z + \frac{1}{\alpha \mu^K} v^K\|_2^2. $$

which, using (10), can be used to reach

$$ \sqrt{\mu^K} \|\hat{z}^{K+1}\|_2 \le \frac{\sqrt{2}}{\sqrt{1-\alpha}} (\sqrt{f(x) - f(x^{K+1}) + M\mu^K} \\ + \frac{\sqrt{1-\alpha}}{\sqrt{\alpha}} \|v^K\|_2). $$

It shows that $\sqrt{\mu^K} \|\hat{z}^{K+1}\|_2$ is bounded since $\{x^K\}$ is bounded and $f$ is a quadratic function.

We are now properly armed to guarantee that $\forall K > 0$:

$$ \|[Cx^{K+1} - u]_+\|_\infty \le A\sqrt{\mu^K}. \quad (13) $$

for some $A > 0$. Indeed, it holds component-wise

$$ \begin{aligned} & [Cx^{K+1} - u]_+ - \mu^K |(z^0 + (\alpha - 1)\hat{z}^{K+1})| \\ & \le [Cx^{K+1} - u + \mu^K(z^0 + (\alpha - 1)\hat{z}^{K+1})]_+, \end{aligned} \quad (14) $$

where $|\cdot|$ is the absolute value taken component-wise. We can deduce from (14) that

$$ \begin{aligned} \|[Cx^{K+1} - u]_+\|_2 & \le \|[Cx^{K+1} - u + \mu^K(z^0 + (\alpha - 1)\hat{z}^{K+1})]_+\|_2 \\ & \quad + \sqrt{\mu^K} \|\sqrt{\mu^K}(z^0 + (\alpha - 1)\hat{z}^{K+1})\|_2 \end{aligned} \quad (15) $$

Hence, from (15), using (12) and the fact that $\{\sqrt{\mu^K}(z^0 + (\alpha - 1)\hat{z}^{K+1})\}_K$ is bounded by some $M_2 > 0$ (since $\{\sqrt{\mu^K}\hat{z}^{K+1}\}$ is bounded and $\{\sqrt{\mu^K}\}_K$ converges to zero) we get

$$ \|[Cx^{K+1} - u]_+\|_2 \le \underbrace{(M_1 + M_2)}_{\text{def}=A>0} \sqrt{\mu^K}. $$

To reach the desired claim, we use (13) together with the contradiction hypothesis that $\epsilon_{\text{bcl}}^K < \|[Cx^{K+1} - u]_+\|_\infty$ which allows reaching the contradiction that $\forall K > 0$:

$$ \epsilon_{\text{bcl}}^K \le A\sqrt{\mu^K}. $$

□

## 2) We enter the “else” of Algorithm 2 a finite number of times

As reviewed in Section -D, this section establishes that the “else” condition of Algorithm 2 is only entered a finite number of times. The proof can be summarized as follows.

* If the “else” condition is never satisfied, then the result directly holds.

* Otherwise, since Lemma 1 ensures the “if” condition is entered an infinite number of times, we consider the following setting. Without loss of generality, we can assume that the “else” condition is entered at iteration $k$ for the $K$th time and that it is followed by a “if” condition. It implies that

$$ \mu^k = \mu^0(\mu_f)^K, \quad \epsilon_{\text{bcl}}^k = \epsilon_{\text{bcl}}^0(\mu^k)^{\alpha_{\text{bcl}}}. $$

We denote by $N \ge 2$ the number of consecutive iterations from $k$ for which we enter the “if” condition, meaning that

$$ \mu^{k+N} = \mu^0(\mu_f)^K, \quad \epsilon_{\text{bcl}}^{k+N-1} = \epsilon_{\text{bcl}}^0(\mu^k)^{\alpha_{\text{bcl}}+(N-1)\beta_{\text{bcl}}}. $$

In this situation, one can establish that for QPs, there exists constants $M > 0$ and $b \ge 1$ (describing the geometry of the problem at hand) such that the primal feasibility can be upper-bounded for $N \ge 2$ by

$$ \|[Cx^{k+N} - u]_+\|_\infty \le M (b\mu^k)^{N-1}, \quad (16) $$

For entering the “else” condition in this scenario at the $(k+N)$th step, it is therefore necessary to be in the situation where

$$ \epsilon_{\text{bcl}}^{k+N-1} < \|[Cx^{k+N} - u]_+\|_\infty \le M (b\mu^k)^{N-1}, $$

Substituting the expressions for $\epsilon_{\text{bcl}}^{k+N-1}$ and $\mu^k$, we arrive to the following necessary condition for entering the “else” at iteration $(k+N)$:

$$ \epsilon_{\text{bcl}}^0(\mu^0(\mu_f)^K)^{\alpha_{\text{bcl}}+(N-1)\beta_{\text{bcl}}} \le M(b\mu^0(\mu_f)^K)^{N-1}. $$
On the contrary, it is therefore sufficient to satisfy

$$M(b\mu^0(\mu_f)^K)^{N-1} \le \epsilon_{b\text{cl}}^0(\mu^0(\mu_f)^K)^{\alpha_{b\text{cl}}+(N-1)\beta_{b\text{cl}}}$$

for not entering the “else”. Given that $\alpha_{b\text{cl}} \in (0, 1/2)$, $\beta_{b\text{cl}} \in (0, 1)$ with $\beta_{b\text{cl}} + \alpha_{b\text{cl}} < 1$, and $\mu_f \in (0, 1)$ it can be established that this condition is met for all $N \ge 2$ as soon as

$$\max\left(\left[\frac{\log\left(\frac{b(\mu^0)^{1-\alpha_{b\text{cl}}-\beta_{b\text{cl}}}M}{\epsilon_{b\text{cl}}^0}\right)}{-\log(\mu_f)(1-\alpha_{b\text{cl}}-\beta_{b\text{cl}})}\right], \left[\frac{\log(b(\mu^0)^{1-\beta_{b\text{cl}}})}{-\log(\mu_f)(1-\beta_{b\text{cl}})}\right], K_\tau\right) \le K, \quad (17)$$

for some $K_\tau \in \mathbb{N}$ (for the pair $(a, \tau)$ from (8), which describes the geometry of the QP at hand). It shows that the “else” condition is entered only a finite number of times, thereby arriving to the desired conclusion.

Our main target is thus to establish that (17) holds, as the desired conclusion nicely follows from this fact. For reaching this target, Lemma 2 provides an intermediary result which ensures that for $K$ sufficiently large (i.e., larger than $K_\tau$ mentioned in (17)), the technical property (8) holds for all the iterates of PROXQP.

**Lemma 2.** Under Assumption 1, Assumption 2, and if $\mu^k \to 0$ (i.e., we enter an infinite number of times the “else” condition), for any $\tau > 0$ $\exists K_\tau \in \mathbb{N}$ such that for all $\forall k \ge K_\tau$, $\mu^k \|Q_{\mu^k}(x^k, z^k)\|_2 \le \tau$.

*Proof.* In this setting $\epsilon^k = \epsilon^0 \mu^k$. Then, by definition of $Q_{\mu^k}$ (6)

$$\begin{align}
\|Q_{\mu^k}(x^k, z^k)\|_2 &= \|(x^k, z^k) - P_{\mu^k}(x^k, z^k)\|_2 \nonumber \\
&\le \left\| \begin{pmatrix} x^k - x^{k+1} \\ z^k - z^{k+1} \end{pmatrix} \right\|_2 + \|(x^{k+1}, z^{k+1}) - P_{\mu^k}(x^k, z^k)\|_2. \tag{18}
\end{align}$$

$P_{\mu^k}(x^k, z^k)$ corresponds to the solution pair to (3). Since $M_{\mu^k, \mu^k, \alpha}$ is strongly convex with parameter at least $(1-\alpha)\mu^k$, it follows that

$$\begin{align*}
(1-\alpha)\mu^k \|(x^{k+1}, z^{k+1}) - P_{\mu^k}(x^k, z^k)\|_2 &\le \|\nabla M_{\mu^k, \mu^k, \alpha}(x^{k+1}, z^{k+1}) - \underbrace{\nabla M_{\mu^k, \mu^k, \alpha}(P_{\mu^k}(x^k, z^k))}_{=0} \|_2 \\
&\le \max(1, \frac{1-\alpha}{\alpha})\epsilon^k,
\end{align*}$$

where the last inequality comes from the fact that

$$\begin{align}
\nabla_z M_{\mu^k, \mu^k, \alpha}(x^{k+1}, z^{k+1}) &= \frac{1-\alpha}{\alpha} ([Cx^{k+1} - u + \mu^k(z^k + (\alpha-1)z^{k+1})]_+ - \alpha \mu^k z^{k+1}), \nonumber \\
\text{and } (x^{k+1}, z^{k+1}) \text{ satisfies (11) at accuracy } \epsilon^k. \text{ Hence, it holds} \nonumber \\
&\qquad \|(x^{k+1}, z^{k+1}) - P_{\mu^k}(x^k, z^k)\|_2 \le \underbrace{\max(\frac{1}{1-\alpha}, \frac{1}{\alpha}) \epsilon^k}_{\text{def}} / \mu^k. \tag{19}
\end{align}$$

As $\epsilon^k = \epsilon^0 \mu^k$, combining (18) with (19) allows obtaining the upper bound

$$\begin{align}
\mu^k \|Q_{\mu^k}(x^k, z^k)\|_2 &\le \mu^k \left\| \begin{pmatrix} x^k - x^{k+1} \\ z^k - z^{k+1} \end{pmatrix} \right\|_2 + w\epsilon^k \tag{20} \\
&\le \mu^k \left\| \begin{pmatrix} x^k - x^{k+1} \\ z^k - z^{k+1} \end{pmatrix} \right\|_2 + \mu^k w \epsilon^0. \nonumber
\end{align}$$

Since $\{(x_k, z_k)\}$ is bounded (see Assumption 1), and since $\mu^k \to 0$ (exponentially in the number of times we enter the

“else” condition), we conclude from (20) that $\forall \tau > 0$, there $\exists K_\tau \in \mathbb{N}$, such that $\forall k \ge K_\tau$, $\mu^k \|Q_{\mu^k}(x^k, z^k)\|_2 \le \tau$. $\square$

Finally, Lemma 3 establishes our main targets. More precisely, we make use of Lemma 2 to establish first the inequality (16) and then (17).

**Lemma 3.** Under Assumption 1 and Assumption 2, $\exists N_{\max} \in \mathbb{N}$ such that for all $k \ge N_{\max}$ the condition $p^{k+1} \le \epsilon_{b\text{cl}}^k$ of Algorithm 2 is satisfied (i.e., we enter the “if condition”).

*Proof.* We split the proof in several cases.

* If we enter the “else condition” a finite number of times, the result holds.

* If we enter the “else condition” an infinite number of times, Lemma 1 ensures that each time we enter the “else”, there is a subsequent iteration for which we enter the “if”.

Therefore, we can without loss of generality assume that we enter the “else” at iteration $k$ for the $k$th time, and that we enter the “if” at iteration $k+1$.

In this setup (we enter an infinite number of times the “else”, $\mu^k \to 0$ and Lemma 2 applies. Therefore, we can also pick without loss of generality $k \ge K_\tau$ where $K_\tau \in \mathbb{N}$ is such that (8) holds (for a specific $(a, \tau)$ describing the geometry of the QP at hand).

In what follows, we consider this situation and show that it cannot happen (i.e., “else” is entered a finite number of times).

Since (QP) is feasible by assumption, it follows that $T_L^{-1}(0, 0) \ne \emptyset$. For $l \in [0, N]$ we denote by $(\bar{x}^{k+l}, \bar{z}^{k+l})$ the projection of $(x^{k+l}, z^{k+l})$ onto the set of solutions $T_L^{-1}(0, 0)$. As $\bar{x}^{k+N}$ is feasible, it follows that

$$\|[Cx^{k+N} - u]_+\|_2 = \|[Cx^{k+N} - u]_+ - [C\bar{x}^{k+N} - u]_+\|_2. \quad (21)$$

As $[.]_+$ is a non-expansive operator (as any projection operator), it follows that (21) can be upper bounded by

$$\begin{align}
& \|[Cx^{k+N} - u]_+\|_2 \le \|C(x^{k+N} - \bar{x}^{k+N})\|_2 \nonumber \\
& \le \|C\|_2 \|x^{k+N} - \bar{x}^{k+N}\|_2 \nonumber \\
& \le \|C\|_2 \left\| \begin{pmatrix} x^{k+N} - \bar{x}^{k+N} \\ z^{k+N} - \bar{z}^{k+N} \end{pmatrix} \right\|_2. \tag{22}
\end{align}$$

The following lines therefore focus on upper bounding the last term in different ways. First,

$$\begin{align}
& \left\| \begin{pmatrix} x^{k+N} - \bar{x}^{k+N} \\ z^{k+N} - \bar{z}^{k+N} \end{pmatrix} \right\|_2 \nonumber \\
& \le \left\| \begin{pmatrix} x^{k+N} \\ z^{k+N} \end{pmatrix} - \bar{P}_{\mu^k}(x^{k+N-1}, z^{k+N-1}) \right\|_2, \tag{23}
\end{align}$$

which follows from the definition of $(\bar{x}^{k+N}, \bar{z}^{k+N})$ as the projection of $(x^{k+N}, z^{k+N})$ and $\bar{P}_{\mu^k}(x^{k+N-1}, z^{k+N-1})$ corresponds to the projection of $P_{\mu^k}(x^{k+N-1}, z^{k+N-1})$ onto
this link between PROXQP and PPA, (i) we first recall PPA global convergence properties, and then (ii) show that in a finite number of iterations PROXQP is a fixed-step PPA.

When (QP) is feasible, the KKT conditions $0 \in T_L(x, z)$ forms a polyhedral variational inequality [6, Section 3D]. In such settings, if we consider a sequence $\{\mu^k\}_k$, bounded below by some $\mu^\infty > 0$, and $\{\eta^k\}_k$ some summable sequence, then the inexact proximal point iteration

$$ (x^{k+1}, z^{k+1}) \approx_{\eta^k} P_{\mu^k}(x^k, z^k), \quad (32) $$

with $\approx_{\eta^k}$ corresponding to

$$ \|(x^{k+1}, z^{k+1}) - P_{\mu^k}(x^k, z^k)\|_2 \le \eta^k, \quad (33) $$

is guaranteed to converge globally to some $(x^*, z^*) \in T_L^{-1}(0, 0)$ [3, Proposition 1.2].

Depending on the value of $k_{max}$, we distinguish two different cases to show that PROXQP is asymptotically equivalent to PPA. As we will see, it amounts to show PROXQP always enter the “if” condition in a finite number of iterations.

* If $k_{max} < +\infty$, then after $k_{max}$ number of iterations, PROXQP iterates always enter the “if” condition.

* Otherwise, under Assumption 1 and Assumption 2 Lemma (3) ensures that there exists some $N_{max} \in \mathbb{N}$, after which PROXQP enter only the “if” condition.

Hence, for $k \ge N \stackrel{\text{def}}{=} \min(k_{max}, N_{max})$, PROXQP always accepts the iterates $(x^{k+1}, \hat{z}^{k+1})$ from (10). Furthermore, for $l \ge 0$

$$ \mu^{N+l} = \mu^N, \\ \epsilon^{N+l} = \epsilon^k (\mu^N)^l. $$

Hence the iterates of Algorithm 2 amount to a fixed step PPA, namely for $k \ge N$

$$ (x^{k+1}, \hat{z}^{k+1}) \approx_{e\epsilon^k} P_{\mu^N}(x^k, z^k), $$

for some constant $e > 0$ which can be provided following the same strategy as detailed in (19). As $\{\epsilon^k\}_k$ is summable for $k \ge N$, it concludes our claim. $\square$

### F. Proof of Lemma 1

**Lemma 4.** Under Assumption 1 (existence of solution to (QP)) and Assumption 2 (bounded iterates), and with all parameters set as required in the inputs of Algorithm 2, $\exists K \in \mathbb{N}$, and $\mu \in \mathbb{R}$ such that $\forall k \ge K$, $\mu^k = \mu$. Hence, $\forall k \ge 0$, $p^{K+k} \le \epsilon_{bcl}^K(\mu^K)^{\beta_{bcl}k}$.

*Proof.* By Lemma 3, $\exists \mu \in \mathbb{R}$, $\exists K \in \mathbb{N}$ such that for all $k \ge K$, it holds that $p^k < \epsilon_{bcl}^k$ and $\mu^k = \mu$ is constant. $\square$

### REFERENCES

[1] A. Bambade, F. Schramm, S. El-Kazdadi, S. Caron, A. Taylor, and J. Carpentier, “PROXQP: an Efficient and Versatile Quadratic Programming Solver for Real-Time Robotics Applications and Beyond,” 2023. [Online]. Available: https://inria.hal.science/hal-04133055

[2] A. R. Conn, N. I. M. Gould, and P. Toint, “A globally convergent augmented lagrangian algorithm for optimization with general constraints and simple bounds,” *SIAM Journal on Numerical Analysis*, vol. 28, no. 2, pp. 545–572, 1991.

[3] F. J. Luque, “Asymptotic convergence analysis of the proximal point algorithm,” *SIAM Journal on Control and Optimization*, vol. 22, no. 2, pp. 277–293, 1984.

[4] R. T. Rockafellar, “Monotone operators and the proximal point algorithm,” *J. Control Optim.*, p. 877–898, 1976.

[5] E. K. Ryu and S. Boyd, “Primer on monotone operator methods,” *Appl. comput. math*, vol. 15, no. 1, pp. 3–43, 2016.

[6] A. L. Dontchev, R. T. Rockafellar, and R. T. Rockafellar, *Implicit functions and solution mappings: A view from variational analysis*. Springer, 2009, vol. 616.

[7] R. T. Rockafellar, *Convex analysis*, ser. Princeton Mathematical Series. Princeton, N. J.: Princeton University Press, 1970.

[8] D. Marchi, “On a primal-dual newton proximal method for convex quadratic programs,” *Computational Optimization and Applications*, vol. 76, pp. 451–467, 2021.