李 穎, 林洪生, 劉 嚴(yán)

(沈陽(yáng)工程學(xué)院 基礎(chǔ)教學(xué)部, 沈陽(yáng) 110136)

基于規(guī)劃理論的最小二乘法改進(jìn)及其在Markov跳變系統(tǒng)參數(shù)估計(jì)中的應(yīng)用

李 穎, 林洪生, 劉 嚴(yán)

(沈陽(yáng)工程學(xué)院 基礎(chǔ)教學(xué)部, 沈陽(yáng) 110136)

分析了高斯最小二乘法在Markov跳變系統(tǒng)參數(shù)估計(jì)中的局限性,即不能夠直接解決帶有約束條件的擬合問題。而Markov跳變系統(tǒng)的轉(zhuǎn)移概率矩陣要滿足列和為1的約束,同時(shí)在多次觀測(cè)值中有部分?jǐn)?shù)據(jù)是未知的。根據(jù)規(guī)劃問題為帶有約束條件的極值問題,且約束條件中決策變量的個(gè)數(shù)可以多于目標(biāo)函數(shù)中決策變量個(gè)數(shù)的特點(diǎn),將Markov跳變系統(tǒng)參數(shù)估計(jì)問題轉(zhuǎn)化為非線性規(guī)劃問題。從求解的角度出發(fā),將非線性規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃,同時(shí)給出了具體的轉(zhuǎn)化方法。從理論上說明了轉(zhuǎn)化后的凸規(guī)劃問題在滿足庫(kù)恩-塔克條件的前提下,庫(kù)恩-塔克點(diǎn)一定為全局最優(yōu)解。最后給出仿真算例,說明結(jié)論的合理性。

凸規(guī)劃; Markov跳變系統(tǒng); 庫(kù)恩-塔克條件; 最小二乘法; 參數(shù)估計(jì)

0 引 言

高斯最小二乘法是工程問題常用方法, 廣泛應(yīng)用于科學(xué)技術(shù)各個(gè)領(lǐng)域。 可以解決觀測(cè)數(shù)據(jù)均為已知且沒有約束條件的數(shù)據(jù)擬合問題, 通常將其轉(zhuǎn)化為多元函數(shù)的極值問題, 采用微分法進(jìn)行求解, 同時(shí)這組解是惟一的[1]。 很多文獻(xiàn)對(duì)最小二乘法做了不同的改進(jìn), 比如利用插值方法的改進(jìn)、為提高精度考慮到的相對(duì)誤差的改進(jìn)、基于遺傳算法的改進(jìn)[2-5]。 但是在處理某些工程問題時(shí)可能會(huì)遇到有部分觀測(cè)數(shù)據(jù)未知, 且?guī)в屑s束條件的數(shù)據(jù)擬合問題, 高斯最小二乘法對(duì)于這類數(shù)據(jù)擬合問題就無(wú)法解決了。

例如下面給出的一個(gè)馬爾科夫跳變系統(tǒng):

其中:x(k)為n維狀態(tài)向量;u(k)為n維可控輸入;rk為馬爾科夫過程,滿足式(2),

由于各種外界條件的限制,每次觀測(cè)后得到的轉(zhuǎn)移概率矩陣未知元素可能處于不同位置,但是對(duì)應(yīng)于同一未知的元素相差不多,且滿足矩陣的列元素之和為1。根據(jù)觀測(cè)數(shù)據(jù)本身的特點(diǎn),考慮能否擬合出一個(gè)最優(yōu)的矩陣作為轉(zhuǎn)移概率矩陣。本文將從這一角度出發(fā),著手研究帶有部分未知觀測(cè)數(shù)據(jù)且有約束條件的數(shù)據(jù)擬合問題。

1 主要結(jié)果以及證明

上面的最小二乘擬合問題,是具有N組觀測(cè)值,每組觀測(cè)值具有n2個(gè)觀測(cè)點(diǎn)的問題。在每組觀測(cè)值中有部分?jǐn)?shù)據(jù)是未知的,可以把這部分未知數(shù)據(jù)以及擬合參數(shù)都看做未知量,來進(jìn)行擬合。這是一個(gè)帶有約束條件的極值問題,用條件極值的方法不能求解,必須找到新的可行的方法。

同時(shí)這也是一個(gè)帶有絕對(duì)值的及附加條件的規(guī)劃問題?？紤]用求解規(guī)劃問題的方法來求解。而在做數(shù)據(jù)擬合的時(shí)候,不可能嚴(yán)格要求所有的觀測(cè)點(diǎn)都符合擬合函數(shù),但是希望盡可能多的點(diǎn)符合擬合函數(shù),或者離擬合函數(shù)的圖形盡可能的近,進(jìn)而也就希望各個(gè)觀測(cè)點(diǎn)到擬合函數(shù)圖形的距離之和為最小。可以考慮用下面的方法將以上的最小二乘擬合問題轉(zhuǎn)化為可以求解的線性規(guī)劃問題。

證明 設(shè)

于是得到下面的結(jié)論:

1)ωi1i2,…,in≥0,zi1i2,…,in≥0;

從而上述擬合問題可以轉(zhuǎn)化為如式(6)的規(guī)劃問題。

證明 在這里將n×n階矩陣看做具有n2個(gè)分量的向量即可,則每組數(shù)據(jù)有n2個(gè)觀測(cè)值,共有N組數(shù)據(jù),由引理1可以直接的轉(zhuǎn)化為以上的規(guī)劃問題。

定義1 若X∈Rn,f:D?Rn→Rl,α1,α2>0,α1+α2=1,任意X1,X2∈D,有f(α1X1+α2X2)≤α1f(X1)+α2f(X2),則稱f(X)為D上的凸函數(shù)[14]。

定義2 若f(X)為D上的凹函數(shù),則-f(X)為D上的凸函數(shù)。

式(10)的條件稱為庫(kù)恩-塔克條件,滿足庫(kù)恩塔克條件的點(diǎn)稱為庫(kù)恩-塔克點(diǎn),這些點(diǎn)顯然滿足所有的約束條件。其中f(X)表示f(X)的梯度。

則相應(yīng)的庫(kù)恩-塔克條件可以變?yōu)橄旅娴谋硎觥?/p>

引理2 若非線性規(guī)劃為凸規(guī)劃,則庫(kù)恩-塔克點(diǎn)一定為全局最優(yōu)點(diǎn)[15]。

引理3 設(shè)規(guī)劃P為凸規(guī)劃,則1)P的可行集為凸集;2)P的最優(yōu)解集合為凸集;3)P的任何局部最優(yōu)解為全集最優(yōu)解[14]。

經(jīng)過前面的分析,可以看出,對(duì)于非線性規(guī)劃問題如果能夠化為凸規(guī)劃,則庫(kù)恩-塔克點(diǎn)即為全局最優(yōu)解,從而可以得到下面的定理。

定理2 如果非線性規(guī)劃(7)滿足庫(kù)恩-塔克條件(12),則庫(kù)恩塔克點(diǎn)一定為全局最優(yōu)解。

證明 對(duì)于非線性規(guī)劃式(7)中的約束條件,如果為凹函數(shù)可以利用定義2的方法化為凸函數(shù)。而對(duì)于目標(biāo)函數(shù)可以令

其中,α1,α2>0,α1+α2=1。對(duì)于任意的

有

f(α1X1+α2X2)=α1f(X1)+α2f(X2)為凸函數(shù),進(jìn)而,總可以將非線性規(guī)劃式(7)化為凸規(guī)劃。根據(jù)引理2、引理3,如果非線性規(guī)劃式(7)滿足庫(kù)恩-塔克條件,則庫(kù)恩塔克點(diǎn)一定為全局最優(yōu)解。

2 仿真算例

現(xiàn)在看一個(gè)實(shí)際的例子,對(duì)于如式(1)的馬爾科夫跳變系統(tǒng)

x(k+1)=A(rk)x(k)+B(rk)u(k)

經(jīng)過3次觀測(cè)以后的概率轉(zhuǎn)移矩陣如式(16):

經(jīng)過前面的分析可以轉(zhuǎn)化為如下的規(guī)劃問題:

通過前面的討論,知道理論上只需求出庫(kù)恩-塔克點(diǎn)即可。這里給出利用LINGO軟件得出的結(jié)果為:a11=0.150 000 0,a12=0.400 000 0,a13=0.366 666 7,a21=0.416 666 6,a22=0.366 666 7,a23=0.366 666 7,a31=0.433 333 3,a32=0.233 333 4,a33=0.266 666 7。即擬合后的矩陣為:

3 結(jié) 論

本文從馬爾科夫跳變系統(tǒng)概率轉(zhuǎn)移矩陣觀測(cè)值有部分未知元素的實(shí)際情況出發(fā), 以觀測(cè)值為基礎(chǔ)來擬合出較好的概率轉(zhuǎn)移矩陣。 基于概率轉(zhuǎn)移矩陣列和為1的特點(diǎn), 這樣一個(gè)有部分元素未知又帶有約束條件的擬合問題顯然不是高斯最小二乘法能夠解決的。 為此,先將最小二乘法進(jìn)行改進(jìn), 轉(zhuǎn)化為規(guī)劃問題。 在馬爾科夫跳變系統(tǒng)參數(shù)估計(jì)中, 將轉(zhuǎn)移概率矩陣的每個(gè)觀測(cè)值看做一個(gè)向量, 所有的未知元素均看做決策變量, 再考慮到約束條件, 可以將擬合問題轉(zhuǎn)化為非線性規(guī)劃問題。 為了求解,將非線性規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃。 同時(shí)證明了在滿足庫(kù)恩-塔克條件的前提下,庫(kù)恩-塔克點(diǎn)一定為全局最優(yōu)解。

[ 1 ]王能超. 數(shù)值分析簡(jiǎn)明教程[M]. 北京:高等教育出版社, 2001:60-63.

[ 2 ]李穎,林洪生. 基于相對(duì)誤差的曲線最小二乘擬合[J]. 沈陽(yáng)師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2012,30(3):338-342.

[ 3 ]李念偉. 帶插值條件的最小二乘法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2009,39(14):88-93.

[ 4 ]管倩,喬冠峰. 基于遺產(chǎn)算法的最小二乘法的應(yīng)用[J]. 機(jī)械管理開發(fā), 2011(5):207-208.

[ 5 ]李成思. 基于相對(duì)誤差意義下的最小二乘法[J]. 數(shù)理統(tǒng)計(jì)與管理, 2003,22(4):36-40.

[ 6 ]XIONG Junlin, LAM J. Fixed-order robustH∞filter design for Markovian jump systems with uncertain probabilities[J]. IEEE T Signal Proces, 2006,54(4):1421-1430.

[ 7 ]ZHANG Lixian, BOUKAS E K. Stability and stabilization of Markovian jump linear systems with partly unknown transition probabilities[J]. Automatica, 2009(45):463-468.

[ 8 ]XIONG Junlin, LAM J, GAO Huijun, et al. On robust stabilization of Markovian jump systems with uncertain switching probabilities[J]. Automatica, 2005(41):897-903.

[ 9 ]ZHANG Lixian, BOUKAS E K.H∞control for discrete-time Markovian jump linear systems with partly unknown transition probabilities[J]. Int J Robust Nonlinear Control, 2008(19):868-883.

[10]ZHANG Lixian, BOUKAS E K, LAM J. Analysis and Synthesis of Markov Jump Linear Systems With Time-varying Delays and Partially Known Transition Probabilities[J]. IEEE T Automat Contr, 2008,53(10):2458-2464.

[11]ZHANG Lixian, BOUKAS E K. Discrete-time Markovian jump linear systems with partly unknown transition probabilities:H∞Filtering Problem[R]. AACC American, 2008:2272-2277.

[12]唐小我,曾勇,曹長(zhǎng)修. 市場(chǎng)預(yù)測(cè)中的馬爾科夫鏈轉(zhuǎn)移概率中的估計(jì)[J]. 電子科技大學(xué)學(xué)報(bào), 1994,23(6):643-648.

[13]葉丹,范泉涌. 轉(zhuǎn)移概論部分已知的Markov跳變系統(tǒng)魯棒H2控制[J]. 東北大學(xué)學(xué)報(bào):自然科學(xué)版, 2013,34(2):153-156.

[14]傅應(yīng)定,成孝予,唐應(yīng)輝. 最優(yōu)化理論與方法[M]. 北京:國(guó)防工業(yè)出版社, 2008:23-28.

[15]甘應(yīng)愛,田豐. 運(yùn)籌學(xué)[M]. 北京:清華大學(xué)出版社, 2005:171-174.

ImprovedleastsquaremethodbasedontheoryofprogrammingandapplicationinparametersestimatingofMarkovjumpingsystems

LI Ying, LIN Hongsheng, LIU Yan

(Department of Preparatory Course, Shenyang Institute of Engineering, Shenyang 110136, China)

The authors analyzed the limitations of the least squares of Gauss in parameters estimation for Markov jumping systems: Not able to solve directly the fitting problem with constraint conditions. But the elements for every columns in the transition probability matrix of Markov jumping systems should add up to one, while partly of the data of observations are unknown. According to the programming problem for the extreme value with constraint conditions, and the number of decision variables in the constraint conditions can be more than the number of decision variables in the objective function, the Markov jumping system parameter estimation problem could be turned into a nonlinear programming problem. Starting from solving the angle, the nonlinear programming problem is transformed into a convex programming, and gives a method into specific. In theory that the convex programming problem transformed in order to meet the conditions of the Kuhn-Tucker, Kuhn-Tucker point to the global optimal solution. Finally, a simulation example is given to illustrate the conclusions is rational.

convex programming; Markov jumping systems; conditions of Kuhn-Tucker; least square method; parameters estimating

2014-02-05。

遼寧省教育廳高等學(xué)校科學(xué)研究項(xiàng)目(L2012464); 沈陽(yáng)工程學(xué)院青年基金資助項(xiàng)目(LGQN-1308)。

李 穎(1962-),女,遼寧鞍山人,沈陽(yáng)工程學(xué)院教授。

1673-5862(2014)02-0172-06

O313.2

: A

10.3969/ j.issn.1673-5862.2014.02.009