运筹学多重最优解的最优值如何求（论文推荐邓兴升）

《测绘学报》

构建与学术的桥梁 拉近与权威的距离

权整体最小二乘EIO模型与算法

邓兴升¹

, 彭思淳¹, 游扬声²

1. 长沙理工大学交通运输工程学院, 湖南 长沙 410114; 2. 重庆大学土木工程学院, 重庆 400044

收稿日期：2017-01-12；修回日期：2017-05-10

基金项目：国家自然科学基金（41671498）；公路地质灾变预警空间信息技术湖南省工程实验室基金（KFJ150602）

第一作者简介：邓兴升(1971-), 男, 博士, 副教授, 研究方向为大地测量数据处理。E-mail：whudxs@163.com

摘要：构造了加权整体最小二乘EIO（errors-in-observations）模型，只改正独立观测值，观测值协因数阵最简洁，可克服EIV模型缺陷。基于EIO模型推导了参数估计和协因数阵精确迭代算法，实例结果正确，计算效率高。

关键词：加权整体最小二乘 EIO模型 参数估计 协因数阵 迭代算法

Weighted total least square adjustment EIO model and its algorithms

DENG Xingsheng¹, PENG Sichun¹, YOU Yangsheng²

1. School of Traffic and Transportation Engineering, Changsha University of Science & Technology, Changsha 410114, China;

2. School of Civil Engineering, Chongqing University, Chongqing 400044, China

Foundation support:The National Natural Science Foundation of China (No. 41671498); The Open Fund of Engineering laboratory of Spatial Information Technology of Highway Geological Disaster Early Warning in Hunan Province (No. KFJ150602)

First author:DENG Xingsheng (1971—), male, PhD, associate professor, majors in geodetic data processing.E-mail:whudxs@163.com.

Abstract: EIO (errors-in-observations) model is proposed for the weighted total least squares adjustment problem. The EIO model only corrects the independent observations. The observation cofactor matrix has the simplest structure. The flaw of EIV model is overcome. Based on the EIO model, the precise parameter estimation and cofactor matrix formulations are derived and proved by several examples, which show that the results are correct and the algorithm is efficient.

Key words: weight total least square (WTLS) errors-in-observations (EIO) model parameter estimation cofactor matrix iterative algorithm

一些学者认为整体最小二乘EIV模型系数矩阵A存在结构性问题^[1-4]，一是含有非随机的常数项被误改正；二是含有相同元素被分配不同改正数。针对A中部分变量随机的结构性问题，有人提出采用Partial-EIV模型^[4-6]，将矩阵分解以避免改正非随机项并缩小计算量。本文研究发现EIV模型结构性问题并不存在，结构性问题是协因数阵QA不正确引起的。EIV模型解与A的结构无关，A的元素可相关，可为常数，可为观测量的函数，其位置可以任意分布。许多算法^[7-9]均基于QA定权，但QA阶数是A中所有元素总数的平方，A元素较多时Q^A阶数过大，因此EIV模型在大数据量平差中迭代计算效率较低。由于EIV模型对矩阵A元素改正处理有缺陷，一些学者提出将观测向量与系数阵A中的随机元素统一至一个向量中进行处理^[10-12]，提出了TLS牛顿算法^[10]、结构化TLS算法^[11]、非典型EIV模型算法^[12]。本文提出WTLS平差EIO模型，它只对平差问题中的独立观测值进行改正，观测值协因数阵是最简洁的对角阵，适用于独立平差，推导了参数估计迭代公式。由于TLS解具有非线性特征，不能直接求得精确方差，为了获得更精确的精度信息，一些学者提出基于误差传播定律的协因数迭代算法^[13]，以及基于无味变换原理的非线性误差传播方法^[14]。前者是一种确定性方法，计算效率更高。本文基于EIO模型提出了QXX的精确迭代算法。

1 EIO模型1.1 函数模型

误差方程如下

(1)

式中，L、X、V都是列向量；L为m维观测向量；V是n维(n≥m)独立观测改正数向量；X是u维未知参数向量；A为未知参数X的m×u阶系数矩阵；B为改正数向量V的m×n阶系数矩阵，B=diag([∂f(L,X)/∂Li]₁m)= ivec(SBX B₀)，SB与B₀为常系数阵，ivec表示反拉直运算，由mn×1向量转换为m×n阶矩阵。式(1)由EIV模型演变而来。由EIV模型

(2)

将误差矩阵EA及e组成增广矩阵[EAe]，归类改写成一个系数矩阵B与独立观测值改正数向量V的矩阵乘积

(3)

式(3)反号即得式(1)。L和A的改正矩阵VL和VA与V的关系为

(4)

式中，SL和SA为设计系数矩阵。

1.2 随机模型

(5)

式中，l为n阶扩展观测值矩阵；V是l矩阵的改正数向量；σ₀²是单位权方差；Qll和P分别是l矩阵对应的协因数矩阵及权矩阵

(6)

式中，QL为观测向量L的协因数矩阵；QA为vec(V_A)的协因数矩阵。

2 参数估计2.1 公式推导

目标方程为V^TPV= min s.t.L－AX－BV=0，构造拉格朗日极值方程

(7)

矩阵A中不含改正数V。由式(3)可知BV=EAX－e。由Φ分别对V、X求偏导，得

(8)

(9)

设=A VA，联合式(1)、式(8)—式(9)可得

(10)

式(10)虽可求V、X、K混合矩阵，但需对n m u阶矩阵求逆。由式(8)得

(11)

将式(11)代入式(1)得

(12)

设

BP^－1B^T)^－1，则

(13)

将式(13)代入式(9)，设

L VAX，则X的WTLS解为

(14a)

或

(14b)

其形式与经典LS解和文献[15]算法一致。由式(13)求K矩阵，并代入式(11)求矩阵V

(15)

本文算法与文献[15]算法之间不同点对比见表 1。

表 1 本文算法与文献[15]算法对比Tab. 1 Comparisons between FANG algorithm^[15]and the proposed algorithm

项目	文献[15]算法	本文算法
函数模型	EIV、式(2)	EIO、式(1)
随机模型	式(6)、QA、QL	式(5)、Qll
Q阶数	m(u 1)×m(u 1)	n×n
Q特征	非主对角矩阵	主对角矩阵
V定义	V=[vec(EA)e]T	V=[vl1vl2…vln]T
V阶数	m(u 1)×1	n×1
B定义	B=[XT⊗In－In]	B=diag([∂f/∂Li]1m)
B阶数	m×m(u 1)	m×n
平差方法	相关平差	独立平差
QXX	近似公式	迭代精确解
计算效率	小数据量无差异	大数据量时更优

表选项

2.2 迭代步骤

(1) 线性化形成误差方程式(1);

(2) 设置X初值，改正数V初值为0；矩阵的初值为A；

(3) 将B、P、A、、L代入式(14)—式(15)中，求X、V；

(4) 将X、V的新值用于更新B、中对应元素；

(5) 重复步骤3—4，‖[XV]i 1－[XV]i‖≤ε(10^－18)结束。

3 EIO模型精度评定3.1 近似精度评定

单位权方差

，其中m是观测向量L的阶数；u是参数X的阶数；V是n阶观测改正数向量，由式(15)计算；P是n阶权矩阵。

由=L e BV= BV得

QXX为

(16)

3.2 QXX迭代精确解

设X、L、vec(A)构成(u m mu)×1阶矩阵Y，其协因数阵为

(17)

式中，A与L不相关，即QLA=QAL=0。若QL、QA已知，则QY为

(18)

QY通过迭代求解，QY⁰初值虽可设置为0，但QX初值可由式(16)计算，QL与QA初值由式(6)计算，其余协因数初值设为0。J为Jacobi矩阵

(19)

式中，因不相关JLX=JLA=JAX=JAL=0；JLL为m阶单位矩阵；JAA为mu阶单位矩阵；

；

。求偏导时需对逆矩阵求导，由d(AA^－1)= d(I)=0得d(A^－1)=－A^－1d(A)A^－1。

设

_i求偏导得

(20)

式中，由

由B=SB·X B₀得

由式(14a)对l_i求偏导得

(21)

式中，

。

由式(14a)对a_ij求偏导得

(22)

式中，

。

符号含义：c为规范化单位向量，u阶ci=[0 … 0 1 0 … 0]^T，第i行为1，其余为0；m阶cj=[0 … 0 1 0 … 0]^T，第j行为1，其余为0；cij为m×u阶矩阵，表示第i行第j列为1，其余为0。

迭代算法求QX精确解的步骤如下：

(1) 设置QY⁰初值，设置容许误差ε(10^－18)及迭代次数Tn(100)；

(2) 计算偏导数及Jacobi矩阵J；

(3) 以QY(k 1)=JQY(k)J^T更新QY值；

(4) 如果||QY(k 1)－QY(k)||>ε重复步骤3，满足收敛条件步骤5；

(5) 从QY中提取QX。

4 实例计算4.1 直线拟合

本例引自文献[16]直线拟合实例，数据见原文。直线方程为y v_y=k(x v_x) b，误差方程形式为

^[16]真值k为-0.480 533 407，b为5.479 910 22；本文算法迭代8次，结果与真值及文献[6, 17]一致，但文献[16]算法迭代585次，效率较低。单位权方差δ₀²为1.483 294 149 316；δk²近似解为0.004 987 222 5，δb²近似解为0.129 058 064，与文献[6, 17]结果一致。迭代11次，精确解δk²为0.004 924 075 2，δb²为0.126 413 995 5。

4.2 平面四参数解算

本实例来自文献[17]，坐标参见原文表4，权数据参见原文式(39)。平面四参数坐标转换模型为

式中，(x_i, y_i)为源坐标；(X_i, Y_i)为目标坐标；x₀和y₀为平移参数；a和b为旋转参数。误差方程形式为

x₀为29.770 065 573，y₀为19.717 128 429 7，a为0.999 884 750 16，b为-6.693 26e-5；本文算法迭代3次结果与其一致。单位权方差δ₀²为0.151 578 658 1；近似解δx₀²为0.005 440 646 1，δy₀²为0.006 942 701 9，δa²为7.0e-9，δb²为5.5 e-9，与文献[6, 17]一致。迭代5次精确解δx₀²为0.005 440 702 56，δy₀²为0.006 942 689 54，δa²为6.954 64e-9，δb²为5.485 56e-9。

5 结论

EIO模型只改正独立观测值，协因数阵最简洁，适用于大规模独立平差，可克服EIV模型缺陷。基于EIO模型的参数估计和协因数阵精确迭代算法，实例结果正确，计算效率高。

【引文格式】邓兴升, 彭思淳, 游扬声. 加权整体最小二乘EIO模型与算法[J]. 测绘学报，2019，48(7)：926-930. DOI: 10.11947/j.AGCS.2019.20170021

权威 | 专业 | 学术 | 前沿

微信投稿邮箱 | song_qi_fan@163.com

,