非線性LTS估計(jì)的截?cái)嗄酃饣椒?/h1>
2014-07-20 11:03:31肖瑜
華東交通大學(xué)學(xué)報(bào) 2014年4期
肖瑜
（華東交通大學(xué)理學(xué)院，江西南昌330013）
非線性LTS估計(jì)的截?cái)嗄酃饣椒?/p>
肖瑜
（華東交通大學(xué)理學(xué)院，江西南昌330013）
LTS估計(jì)是一類穩(wěn)健估計(jì)，其模型可以轉(zhuǎn)化為min-min-sum型非凸非光滑優(yōu)化問題，其目標(biāo)函數(shù)是從m個(gè)光滑函數(shù)中取m?個(gè)的組合求和，即使m不是很大，組合數(shù)也會(huì)非常大，導(dǎo)致min函數(shù)的組成函數(shù)個(gè)數(shù)非常多，求解非常困難。針對(duì)這個(gè)問題的特點(diǎn)，并結(jié)合解一般minmax問題的截?cái)嗄酃饣椒ǎo出了解LTS估計(jì)問題的截?cái)嗄酃饣惴?。?shù)值結(jié)果表明了算法的有效性和高效率。
LTS估計(jì)；凝聚函數(shù)；截?cái)嗄酃饣?/p>
在數(shù)據(jù)擬合中，最小二乘估計(jì)（the least squares estimator，簡(jiǎn)記為L(zhǎng)S估計(jì)），l1估計(jì)及l(fā)∞估計(jì)等方法都會(huì)受到異常點(diǎn)的影響。1985年，Rousseeuw提出一種穩(wěn)健估計(jì)——LTS估計(jì)［1-3］（The least trimmed squares esti?mator）。設(shè)觀測(cè)數(shù)據(jù)(ui,vi)，i=1,…,m。
其中：x為待估計(jì)的參數(shù)；ηi為對(duì)應(yīng)的殘量。那么LTS估計(jì)為
LTS估計(jì)模型雖然目標(biāo)函數(shù)連續(xù)，但是非凸非光滑，求解比較困難。目前，解LTS估計(jì)大概有3類算法。一種是精確求解［1］。由于LTS估計(jì)實(shí)際上是對(duì)某個(gè)子集（包含m?個(gè)數(shù)據(jù)點(diǎn)的子集，特別的，對(duì)線性擬合問題取n個(gè)數(shù)據(jù)點(diǎn)）的最小二乘估計(jì)，可以通過對(duì)所有含m?個(gè)數(shù)據(jù)點(diǎn)的子集做最小二乘估計(jì)，然后取殘量平方和最小的。這種方法需要做次最小二乘估計(jì)，若m和m?稍大，總計(jì)算量就非常大，如m=40,m?=32時(shí)，需要計(jì)算7千多萬(wàn)次最小二乘估計(jì)。還有一類隨機(jī)近似算法［1-3，7］，其中使用最廣泛的是Rousseeuw和Leroy于1987年提出的的PROGRESS算法，其具體步驟如下［1］：從m個(gè)數(shù)據(jù)點(diǎn)中隨機(jī)取m?個(gè)，記為?；對(duì)?做最小二乘估計(jì)，得到最小二乘解x*；計(jì)算x*對(duì)應(yīng)的目標(biāo)函數(shù)值，即；重復(fù)以上步驟若干次，取使目標(biāo)函數(shù)最小的x*為近似解。PROGRESS算法中，設(shè)重復(fù)次數(shù)為p，那么得到原問題解的概率為還有啟發(fā)式算法，如文獻(xiàn)［8］中運(yùn)用微分進(jìn)化算法來(lái)計(jì)算LTS估計(jì)。這些算法都有各自的優(yōu)缺點(diǎn)，第1類算法雖然能精確求解，但是計(jì)算量非常大。第2、3類算法可以通過控制重復(fù)次數(shù)來(lái)控制計(jì)算量，但是這些算法是依概率得到最優(yōu)解的，重復(fù)次數(shù)越多，概率越大，但計(jì)算量也越大，并且還是不能保證得到最優(yōu)解，甚至局部最優(yōu)解。
LTS問題式（1）可以等價(jià)變形為min-min-sum規(guī)劃問題。對(duì)于max型的非光滑函數(shù)，基于Jaynes的最大熵原理，李興斯提出了一類光滑函數(shù)，稱為凝聚函數(shù)，并給出了解min-max等問題的凝聚函數(shù)法［9］。在計(jì)算上，當(dāng)max函數(shù)的組成函數(shù)很多時(shí)，凝聚函數(shù)的梯度和Hessen計(jì)算量很大，影響了凝聚函數(shù)法計(jì)算效率。在文［10-11］中，作者提出了解min-max問題的截?cái)嗄酃饣惴āＴ诿總€(gè)迭代點(diǎn)處，在不影響算法的收斂速度的前提下，均自適應(yīng)的選取一部分函數(shù)凝聚。這樣，參與梯度、Hessen計(jì)算的函數(shù)也只有很少一部分，從而大大的減少了計(jì)算量。
采用凝聚函數(shù)光滑化min-sum型目標(biāo)函數(shù)，然后用截?cái)嗄酃饣ｎD法求解。記q={} 1,2,…,m，S={I∈q|#(I)=m?}，#(I)表示集合I所含元素?cái)?shù)目。由于問題的特殊性（min-sum型函數(shù)的下標(biāo)集合包含從1,…,m中取m?個(gè)數(shù)的所有可能的組合），如果直接采用［10］中的截?cái)喾椒?，在每個(gè)迭代點(diǎn)x處，需要對(duì)所有的組合I∈S，求出殘差平方和（計(jì)算量是），再進(jìn)行次函數(shù)值大小比較計(jì)算。實(shí)際上，我們可以利用問題的特殊性，只要對(duì)m個(gè)函數(shù)值求出第m?小的，即求出（計(jì)算量為O(m)），然后根據(jù)的值來(lái)設(shè)計(jì)截?cái)鄿?zhǔn)則。
1 LTS估計(jì)的截?cái)嗄酃饣ｎD法
顯然，LTS估計(jì)（1）可以寫成如下形式
問題（2）的一階最優(yōu)性條件［13-14］：
命題1設(shè)（2）在x*處取得的最小值，那么
我們采用如下凝聚函數(shù)光滑化（2）的目標(biāo)函數(shù)）
其中：t＞0是凝聚參數(shù)，當(dāng)t→0+時(shí)，F(xiàn)t(x)→F(x)。因?yàn)長(zhǎng)TS估計(jì)含有大量的下標(biāo)組合，文獻(xiàn)［10］中mini?max問題的截?cái)喾绞讲⒉皇呛苓m合。下面，我們嘗試尋求合適的截?cái)喾绞?。?duì)給定的xˉ，取參數(shù)μ＞0，令
定義截?cái)嗄酆瘮?shù)為
接下來(lái)，我們給出FSˉt(x)與精確凝聚函數(shù)Ft(x)的函數(shù)值，梯度及Hesse陣的一些估計(jì)式。首先定義函數(shù)
上述命題的證明過程繁瑣，此處不贅述，具體過程可參閱文獻(xiàn)［12］。
對(duì)任意x0∈Rn,t0＞0,記Ω={x|F(x)≤Ft0(x0)}。由上面的命題，得到如下推論：
推論1對(duì)任意x∈Rn,t＞0,ε1＞0,ε2＞0，若（4）中的μ按照如下方式選擇
其中：γ,ω滿足γ≥γ(x),ω≥ω(x)，則有
由推論1知，在計(jì)算過程中，可以按照式（7）選取截?cái)鄥?shù)μ，來(lái)控制截?cái)嗄壅`差。接下來(lái)，我們采用截?cái)嗄鄯绞剑?）～（7），結(jié)合光滑化牛頓法，得到解LTS估計(jì)問題的截?cái)嗄酃饣ｎD法。具體的算法如下：
算法1（截?cái)嗄酃饣ｎD法）
初始值：x0∈Rn。
參數(shù)：t0＞0,t?∈(0,1);α,β,κ1∈(0,1);θ∈(0,(1-α)/32),δ＞0,γ,ω充分大使得γ≥mx∈aRxnγ(x),ω≥mx∈aRxnω(x)；函數(shù)εa(t),εb(t)，τ(t),σ(t):(0,∞)→(0,∞)滿足εb(t)≥εa(t)＞τ(t),lt→im0+τ(t)=0,ε1(t)=θτ(t),ε2(t)＞0。
步驟1 設(shè)i=0,k=0,s=1,xk,i=0。
征值：然后計(jì)算Cholesky因子R，使得B(xk,i)=RRT，以及計(jì)算R的倒條件數(shù)c(R)。如果c(R)≥κ1，轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟5。
步驟6 計(jì)算步長(zhǎng)λk,i=βl，其中l(wèi)≥0為滿足下面條件的最小正整數(shù)～Ftk(xk,i+λk,ihk,i)-Ftk(xk,i)≤αλk,i＜
步驟7 設(shè)xk,i+1=xk,i+λk,ihk,i,i=i+1。按照（7）和（4）計(jì)算μ和。如果，轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟3。
步驟8 如果s=1，計(jì)算t*使得，轉(zhuǎn)步驟9，否則設(shè)tk+1=1/(s(k+2))，k=k+1，i=0，轉(zhuǎn)步驟2。
算法1 有如下收斂結(jié)果（具體證明過程與［10］中算法2的收斂性證明類似，此處不贅述，可參閱文獻(xiàn)［10，12］）：
定理1設(shè)二次連續(xù)可微，水平集Ω有界，是算法1產(chǎn)生的序列。那么，存在無(wú)窮子序列N′?N，使得當(dāng)k→N′∞時(shí)，有,并且0∈?F(x*)。
2 數(shù)值結(jié)果
我們用matlab語(yǔ)言實(shí)現(xiàn)了截?cái)喙饣ｎD法（簡(jiǎn)記為TSN）。因?yàn)椋?］中的精確求解方法計(jì)算時(shí)間太長(zhǎng)，如對(duì)例1求解時(shí)間超過24×7小時(shí)，因此我們只將TSN算法與PROGRESS算法，以及凝聚光滑化牛頓法（即在TSN算法中略去截?cái)嗉记桑┻M(jìn)行了比較。
例1（Circle Fitting問題［15］）LTS估計(jì)不僅可以估計(jì)v=f(u,x)這類型模型，也可以估計(jì)形如f(u,x)=0的模型，如Circle Fitting問題——找一個(gè)合適的球，使得所有的數(shù)據(jù)點(diǎn)到球面的距離的范數(shù)最小。我們用matlab產(chǎn)生40個(gè)數(shù)據(jù)點(diǎn)ui∈R3，使得其分布在某個(gè)球面上，然后對(duì)所有的數(shù)據(jù)點(diǎn)做擾動(dòng)（其中有8個(gè)數(shù)據(jù)點(diǎn)的擾動(dòng)程度大于其他點(diǎn)），最后得到的數(shù)據(jù)點(diǎn)參閱［12］表6.3。設(shè)待求的球面的中心為o∈R3，半徑為r，則ui對(duì)應(yīng)的誤差項(xiàng)
例2（圓錐擬合問題［12］）這個(gè)例子的數(shù)據(jù)由matlab程序生成，只是對(duì)其中一部分?jǐn)?shù)據(jù)點(diǎn)增加了比較大的擾動(dòng)作為異常點(diǎn)。首先產(chǎn)生標(biāo)準(zhǔn)圓錐面上的數(shù)據(jù)點(diǎn)
其中：ri和γi分別是[0.1,10]和[0,2π]上均勻分布的偽隨機(jī)數(shù)。然后在z?i上加一個(gè)服從N(0,0.3)分布的擾動(dòng)項(xiàng)，并對(duì)數(shù)據(jù)進(jìn)行旋轉(zhuǎn)和平移
其中：T(?)為變換矩陣
具體的數(shù)據(jù)參閱［12］表6.4（總共30個(gè)數(shù)據(jù)點(diǎn)，含6個(gè)異常點(diǎn)）。
表1 例1的數(shù)值結(jié)果Tab.1 The numerical results of Example 1
其中：o0=(-1.2,1.2,-1.2,1.2,-1.2,1.2,-1.2,1.2)T,r0=1。
表2 例2的數(shù)值結(jié)果Tab.2 The numerical results of Example 2
其中：x0=(-0.1,-0.1,-2,1.5,-1.5,0.6)T。
3 結(jié)論
LTS估計(jì)是一類穩(wěn)健估計(jì)，一般采用隨機(jī)算法計(jì)算其近似解。從數(shù)值優(yōu)化的角度考慮此問題，將其模型可以轉(zhuǎn)化為min-min-sum型非凸非光滑優(yōu)化問題，并給出截?cái)嗄酃饣ｎD法（TSN）。不但理論上可行，數(shù)值結(jié)果也說明了算法具有很高的計(jì)算效率。與傳統(tǒng)的算法PROGRESS相比，截?cái)嗄酃饣ｎD法能在更短的計(jì)算時(shí)間內(nèi)達(dá)到更優(yōu)的目標(biāo)函數(shù)值。與沒有加截?cái)嗖呗缘哪酃饣ｎD法（SN）相比，兩種算法得到的解完全一樣，但是我們的算法在計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)少于SN算法。
[1]ROUSSEEUW P J.Leastmedian of squares regression[J].J Amer Statist Assoc,1984,79:871-880.
[2]ROUSSEEUW P J.Multivariate estimation with high breakdown point[C]//Mathematical Statistics and Applications,Dordrecht: Reidel,1985:283-297.
[3]ROUSSEEUW P J,LEROY A M.Robust regression and outlier detection[M].New York:John Wiley&Sons Inc,1987:87.
[4]ZAMAN A,ROUSSEEUW P J,ORHAN M.Econometric applications of high-breakdown robust regression techniques[J].Econo?metrics Letters,2001,71(1):1-8.
[5]YE M,HARALICK R M.Optical flow from a least-trimmed squares based adaptive approach[C]//International Conference on Pat?tern Recognition ICPR 2000,Barcelona:IEEE,2000:1052-1055.
[6]WANG H,SUTER D.Using symmetry in robustmodel fitting[J].Pattern Recognition Letters,2003,24(16):2953-2966.
[7]ROUSSEEUW P J,HUBERT M.Recent developments in PROGRESS[C]//L1-Statistical Procedures and Related Topics,CA:In?stitute of Mathematical Statistics,1997:201-214.
[8]CIZEK P.Robust estimation in nonlinear regression and limited dependent variablemodels[R].Berlin:Humboldt University of Berlin,2002:189.
[9]LI X S.An aggregate functionmethod for nonlinear programming[J].Science in China,1991,34(2):1467-1473.
[10]XIAO Y,YU B.A truncated aggregate smoothing newtonmethod forminimax problems[J].Appl Math Comput,2010,216:1868-1879.
[11]XIAO Y,YU B,XIONG H J.Truncated aggregate homotopymethod for nonconvex nonli-near programming[J].Optimization Methods&Software,2014,29(1):160-176.
[12]肖瑜.截?cái)嗄酃饣惴╗D].大連:大連理工大學(xué),2010.
[13]ROLEFF K.A stablemultiple exchange algorithm for linear SIP[C]//Lecture Notes in Control and Information Science,Berlin: Springer,1979:83-96.
[14]CLARKE F H.Optimization and nonsmooth analysis[M].New York:John Wiley&Sons Inc,1983:56.
[15]GANDER W,GOLUB G H.TREBEL R.Least-squares Fitting of Circles and Ellipses[J].BIT Numerical Mathematics,1994,34 (4):558-578.
[16]曾明華,肖瑜,黃細(xì)燕.多層次交通網(wǎng)絡(luò)的UE與SO混合均衡與效率損失[J].華東交通大學(xué)學(xué)報(bào),2012,29(2):57-62.
Truncated Aggregate Smoothing Method for Nonlinear LTS Estimator
Xiao Yu
(School of Basic Science,East China Jiaotong University,Nanchang 330013,China)
The computing of the nonlinear least trimmed squares(LTS)estimator is considered.LTS is a robust esti?mator and can be converted to amin-min non-convex and non-smooth programming problem.For the data set with sizem,the objective function is theminimum of all them?-subsets'residual sum of squares.Even ifmis not big,the number of the subsetsmay be very large whichmakes computing LTS estimator difficult.For such a special kind of problem,an appropriate truncated criteria standard is given and then an efficient truncated smooth?ing Newtonmethod is proposed.The numerical results show the efficiency.
LTS estimator;aggregate function;truncation smoothing
O221.2
A
2014-03-07
國(guó)家自然科學(xué)基金資助項(xiàng)目（11171051，11261019）
肖瑜（1981—），女，講師，博士，主要研究方向?yàn)閿?shù)值優(yōu)化。
1005-0523（2014）04-0059-06
猜你喜歡
用固定數(shù)值計(jì)算小學(xué)生學(xué)習(xí)指導(dǎo)(低年級(jí))(2023年4期)2023-05-09 11:52:52 二次函數(shù)新世紀(jì)智能(數(shù)學(xué)備考)(2021年9期)2021-11-24 01:14:34 數(shù)值大小比較“招招鮮”中學(xué)生數(shù)理化·高一版(2021年11期)2021-09-05 14:27:13 第3講 “函數(shù)”復(fù)習(xí)精講中學(xué)生數(shù)理化·中考版(2021年3期)2021-07-22 07:41:30 二次函數(shù)新世紀(jì)智能(數(shù)學(xué)備考)(2020年9期)2021-01-04 00:25:12 函數(shù)備考精講中學(xué)生數(shù)理化(高中版.高考數(shù)學(xué))(2020年9期)2020-10-28 08:43:52 牛頓忘食小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2019年10期)2019-10-08 09:11:38 風(fēng)中的牛頓小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2017年4期)2017-03-20 15:46:51 失信的牛頓作文與考試·小學(xué)高年級(jí)版(2016年7期)2016-05-14 05:39:03 基于Fluent的GTAW數(shù)值模擬焊接(2016年2期)2016-02-27 13:01:02
肖瑜
（華東交通大學(xué)理學(xué)院，江西南昌330013）
非線性LTS估計(jì)的截?cái)嗄酃饣椒?/p>
肖瑜
（華東交通大學(xué)理學(xué)院，江西南昌330013）
LTS估計(jì)是一類穩(wěn)健估計(jì)，其模型可以轉(zhuǎn)化為min-min-sum型非凸非光滑優(yōu)化問題，其目標(biāo)函數(shù)是從m個(gè)光滑函數(shù)中取m?個(gè)的組合求和，即使m不是很大，組合數(shù)也會(huì)非常大，導(dǎo)致min函數(shù)的組成函數(shù)個(gè)數(shù)非常多，求解非常困難。針對(duì)這個(gè)問題的特點(diǎn)，并結(jié)合解一般minmax問題的截?cái)嗄酃饣椒ǎo出了解LTS估計(jì)問題的截?cái)嗄酃饣惴?。?shù)值結(jié)果表明了算法的有效性和高效率。
LTS估計(jì)；凝聚函數(shù)；截?cái)嗄酃饣?/p>
在數(shù)據(jù)擬合中，最小二乘估計(jì)（the least squares estimator，簡(jiǎn)記為L(zhǎng)S估計(jì)），l1估計(jì)及l(fā)∞估計(jì)等方法都會(huì)受到異常點(diǎn)的影響。1985年，Rousseeuw提出一種穩(wěn)健估計(jì)——LTS估計(jì)［1-3］（The least trimmed squares esti?mator）。設(shè)觀測(cè)數(shù)據(jù)(ui,vi)，i=1,…,m。
其中：x為待估計(jì)的參數(shù)；ηi為對(duì)應(yīng)的殘量。那么LTS估計(jì)為
LTS估計(jì)模型雖然目標(biāo)函數(shù)連續(xù)，但是非凸非光滑，求解比較困難。目前，解LTS估計(jì)大概有3類算法。一種是精確求解［1］。由于LTS估計(jì)實(shí)際上是對(duì)某個(gè)子集（包含m?個(gè)數(shù)據(jù)點(diǎn)的子集，特別的，對(duì)線性擬合問題取n個(gè)數(shù)據(jù)點(diǎn)）的最小二乘估計(jì)，可以通過對(duì)所有含m?個(gè)數(shù)據(jù)點(diǎn)的子集做最小二乘估計(jì)，然后取殘量平方和最小的。這種方法需要做次最小二乘估計(jì)，若m和m?稍大，總計(jì)算量就非常大，如m=40,m?=32時(shí)，需要計(jì)算7千多萬(wàn)次最小二乘估計(jì)。還有一類隨機(jī)近似算法［1-3，7］，其中使用最廣泛的是Rousseeuw和Leroy于1987年提出的的PROGRESS算法，其具體步驟如下［1］：從m個(gè)數(shù)據(jù)點(diǎn)中隨機(jī)取m?個(gè)，記為?；對(duì)?做最小二乘估計(jì)，得到最小二乘解x*；計(jì)算x*對(duì)應(yīng)的目標(biāo)函數(shù)值，即；重復(fù)以上步驟若干次，取使目標(biāo)函數(shù)最小的x*為近似解。PROGRESS算法中，設(shè)重復(fù)次數(shù)為p，那么得到原問題解的概率為還有啟發(fā)式算法，如文獻(xiàn)［8］中運(yùn)用微分進(jìn)化算法來(lái)計(jì)算LTS估計(jì)。這些算法都有各自的優(yōu)缺點(diǎn)，第1類算法雖然能精確求解，但是計(jì)算量非常大。第2、3類算法可以通過控制重復(fù)次數(shù)來(lái)控制計(jì)算量，但是這些算法是依概率得到最優(yōu)解的，重復(fù)次數(shù)越多，概率越大，但計(jì)算量也越大，并且還是不能保證得到最優(yōu)解，甚至局部最優(yōu)解。
LTS問題式（1）可以等價(jià)變形為min-min-sum規(guī)劃問題。對(duì)于max型的非光滑函數(shù)，基于Jaynes的最大熵原理，李興斯提出了一類光滑函數(shù)，稱為凝聚函數(shù)，并給出了解min-max等問題的凝聚函數(shù)法［9］。在計(jì)算上，當(dāng)max函數(shù)的組成函數(shù)很多時(shí)，凝聚函數(shù)的梯度和Hessen計(jì)算量很大，影響了凝聚函數(shù)法計(jì)算效率。在文［10-11］中，作者提出了解min-max問題的截?cái)嗄酃饣惴āＴ诿總€(gè)迭代點(diǎn)處，在不影響算法的收斂速度的前提下，均自適應(yīng)的選取一部分函數(shù)凝聚。這樣，參與梯度、Hessen計(jì)算的函數(shù)也只有很少一部分，從而大大的減少了計(jì)算量。
采用凝聚函數(shù)光滑化min-sum型目標(biāo)函數(shù)，然后用截?cái)嗄酃饣ｎD法求解。記q={} 1,2,…,m，S={I∈q|#(I)=m?}，#(I)表示集合I所含元素?cái)?shù)目。由于問題的特殊性（min-sum型函數(shù)的下標(biāo)集合包含從1,…,m中取m?個(gè)數(shù)的所有可能的組合），如果直接采用［10］中的截?cái)喾椒?，在每個(gè)迭代點(diǎn)x處，需要對(duì)所有的組合I∈S，求出殘差平方和（計(jì)算量是），再進(jìn)行次函數(shù)值大小比較計(jì)算。實(shí)際上，我們可以利用問題的特殊性，只要對(duì)m個(gè)函數(shù)值求出第m?小的，即求出（計(jì)算量為O(m)），然后根據(jù)的值來(lái)設(shè)計(jì)截?cái)鄿?zhǔn)則。
1 LTS估計(jì)的截?cái)嗄酃饣ｎD法
顯然，LTS估計(jì)（1）可以寫成如下形式
問題（2）的一階最優(yōu)性條件［13-14］：
命題1設(shè)（2）在x*處取得的最小值，那么
我們采用如下凝聚函數(shù)光滑化（2）的目標(biāo)函數(shù)）
其中：t＞0是凝聚參數(shù)，當(dāng)t→0+時(shí)，F(xiàn)t(x)→F(x)。因?yàn)長(zhǎng)TS估計(jì)含有大量的下標(biāo)組合，文獻(xiàn)［10］中mini?max問題的截?cái)喾绞讲⒉皇呛苓m合。下面，我們嘗試尋求合適的截?cái)喾绞?。?duì)給定的xˉ，取參數(shù)μ＞0，令
定義截?cái)嗄酆瘮?shù)為
接下來(lái)，我們給出FSˉt(x)與精確凝聚函數(shù)Ft(x)的函數(shù)值，梯度及Hesse陣的一些估計(jì)式。首先定義函數(shù)
上述命題的證明過程繁瑣，此處不贅述，具體過程可參閱文獻(xiàn)［12］。
對(duì)任意x0∈Rn,t0＞0,記Ω={x|F(x)≤Ft0(x0)}。由上面的命題，得到如下推論：
推論1對(duì)任意x∈Rn,t＞0,ε1＞0,ε2＞0，若（4）中的μ按照如下方式選擇
其中：γ,ω滿足γ≥γ(x),ω≥ω(x)，則有
由推論1知，在計(jì)算過程中，可以按照式（7）選取截?cái)鄥?shù)μ，來(lái)控制截?cái)嗄壅`差。接下來(lái)，我們采用截?cái)嗄鄯绞剑?）～（7），結(jié)合光滑化牛頓法，得到解LTS估計(jì)問題的截?cái)嗄酃饣ｎD法。具體的算法如下：
算法1（截?cái)嗄酃饣ｎD法）
初始值：x0∈Rn。
參數(shù)：t0＞0,t?∈(0,1);α,β,κ1∈(0,1);θ∈(0,(1-α)/32),δ＞0,γ,ω充分大使得γ≥mx∈aRxnγ(x),ω≥mx∈aRxnω(x)；函數(shù)εa(t),εb(t)，τ(t),σ(t):(0,∞)→(0,∞)滿足εb(t)≥εa(t)＞τ(t),lt→im0+τ(t)=0,ε1(t)=θτ(t),ε2(t)＞0。
步驟1 設(shè)i=0,k=0,s=1,xk,i=0。
征值：然后計(jì)算Cholesky因子R，使得B(xk,i)=RRT，以及計(jì)算R的倒條件數(shù)c(R)。如果c(R)≥κ1，轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟5。
步驟6 計(jì)算步長(zhǎng)λk,i=βl，其中l(wèi)≥0為滿足下面條件的最小正整數(shù)～Ftk(xk,i+λk,ihk,i)-Ftk(xk,i)≤αλk,i＜
步驟7 設(shè)xk,i+1=xk,i+λk,ihk,i,i=i+1。按照（7）和（4）計(jì)算μ和。如果，轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟3。
步驟8 如果s=1，計(jì)算t*使得，轉(zhuǎn)步驟9，否則設(shè)tk+1=1/(s(k+2))，k=k+1，i=0，轉(zhuǎn)步驟2。
算法1 有如下收斂結(jié)果（具體證明過程與［10］中算法2的收斂性證明類似，此處不贅述，可參閱文獻(xiàn)［10，12］）：
定理1設(shè)二次連續(xù)可微，水平集Ω有界，是算法1產(chǎn)生的序列。那么，存在無(wú)窮子序列N′?N，使得當(dāng)k→N′∞時(shí)，有,并且0∈?F(x*)。
2 數(shù)值結(jié)果
我們用matlab語(yǔ)言實(shí)現(xiàn)了截?cái)喙饣ｎD法（簡(jiǎn)記為TSN）。因?yàn)椋?］中的精確求解方法計(jì)算時(shí)間太長(zhǎng)，如對(duì)例1求解時(shí)間超過24×7小時(shí)，因此我們只將TSN算法與PROGRESS算法，以及凝聚光滑化牛頓法（即在TSN算法中略去截?cái)嗉记桑┻M(jìn)行了比較。
例1（Circle Fitting問題［15］）LTS估計(jì)不僅可以估計(jì)v=f(u,x)這類型模型，也可以估計(jì)形如f(u,x)=0的模型，如Circle Fitting問題——找一個(gè)合適的球，使得所有的數(shù)據(jù)點(diǎn)到球面的距離的范數(shù)最小。我們用matlab產(chǎn)生40個(gè)數(shù)據(jù)點(diǎn)ui∈R3，使得其分布在某個(gè)球面上，然后對(duì)所有的數(shù)據(jù)點(diǎn)做擾動(dòng)（其中有8個(gè)數(shù)據(jù)點(diǎn)的擾動(dòng)程度大于其他點(diǎn)），最后得到的數(shù)據(jù)點(diǎn)參閱［12］表6.3。設(shè)待求的球面的中心為o∈R3，半徑為r，則ui對(duì)應(yīng)的誤差項(xiàng)
例2（圓錐擬合問題［12］）這個(gè)例子的數(shù)據(jù)由matlab程序生成，只是對(duì)其中一部分?jǐn)?shù)據(jù)點(diǎn)增加了比較大的擾動(dòng)作為異常點(diǎn)。首先產(chǎn)生標(biāo)準(zhǔn)圓錐面上的數(shù)據(jù)點(diǎn)
其中：ri和γi分別是[0.1,10]和[0,2π]上均勻分布的偽隨機(jī)數(shù)。然后在z?i上加一個(gè)服從N(0,0.3)分布的擾動(dòng)項(xiàng)，并對(duì)數(shù)據(jù)進(jìn)行旋轉(zhuǎn)和平移
其中：T(?)為變換矩陣
具體的數(shù)據(jù)參閱［12］表6.4（總共30個(gè)數(shù)據(jù)點(diǎn)，含6個(gè)異常點(diǎn)）。
表1 例1的數(shù)值結(jié)果Tab.1 The numerical results of Example 1
其中：o0=(-1.2,1.2,-1.2,1.2,-1.2,1.2,-1.2,1.2)T,r0=1。
表2 例2的數(shù)值結(jié)果Tab.2 The numerical results of Example 2
其中：x0=(-0.1,-0.1,-2,1.5,-1.5,0.6)T。
3 結(jié)論
LTS估計(jì)是一類穩(wěn)健估計(jì)，一般采用隨機(jī)算法計(jì)算其近似解。從數(shù)值優(yōu)化的角度考慮此問題，將其模型可以轉(zhuǎn)化為min-min-sum型非凸非光滑優(yōu)化問題，并給出截?cái)嗄酃饣ｎD法（TSN）。不但理論上可行，數(shù)值結(jié)果也說明了算法具有很高的計(jì)算效率。與傳統(tǒng)的算法PROGRESS相比，截?cái)嗄酃饣ｎD法能在更短的計(jì)算時(shí)間內(nèi)達(dá)到更優(yōu)的目標(biāo)函數(shù)值。與沒有加截?cái)嗖呗缘哪酃饣ｎD法（SN）相比，兩種算法得到的解完全一樣，但是我們的算法在計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)少于SN算法。
[1]ROUSSEEUW P J.Leastmedian of squares regression[J].J Amer Statist Assoc,1984,79:871-880.
[2]ROUSSEEUW P J.Multivariate estimation with high breakdown point[C]//Mathematical Statistics and Applications,Dordrecht: Reidel,1985:283-297.
[3]ROUSSEEUW P J,LEROY A M.Robust regression and outlier detection[M].New York:John Wiley&Sons Inc,1987:87.
[4]ZAMAN A,ROUSSEEUW P J,ORHAN M.Econometric applications of high-breakdown robust regression techniques[J].Econo?metrics Letters,2001,71(1):1-8.
[5]YE M,HARALICK R M.Optical flow from a least-trimmed squares based adaptive approach[C]//International Conference on Pat?tern Recognition ICPR 2000,Barcelona:IEEE,2000:1052-1055.
[6]WANG H,SUTER D.Using symmetry in robustmodel fitting[J].Pattern Recognition Letters,2003,24(16):2953-2966.
[7]ROUSSEEUW P J,HUBERT M.Recent developments in PROGRESS[C]//L1-Statistical Procedures and Related Topics,CA:In?stitute of Mathematical Statistics,1997:201-214.
[8]CIZEK P.Robust estimation in nonlinear regression and limited dependent variablemodels[R].Berlin:Humboldt University of Berlin,2002:189.
[9]LI X S.An aggregate functionmethod for nonlinear programming[J].Science in China,1991,34(2):1467-1473.
[10]XIAO Y,YU B.A truncated aggregate smoothing newtonmethod forminimax problems[J].Appl Math Comput,2010,216:1868-1879.
[11]XIAO Y,YU B,XIONG H J.Truncated aggregate homotopymethod for nonconvex nonli-near programming[J].Optimization Methods&Software,2014,29(1):160-176.
[12]肖瑜.截?cái)嗄酃饣惴╗D].大連:大連理工大學(xué),2010.
[13]ROLEFF K.A stablemultiple exchange algorithm for linear SIP[C]//Lecture Notes in Control and Information Science,Berlin: Springer,1979:83-96.
[14]CLARKE F H.Optimization and nonsmooth analysis[M].New York:John Wiley&Sons Inc,1983:56.
[15]GANDER W,GOLUB G H.TREBEL R.Least-squares Fitting of Circles and Ellipses[J].BIT Numerical Mathematics,1994,34 (4):558-578.
[16]曾明華,肖瑜,黃細(xì)燕.多層次交通網(wǎng)絡(luò)的UE與SO混合均衡與效率損失[J].華東交通大學(xué)學(xué)報(bào),2012,29(2):57-62.
Truncated Aggregate Smoothing Method for Nonlinear LTS Estimator
Xiao Yu
(School of Basic Science,East China Jiaotong University,Nanchang 330013,China)
The computing of the nonlinear least trimmed squares(LTS)estimator is considered.LTS is a robust esti?mator and can be converted to amin-min non-convex and non-smooth programming problem.For the data set with sizem,the objective function is theminimum of all them?-subsets'residual sum of squares.Even ifmis not big,the number of the subsetsmay be very large whichmakes computing LTS estimator difficult.For such a special kind of problem,an appropriate truncated criteria standard is given and then an efficient truncated smooth?ing Newtonmethod is proposed.The numerical results show the efficiency.
LTS estimator;aggregate function;truncation smoothing
O221.2
A
2014-03-07
國(guó)家自然科學(xué)基金資助項(xiàng)目（11171051，11261019）
肖瑜（1981—），女，講師，博士，主要研究方向?yàn)閿?shù)值優(yōu)化。
1005-0523（2014）04-0059-06
猜你喜歡
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級(jí))(2023年4期)2023-05-09 11:52:52
新世紀(jì)智能(數(shù)學(xué)備考)(2021年9期)2021-11-24 01:14:34
中學(xué)生數(shù)理化·高一版(2021年11期)2021-09-05 14:27:13
中學(xué)生數(shù)理化·中考版(2021年3期)2021-07-22 07:41:30
新世紀(jì)智能(數(shù)學(xué)備考)(2020年9期)2021-01-04 00:25:12
中學(xué)生數(shù)理化(高中版.高考數(shù)學(xué))(2020年9期)2020-10-28 08:43:52
小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2019年10期)2019-10-08 09:11:38
小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2017年4期)2017-03-20 15:46:51
作文與考試·小學(xué)高年級(jí)版(2016年7期)2016-05-14 05:39:03
焊接(2016年2期)2016-02-27 13:01:02
