HPR-QP: A GPU Solver for Convex Composite Quadratic Programming in Julia

HPR-QP: A dual Halpern Peaceman–Rachford (HPR) method for solving large-scale convex composite quadratic programming (CCQP).

---

🎉 What's New in v0.1.1

This version represents a major architectural overhaul with significant improvements:

1. Unified Architecture

• Single codebase for all problem types (standard QP, QAP, LASSO)
• Modular Q operator system for extensibility: easily add custom problem types

2. CPU & GPU Support

• Full CPU implementation in addition to GPU acceleration
• Automatic device selection via use_gpu parameter

3. JuMP Integration

• Native JuMP/MathOptInterface (MOI) support for easy modeling
• Use HPR-QP directly as a JuMP optimizer

4. Warm-Start Capability

• Initialize via initial_x and initial_y parameters
• Resume optimization from previous (auto-saved) solutions

5. Auto-Save Feature

• Automatically save best solution during optimization (auto_save=true)
• Resume from saved states for long-running problems

---

CCQP Problem Formulation

$$ \begin{array}{ll} \underset{x \in \mathbb{R}^n}{\min} \quad \frac{1}{2}\langle x,Qx \rangle + \langle c, x \rangle +\phi(x)\\ \text{s.t.} \quad \quad \quad \quad \quad l \leq A x \leq u, \end{array} $$

• $Q$ is a positive semidefinite self-adjoint linear operator;
• $Q$'s matrix representation may not be computable in large-scale instances, such as QAP relaxation and LASSO problems;
• $\phi$ is a proper closed convex function.

---

Getting Started

Prerequisites

Before using HPR-QP, make sure the following dependencies are installed:

• Julia (Recommended version: 1.10.4)
• CUDA (Required for GPU acceleration; install the appropriate version for your GPU and Julia)
• Required Julia packages

To install the required Julia packages and build the HPR-QP environment, run:

julia --project -e 'using Pkg; Pkg.instantiate()'

To verify that CUDA is properly installed and working with Julia, run:

using CUDA
CUDA.versioninfo()

---

Usage 1: Test Instances in MPS (MAT for QAP and LASSO) Format

Setting Data and Result Paths

Before running the scripts, please modify run_single_file.jl or run_dataset.jl in the demo directory to specify the data path and result path according to your setup.

Running a Single Instance

To test the script on a single instance:

julia --project demo/run_single_file.jl

Running All Instances in a Directory

To process all files in a directory:

julia --project demo/run_dataset.jl

Note

QAP Instances:
The .mat file for QAP should include the matrices $A$, $B$, $S$, and $T$.
For details, refer to Section 4.5 of the paper.
See HPR-QP_QAP_LASSO/demo/demo_QAP.jl for an example of generating such files.

LASSO Instances:
The .mat file for LASSO should contain the matrix $A$, vector $b$.

---

Usage 2: Define Your CQP Model in Julia Scripts

Example 1: Build and Export a CQP Model Using JuMP

This example demonstrates how to construct a CQP model using the JuMP modeling language in Julia and export it to MPS format for use with the HPR-QP solver.

julia --project demo/demo_JuMP.jl

The script:

• Builds a CQP model.
• Uses HPR-QP to solve the CQP instance.

Remark: If the model may be infeasible or unbounded, you can use HiGHS to check it.

using JuMP, HiGHS
## read a model from file (or create in other ways)
mps_file_path = "xxx" # your file path
model = read_from_file(mps_file_path)
## set HiGHS as the optimizer
set_optimizer(model, HiGHS.Optimizer)
## solve it
optimize!(model)

---

Example 2: Define a CQP Instance Directly in Julia

This example demonstrates how to construct and solve a CQP problem directly in Julia without relying on JuMP.

julia --project demo/demo_QAbc.jl

---

Example 3: Generate a Random LASSO Instance in Julia

This example demonstrates how to construct and solve a random LASSO instance.

julia --project demo/demo_LASSO.jl

---

Note on First-Time Execution Performance

You may notice that solving a single instance — or the first instance in a dataset — appears slow. This is due to Julia’s Just-In-Time (JIT) compilation, which compiles code on first execution.

💡 Tip for Better Performance:
To reduce repeated compilation overhead, it’s recommended to run scripts from an IDE like VS Code or the Julia REPL in the terminal.

Start Julia REPL with the project environment:

julia --project

Then, at the Julia REPL, run demo/demo_QAbc.jl (or other scripts):

include("demo/demo_QAbc.jl")

CAUTION:
If you encounter the error message:
Error: Error during loading of extension AtomixCUDAExt of Atomix, use Base.retry_load_extensions() to retry.

Don’t panic — this is usually a transient issue. Simply wait a few moments; the extension typically loads successfully on its own.

---

Parameters

Below is a list of the parameters in HPR-QP along with their default values and usage:

Parameter	Default Value	Description
stoptol	1e-6	Stopping tolerance for convergence checks.
sigma	-1 (auto)	Initial value of the σ parameter used in the algorithm.
max_iter	typemax(Int32)	Maximum number of iterations allowed.
sigma_fixed	false	Whether σ is fixed throughout the optimization process.
time_limit	3600.0	Maximum allowed runtime (seconds) for the algorithm.
eig_factor	1.05	Factor used to scale the maximum eigenvalue estimation.
check_iter	100	Frequency (in iterations) to check for convergence or perform other checks.
warm_up	false	Determines if a warm-up phase is performed before main execution.
spmv_mode_Q	"auto"	Mode for Q matrix-vector multiplication (e.g., "auto", "CUSPARSE", "customized", "operator").
spmv_mode_A	"auto"	Mode for A matrix-vector multiplication (e.g., "auto", "CUSPARSE", "customized").
print_frequency	-1 (auto)	Frequency (in iterations) for printing progress or logging information.
device_number	0	GPU device number (e.g., 0, 1, 2, 3).
use_Ruiz_scaling	true	Whether to apply Ruiz scaling to the problem data.
use_bc_scaling	false	Whether to apply bc scaling. (For QAP and LASSO, only this scaling is applicable)
use_l2_scaling	false	Whether to apply L2-norm based scaling.
use_Pock_Chambolle_scaling	true	Whether to apply Pock-Chambolle scaling to the problem data.
problem_type	"QP"	Type of problem being solved (e.g., "QP", "LASSO", "QAP").
lambda	0.0	Regularization parameter for LASSO problems.
initial_x	nothing	Initial primal solution for warm-start.
initial_y	nothing	Initial dual solution for warm-start.
auto_save	false	Automatically save best x, y, z, w, and sigma during optimization.
save_filename	"hprqp_autosave.h5"	Filename for auto-save HDF5 file.
verbose	true	Enable verbose output during optimization.
use_gpu	true	Whether to use GPU acceleration (requires CUDA).

---

Result Explanation

After solving an instance, you can access the result variables as shown below:

# Example from /demo/demo_QAbc.jl
println("Objective value: ", result.primal_obj)
println("x1 = ", result.x[1])
println("x2 = ", result.x[2])

Category	Variable	Description
Iteration Counts	iter	Total number of iterations performed by the algorithm.
	iter_4	Number of iterations required to achieve an accuracy of 1e-4.
	iter_6	Number of iterations required to achieve an accuracy of 1e-6.
Time Metrics	time	Total time in seconds taken by the algorithm.
	time_4	Time in seconds taken to achieve an accuracy of 1e-4.
	time_6	Time in seconds taken to achieve an accuracy of 1e-6.
	power_time	Time in seconds used by the power method.
Objective Values	primal_obj	The primal objective value obtained.
	gap	The gap between the primal and dual objective values.
Residuals	residuals	Relative residuals of the primal feasibility, dual feasibility, and duality gap.
Algorithm Status	status	The final status of the algorithm: - OPTIMAL: Found optimal solution - MAX_ITER: Max iterations reached - TIME_LIMIT: Time limit reached
Solution Vectors	x	The final solution vector x.
	y	The final solution vector y.
	z	The final solution vector z.
	w	The final solution vector w.

---

Citation

@article{chen2025hpr,
  title={HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming},
  author={Chen, Kaihuang and Sun, Defeng and Yuan, Yancheng and Zhang, Guojun and Zhao, Xinyuan},
  journal={arXiv preprint arXiv:2507.02470},
  year={2025}
}