序贯最大最小距离设计的空间填充性*

滕一阳，武 赟，熊世峰†，杨建奎

(1 北京邮电大学理学院， 北京 100876； 2 中国科学院数学与系统科学研究院， 北京 100190)

s.t.x1,…,xn∈[0,1]d,d∈Z+的解，其中‖·‖代表欧式距离[2]。 最大最小距离设计也可以做成序贯类型[19]，即按照最小距离准则一个个地增加试验点，这样就可以用较少的试验点得出结论，也可避免盲目加大样本数而造成浪费。 文献[6]给出了其具体的定义。 如今，已有不少文献讨论过最大最小距离设计的性质和构造，如文献[10-18]，但目前还没有文章对序贯最大最小距离设计的性质进行讨论。 本文将讨论序贯最大最小距离设计的空间填充性质。 证明序贯最大最小距离设计满足最基本的空间填充性，即随着样本量的增大，该设计在试验区域内具有稠密性，可以任意逼近试验区域内的任意一个点。

1 构造序贯最大最小距离设计

在[0,1]d,d∈Z+中，按如下规则取点：使新取的点到所有已取点的最小距离最大化。 引入下列记号表示：

记前n步取的点分别为s1,s2,…,sn，Sn={s1,s2,…,sn} 为前n步取点的点集，

1)记任意两点x,y∈[0,1]d间的距离为d(x,y)=‖x-y‖2。

2)记任意一点x∈[0,1]d到已选点集合Sn

按上述规则，在[0,1]2中，依次规定取点个数画图。

进入21世纪以来，山东聊城历届市委、市政府紧紧抓住发展机遇，挖掘水的内涵，做足水的文章，努力打造生产发展、生态良好的优美环境，为改善聊城人民居住环境条件，提高城市竞争力，实现经济社会快速发展，发挥了重要作用。

图1中，当在[0,1]2中第1次取点时，因为此时[0,1]2中不存在点，规定取的第1个点在正方形的中心。接下来就可以按照序贯最大最小距离设计在空间中依次取点。 第2次取点时，有4个点同时满足规则，它们在正方形的4个顶点处。可以看出，按序贯最大最小距离设计取点，可以将[0,1]2逐步填充。

图1 [0,1]2中不存在点时按序贯最大最小距离设计取点Fig.1 Taking points by sequential maximin distance designs when there is no point in [0,1]2

图2 中，一开始[0,1]2中已经取了3个点，这3个点用三角形表示，再按序贯最大最小距离设计取点，取得的点用圆形表示。 可以看出，这种情况下序贯最大最小距离设计也可以对[0,1]2进行逐步填充。

2 主要结果及证明

从第1节可以看出，随着样本量的增加， 序贯最大最小距离设计可以对2维试验区域进行逐步填充。 下面对任意的维数严格证明这一性质。

定理2.1在[0,1]d,d∈Z+中，按序贯最大最小距离设计取点，设所取得的点依次为s1,s2,…,sn，则对任意ε>0，任意x∈[0,1]d，都存在一个N>0，当n>N时，有d(x,Sn)<ε。

证明反证方向为：存在ε>0，存在一个x0∈[0,1]d，对任意的N1>0，都存在一个N2>N1，有d(x0,SN2)≥ε。

图2 [0,1]2中存在3个点时按序贯最大最小距离设计取点Fig.2 Taking points by sequential maximin distance designs when there are 3 points in [0,1]2

即存在ε>0，对任意的N1>0，都存在一个N2>N1，使得qN2≥ε>0，且{qn}n=1,2,…单调递减，故可以得a≥ε>0。

下面证明对于任意已取得的点si,sj∈SN2，均有d(si,sj)≥a>0，证明如下：

但由于在空间[0,1]d中，任意两点间的最大距离不超过d1/2，故每个球的半径应满足

Vqiu<(1+d1/2)d，

这与N2·πd/2(a/2)d/Γ(d/2+1)>(1+d1/2)d矛盾。

故原假设不成立，即我们证明了：对任意ε>0，任意x∈[0,1]d，都存在一个N>0，当n>N时，均有d(x,Sn)<ε。即按序贯最大最小距离设计多次取点，可以填充空间[0,1]d。

注1上面证明的是[0,1]d中一开始没有取任何点时，按照序贯最大最小距离设计取点，可将[0,1]d填充。 这个时候第1个点放在空间的中心，第2个点就应该取在空间[0,1]d的一个顶点处。

注2上述定理证明的是序贯最大最小距离设计对[0,1]d的填充性，同样地，对任一d维紧集，在空间中一开始已经取了点和没取点两种情况下，仍能证明按序贯最大最小距离设计取点可将空间填充。