We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An Entropy-Regularized ADMM For Binary Quadratic Programming.
- Authors
Liu, Haoming; Deng, Kangkang; Liu, Haoyang; Wen, Zaiwen
- Abstract
We propose an entropy regularized splitting model using low-rank factorization for solving binary quadratic programming with linear inequality constraints. Different from the semidefinite programming relaxation model, our model preserves the rank-one constraint and aims to find high quality rank-one solutions directly. The factorization transforms the variables into low-rank matrices, while the entropy term enforces the low-rank property of the splitting variable. A customized alternating direction method of multipliers is utilized to solve the proposed model. Specifically, our method uses the augmented Lagrangian function to deal with inequality constraints, and solves one subproblem on the oblique manifold by a regularized Newton method. Numerical results on the multiple-input multiple-output detection problem, the maxcut problem and the quadratic 0 - 1 problem indicate that our proposed algorithm has advantage over the SDP methods.
- Subjects
LINEAR programming; SEMIDEFINITE programming; QUADRATIC programming; LOW-rank matrices; LAGRANGIAN functions; NEWTON-Raphson method; MULTIPLIERS (Mathematical analysis)
- Publication
Journal of Global Optimization, 2023, Vol 87, Issue 2-4, p447
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-022-01144-0