21.2 Notes 254
Geometric interpretation
There is a geometric interpretation of theD-optimal design problem. Letπbe a
D-optimal design forAandV=
∑
a∈Aπ(a)aa
>and
E=
{
x∈Rd:‖x‖^2 V− 1 ≤d
}
,
which is a centered ellipsoid. By Theorem 21.1, it holds thatA⊂Ewith the core
set lying on the boundary (see Fig. 21.1). As you might guess from the figure,
the ellipsoidEis the minimum volume centered ellipsoid containingA. This is
known to be unique and the optimization problem that characterizes it is in fact
the dual of the log determinant problem that determines theD-optimal design.
Figure 21.1The minimum volume centered ellipsoid containing a point cloud. The points
on the boundary are the core set. The ellipse isE={x:‖x‖^2 V(π)− 1 =d}whereπis an
optimal design.
21.2 Notes
1 The letter ‘d’ in D-optimal design comes from the determinant in the objective.
The ‘g’ in G-optimal design stands for ‘globally optimal’. The names were coined
by Kiefer and Wolfowitz, though both problems appeared in the literature
before them.
2 In applications we seldom need an exact solution to the design problem. Finding
a distributionπsuch thatg(π)≤(1 +ε)g(π∗) will increase the regret of our
algorithms by a factor of just (1 +ε)^1 /^2.
3 The computation of an optimal design for finite action sets is a convex problem
for which there are numerous efficient approximation algorithms. The Frank-
Wolfe algorithm is one such algorithm, which can be used to find a near-optimal
solution for modestly sized problems. The algorithm starts with an initialπ 0
and updates according to
πk+1(a) = (1−γk)πk(a) +γkI{ak=a}, (21.7)
