Computing Experiment-Constrained D-Optimal Designs
Aditya Pillai, Gabriel Ponte, Marcia Fampa, Jon Lee, Mohit Singh, Weijun Xie · 2024
Read Computing Experiment-Constrained D-Optimal Designs by Aditya Pillai, Gabriel Ponte, Marcia Fampa, Jon Lee, Mohit Singh, Weijun Xie (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01405.txt.
Description
Abstract In optimal experimental design, the objective is to select a limited set of experiments that maximizes information about unknown model parameters based on factor levels. This work addresses the generalized D-optimal design problem, allowing for nonlinear relationships in factor levels.
Catalog record
| CREATOR | Aditya Pillai, Gabriel Ponte, Marcia Fampa, Jon Lee, Mohit Singh, Weijun Xie |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01405
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computing Experiment-Constrained D-Optimal Designs Aditya Pillai, Gabriel Ponte, Marcia Fampa, Jon Lee, Mohit Singh, Weijun Xie Abstract In optimal experimental design, the objective is to select a limited set of experiments that maximizes information about unknown model parameters based on factor levels. This work addresses the generalized D-optimal design problem, allowing for nonlinear relationships in factor levels. We develop scalable algorithms suitable for cases where the number of candidate experiments grows exponentially with the factor dimension, focusing on both first- and second-order models under design constraints. Particularly, our approach integrates convex relaxation with pricing-based local search techniques, which can provide upper bounds and performance guarantees. Unlike traditional local search methods, such as the “Fedorov exchange” and its variants, our method effectively accommodates arbitrary side constraints in the design space. Furthermore, it yields both a feasible solution and an upper bound on the optimal value derived from the convex relaxation. Numerical results highlight the efficiency and scalability of our algorithms, demonstrating superior performance compared to the state-of-the-art commercial software, JMP . \NatBibNumeric keywords D -optimal design; experimental design; convex relaxation; local search; approximation algorithm; determinant maximization † † runningauthor: A. Pillai, G. Ponte, M. Fampa, J. Lee, M. Singh, W. Xie † † runningtitle: Large-Scale D -optimal Design † † authors: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, [email protected]. IOE Dept., University of Michigan and Federal University of Rio de Janeiro, [email protected] COPPE, Federal University of Rio de Janeiro, [email protected] IOE Dept., University of Michigan, Ann Arbor, MI, [email protected] H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, [email protected]. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, [email protected]. † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction. Optimal experimental design is a classical problem in statistics. The goal of optimal experimental design is to identify a limited number of experiments to obtain the maximum information about a vector of unknown model parameters in a given model based on levels of independent variables/factors. In this work, and as is common, we assume that the model is linear in the parameters. However, the model is often nonlinear in the factor levels. We focus on one of the most popular optimal design criteria, D-optimality. In D-optimal experimental design, under i.i.d. Gaussian noise, we aim to identify a set of experiments to minimize the generalized covariance of the least-squares parameter estimator. In other words, we seek to minimize the volume of the standard confidence ellipsoid for the parameter centered on the least-squares parameter estimate. This is equivalent to maximizing the (logarithm of the) determinant of the Fisher information matrix (see [ 27 ] for more details; also see [ 28 , 11 , 12 , 26 , 7 ] for history and more information). We let integer d\geq 1 denote the dimension of factors and let \bm{x}:=(x_{1},\ldots,x_{d})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}} represent a vector of factors. In our most general setting, we consider a model based on a list of p distinct monomials \mathcal{M}:=\{m_{1}(\bm{x}),\ldots m_{p}(\bm{x})\} in the variables. Specifically, y\approx\sum_{i=1}^{p}\theta_{i}m_{i}(\bm{x}), where “ \approx ” indicates that the model incorporates a zero-mean Gaussian noise. The model is linear in the parameter vector \bm{\theta}\in{\mathbb{R}}^{p} , and so, by choosing a set of experiments \bm{X}=\{\bm{x}^{1},\ldots,\bm{x}^{k}\} and their associated observations, y^{1},\ldots,y^{k} respectively, we can calculate the least-squares estimate \widehat{\theta}=\argmin_{\theta}\sum_{j=1}^{k}\sum_{i=1}^{p}\left(\theta_{i}m_{i}(\bm{x}^{j})-y^{j}\right)^{2} . The challenge, of course, is to choose the best experiments, \bm{X}=\{\bm{x}^{1},\ldots,\bm{x}^{k}\} . Following the convention, we assume that experiments can be repeated. For there to be a unique least-squares solution to the linear regression problem associated with a set of experiments (i.e., the model is “identifiable” given the experiments), we need a set of design points of rank p . Assuming that the model is identifiable, given a multi-set of experiments \bm{X} , the D-optimality criterion gives the value \log\det(\sum_{\bm{x}\in\bm{X}}\bm{p}(\bm{x})\bm{p}(\bm{x})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}}) , which we wish to maximize. Before continuing, it is useful to settle on some terminology. If the maximum degree of a monomial in \mathcal{M} is \ell , then we say that we have an \ell -th order model . In an \ell -th order model, if we have all possible monomials of maximum degree \ell , then we say that it is a full \ell -th order model . We refer to models that are not full as partial . In what follows, we will be mostly interested in full first-order models (having d+1 monomials), full second-order models (having \binom{d}{2}+d+1 monomials), and partial second-order models. The design point associated with an experiment \bm{x}\in\mathbb{R}^{d} is simply \bm{p}(\bm{x}):=(m_{1}(\bm{x}),\ldots,m_{p}(\bm{x}))^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}}\in\mathbb{Z}^{p} . That is, it is the vector of evaluations of each monomial on the experiment \bm{x} . We assume that we have a set of L\geq 2 levels \{0,1,\ldots,L-1\} , that are the possible values of the factors. So, without additional structural requirements, we have a universe of L^{d} possible experiments, one for each \bm{x}\in\{0,1\,\ldots,L-1\}^{d} . It is common for one to have L\geq\ell+1 for a full \ell -th order model. For example, to capture a second-order effect at least in one variable, we would need at least three levels (this is the motivation for many second-order designs in the literature that use three levels, such as the well-known Box-Behnken design; see [ 19 , Sec. 5.3.3.6.2] and [ 4 ] ). We note that modeling and algorithms associated with constrained design regions are a central topic in the design of experiments literature; see [ 6 , 18 , 3 ] for references. Specifically, we consider the constraints of form \bm{A}\bm{x}\leq\bm{b} , for \bm{x}\in\mathcal{Y} . So, we define our universe of allowable experiments as \mathcal{Y}:=\{\bm{x}\in\{0,1,\ldots,L-1\}^{d}~:~\bm{A}\bm{x}\leq\bm{b}\}. Finally, we impose a “budget restriction” on the size of \bm{X} , the chosen multi-set of experiments, to be k . With all of this, we are now ready to formally state our experiment-constrained D-Optimal design problem : \displaystyle\phi:=\max\left\{\log\det\left(\sum_{\bm{x}\in\mathcal{Y}}\lambda(\bm{x})\bm{p}(\bm{x})\bm{p}(\bm{x})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}}\right)~:~\sum_{\bm{x}\in\mathcal{Y}}\lambda(\bm{x})=k;~\lambda(\bm{x})\in\mathbb{Z}_{+}\,,\mbox{ for }\bm{x}\in\mathcal{Y}\right\}. (ECD-Opt) The solution selects the multi-set of experiments \bm{X} , by simply having \lambda(\bm{x}) copies of \bm{x} in \bm{X} . We can further associate matrices \bm{P} and \bm{S} where \bm{P} has a row \bm{p}(\bm{x}) for each \bm{x}\in\bm{X} and matrix \bm{S}=\bm{P}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}}\bm{P} . In this way, we have \bm{S}=\bm{P}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}}\bm{P}=\sum_{x\in\bm{X}}\bm{p}(\bm{x})\bm{p}(\bm{x})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}} , and we can rewrite the objective function as \log\det(\bm{S})=\log\det(\bm{P}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}}\bm{P}) . In what follows, we let the collection of feasible design points be \mathcal{P}:=\{\bm{p}(\bm{x})\in{\mathbb{R}}^{p}~:~\bm{x}\in\mathcal{Y}\}. Therefore, ECD-Opt is equivalent to \displaystyle\max\left\{\log\det\left(\sum_{v\in\mathcal{P}}\lambda(\bm{v})\bm{v}\bm{v}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\textstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptstyle\scriptscriptstyle\mathsf{T}$}}{\raisebox{0.0pt}{$\scriptscriptstyle\scriptscriptstyle\mathsf{T}$}}}\right)~:~\sum_{\bm{v}\in\mathcal{P}}\lambda(\bm{v})=k;~\lambda(\bm{v})\in\mathbb{Z}_{+}\,,\mbox{ for }\bm{v}\in\mathcal{P}\right\}. (1) The main computational challenge is that the set of vectors \mathcal{P} consists of exponentially many vectors in the dimension p , and in practice, may not be explicitly defined. As studied in the literature and available software, when the set of allowable experiments \mathcal{Y} is given explicitly, as a list, it is interesting to have linear constraints on the integer variable vector \bm{\lambda} , whereupon the associated D-optimal design problem has been referred to as CD-Opt (see [ 25 ] ). In this paper, set \mathcal{Y} is given by a set of allowable experiment vectors \bm{x} , described via a range of levels for each factor with optionally additional linear constraints. To distinguish it from CD-Opt, we