An ADMM based method for underdetermined box-constrained integer least squares problems

Abstract

To solve underdetermined box-constrained integer least squares (UBILS) problems, we propose an integer-constrained alternating direction method of multipliers (IADMM), which can be much more accurate than the ADMM method. To guarantee to find the optimal solution, then we incorporate IADMM to DTS, a tree search method, to make the latter more efficient. Numerical tests show that the combined method IADMM-DTS can be much faster than the original DTS method. Finally, we apply the combined method to a practical communication problem. Numerical results indicate that IADMM-DTS typically performs better than the commercial solvers CPLEX and MOSEK in terms of both efficiency and accuracy, and it can be used as an alternative to the commercial solver Gurobi for UBILS problems.

Keywords:

• Integer parameter estimation
• underdetermined integer least squares
• box constraints
• alternating direction method of multipliers
• enumeration

AMS CLASSIFICATIONS:

• 90C10
• 90C59
• 90C90
• 62F10
• 62H12
• 62P30
• 94A13

Acknowledgments

We are very grateful to the referees for their detailed valuable comments and suggestions which helped us to improve the paper significantly.

Disclosure statement

The authors report there are no competing interests to declare

Data availability statements

All data generated or analyzed during this study are included in this article and [31].

Additional information

Funding

The research of this work was supported by NSERC of Canada grant RGPIN-2017-05138.

Notes on contributors

Xiao-Wen Chang

Prof. Xiao-Wen Chang is with School of Computer Science, McGill University. He has published about 70 journal papers and 40 conferenced papers in matrix computations, optimization, global navigation satellite systems, communications, information theory, and machine learning.

Tianchi Ma

Mr. Tianchi Ma is currently a software developer in Google Montreal.