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的版本大大优于现有方法,在中高维度和高维度问题上找到雌球体边界之间的距离。

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
52+阅读 · 2020年9月7日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
159+阅读 · 2020年1月16日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Meta Learning for Causal Direction
Arxiv
5+阅读 · 2020年7月6日
Arxiv
4+阅读 · 2020年1月17日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员