D-Optimal Data Fusion: Exact and Approximation Algorithms
D-Optimal Data Fusion: Exact and Approximation Algorithms
复制标题
DOI：
10.1287/ijoc.2022.0235
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Yongchun Li;M. Fampa;Jon Lee;Feng Qiu;Weijun Xie;Rui Yao
中科院分区：
文献类型：
--
作者：
Yongchun Li;M. Fampa;Jon Lee;Feng Qiu;Weijun Xie;Rui Yao
我们研究了 D 最优数据融合（DDF）问题，其目的是在给定现有的 Fisher 信息矩阵的情况下选择新的数据点，从而最大化整个 Fisher 信息矩阵的行列式的对数。我们证明 DDF 问题是 NP 难问题，并且没有常数因子多项式时间逼近算法，除非 P = NP。因此，为了有效地解决DDF问题，我们提出了两个凸整数规划公式并研究了它们相应的互补问题和拉格朗日对偶问题。利用两个提出的凸整数规划公式中目标函数的凹性，我们设计了一种精确的算法，旨在最优地解决 DDF 问题。我们进一步推导了一系列子模有效不等式和最优割，可以显着提高算法性能。我们还开发可扩展的随机采样和本地搜索算法，并具有可证明的性能保证。最后，考虑到现有的传统传感器，我们使用现代电网新相量测量单元放置问题的真实数据来测试我们的算法。我们的数值研究证明了我们精确算法的效率以及我们近似算法的可扩展性和高质量输出。历史：被离散算法设计与分析领域编辑 Andrea Lodi 接受。资金来源：Y. Li 和 W. Xie 得到了土木、机械和制造创新司 [Grant 2046414] 以及计算和通信基础司 [Grant 2246417] 的部分支持。 J. Lee 得到了空军科学研究办公室的部分支持 [拨款 FA9550-19-1-0175 和 FA9550-22-1-0172]。 M. Fampa 得到了 Conselho Nacional de Desenvolvimento Científico e Tecnológico [赠款 305444/2019-0 和 434683/2018-3] 的部分支持。补充材料：电子伴侣可在 https://doi.org/10.1287/ijoc.2022.0235 上获取。
We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. Leveraging the concavity of the objective functions in the two proposed convex integer-programming formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Y. Li and W. Xie were supported in part by Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046414] and Division of Computing and Communication Foundations [Grant 2246417]. J. Lee was supported in part by Air Force Office of Scientific Research [Grants FA9550-19-1-0175 and FA9550-22-1-0172]. M. Fampa was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 305444/2019-0 and 434683/2018-3]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.0235 .