Convergence-Guaranteed Algorithms for l1/2-Regularized Quadratic Programs with Assignment Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909957750784000 |
|---|---|
| author | Xie, Lijun Gu, Ran Liu, Xin |
| author_facet | Xie, Lijun Gu, Ran Liu, Xin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11429 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence-Guaranteed Algorithms for l1/2-Regularized Quadratic Programs with Assignment Constraints Xie, Lijun Gu, Ran Liu, Xin Optimization and Control 90C26, 90C30, 65K05 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. |
| title | Convergence-Guaranteed Algorithms for l1/2-Regularized Quadratic Programs with Assignment Constraints |
| topic | Optimization and Control 90C26, 90C30, 65K05 |
| url | https://arxiv.org/abs/2512.11429 |