A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments

Abstract

We propose a class of subspace ascent methods for computing optimal approximate designs that covers existing algorithms as well as new and more efficient ones. Within this class of methods, we construct a simple, randomized exchange algorithm (REX). Numerical comparisons suggest that the performance of REX is comparable or superior to that of state-of-the-art methods across a broad range of problem structures and sizes. We focus on the most commonly used criterion of D-optimality, which also has applications beyond experimental design, such as the construction of the minimum-volume ellipsoid containing a given set of data points. For D-optimality, we prove that the proposed algorithm converges to the optimum. We also provide formulas for the optimal exchange of weights in the case of the criterion of A-optimality, which enable one to use REX and some other algorithms for computing A-optimal and I-optimal designs. Supplementary materials for this article are available online.

Keywords:

• A-optimality
• Convex optimization
• D-optimality
• I-optimality
• Minimum-volume enclosing ellipsoid
• Optimal approximate designs of experiments

Acknowledgments

The last author acknowledges support through the KAUST baseline research funding scheme. We are also grateful to Valerii Fedorov, Anatoly Zhigljavsky, Luc Pronzato, Bernhard Spangl, Samuel Rosa and two anonymous referees for insightful comments on the first version of this article.

Additional information

Funding

The work of the first two authors was supported by Grant Number 1/0521/16 from the Slovak Scientific Grant Agency (VEGA).