Centering ADMM for the Semidefinite Relaxation of the QAP
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911748201644032 |
|---|---|
| author | Kanoh, Shin-ichi Yoshise, Akiko |
| author_facet | Kanoh, Shin-ichi Yoshise, Akiko |
| contents | We propose a new method for solving the semidefinite (SD) relaxation of the quadratic assignment problem (QAP), called Centering ADMM. Centering ADMM is an alternating direction method of multipliers (ADMM) combining the centering steps used in the interior-point method. The first stage of Centering ADMM updates the iterate so that it approaches the central path by incorporating a barrier function term into the objective function, as in the interior-point method. If the current iterate is sufficiently close to the central path with a sufficiently small value of the barrier parameter, the method switches to the standard version of ADMM. We show that Centering ADMM (not employing a dynamic update of the penalty parameter) has global convergence properties. To observe the effect of the centering steps, we conducted numerical experiments with SD relaxation problems of instances in QAPLIB. The results demonstrate that the centering steps are quite efficient for some classes of instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2001_05739 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Centering ADMM for the Semidefinite Relaxation of the QAP Kanoh, Shin-ichi Yoshise, Akiko Optimization and Control We propose a new method for solving the semidefinite (SD) relaxation of the quadratic assignment problem (QAP), called Centering ADMM. Centering ADMM is an alternating direction method of multipliers (ADMM) combining the centering steps used in the interior-point method. The first stage of Centering ADMM updates the iterate so that it approaches the central path by incorporating a barrier function term into the objective function, as in the interior-point method. If the current iterate is sufficiently close to the central path with a sufficiently small value of the barrier parameter, the method switches to the standard version of ADMM. We show that Centering ADMM (not employing a dynamic update of the penalty parameter) has global convergence properties. To observe the effect of the centering steps, we conducted numerical experiments with SD relaxation problems of instances in QAPLIB. The results demonstrate that the centering steps are quite efficient for some classes of instances. |
| title | Centering ADMM for the Semidefinite Relaxation of the QAP |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2001.05739 |