Multidimensional sum-up rounding for integer programming in optimal experimental design

• 成果类型: Article
• 署名作者: Yu, Jing; Anitescu, Mihai
• 署名单位: University of Chicago; United States Department of Energy (DOE); Argonne National Laboratory
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01421-z
• 发表日期: 2021
• 页码: 37-76

摘要

We present a numerical method for approximating the solution of convex integer programs stemming from optimal experimental design. The statistical setup consists of a Bayesian framework for linear inverse problems for which the direct relationship is described by a discretized integral equation. Specifically, we aim to find the optimal sensor placement from a set of candidate locations where data are collected with measurement error. The convex objective function is a measure of the uncertainty, described here by the trace or log-determinant of the posterior covariance matrix, for the discretized linear inverse problem solution. The resulting convex integer program is relaxed, producing a lower bound. An upper bound is obtained by extending the sum-up rounding approach to multiple dimensions. For this extension, we analyze its accuracy as a function of the discretization mesh size for a rectangular domain. We show asymptotic optimality of the integer solution defining the upper bound for different experimental design criteria (A- and D-optimal), by proving the convergence to zero of the gap between the upper and lower bounds as the mesh size goes to zero. The technique is illustrated on a two-dimensional gravity surveying problem for both A-optimal and D-optimal sensor placement where our designs yield better results compared with a thresholding rounding approach.