HUANet: Hard-Constrained Unrolled ADMM for Constrained Convex Optimization

1. Problem Statement

The paper addresses parametric constrained convex optimization, a class of problems where the goal is to minimize a convex objective function subject to equality and inequality constraints, with problem parameters varying across instances.

• Formulation:
  $$\min_{x} f_\lambda(x) \quad \text{s.t.} \quad A_\lambda x = b_\lambda, \quad C_\lambda x \leq d_\lambda$$
  where $\lambda$ represents problem parameters.
• Challenges:
  • Computational Efficiency: Traditional solvers (e.g., interior-point methods) require many iterations, creating a bottleneck for real-time applications, especially as problem dimensionality scales.
  • Feasibility: Solutions must strictly satisfy all constraints. Existing deep learning approaches often fail to guarantee this.
  • Optimality: Solutions must be near-optimal, not just feasible.
  • Limitations of Existing Methods:
    • End-to-End Surrogates: Treat constraints as soft penalties, failing to guarantee feasibility.
    • Predict-and-Correct: Improve feasibility but lack interpretability and structural connection to optimization theory.
    • Existing Unrolled ADMM: Typically treat constraints as soft penalties or focus only on unconstrained problems, lacking guarantees for general constrained cases.

2. Methodology: HUANet Architecture

The authors propose HUANet (Hard-Constrained Unrolled ADMM), a deep neural network that unrolls the iterations of the Alternating Direction Method of Multipliers (ADMM) into a trainable architecture.

A. Core Architecture

HUANet consists of $N$ sequential neural layers, where each layer $F_{\theta_p}$ corresponds to one ADMM iteration. The architecture is designed to approximate the primal update of ADMM while strictly enforcing constraints.

1. Hard-Constrained Neural Network (HNN):

   • MLP Component: A Multi-Layer Perceptron takes the current dual variables and problem parameters as input to predict an unconstrained estimate $(\bar{x}, \bar{s})$ of the primal and slack variables.
   • Correction Stage (Differentiable Projection): To enforce equality constraints ($A_\lambda x = b_\lambda$ and $C_\lambda x + s = d_\lambda$), the MLP output is passed through a differentiable correction stage. This stage projects the unconstrained estimate onto the affine subspace defined by the equality constraints.
   • Closed-Form Projection: The projection is computed analytically using the formula:
     $$\hat{y} = \bar{y} - E_\lambda^\top (E_\lambda E_\lambda^\top)^{-1} (E_\lambda \bar{y} - \eta_\lambda)$$
     This ensures that the output $\hat{y}$ satisfies equality constraints exactly (to machine precision) at every iteration.

2. ADMM Updates:

   • After the correction stage, the standard ADMM updates for the auxiliary variable ($w$) and dual variable ($v$) are applied.
   • The network is unrolled for $N$ steps during training, but inference can stop earlier or later depending on convergence needs.

B. Training Strategy: Self-Supervised Optimality

Unlike supervised learning that requires ground-truth optimal solutions (which are expensive to compute), HUANet uses a self-supervised loss function based on the Karush-Kuhn-Tucker (KKT) conditions.

• Loss Function Components:

  1. Terminal Objective ($h_\lambda$): Minimizes the objective function $f_\lambda(x)$ at the final layer.
  2. Inequality Penalty: Penalizes violations of inequality constraints ($C_\lambda x \leq d_\lambda$) at the final layer.
  3. KKT Residuals ($r_k$): A novel term that penalizes the violation of first-order optimality conditions (stationarity) at every unrolled layer.
     • The network includes a secondary MLP ($MLP_{\theta_d}$) to predict the Lagrange multipliers ($z$) for the primal subproblem.
     • The residual $r_k$ measures how well the predicted primal and dual variables satisfy the stationarity condition: $\nabla f + A^\top z + C^\top \beta = 0$.

• Advantage: This approach drives the network toward true optimality without needing labeled optimal solutions, making it scalable and data-efficient.

3. Key Contributions

1. Hard-Constrained Unrolling: Introduces a neural architecture that enforces equality constraints via a differentiable correction stage at every iteration, guaranteeing feasibility without soft penalties.
2. Optimality-Driven Training: Develops a self-supervised loss function incorporating KKT residuals and terminal objectives. This ensures the unrolled network converges to optimal solutions rather than just feasible ones, eliminating the need for ground-truth labels.
3. Dual Variable Prediction: Integrates a learnable network to predict Lagrange multipliers, enabling the enforcement of stationarity conditions during training.
4. Scalability: Demonstrates that the unrolled architecture significantly reduces computational complexity compared to iterative solvers, particularly in high-dimensional settings.

4. Experimental Results

The authors evaluated HUANet on three problem types: LASSO, Quadratic Programming (QP), and Entropy Maximization, comparing it against classical solvers (OSQP, Clarabel, SCS) and vanilla ADMM.

• Feasibility:
  • Equality Constraints: Satisfied exactly (machine precision, e.g., $10^{-15}$) due to the hard-constrained correction stage.
  • Inequality Constraints: Violations were minimal (e.g., $< 10^{-5}$), comparable to or better than state-of-the-art solvers.
• Optimality:
  • Achieved small optimality gaps (e.g., $< 0.2\%$ for QP, $< 0.01\%$ for LASSO in low dimensions).
• Speedup (Significance):
  • vs. Classical Solvers: HUANet achieved 7x to 44x speedups over OSQP and Clarabel in high-dimensional scenarios ($n_x=100$).
  • vs. Vanilla ADMM: The speedup was dramatic, ranging from 61x to 4700x depending on the problem and dimension.
  • Scalability: As problem dimension increased from 10 to 100, HUANet's solve time increased only slightly (e.g., 4x), whereas vanilla ADMM time increased by orders of magnitude (e.g., 100x to 1000x).

5. Significance and Conclusion

HUANet represents a significant advancement in Learning-to-Optimize (L2O) by bridging the gap between the interpretability of classical optimization and the speed of deep learning.

• Practical Impact: It enables real-time solution of large-scale constrained optimization problems in fields like robotics, power grids, and finance, where strict constraint satisfaction and low latency are critical.
• Theoretical Contribution: It proves that unrolled networks can be trained to satisfy hard constraints and optimality conditions simultaneously without relying on black-box data fitting.
• Future Work: The authors plan to extend the architecture to embed inequality constraints directly into the network (removing the need for post-correction) and apply the framework to non-convex problems.

In summary, HUANet offers a scalable, feasible, and optimal framework for parametric convex optimization, outperforming traditional solvers by orders of magnitude in high-dimensional settings while maintaining rigorous constraint satisfaction.