I-ADMM-LSTM: A Learning-Based Inexact ADMM for Solving Quadratic Programs

This represitory is an implementation of the paper: A Learning-Based Inexact ADMM for Solving Quadratic Programs.

Introduction

Quadratic programs (QPs) constitute a fundamental class of constrained optimization problems with broad applications spanning multiple disciplines, including finance, engineering, and machine learning. The development of efficient and reliable algorithms for solving QPs continues to be an important research direction due to their widespread utility. This paper focuses on solving the following convex quadratic program:

$$ \begin{aligned} &\underset{x\in\mathbb{R}^n}{\text{min}} && \frac{1}{2} x^{\top} Q x + p^{\top} x \\ & \text{s.t.} && l \leq A x \leq u, \end{aligned} $$

where the optimization variable $x \in \mathbb{R}^n$ minimizes a quadratic objective function characterized by a positive semidefinite matrix $Q \in \mathbb{S}^n_+$ and a linear term $p \in \mathbb{R}^n$. The problem constraints are linear inequalities defined by the matrix $A \in \mathbb{R}^{m \times n}$, with each constraint $i = 1,...,m$ having associated lower and upper bounds $l_i \in \mathbb{R} \cup {-\infty}$ and $u_i \in \mathbb{R} \cup {+\infty}$, respectively. The alternating direction method of multipliers (ADMM) denotes as a preeminent first order method for addressing QPs. The alternating direction method of multipliers (ADMM) has emerged as a preeminent first-order methodology for solving QPs. OSQP represents a canonical ADMM-based solver specifically designed for QPs. To further reduce the computational overhead associated with matrix factorizations in OSQP iterations, we propose employing a single Long Short-Term Memory (LSTM) cell to obtain inexact solutions to the subproblems, thereby introducing a novel framework termed I-ADMM-LSTM. Building upon OSQP's native update procedures, our model is trained using the following unsupervised loss function based on primal-dual residuals:

$$ \begin{aligned} \min_{\theta} \frac{1}{|\mathcal{B}|} \sum_{B \in \mathcal{B}}\left(\frac{1}{K} \sum_{k=1}^{K} \left||A x^k - z^k\right||+\left||Q x^k + p + A^\top y^k\right||\right)_{B}, \end{aligned} $$

where ${(x^1, z^1, y^1),...,(x^K, z^K, y^K)}$ denotes the sequence of iterates generated by I-ADMM-LSTM, and ( \mathcal{B} ) represents a dataset comprising identically distributed convex quadratic programs.

Software dependencies

python=3.10
pytorch=1.13.1 
gurobi=10.0.3
osqp=0.6.3

Running experiments

To generate a convex QP dataset with 1000 variables, 500 inequality constraints, and 500 equality constraints, run:

python generate_data.py --config ./configs/Generate_Data.yaml --prob_type QP --num_var 1000 --num_ineq 500 --num_eq 500

For training phase, you can run following command:

python main.py --config ./configs/QP.yaml --prob_type QP --outer_T 100 --truncated_length 100 --hidden_dim 800 --eq_tol 0.2 --ineq_tol 0.2 --scaling

Our model will be stored at ./results/lstm/params/QP_1000_500_500_100_800.pth. During the testing phase, you can run the following command to obtain our experimental results:

python main.py --config ./configs/QP.yaml --prob_type QP --outer_T 100 --truncated_length 100 --hidden_dim 800 --eq_tol 0.2 --ineq_tol 0.2 --scaling --test --test_outer_T 100 --save_sol