论文标题
以QAP的半限定放松为中心的ADMM
Centering ADMM for the Semidefinite Relaxation of the QAP
论文作者
论文摘要
我们提出了一种解决二次分配问题（QAP）的半芬矿（SD）放松的新方法，称为中心ADMM。集中ADMM是乘数的交替方向方法（ADMM），结合了内点方法中使用的中心步骤。居中的第一阶段ADMM更新迭代，从而通过将屏障函数项纳入目标函数来接近中心路径，如内点法所示。如果电流迭代足够靠近屏障参数值足够小的中心路径，则该方法将切换到ADMM的标准版本。我们表明，居中（不使用惩罚参数的动态更新）具有全球收敛属性。为了观察中心步骤的效果，我们在Qaplib中使用了实例的SD松弛问题进行了数值实验。结果表明，对于某些类别的实例，中心步骤非常有效。
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.
