论文标题
乘数的交替方向方法，用于查找椭圆形之间的距离
The Alternating Direction Method of Multipliers for Finding the Distance between Ellipsoids
论文作者
论文摘要
我们研究了乘数的交替方向方法（ADMM）的几个版本，以解决凸的问题，即找到两个椭圆形之间的距离和发现两个椭圆形边界之间距离的非凸问题。在凸情况下，我们介绍了有或没有自动惩罚更新的ADMM，并通过数值实验对各种维度的问题进行了证明，我们的方法明显优于所有其他现有方法，以查找椭球之间的距离。在非convex情况下，我们提出了一个启发式规则，用于更新惩罚参数和启发式重新启动程序（算法第二运行的新起点的启发式选择）。通过基于KKT最佳条件的全局方法，通过数值验证重新启动过程。关于各种测试问题的数值实验的结果表明，此过程始终允许在非凸情况下找到全球最佳解决方案。此外，数值实验还表明，我们的ADMM版本显着胜过现有的方法，即在中等和高维问题上找到椭球之间的距离之间的距离。
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.
