滕一陽，武 赟，熊世峰?，楊建奎

(1 北京郵電大學(xué)理學(xué)院， 北京 100876； 2 中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院， 北京 100190)

s.t.x1,…,xn∈[0,1]d,d∈Z+的解，其中‖·‖代表歐式距離[2]。 最大最小距離設(shè)計也可以做成序貫類型[19]，即按照最小距離準(zhǔn)則一個個地增加試驗點，這樣就可以用較少的試驗點得出結(jié)論，也可避免盲目加大樣本數(shù)而造成浪費。 文獻(xiàn)[6]給出了其具體的定義。 如今，已有不少文獻(xiàn)討論過最大最小距離設(shè)計的性質(zhì)和構(gòu)造，如文獻(xiàn)[10-18]，但目前還沒有文章對序貫最大最小距離設(shè)計的性質(zhì)進(jìn)行討論。 本文將討論序貫最大最小距離設(shè)計的空間填充性質(zhì)。 證明序貫最大最小距離設(shè)計滿足最基本的空間填充性，即隨著樣本量的增大，該設(shè)計在試驗區(qū)域內(nèi)具有稠密性，可以任意逼近試驗區(qū)域內(nèi)的任意一個點。

1 構(gòu)造序貫最大最小距離設(shè)計

在[0,1]d,d∈Z+中，按如下規(guī)則取點：使新取的點到所有已取點的最小距離最大化。 引入下列記號表示：

記前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

按上述規(guī)則，在[0,1]2中，依次規(guī)定取點個數(shù)畫圖。

進(jìn)入21世紀(jì)以來，山東聊城歷屆市委、市政府緊緊抓住發(fā)展機遇，挖掘水的內(nèi)涵，做足水的文章，努力打造生產(chǎn)發(fā)展、生態(tài)良好的優(yōu)美環(huán)境，為改善聊城人民居住環(huán)境條件，提高城市競爭力，實現(xiàn)經(jīng)濟社會快速發(fā)展，發(fā)揮了重要作用。

圖1中，當(dāng)在[0,1]2中第1次取點時，因為此時[0,1]2中不存在點，規(guī)定取的第1個點在正方形的中心。接下來就可以按照序貫最大最小距離設(shè)計在空間中依次取點。 第2次取點時，有4個點同時滿足規(guī)則，它們在正方形的4個頂點處。可以看出，按序貫最大最小距離設(shè)計取點，可以將[0,1]2逐步填充。

圖1 [0,1]2中不存在點時按序貫最大最小距離設(shè)計取點Fig.1 Taking points by sequential maximin distance designs when there is no point in [0,1]2

圖2 中，一開始[0,1]2中已經(jīng)取了3個點，這3個點用三角形表示，再按序貫最大最小距離設(shè)計取點，取得的點用圓形表示。 可以看出，這種情況下序貫最大最小距離設(shè)計也可以對[0,1]2進(jìn)行逐步填充。

2 主要結(jié)果及證明

從第1節(jié)可以看出，隨著樣本量的增加， 序貫最大最小距離設(shè)計可以對2維試驗區(qū)域進(jìn)行逐步填充。 下面對任意的維數(shù)嚴(yán)格證明這一性質(zhì)。

定理2.1在[0,1]d,d∈Z+中，按序貫最大最小距離設(shè)計取點，設(shè)所取得的點依次為s1,s2,…,sn，則對任意ε>0，任意x∈[0,1]d，都存在一個N>0，當(dāng)n>N時，有d(x,Sn)<ε。

證明反證方向為：存在ε>0，存在一個x0∈[0,1]d，對任意的N1>0，都存在一個N2>N1，有d(x0,SN2)≥ε。

圖2 [0,1]2中存在3個點時按序貫最大最小距離設(shè)計取點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,…單調(diào)遞減，故可以得a≥ε>0。

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

但由于在空間[0,1]d中，任意兩點間的最大距離不超過d1/2，故每個球的半徑應(yīng)滿足

Vqiu<(1+d1/2)d，

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

故原假設(shè)不成立，即我們證明了：對任意ε>0，任意x∈[0,1]d，都存在一個N>0，當(dāng)n>N時，均有d(x,Sn)<ε。即按序貫最大最小距離設(shè)計多次取點，可以填充空間[0,1]d。

注1上面證明的是[0,1]d中一開始沒有取任何點時，按照序貫最大最小距離設(shè)計取點，可將[0,1]d填充。 這個時候第1個點放在空間的中心，第2個點就應(yīng)該取在空間[0,1]d的一個頂點處。

注2上述定理證明的是序貫最大最小距離設(shè)計對[0,1]d的填充性，同樣地，對任一d維緊集，在空間中一開始已經(jīng)取了點和沒取點兩種情況下，仍能證明按序貫最大最小距離設(shè)計取點可將空間填充。