ProxSuite

ProxQP is a numerical optimization approach within ProxSuite designed to solve Quadratic Programming (QP) problems of the form:

$$\min_{x} , \frac{1}{2}x^{T}Hx+g^{T}x$$ $$\text{s.t.} , A x = b$$ $$\text{s.t.} , l \leq C x \leq u$$

Where:

• $x \in \mathbb{R}^n$ is the optimization variable.
• $H \in \mathcal{S}^n_+$ is a positive semidefinite matrix.
• $g \in \mathbb{R}^n$ is a vector.
• $A \in \mathbb{R}^{n_{\text{eq}} \times n}$ is the equality-constraint matrix.
• $C \in \mathbb{R}^{n_{\text{in}} \times n}$ is the inequality-constraint matrix.
• $b, l, u$ are the corresponding constraint vectors.

QPLayer is a component that enables using a Quadratic Program (QP) as a layer within standard machine learning architectures. It is interfaced with PyTorch and allows for parallelized calculus over CPUs.

Key capabilities include:

• Differentiating over parameters $\theta$ for both primal and dual solutions.
• Differentiating over Linear Programs (LPs).
• Learning structured architectures (e.g., learning elements of the constraint matrix $A$ while keeping $b$ fixed).

When benchmarking ProxQP against other solvers, use results.info.run_time (the sum of setup_time and solve_time).

ProxQP's timing breakdown is:

• setup_time: Measures model initialization and preconditioning (if activated).
• solve_time: Measures everything else, including the first matrix factorization.

Warning: Some solvers (like OSQP) include the first factorization in their setup_time. To ensure a fair comparison, always compare the total runtime (setup + solve) of ProxQP against the total runtime of the other solver.

By default, ProxQP stops based on primal and dual residuals (using the $L_ ext{inf}$ norm). However, satisfying residual criteria alone does not guarantee optimality. To ensure a stronger guarantee, you can enable the check_duality_gap option.

When check_duality_gap is True, the solver also checks the duality gap $r_g$ against absolute and relative thresholds (eps_duality_gap_abs and eps_duality_gap_rel).

Recommendation for thresholds: Because the duality gap scales with the square root of the problem dimension, it is numerically harder to achieve for large problems. A recommended setting for the absolute duality gap threshold is: $$\epsilon^{\text{gap}}{\text{abs}} = \epsilon{\text{abs}} \sqrt{\max(n, n_{\text{eq}}, n_{\text{ineq}})}$$

ProxQP provides both sparse and dense backends. Use the following heuristic to choose:

Use the Dense backend if your problem is:

1. Relatively small (less than a few thousand variables).
2. Relatively dense (sparsity ratio of matrices is greater than 0.1).

Sparsity ratio is calculated as: $$\text{sparsity}(A) = \frac{\text{nnz}(A)}{\text{number}{\text{row}}(A) * \text{number}{\text{col}}(A)}$$

By default, ProxQP checks convergence based on primal and dual residuals. However, checking residuals alone does not guarantee that the KKT conditions are fully satisfied.

To ensure a stronger guarantee of optimality, enable the check_duality_gap option in the settings. This includes the duality gap ($r_g$) in the stopping criterion, similar to the SCS solver.

Recommendation: Because the duality gap scales with the square root of the problem dimension, it is numerically harder to achieve than residual targets. A recommended setting for the absolute duality gap threshold is: $$\epsilon^{\text{gap}}{\text{abs}} = \epsilon{\text{abs}} \sqrt{\max(n, n_{\text{eq}}, n_{\text{ineq}})}$$

To speed up runtime in optimal control-like problems where the next problem is similar to the previous one, you can enable warm starting.

When this option is set, the solver warms starts the primal solution x, equality multiplier y, and inequality multiplier z with the values from the previous solve.

Note: Unlike the WARM_START_WITH_PREVIOUS_RESULT option, this specific warm start resets all other parameters (such as proximal step sizes and the full workspace/LDLT factorization) to their default values. This means a new factorization is performed, but it takes the z warm start into account for the active set.

At the first solve, x, y, and z are initialized to the zero vector.

The dense version of ProxQP offers two specialized backends. While the constructor uses a heuristic to choose automatically, you can specify one manually for better performance or accuracy:

• PrimalDualLDLT: Factorizes a regularized version of the KKT system. It provides high accuracy and stability. It is slower if the primal dimension ($n$) is significantly smaller than the number of constraints.
• PrimalLDLT: Factorizes the matrix $H+\rho I+\frac{1}{\mu_{eq}} A^\top A$ and uses rank-one updates. It is faster when the primal dimension is much smaller than the constraint dimensions, but it is less accurate than PrimalDualLDLT.

# Example: Specifying a backend in Python
# (Note: Actual syntax depends on the specific implementation of the constructor)
qp = ProxQP.dense(n, n_eq, n_in, backend='PrimalLDLT')