﻿ 一种基于改进外点法的多项式拟合解法
 文章快速检索 高级检索
 大地测量与地球动力学  2019, Vol. 39 Issue (1): 57-60  DOI: 10.14075/j.jgg.2019.01.011

### 引用本文

WU Tong, ZHANG Yangyang, SUN Yanyan, et al. A Polynomial Fitting Method Based on Improved Exterior Point Method[J]. Journal of Geodesy and Geodynamics, 2019, 39(1): 57-60.

### 第一作者简介

WU Tong, postgraduate, majors in modern geodetic data processing, E-mail:dbdxchwt@163.com.

### 文章历史

1. 东北大学资源与土木工程学院，沈阳市文化路3号巷11号，110819

1 相关概念 1.1 多项式拟合模型

 $\quad \quad \left[ \begin{gathered} {y_1} + {e_{{y_1}}} \hfill & {y_2} + {e_{{y_2}}} \hfill & ... \hfill & {y_n} + {e_{{y_n}}} \hfill \end{gathered} \right]^{\rm{T}} = \\ \left[ \begin{gathered} 1&{x_1} + {e_{{x_1}}}& ({x_1} + {e_{{x_1}}}{)^2}&...& ({x_1} + {e_{{x_1}}}{)^m} \hfill \\ 1&{x_2} + {e_{{x_2}}}& ({x_2} + {e_{{x_2}}}{)^2}&...& ({x_2} + {e_{{x_2}}}{)^m} \hfill \\ ...&...&...&...&... \hfill \\ 1&{x_n} + {e_{{x_n}}}& ({x_n} + {e_{{x_n}}}{)^2}&...& ({x_n} + {e_{{x_n}}}{)^m} \hfill \\ \end{gathered} \right]\left[ \begin{gathered} {c_0} \hfill \\ {c_1} \hfill \\ ... \hfill \\ {c_m} \hfill \\ \end{gathered} \right]$ (1)

 ${Y_x} = f\left( {x,\theta } \right) + {\varepsilon _x}$ (2)

1.2 约束最优化方法 1.2.1 有约束的非线性规划

 $\left\{ \begin{array}{l} \min f\left( x \right)\\ {\rm{s}}.{\rm{t}}.\;\;\;\;s\left( x \right) \ge 0\\ h\left( x \right) = 0 \end{array} \right.$ (3)

 $f({x^*}) \le f(x)$

1.2.2 外点法

 $\left\{ \begin{array}{l} \min f\left( x \right)\\ {\rm{s}}.{\rm{t}}.\;\;\;\;{s_i}\left( x \right) \ge 0,i = 1,2, \ldots ,m\\ {h_j}\left( x \right) = 0,j = 1,2, \ldots ,l \end{array} \right.$ (4)

 $F\left( {x,\mu } \right) = f\left( x \right) + \mu \alpha \left( x \right)$ (5)

 $\begin{array}{c} \alpha \left( x \right) = \sum\limits_{j = 1}^l {{{[{h_j}\left( x \right)]}^2}} + \sum\limits_{i = 1}^m {{{[{s_i}\left( x \right)]}^2}} u({s_i}\left( x \right)),\\ u({s_i}\left( x \right)) = \left\{ \begin{array}{l} 0,{s_i}\left( x \right) \ge 0\\ 1,{s_i}\left( x \right) < 0 \end{array} \right.,i = 1,2, \ldots ,m \end{array}$

F(x, μ)称为约束问题(4)的增广目标函数，μ(>0)称为罚因子，μα(x)称为惩罚项。

μ取为一个趋于正无穷大的正数序列{μk}，并对k=0, 1, 2, …依次求解无约束问题：

 $F(x,{\mu _k}) = f\left( x \right) + {\mu _k}\alpha \left( x \right)$ (6)

1.2.3 改进的外点法

 ${\varepsilon _{{x_m}}} = {Y_{{x_m}}} - f({x_m},\theta )$ (7)

 $\varepsilon _{{x_m}}^2 = {[{Y_{{x_m}}} - f({x_m},\theta )]^2}$

 ${\alpha _p}\left( \theta \right) = \sum {[{Y_{{x_p}}} - f({x_p},\theta )]^2}$ (8)

1) 选定初始迭代点θ0及罚因子μ(>0)，选择观测值构造罚函数；

2) 用最速下降法[10]求解无约束问题：

 $\min {\varepsilon _{{x_m}}} + \mu \alpha \left( \theta \right)$ (9)

3) 计算范数差值$\left\| {\tilde \theta - {\theta _1}} \right\|$及目标函数拟合绝对误差$\left| {{{\tilde Y}_m} - {Y_{{m_1}}}} \right|$${\tilde \theta }$${{{\tilde Y}_m}}$分别为参数值和观测值的真值；

4) 改变罚函数(共2m－1－1种选择方式)，当$\left\| {\tilde \theta - {\theta _i}} \right\|$取得最小值时即是最优解(下面算例中将给出$\left\| {\tilde \theta - {\theta _i}} \right\|$$\left| {{{\tilde Y}_m} - {Y_{{m_1}}}} \right|$i=1, 2, …, m－1的关系)。当目标函数迭代数值不能充分小时，手动放大罚因子(一般情况下，使得等式约束条件方程与目标函数具有显著差异即可)。由于罚因子并未如定义中趋于正无穷大，从而明显减少计算量，因此称为改进的外点法。首先说明算法的合理性，之后进行参数求解。

2 算例与分析

2.1 罚因子大小的影响

2.2 目标函数的位置对计算结果的影响

 图 1 目标函数选点位置的影响 Fig. 1 The influence of the objective function for choosing location
2.3 迭代初值对计算结果的影响

 图 2 范数差值与迭代初值的关系 Fig. 2 Norm difference and the relationship of the initial value of iteration

3 算例及其分析

m=7，即用第7组观测值建立目标函数，前6组观测值建立等式约束条件方程，初始迭代点为PEIV法求得的参数值，罚因子定为μ=1 000，使用上文改进的外点法进行求解，结果见表 56

4 结语

 [1] 张俊, 独知行, 杜宁, 等. 非线性模型的补偿最小二乘估计[J]. 大地测量与地球动力学, 2005, 35(1): 122-125 (Zhang Jun, Du Zhixing, Du Ning, et al. Penalized Least Square Estimator for Non-Linear Models[J]. Journal of Geodesy and Geodynamics, 2005, 35(1): 122-125) (0) [2] 李朝奎. 非线性模型空间测量数据处理理论及其应用[M]. 北京: 化学工业出版社, 2013 (Li Chaokui. Theory and Application of Data Processing in Space of Nonlinear Models[M]. Beijing: Chemical Industry Press, 2013) (0) [3] Box M J. The Occurrence of Replications in Optimal Designs of Experiments to Estimate Parameters in Nonlinear Models[J]. Journal of the Royal Statistical Society(Ser B), 1968, 30(2): 290-302 (0) [4] Bates D M, Watts D G. Relative Curvature Measures of Non-Linearity[J]. Journal of the Royal Statistical Society(Ser B), 1980, 42(1): 1-25 (0) [5] 王新洲. 非线性模型参数估计的直接解法[J]. 武汉测绘科技大学学报, 1999, 24(1): 64-67 (Wang Xinzhou. A Direct Solution Method of Parameter Estimation of Nonlinear Model[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(1): 64-67) (0) [6] 陶本藻. 关于测量中非线性模型的估计问题[J]. 测绘通报, 1998(2): 6-8 (Tao Benzao. On the Estimation of Nonlinear Models in Measurement[J]. Bulletin of Surveying and Mapping, 1998(2): 6-8) (0) [7] 韦博成. 近代非线性回归分析[M]. 南京: 东南大学出版社, 1989 (Wei Bocheng. Modern Nonlinear Regression Analysis[M]. Nanjing: Southeast University Press, 1989) (0) [8] 李朝奎, 黄健柏, 黄力民. 基于非线性误差模型的参数估计[J]. 测绘工程, 2000, 9(3): 19-22 (Li Chaokui, Huang Jianbai, Huang Limin. Parameters Estimation Based on Nonlinear Error Models[J]. Engineering of Surveying and Mapping, 2000, 9(3): 19-22 DOI:10.3969/j.issn.1006-7949.2000.03.005) (0) [9] 王乐洋, 温贵森. 一种基于Partial EIV模型的多项式拟合解法[J]. 大地测量与地球动力学, 2017, 37(7): 737-742 (Wang Leyang, Wen Guisen. A Kind of Polynomial Fitting Method Based on Partial EIV Model[J]. Journal of Geodesy and Geodynamics, 2017, 37(7): 737-742) (0) [10] 张薇, 薛嘉庆. 最优化方法[M]. 沈阳: 东北大学出版社, 2004 (Zhang Wei, Xue Jiaqing. Optimization Method[M]. Shenyang: Northeast University Press, 2004) (0) [11] 胡川, 陈义. 非线性整体最小平差迭代算法[J]. 测绘学报, 2014, 43(7): 668-674 (Hu Chuan, Chen Yi. An Iterative Algorithm for Nonlinear Total Least Squares Adjustment[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(7): 668-674) (0)
A Polynomial Fitting Method Based on Improved Exterior Point Method
WU Tong1     ZHANG Yangyang1     SUN Yanyan1     ZHANG Wandong1     LIU Cuizhi1
1. School of Resources and Civil Engineering, Northeastern University, 11 Wenhua Road, 3 Lane, Shenyang 110819, China
Abstract: This paper considers the problem of parameter fitting for polynomial models. Based on the theory of optimization method, we transform the problem into a constrained nonlinear programming problem, using the fastest descent method to iterate in the calculation to solve the nonlinear problems without linearization. Firstly, the rationality of the improvement of the external point method is illustrated by analysis of the penalty factor, the objective function, and the initial value of the external point method. Secondly, using an example we explain the feasibility of the method; compared with the traditional method, this method possesses high precision and multi-solution, and provides a new idea for studying the spatial data processing theory of nonlinear models.
Key words: polynomial fitting; optimization method; constrained nonlinear programming; parameter solution; steepest descent method