Convergence-Guaranteed Algorithms for l1/2-Regularized Quadratic Programs with Assignment Constraints
Authors
Lijun Xie
Ran Gu
Xin Liu
Abstract
This paper addresses a quadratic problem with assignment constraints, an NP-hard combinatorial optimization problem arisen from facility location, multiple-input multiple-output detection, and maximum mean discrepancy calculation et al. The discrete nature of the constraints precludes the use of continuous optimization algorithms. Therefore, we begin by relaxing the binary constraints into continuous box constraints and incorporate an l1/2 regularization term to drive the relaxed variables toward binary values. We prove that when the regularization parameter is larger than a threshold, the regularized problem is equivalent to the original problem: they share identical local and global minima, and all Karush-Kuhn-Tucker points of the regularized problem are feasible assignment matrices. To solve the regularized problem approximately and efficiently, we adopt the variable splitting technique, and solve it using the alternating direction method of multipliers (ADMM) framework, in which all subproblems admit closed-form solutions. Detailed theoretical analysis confirms the algorithm's convergence, and finite-step termination under certain conditions. Finally, the algorithm is validated on various numerical tests.
