Message Board

Respected readers, authors and reviewers, you can add comments to this page on any questions about the contribution, review,        editing and publication of this journal. We will give you an answer as soon as possible. Thank you for your support!

Name
E-mail
Phone
Title
Content
Verification Code
Volume 43 Issue 10
Oct.  2018
Turn off MathJax
Article Contents

XIE Jian, LONG Sichun, LI Li, LI Bochao. An Aggregate Function Method for Weighted Total Least Squares with Inequality Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(10): 1526-1530. doi: 10.13203/j.whugis20160507
Citation: XIE Jian, LONG Sichun, LI Li, LI Bochao. An Aggregate Function Method for Weighted Total Least Squares with Inequality Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(10): 1526-1530. doi: 10.13203/j.whugis20160507

An Aggregate Function Method for Weighted Total Least Squares with Inequality Constraints

doi: 10.13203/j.whugis20160507
Funds:

The National Natural Science Foundation of China 41704007

The National Natural Science Foundation of China 41474014

Scientific Research Fund of Hunan Provincial Education Department 16C0632

the Doctoral Scientific Foundation of Hunan University of Science and Technology E51673

Open Fundation of Hunan Province Key Laboratory of Coal Resources Clean-Utilization and Mine Environment Protection, Hunan University of Science and Technology E21610

Open Fundation of Hunan Province Key Laboratory of Coal Resources Clean-Utilization and Mine Environment Protection, Hunan University of Science and Technology E21504

More Information
  • Author Bio:

    XIE Jian, PhD, specializes in surveying adjustment and data processing. E-mail: hsiejian841006@163.com

  • Received Date: 2017-05-31
  • Publish Date: 2018-10-05
  • When the variance-covariance matrix of the error is fairly symmetric and positively definite, parameter estimation and accuracy assessment of weighted total least squares adjustment with inequality constraints(ICWTLS) are investigated in this paper. First, the problem of minimizing the residual sum of squares are converted to an optimization problem with only the model parameters under the total least squares, and all the inequality constraints are transformed into an equivalent aggregate constraint. Accordingly, the ICWTLS problem is converted to unconstrained optimization problem by a penalty function approach and is then solved by BFGS optimization method. Then, the observation equation and constraints function are expanded to the first order Taylor series and the linear approximation between the solution and observations is derived as well as the approximate dispersion matrix of the solution under the variance propagation law. Finally, a numerical simulation is given to indicate the validity and feasibility of this method.
  • [1] Peng J H, Zhang H P, Shong S L, et al. An Aggregate Constraint Method for Inequality-Constrained Least Squares Problems[J]. Journal of Geodesy, 2006, 79(12):705-713 doi:  10.1007/s00190-006-0026-z
    [2] Mahboub V, Sharifi M A. On Weighted Total Least-Squares with Linear and Quadratic Constraints[J]. Journal of Geodesy, 2013, 87:279-286 doi:  10.1007/s00190-012-0598-8
    [3] Zhu J J, Santerre R, Chang X W. A Bayesian Method for Linear Inequality Constrained Adjustment and Its Application to GPS Positioning[J]. Journal of Geodesy, 2005, 78(9):528-534 doi:  10.1007/s00190-004-0425-y
    [4] 戴吾蛟, 朱建军. GPS建筑物震动变形监测中的单历元算法[J].武汉大学学报·信息科学版, 2007, 32(3):234-237 http://ch.whu.edu.cn/CN/abstract/abstract1844.shtml

    Dai Wujiao, Zhu Jianjun. Single Epoch Ambiguity Resolution in Structure Monitoring Using GPS[J]. Geomatics and Information Science of Wuhan University, 2007, 32(3):234-237 http://ch.whu.edu.cn/CN/abstract/abstract1844.shtml
    [5] Rao C R, Toutenburg H. Linear Model:Least Squares and Alternatives[M]. Heidelberg:Springer, 2005
    [6] Lu G, Krakiwsky E J, Lachapelle G. Application of Inequality Constraint Least Squares to GPS Navigation Under Selective Availability[J]. Manuscripta Geodaetica, 1993, 18:124-130
    [7] Liew C K. Inequality Constrained Least-Squares Estimation[J]. Journal of the American Statistical Association, 1976, 71(355):746-751 doi:  10.1080/01621459.1976.10481560
    [8] Roese-Koerner L, Devaraju B, Sneeuw N, et al. A Stochastic Framework for Inequality Constrained Estimation[J]. Journal of Geodesy, 2012, 86(11):1005-1018 doi:  10.1007/s00190-012-0560-9
    [9] Xu P L, Liu J N, Shi C. Total Least Squares in Partial Errors-in-Variables Models:Algorithm and Statistical Analysis[J]. Journal of Geodesy, 2012, 86(8):661-675 doi:  10.1007/s00190-012-0552-9
    [10] Shen Y Z, Li B F, Chen Y. An Iterative Solution of Weighted Total Least-Squares Adjustment[J]. Journal of Geodesy, 2011, 85(4):229-238 doi:  10.1007/s00190-010-0431-1
    [11] Schaffrin B, Felus Y A. An Algorithmic Approach to the Total Least-Squares Problem with Linear and Quadratic Constraints[J]. Studia Geophysica Geodaetica, 2009, 53(1):1-16 doi:  10.1007/s11200-009-0001-2
    [12] Fang X. Weighted Total Least Squares:Necessary and Sufficient Conditions, Fixed and Random Parameters[J]. Journal of Geodesy, 2013, 87(8):733-749 doi:  10.1007/s00190-013-0643-2
    [13] de Moor B. Total Linear Least Squares with Inequality Constraints[R]. ESAT-SISTA Report 1990-02, Department of Electrical Engineering, Katholieke Universiteit Leuven, Belgium, 1990
    [14] Zhang S L, Tong X H, Zhang K. A Solution to EIV Model with Inequality Constraints and Its Geodetic Applications[J]. Journal of Geodesy, 2013, 87(1):23-28 doi:  10.1007/s00190-012-0575-2
    [15] Fang X. On Non-combinatorial Weighted Total Least Squares with Inequality Constraints[J]. Journal of Geodesy, 2014, 88(8):805-816 doi:  10.1007/s00190-014-0723-y
    [16] 曾文宪, 方兴, 刘经南, 等.附有不等式约束的加权整体最小二乘算法[J].测绘学报, 2014, 43(10):1013-1018 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201410005.htm

    Zeng Wenxian, Fang Xing, Liu Jingnan, et al. Weighted Total Least Squares Algorithm with Inequality Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(10):1013-1018 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201410005.htm
    [17] Zeng W X, Liu J N, Yao Y B. On Partial Errors-in-Variables Models with Inequality Constraints of Parameters and Variables[J]. Journal of Geodesy, 2015, 89(2):111-119 doi:  10.1007/s00190-014-0775-z
    [18] 王乐洋, 许才军, 鲁铁定.病态加权总体最小二乘平差的岭估计解法[J].武汉大学学报·信息科学版, 2010, 35(11):1346-1350 http://ch.whu.edu.cn/CN/Y2010/V35/I11/1346

    Wang Leyang, Xu Caijun, Lu Tieding. Ridge Estimation Method in Ill-posed Weighted Total Least Squares Adjustment[J]. Geomatics and Information Science of Wuhan University, 2010, 35(11):1346-1350 http://ch.whu.edu.cn/CN/Y2010/V35/I11/1346
  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Tables(2)

Article Metrics

Article views(1352) PDF downloads(406) Cited by()

Related
Proportional views

An Aggregate Function Method for Weighted Total Least Squares with Inequality Constraints

doi: 10.13203/j.whugis20160507
Funds:

The National Natural Science Foundation of China 41704007

The National Natural Science Foundation of China 41474014

Scientific Research Fund of Hunan Provincial Education Department 16C0632

the Doctoral Scientific Foundation of Hunan University of Science and Technology E51673

Open Fundation of Hunan Province Key Laboratory of Coal Resources Clean-Utilization and Mine Environment Protection, Hunan University of Science and Technology E21610

Open Fundation of Hunan Province Key Laboratory of Coal Resources Clean-Utilization and Mine Environment Protection, Hunan University of Science and Technology E21504

  • Author Bio:

Abstract: When the variance-covariance matrix of the error is fairly symmetric and positively definite, parameter estimation and accuracy assessment of weighted total least squares adjustment with inequality constraints(ICWTLS) are investigated in this paper. First, the problem of minimizing the residual sum of squares are converted to an optimization problem with only the model parameters under the total least squares, and all the inequality constraints are transformed into an equivalent aggregate constraint. Accordingly, the ICWTLS problem is converted to unconstrained optimization problem by a penalty function approach and is then solved by BFGS optimization method. Then, the observation equation and constraints function are expanded to the first order Taylor series and the linear approximation between the solution and observations is derived as well as the approximate dispersion matrix of the solution under the variance propagation law. Finally, a numerical simulation is given to indicate the validity and feasibility of this method.

XIE Jian, LONG Sichun, LI Li, LI Bochao. An Aggregate Function Method for Weighted Total Least Squares with Inequality Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(10): 1526-1530. doi: 10.13203/j.whugis20160507
Citation: XIE Jian, LONG Sichun, LI Li, LI Bochao. An Aggregate Function Method for Weighted Total Least Squares with Inequality Constraints[J]. Geomatics and Information Science of Wuhan University, 2018, 43(10): 1526-1530. doi: 10.13203/j.whugis20160507
  • 在测量数据处理领域,根据观测对象的几何或物理特性,往往能建立起参数间的不等式约束关系。合理地利用这些先验信息,能提高平差结果的精度和可靠性[1]。不等式约束最小二乘平差在GPS数据处理[2-3]、变形分析[4]领域得到成功应用。不等式约束最小二乘平差算法主要包括规划类算法、椭圆约束法[5]、最小距离法[6]、贝叶斯方法[3]、凝聚函数法[1]等。参数精度评定的方法主要有贝叶斯方法[3]、将有效约束视为等式约束[7]、凝聚函数法[1]和Monte-Carlo模拟法[8]

    由于能考虑系数阵元素含误差的情况,变量含误差(errors-in-variables, EIV)模型成为近年来的研究热点[9-12]。当参数间含有不等式约束时,就形成了不等式约束EIV(inequality cvonstrained EIV, ICEIV)模型。de Moor给出了不等式约束TLS问题的KKT条件,并转化为广义线性补问题采用组合式方法求解[13]。Zhang等采用穷举搜索求解不等式约束EIV模型,其计算量随约束数的增加呈指数增长,且未考虑不等权和相关观测量[14]; Fang提出了不等式约束加权整体最小二乘(weighted total least squares with inequality constraints, ICWTLS)问题,给出了最优解的一阶必要和二阶充分条件,将ICWTLS转换为标准形式的约束最优化问题,采用起作用集方法和SQP方法求解[15]; Zeng等给出了不等式约束部分EIV(inequality constrained partial EIV, ICPEIV)模型,转化为非线性约束最优化问题采用罚函数法求解[16, 17], 当约束同时包含待求参数和系数阵元素时,将ICPEIV模型转化为线性补(linear complementarity problem, LCP)问题求解,并得到了解的近似精度。

    Fang的算法基于最优化方法,未考虑解的精度,而Zeng等的方法没有考虑系数阵元素与右端项相关的情况。本文将所有的不等式约束转换成一个等价的凝聚约束函数,将不等式约束加权整体最小二乘平差转换成等式约束非线性最优化问题,引入乘子罚函数策略进一步表达成无约束非线性规划问题,采用BFGS算法求解。推导了不等式约束加权整体最小二乘解与观测向量的一阶线性近似函数关系,采用协方差传播律得到了解的近似方差。并用数值实例对该方法进行了验证。

  • 不等式约束加权整体最小二乘平差模型的函数模型为[17]

    式中,yey分别表示n维观测向量和误差向量;AEA表示n×u维的设计矩阵和误差矩阵;x表示u维参数向量;G表示s×u的约束矩阵;W表示相应的s维常数向量。将约束矩阵按行表达成G=[g1  g2gs]T,其中,giT=[gi1  gi2giu]是G的第i行(i=1, 2…s)。W=[w1  w2ws]T表示约束右端项。式(2)可以写成gi(x)=giTx-wi

    相应的随机模型为:

    式中,QAAQyy表示nu×nu系数阵元素的协因数阵和n×n观测值协因数阵;QAy=QyAT表示nu×n的系数阵元素和观测值向量的互协因数阵;Qe是所有随机误差向量的对称正定协因数矩阵;σ02为单位权方差。式(1)-(4)的最优解应使所有随机误差的平方和最小,且满足不等式约束条件,即

    式(5)中极小化函数的变量是eAey,而约束条件中的变量是待求参数x。为了使最小化函数和约束条件中的变量一致,首先不考虑不等式约束条件,函数模型式(1)和随机模型在整体最小二乘准则下,组成Lagrange目标函数为:

    分别对xeλ求偏导,并令其值为0,最优解的Euler-Lagrange必要条件为[15]

    式中,${\mathit{\boldsymbol{\hat x}}}$、${\mathit{\boldsymbol{\hat \lambda }}}$分别表示参数和Lagrange乘子的估值;${\mathit{\boldsymbol{\tilde e}}}$表示观测误差的预测值。并且令$\mathit{\boldsymbol{\hat B = }}\left[ {{{\mathit{\boldsymbol{\hat x}}}^{\rm{T}}} \otimes {\mathit{\boldsymbol{I}}_n}, - {\mathit{\boldsymbol{I}}_n}} \right]$,由式(8)可以得到:

    代入式(9),则有:

    将式(11)重新代入式(10)得:

    根据式(12),可以得到整体最小二乘准则函数的另一种形式如下:

    因此,由式(13)可以得到和式(5)等价的约束非线性最优化问题:

    式(14)中极小化目标函数和约束条件仅含待估参数,是一个典型的非线性最优化问题。可以采用最优化理论与方法中的积极约束法、序列二次规划算法、牛顿法、拟牛顿法等计算。但这些方法都基于迭代策略,不能得到解与观测值之间的函数关系,难以获得解的统计性质。因此,采用凝聚函数法来解式(14)并推导解的统计性质。

  • 在最优化理论与方法中,处理不等式约束非线性最优化问题的一种策略是将其转换为相应的等式约束最优化问题求解。凝聚函数法是将多个不等式约束合并成一个等价的凝聚约束函数,然后用拉格朗日乘子迭代法求解。根据文献[1]的结论,式(2)可以转换为如下的凝聚约束函数:

    式中,p是趋向于无穷大的正数,在计算中根据计算精度和计算效率的要求,一般取p=106。联合式(14)、式(15),不等式约束的加权整体最小二乘平差模型等价于求以下等式约束的加权整体最小二乘平差模型:

    式(16)是一个附有等式约束的非线性最优化问题,它的解可以通过极小化如下的拉格朗日目标函数得到:

    其中,α是等式约束对应的拉格朗日乘子,是一个标量。当式(17)不收敛的情况下,可以在此目标函数的基础上加入一个二次惩罚项,得到一个新的最小化目标函数:

    式中,c是一个充分大的正常数,称为罚因子,可取c=106。其作用是:当gp(x)≠0时施以惩罚。在迭代计算过程中,α通过下式更新:

    实际运算中,初值可以取α0=0,p=c=106,可以取相应的不等式约束最小二乘解作为迭代初值,当‖xk+1-xk‖≤ε(ε是迭代终止阈值,可取ε=10-6)时,停止迭代。然后计算▽Φ(x, α),若▽Φ(x, α)较大,根据式(19)计算新的α值,迭代直到‖▽Φ(x, α)‖也满足限差,最终得到不等式约束加权整体最小二乘解。由于拟牛顿算法解非线性规划问题具有较快的收敛速度,且无需求解目标函数的Hesse矩阵,近似的二阶校正公式更新规则简单,从而得到广泛应用。本文采用目前最流行有效的拟牛顿算法BFGS方法来求解无约束非线性最优化问题。

  • 式(16)是关于参数的非线性等式约束平差模型,为了得到解的近似精度,需要将目标函数做线性近似处理。设参数x可以表示成它的近似值和改正数之和,即x=x0+Δx,注意,经过非线性平差有限次迭代计算后x0无限趋近于不等式约束加权整体最小二乘解${{\hat x}_{{\rm{IC}}}}$,Δx趋向于0。且xΔx具有相同的方差,则式(1)可以表示为[18]

    将式(20)展开,并忽略二阶微小量EAΔx,则式(20)可以重新表示为:

    令:

    e′=EAx0-eyy′=y-Ax0,则式(21)可以写成:

    由于EAx0-ey=Ke,根据协方差传播律有:

    将凝聚约束函数式(15)在x0处线性化,有:

    联立式(22)与式(25),组成只含有一个等式约束的线性最小二乘平差模型,参数Δx的协因数矩阵可以表示为:

    式中,Naa=ATQe-1′ANcc=CTNaa-1C是一个常数;矩阵K的元素用最终迭代解${{\mathit{\boldsymbol{\hat x}}}_{{\rm{IC}}}}$代替。单位权方差的有偏估值近似写成:

    协因数矩阵式(26)与文献[1]相比较完全一致。由于加权整体最小二乘模型线性化过程中忽略了二阶项的影响,且凝聚函数只有当p趋向无穷大时才与不等式约束等价,所以,式(26)是不等式约束加权整体最小二乘的近似协因数估值。对于单位权方差式(27),文献[1]考虑了偏差项,而本文是把不等式约束加权整体最小二乘平差模型近似成等式约束的非线性平差模型,然后一阶线性近似成附有等式约束的间接平差模型来评定参数的精度。

  • 算例引自文献[1],观测方程(1)和约束条件(2)中的AyG1w1表 1所示。区间约束条件为-0.1≤xi≤2(i=1, 2, 3, 4)。设系数阵元素和右端向量的随机误差都是独立同分布,即Qe=I25为25阶单位矩阵。首先,采用二次规划方法计算相应的不等式约束最小二乘解:

    Ay
    0.950 10.762 00.615 30.405 70.057 8
    0.231 10.456 40.791 90.935 40.352 8
    0.606 80.018 50.921 80.916 90.813 1
    0.485 90.821 40.738 20.410 20.009 8
    0.891 20.444 70.176 20.893 60.138 8
    G1w1
    0.202 70.272 10.746 70.465 90.525 1
    0.198 70.198 80.445 00.418 60.202 6
    0.603 70.015 20.931 80.846 20.672 1

    Table 1.  A, y, G1, w1 of Observation Vector(1), Constraints Condition(2)

    然后将上述不等式约束最小二乘解作为迭代初始值,计算相应的不等式约束整体最小二乘解。比较文献[17]提出的有效集方法、序列二次规划算法以及文献[16]的穷举搜索法和本文提出的凝聚函数法,数值计算结果如表 2所示。

    有效集方法序列二次规划穷举搜索法凝聚函数法
    ${{\hat x}_1}$-0.100 000-0.100 000-0.100 000-0.099 991
    ${{\hat x}_2}$-0.100 000-0.100 000-0.100 000-0.100 003
    ${{\hat x}_3}$0.168 5470.168 5470.168 5000.168 561
    ${{\hat x}_4}$0.399 7770.399 7770.399 8000.399 765
    ${{\hat e}^{\rm{T}}}\mathit{\boldsymbol{P}}\hat e$0.139 7370.139 7370.139 7420.139 741

    Table 2.  The Solutions of Different Algorithms and the Residuals

    采用有效集方法外部迭代3次,内部迭代平均8次;序列二次规划算法外部迭代4次;内部迭代平均4次,而穷举搜索法外部迭代2 048次,内部迭代平均23次。采用凝聚函数方法,取p=c=105,经过9次迭代就能得到上述解,相应的目标函数梯度为:

    ▽Φ(x, α)‖满足阈值,停止迭代,可见本文的凝聚约束函数目标函数采用BFGS算法具有较快的收敛速度。

    计算凝聚函数在最优解处对参数x的梯度值为:

    根据式(27)得到单位权方差的有偏估计量为:σ02=0.069 9。根据式(26)可以得到不等式约束整体最小二乘解的近似协因数矩阵为:

    在运用凝聚函数法进行计算时,如果p取值过大,采用普通不等式约束最小二乘解作为初值进行计算时,容易出现不收敛的情况,并且随着p值的增大计算量会显著增加,可以根据精度和计算效率选取合适的p值。根据计算结果可以看出,解算值并不是严格满足所有不等式约束,这是由于p值是有限值时,凝聚函数并不是完全等价于最大的不等式约束。前面两种方法的结果在小数点后前6位都相同,凝聚函数法也能得到接近一致的结果。这说明凝聚函数法求解不等式约束的加权整体最小二乘问题是可行的。

  • 本文提出了一般权矩阵情形下的不等式约束加权整体最小二乘模型的计算方法和近似精度评定公式。对于不等式约束加权整体最小二乘平差模型,且权矩阵为一般对称正定矩阵的情形,将残差加权平方和最小准则先转化成仅含有参数的非线性目标函数极小化问题,并将所有不等式约束表达成一个近似的凝聚等式约束,构造出无约束拉格朗日目标函数,采用非线性最优化BFGS算法得到不等式约束加权整体最小二乘平差的解。数值实例结果表明,该方法能收敛到最优解,且具有较快的收敛速度。

Reference (18)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return