Computing exact $D$-optimal designs by mixed integer second-order cone programming

Abstract

Let the design of an experiment be represented by an $s$-dimensional vector $\mathbf{w}$ of weights with nonnegative components. Let the quality of $\mathbf{w}$ for the estimation of the parameters of the statistical model be measured by the criterion of $D$-optimality, defined as the $m$th root of the determinant of the information matrix $M(\mathbf{w})={\sum }_{i=1}^s{w}_i{A}_i{A}_i^T$, where $A_i,i=1,\dots ,s$ are known matrices with $m$ rows. In this paper, we show that the criterion of $D$-optimality is second-order cone representable. As a result, the method of second-order cone programming can be used to compute an approximate $D$-optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an exact $D$-optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second-order cone programming problems. Our results extend to the case of the criterion of $D_K$-optimality, which measures the quality of $\mathbf{w}$ for the estimation of a linear parameter subsystem defined by a full-rank coefficient matrix $K$. We prove that some other widely used criteria are also second-order cone representable, for instance, the criteria of $A$-, $A_K$-, $G$- and $I$-optimality. We present several numerical examples demonstrating the efficiency and general applicability of the proposed method. We show that in many cases the mixed integer second-order cone programming approach allows us to find a provably optimal exact design, while the standard heuristics systematically miss the optimum.

Published at http://dx.doi.org/10.1214/15-AOS1339 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Monotonic convergence of a general algorithm for computing optimal designs
• Computing exact $D$-optimal designs by mixed integer second-order cone programming
• D-optimal designs via a cocktail algorithm
• Improvements on removing non-optimal support points in D-optimum design algorithms

Cited by in corpus (16)

• Computing exact $D$-optimal designs by mixed integer second-order cone programming
• Robust Experimental Designs for Model Calibration
• Mixed-integer linear programming for computing optimal experimental designs
• Generation of point sets by convex optimization for interpolation in reproducing kernel Hilbert spaces
• Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees
• Heuristic construction of exact experimental designs under multiple resource constraints
• On optimal designs for non-regular models
• The Polytope of Optimal Approximate Designs: Extending the Selection of Informative Experiments
• Approximation Algorithms for D-optimal Design
• Scalable Algorithms for the Sparse Ridge Regression
• Approximate D-optimal Experimental Design with Simultaneous Size and Cost Constraints
• First-Order Methods for Optimal Experimental Design Problems with Bound Constraints
• Submodular maximization and its generalization through an intersection cut lens
• Removal of Redundant Candidate Points for the Exact D-Optimal Design Problem
• A Randomized Exchange Algorithm for Optimal Design of Multi-Response Experiments
• Design of Complex Experiments Using Mixed Integer Linear Programming