SOR-Unrolled Learning-to-Solve Method for Absolute Value Equations
摘要
The absolute value equation (AVE), which is equivalent to the linear complementarity problem and mixed integer programming, has wide applications. Determining a solution to the AVE is NP-hard, and many algorithms have been proposed. SOR-like iteration, which is designed based on fixed point iteration and has a simple form and good theoretical guarantee, is one of the state-of-the-art methods for solving the AVE. However, its performance heavily relies on complex parameter selection. In this paper, we utilize deep neural networks to avoid difficult parameter selection. Concretely, we propose the first deep unrolled neural network based on SOR-like iteration to solve the AVE. On the one hand, in theory, we verify the feasibility of approximating the solution to AVE by unrolling SOR-like iterations with neural networks. On the other hand, in practice, we propose a specialized network architecture called SOR-Net, which incorporates learnable parameters and nonlinear activation functions into a deep network, with computational layers unrolled from the SOR-like iterations. Furthermore, to efficiently obtain more accurate solutions and further leverage the strengths of neural networks, we design a two-stage framework. The first stage treats the sign prediction in the AVE as a binary classification task using SOR-Net, effectively reducing the original AVE to a standard linear equation system. Then, in the second stage, this system can be solved using traditional numerical algorithms with higher precision. Extensive numerical experiments validate the effectiveness and efficiency of our proposed approach.