We study several versions of the alternating direction method of multipliers (ADMM) for solving the convex problem of finding the distance between two ellipsoids and the nonconvex problem of finding the distance between the boundaries of two ellipsoids. In the convex case we present the ADMM with and without automatic penalty updates and demonstrate via numerical experiments on problems of various dimensions that our methods significantly outperform all other existing methods for finding the distance between ellipsoids. In the nonconvex case we propose a heuristic rule for updating the penalty parameter and a heuristic restarting procedure (a heuristic choice of a new starting for point for the second run of the algorithm). The restarting procedure was verified numerically with the use of a global method based on KKT optimality conditions. The results of numerical experiments on various test problems showed that this procedure always allows one to find a globally optimal solution in the nonconvex case. Furthermore, the numerical experiments also demonstrated that our version of the ADMM significantly outperforms existing methods for finding the distance between the boundaries of ellipsoids on problems of moderate and high dimensions.
翻译:我们研究了多种倍数交替方向方法的几种版本,以解决在找到两个椭球体之间的距离和找到两个椭球体边界之间的距离这一非曲线问题之间的偏移方向问题。在Convex案中,我们向ADMM提供了自动罚款更新,而且没有自动罚款更新,并通过数字实验表明,我们的方法大大优于所有其他现有的寻找雌球体之间距离的方法。在非曲线案中,我们提出了一个更新惩罚参数的超常规则,并提出了一个超常的重新启动程序(对算法第二次运行的点进行新的起点选择的超常选择 ) 。在使用基于KKT的最佳性条件的全球方法时,对重新启动程序进行了数字核查。对各种测试问题进行的数字实验的结果显示,这一程序总能使人们在非碳球体案例中找到一个全球最佳的解决办法。此外,数字实验还表明,我们采用的ADMMMy的版本大大优于现有方法,在中高维度和高维度问题上找到雌球体边界之间的距离。