基于规划理论的最小二乘法改进及其在Markov跳变系统参数估计中的应用

李 颖, 林洪生, 刘 严

(沈阳工程学院 基础教学部, 沈阳 110136)

基于规划理论的最小二乘法改进及其在Markov跳变系统参数估计中的应用

李 颖, 林洪生, 刘 严

(沈阳工程学院 基础教学部, 沈阳 110136)

分析了高斯最小二乘法在Markov跳变系统参数估计中的局限性,即不能够直接解决带有约束条件的拟合问题。而Markov跳变系统的转移概率矩阵要满足列和为1的约束,同时在多次观测值中有部分数据是未知的。根据规划问题为带有约束条件的极值问题,且约束条件中决策变量的个数可以多于目标函数中决策变量个数的特点,将Markov跳变系统参数估计问题转化为非线性规划问题。从求解的角度出发,将非线性规划问题转化为凸规划,同时给出了具体的转化方法。从理论上说明了转化后的凸规划问题在满足库恩-塔克条件的前提下,库恩-塔克点一定为全局最优解。最后给出仿真算例,说明结论的合理性。

凸规划; Markov跳变系统; 库恩-塔克条件; 最小二乘法; 参数估计

0 引 言

高斯最小二乘法是工程问题常用方法, 广泛应用于科学技术各个领域。 可以解决观测数据均为已知且没有约束条件的数据拟合问题, 通常将其转化为多元函数的极值问题, 采用微分法进行求解, 同时这组解是惟一的[1]。 很多文献对最小二乘法做了不同的改进, 比如利用插值方法的改进、为提高精度考虑到的相对误差的改进、基于遗传算法的改进[2-5]。 但是在处理某些工程问题时可能会遇到有部分观测数据未知, 且带有约束条件的数据拟合问题, 高斯最小二乘法对于这类数据拟合问题就无法解决了。

例如下面给出的一个马尔科夫跳变系统:

其中:x(k)为n维状态向量;u(k)为n维可控输入;rk为马尔科夫过程,满足式(2),

由于各种外界条件的限制,每次观测后得到的转移概率矩阵未知元素可能处于不同位置,但是对应于同一未知的元素相差不多,且满足矩阵的列元素之和为1。根据观测数据本身的特点,考虑能否拟合出一个最优的矩阵作为转移概率矩阵。本文将从这一角度出发,着手研究带有部分未知观测数据且有约束条件的数据拟合问题。

1 主要结果以及证明

上面的最小二乘拟合问题,是具有N组观测值,每组观测值具有n2个观测点的问题。在每组观测值中有部分数据是未知的,可以把这部分未知数据以及拟合参数都看做未知量,来进行拟合。这是一个带有约束条件的极值问题,用条件极值的方法不能求解,必须找到新的可行的方法。

同时这也是一个带有绝对值的及附加条件的规划问题。考虑用求解规划问题的方法来求解。而在做数据拟合的时候,不可能严格要求所有的观测点都符合拟合函数,但是希望尽可能多的点符合拟合函数,或者离拟合函数的图形尽可能的近,进而也就希望各个观测点到拟合函数图形的距离之和为最小。可以考虑用下面的方法将以上的最小二乘拟合问题转化为可以求解的线性规划问题。

证明 设

于是得到下面的结论:

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

从而上述拟合问题可以转化为如式(6)的规划问题。

证明 在这里将n×n阶矩阵看做具有n2个分量的向量即可,则每组数据有n2个观测值,共有N组数据,由引理1可以直接的转化为以上的规划问题。

定义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上的凸函数[14]。

定义2 若f(X)为D上的凹函数,则-f(X)为D上的凸函数。

式(10)的条件称为库恩-塔克条件,满足库恩塔克条件的点称为库恩-塔克点,这些点显然满足所有的约束条件。其中f(X)表示f(X)的梯度。

则相应的库恩-塔克条件可以变为下面的表述。

引理2 若非线性规划为凸规划,则库恩-塔克点一定为全局最优点[15]。

引理3 设规划P为凸规划,则1)P的可行集为凸集;2)P的最优解集合为凸集;3)P的任何局部最优解为全集最优解[14]。

经过前面的分析,可以看出,对于非线性规划问题如果能够化为凸规划,则库恩-塔克点即为全局最优解,从而可以得到下面的定理。

定理2 如果非线性规划(7)满足库恩-塔克条件(12),则库恩塔克点一定为全局最优解。

证明 对于非线性规划式(7)中的约束条件,如果为凹函数可以利用定义2的方法化为凸函数。而对于目标函数可以令

其中,α1,α2>0,α1+α2=1。对于任意的

有

f(α1X1+α2X2)=α1f(X1)+α2f(X2)为凸函数,进而,总可以将非线性规划式(7)化为凸规划。根据引理2、引理3,如果非线性规划式(7)满足库恩-塔克条件,则库恩塔克点一定为全局最优解。

2 仿真算例

现在看一个实际的例子,对于如式(1)的马尔科夫跳变系统

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

经过3次观测以后的概率转移矩阵如式(16):

经过前面的分析可以转化为如下的规划问题:

通过前面的讨论,知道理论上只需求出库恩-塔克点即可。这里给出利用LINGO软件得出的结果为: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 结 论

本文从马尔科夫跳变系统概率转移矩阵观测值有部分未知元素的实际情况出发, 以观测值为基础来拟合出较好的概率转移矩阵。 基于概率转移矩阵列和为1的特点, 这样一个有部分元素未知又带有约束条件的拟合问题显然不是高斯最小二乘法能够解决的。 为此,先将最小二乘法进行改进, 转化为规划问题。 在马尔科夫跳变系统参数估计中, 将转移概率矩阵的每个观测值看做一个向量, 所有的未知元素均看做决策变量, 再考虑到约束条件, 可以将拟合问题转化为非线性规划问题。 为了求解,将非线性规划问题转化为凸规划。 同时证明了在满足库恩-塔克条件的前提下,库恩-塔克点一定为全局最优解。

[ 1 ]王能超. 数值分析简明教程[M]. 北京:高等教育出版社, 2001:60-63.

[ 2 ]李颖,林洪生. 基于相对误差的曲线最小二乘拟合[J]. 沈阳师范大学学报:自然科学版, 2012,30(3):338-342.

[ 3 ]李念伟. 带插值条件的最小二乘法[J]. 数学的实践与认识, 2009,39(14):88-93.

[ 4 ]管倩,乔冠峰. 基于遗产算法的最小二乘法的应用[J]. 机械管理开发, 2011(5):207-208.

[ 5 ]李成思. 基于相对误差意义下的最小二乘法[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]唐小我,曾勇,曹长修. 市场预测中的马尔科夫链转移概率中的估计[J]. 电子科技大学学报, 1994,23(6):643-648.

[13]叶丹,范泉涌. 转移概论部分已知的Markov跳变系统鲁棒H2控制[J]. 东北大学学报:自然科学版, 2013,34(2):153-156.

[14]傅应定,成孝予,唐应辉. 最优化理论与方法[M]. 北京:国防工业出版社, 2008:23-28.

[15]甘应爱,田丰. 运筹学[M]. 北京:清华大学出版社, 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。

辽宁省教育厅高等学校科学研究项目(L2012464); 沈阳工程学院青年基金资助项目(LGQN-1308)。

李 颖(1962-),女,辽宁鞍山人,沈阳工程学院教授。

1673-5862(2014)02-0172-06

O313.2

: A

10.3969/ j.issn.1673-5862.2014.02.009