分布式约束优化问题主要算法完备性反例

筑波大学的研究人员对异步分布式优化 (ADOPT) 及其后续算法的关键属性提出了反例。ADOPT 是解决分布式约束优化问题的著名算法。

该团队证明，这些算法不一定保证关键属性，即终止性和最优性。此外，他们提出了 ADOPT 的修改版本来保证这些属性。该研究发表在《人工智能》杂志上。

分布式约束优化问题对于协作多智能体系统建模至关重要。ADOPT算法被认为有两个重要的性质：终止性，即算法在有限时间内终止;最优性，即算法终止时总是获得最优解。这些属性被认为适用于基于 ADOPT 的后续算法。

本研究提出了 ADOPT 及其后续算法的终止和最优性的反例。这意味着为 ADOPT 及其后续算法给出的证明是不正确的，并且存在算法不终止或以次优解决方案终止的可能性。

此外，研究人员还确定了 ADOPT 中存在此类反例的原因，并提出了一种纠正这些反例的算法。此外，他们还证明了ADOPT修改版本的终止性和最优性。

通过应用ADOPT的修改版本，可以防止ADOPT及其后续算法的失败，并且基于这些算法的系统的可靠性有望得到提高。