[go: up one dir, main page]

CN103425838A - Path tracking method based on linux - Google Patents

Path tracking method based on linux Download PDF

Info

Publication number
CN103425838A
CN103425838A CN2013103485777A CN201310348577A CN103425838A CN 103425838 A CN103425838 A CN 103425838A CN 2013103485777 A CN2013103485777 A CN 2013103485777A CN 201310348577 A CN201310348577 A CN 201310348577A CN 103425838 A CN103425838 A CN 103425838A
Authority
CN
China
Prior art keywords
point
estimate
iteration
path
estimated
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN2013103485777A
Other languages
Chinese (zh)
Inventor
孟祥飞
吴楠
何志平
郭美思
宗栋瑞
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
IEIT Systems Co Ltd
Original Assignee
Inspur Electronic Information Industry Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Inspur Electronic Information Industry Co Ltd filed Critical Inspur Electronic Information Industry Co Ltd
Priority to CN2013103485777A priority Critical patent/CN103425838A/en
Publication of CN103425838A publication Critical patent/CN103425838A/en
Pending legal-status Critical Current

Links

Images

Landscapes

  • Complex Calculations (AREA)

Abstract

本发明提供一种基于linux的路径跟踪方法，针对经济学、电子线路设计、自动控制、计算机辅助设计和制造以及计算机图形学等诸多领域中遇到一类问题都可归结为求解某一类非线性规划问题，尤其在神经网络以及图形图像处理中运用极为广泛。路径跟踪方法通过对已构建目标函数

Figure DEST_PATH_IMAGE002
的跟踪路径函数
Figure DEST_PATH_IMAGE004
进行建模，并在
Figure DEST_PATH_IMAGE006
区间通过初始化化步、预估步、校正步、调换步、校验步五个步骤进行跟踪，最终得到目标函数的解。

The present invention provides a path tracking method based on linux, aiming at solving a class of problems encountered in many fields such as economics, electronic circuit design, automatic control, computer-aided design and manufacturing, and computer graphics, all can be attributed to solving a certain type of non- Linear programming problems are widely used, especially in neural networks and graphics and image processing. The path tracing method passes through the constructed objective function

Figure DEST_PATH_IMAGE002
The trace path function of
Figure DEST_PATH_IMAGE004
to model, and to
Figure DEST_PATH_IMAGE006
The interval is tracked through five steps of initialization step, estimation step, correction step, exchange step, and verification step, and finally obtains the objective function solution.

Description

一种基于linux的路径跟踪方法A Path Tracing Method Based on Linux

技术领域 technical field

本发明涉及计算机应用技术领域,具体地说是一种基于linux的路径跟踪方法。  The invention relates to the technical field of computer applications, in particular to a linux-based path tracing method. the

背景技术 Background technique

在最近的几十年，求解一些优化问题（如均衡问题、非线性规划、多目标规划、变分不等式、互补问题等）的方法相继被提出来。其中，非线性规划问题是一个非常重要的问题，它在经济学、电子线路设计、自动控制、计算机辅助设计和制造、神经网络以及图形图像处理等诸多领域中，都有很多应用。  In recent decades, methods for solving some optimization problems (such as equilibrium problems, nonlinear programming, multi-objective programming, variational inequalities, complementary problems, etc.) have been proposed one after another. Among them, the nonlinear programming problem is a very important problem. It has many applications in many fields such as economics, electronic circuit design, automatic control, computer-aided design and manufacturing, neural network, and graphics and image processing. the

求解数学规划问题方面的工作是于1979年C. B. Garcia和W. J. Zangwill首先提出的。为了求解凸规划问题，他们构造了带有参数的约束问题：  Work on solving mathematical programming problems was first proposed in 1979 by C. B. Garcia and W. J. Zangwill. In order to solve the convex programming problem, they construct a constraint problem with parameters:

Figure 2013103485777100002DEST_PATH_IMAGE001
Figure 2013103485777100002DEST_PATH_IMAGE001

其中，

Figure 75526DEST_PATH_IMAGE002
，
Figure 2013103485777100002DEST_PATH_IMAGE003
。然后，利用非光滑函数
Figure 274426DEST_PATH_IMAGE004
和
Figure 2013103485777100002DEST_PATH_IMAGE005
将KKT系统中含有不等式的部分转化为等式，这样一来，就可以将原始问题转化为一个非线性方程组问题，然后可以构造一个同伦对其进行求解。1984年，一种新的方法被N. Karmarkar提出求解线性规划问题，该方法其实是一种路径跟踪的方法或者称之为内点法。这种方法求解线性规划问题具有多项式复杂性。该方法提出后引起了好多学者的关注。 in,
Figure 75526DEST_PATH_IMAGE002
,
Figure 2013103485777100002DEST_PATH_IMAGE003
. Then, using the non-smooth function
Figure 274426DEST_PATH_IMAGE004
and
Figure 2013103485777100002DEST_PATH_IMAGE005
The part of the KKT system that contains inequalities is transformed into an equation, so that the original problem can be transformed into a problem of nonlinear equations, and then a homotopy can be constructed to solve it. In 1984, a new method was proposed by N. Karmarkar to solve linear programming problems. This method is actually a path tracking method or interior point method. This approach to solving linear programming problems has polynomial complexity. This method has attracted the attention of many scholars after it was proposed.

为了求解非凸非线性规划问题，一种组合同伦方法（Combined Homotopy Interior Point Method，简称CHIP方法）被冯果忱、林正华、于波提出来，并且同伦路径的存在性和全局收敛性也得到了证明。随后林正华、李勇及于波在1996年将含有不等式约束的非线性规划问题的同伦方法推广到了带有等式约束的问题上。林正华、于波及冯果忱在1997年提出了求解凸规划问题的同伦方法。紧接着，在自和谐条件下，关于凸规划的组合同伦方法的全局收敛性及与当前存在的内点法相似的多项式复杂性也被于波、徐庆、冯果忱进行了证明。近些年来，一些研究者不断地改善了这种方法，组合同伦内点法不断地得到了改善与推广。  In order to solve non-convex nonlinear programming problems, a combined homotopy method (Combined Homotopy Interior Point Method, referred to as CHIP method) was proposed by Feng Guochen, Lin Zhenghua, and Yu Bo, and the existence and global convergence of homotopy paths have also been proved. . Subsequently, Lin Zhenghua, Li Yong and Yu Bo extended the homotopy method for nonlinear programming problems with inequality constraints to problems with equality constraints in 1996. Lin Zhenghua, Yu Bo and Feng Guochen proposed a homotopy method for solving convex programming problems in 1997. Then, under the condition of self-concordance, the global convergence of the combinatorial homotopy method for convex programming and the polynomial complexity similar to the existing interior point method were also proved by Yu Bo, Xu Qing, and Feng Guochen. In recent years, some researchers have continuously improved this method, and the combined homotopy interior point method has been continuously improved and promoted. the

2001年，一种称为凝聚同伦（Aggregate Constraint Homotopy，简称ACH方法）的方法被于波、冯果忱及张绍良提出，该方法可以求解带有多约束的非凸规划问题。随后他们做了一些假设条件，即可行集有界、边界正则及弱法锥条件，对同伦路径的存在性和收敛性进行证明。在ACH中，其同伦变量的个数为

Figure 5622DEST_PATH_IMAGE006
，而在CHIP中同伦变量的个数为
Figure 2013103485777100002DEST_PATH_IMAGE007
。在凝聚同伦中，将约束条件较多的非线性规划变成单约束规划来处理，这样求解问题的规模就被大大压缩。因此，如果在实际当中遇到约束个数多的情况下，我们优先选择凝聚同伦。但是，在一些条件，比如在“弱法锥条件”下，凝聚同伦对初始点的要求比较高，必须取在可行集合中的某个子集当中，有些时候这种条件难以达到或者不好取；在其他的某些条件下，需要一些辅助的函数才能构造同伦方程，而这些辅助函数往往都难以实现。因此，如果想做到大规模应用还有些困难。在2006年，一种更便于使用的组合同伦被于波、商玉凤提出。该同伦方法对条件的要求更少，但是却可以求解一些边界不断变动的非凸规划问题。他们证明了此方法路径的存在性与大范围收敛性，而且该方法与先前提出的一些同伦方法相比，对初始点的要求更弱，同伦也容易构造。  In 2001, a method called Aggregate Constraint Homotopy (ACH method) was proposed by Yu Bo, Feng Guochen and Zhang Shaoliang, which can solve non-convex programming problems with multiple constraints. Then they made some assumptions, namely the bounded feasible set, regular boundary and weak normal cone conditions, to prove the existence and convergence of the homotopy path. In ACH, the number of its homotopy variables is
Figure 5622DEST_PATH_IMAGE006
, and the number of homotopy variables in CHIP is
Figure 2013103485777100002DEST_PATH_IMAGE007
. In the cohesive homotopy, the nonlinear programming with many constraints is transformed into a single-constraint programming, so that the scale of the solution problem is greatly reduced. Therefore, if we encounter a large number of constraints in practice, we give priority to cohesive homotopy. However, under some conditions, such as the "weak legal cone condition", the condensed homotopy has relatively high requirements for the initial point, and must be selected in a certain subset of the feasible set. Sometimes this condition is difficult to achieve or not good to choose ; Under some other conditions, some auxiliary functions are needed to construct the homotopy equation, and these auxiliary functions are often difficult to realize. Therefore, it is still difficult to achieve large-scale application. In 2006, a more convenient combinatorial homotopy was proposed by Yu Bo and Shang Yufeng. The homotopy method requires fewer conditions, but it can solve some non-convex programming problems with changing boundaries. They proved the existence and large-scale convergence of the path of this method, and compared with some previously proposed homotopy methods, this method has weaker requirements on the initial point, and the homotopy is also easy to construct.

随着工程中的问题越来越多，产生的一些问题的规模可能非常大，对求解这类问题的方法的效率的要求也越来越高。对于这样的需求，在2011年，周正勇、于波提出了平整化的凝聚同伦方法以改善凝聚同伦方法的一些计算缺点，并且给出了这种方法的大范围收敛性的证明。这种方法主要是利用某些函数对原来的约束函数进行加权划分，并设立一个准则来减少约束函数求一阶导数和二阶导数的计算。此方法对约束个数非常多的非线性规划问题非常有效。  With the increasing number of problems in engineering, the scale of some generated problems may be very large, and the requirements for the efficiency of methods for solving such problems are also getting higher and higher. For such needs, in 2011, Zhou Zhengyong and Yu Bo proposed a flattened agglomerative homotopy method to improve some computational shortcomings of the agglomerative homotopy method, and gave a proof of the large-scale convergence of this method. This method mainly uses some functions to weight the original constraint function, and establishes a criterion to reduce the calculation of the first-order derivative and the second-order derivative of the constraint function. This method is very effective for nonlinear programming problems with a very large number of constraints. the

虽然非线性规划问题的理论研究有很多突破，这样只能保证能适应不同复杂度的问题在建立路径跟踪模型时提高效率，但是在跟踪过程中尚无一个统一有效的方法可供大家使用，本方法作为一个求解非线性规划问题解集的一个重要工具，可以很好的满足科研领域以及工程应用当中的遇到的实际问题。  Although there have been many breakthroughs in the theoretical research of nonlinear programming problems, which can only ensure that problems of different complexity can be adapted to improve efficiency when establishing path tracking models, there is no unified and effective method for everyone to use in the tracking process. As an important tool to solve the solution set of nonlinear programming problems, the method can well meet the practical problems encountered in the field of scientific research and engineering applications. the

在实际的工程项目当中，非线性规划问题有如下特征：  In actual engineering projects, nonlinear programming problems have the following characteristics:

a)   所涉及的数据量非常大，而且要求性能非常苛刻（往往是毫秒级的），因此如何能快速得到目标解是极其重要的； a) The amount of data involved is very large, and the performance requirements are very demanding (often milliseconds), so how to quickly obtain the target solution is extremely important;

b)   非线性规划问题的描述转换成数学模型往往是通过向量的形式，通常我们采取矩阵结构来保存处理这些数据。但是，这些向量当中好多都是非对称的，因此，我们在数据结构的设计当中，如何既能保证空间复杂度又能保证时间复杂度而且精确的跟踪路径尤为重要； b) The description of nonlinear programming problems is often converted into a mathematical model in the form of vectors. Usually we use a matrix structure to store and process these data. However, many of these vectors are asymmetrical. Therefore, in the design of the data structure, how to ensure both space complexity and time complexity and accurate tracking path is particularly important;

c)  在路径跟踪过程中，方法要不断循环预估、校正、调换、校验这四个步骤，如何能使循环次数降低但又不缺失精度也是我们要攻克的技术问题。 c) In the path tracking process, the method needs to continuously cycle through the four steps of estimation, correction, exchange, and verification. How to reduce the number of cycles without losing accuracy is also a technical problem we need to overcome.

发明内容 Contents of the invention

本发明的目的是提供一种基于linux的路径跟踪方法。  The purpose of the present invention is to provide a path tracing method based on linux. the

本发明的目的是提出一种基于Linux系统下的路径跟踪方法。该方法可以快速精确地得出非线性规划问题当中原始问题（目标函数）的解。  The purpose of the invention is to propose a path tracing method based on the Linux system. This method can quickly and accurately obtain the solution of the original problem (objective function) in nonlinear programming problems. the

本发明的目的是按以下方式实现的，针对求解非线性方程组

Figure 668160DEST_PATH_IMAGE008
的结果，首先要选取一个简单的方程，它的解
Figure 422489DEST_PATH_IMAGE010
已知或比较容易求解，然后构造一个带有参数的光滑函数
Figure 2013103485777100002DEST_PATH_IMAGE013
，使其满足  The purpose of the present invention is achieved in the following manner, for solving nonlinear equations
Figure 668160DEST_PATH_IMAGE008
, first choose a simple equation , its solution
Figure 422489DEST_PATH_IMAGE010
known or relatively easy to solve, and then construct a parameter smooth function of
Figure 2013103485777100002DEST_PATH_IMAGE013
, to satisfy

Figure 886148DEST_PATH_IMAGE014
；
Figure 886148DEST_PATH_IMAGE014
;

并且在一定的条件下，方程的解集合包含一条从开始，趋近于超平面

Figure 2013103485777100002DEST_PATH_IMAGE017
的光滑曲线
Figure 229722DEST_PATH_IMAGE018
，
Figure 504846DEST_PATH_IMAGE018
的另一端极限点为
Figure 2013103485777100002DEST_PATH_IMAGE019
，则
Figure 351579DEST_PATH_IMAGE020
是
Figure 686745DEST_PATH_IMAGE008
的解； And under certain conditions, the equation The solution set of contains a line from start, approaching the hyperplane
Figure 2013103485777100002DEST_PATH_IMAGE017
smooth curve of
Figure 229722DEST_PATH_IMAGE018
,
Figure 504846DEST_PATH_IMAGE018
The other extreme point of
Figure 2013103485777100002DEST_PATH_IMAGE019
,but
Figure 351579DEST_PATH_IMAGE020
yes
Figure 686745DEST_PATH_IMAGE008
solution;

所述的一定条件，是首先对路径函数

Figure 415667DEST_PATH_IMAGE013
进行建模，接着在
Figure 2013103485777100002DEST_PATH_IMAGE021
区间通过初始化化步、预估步、校正步、调换步、校验步五个步骤进行跟踪，最终得到目标函数
Figure 307531DEST_PATH_IMAGE022
的解； The certain condition mentioned above is that the path function
Figure 415667DEST_PATH_IMAGE013
to model, then
Figure 2013103485777100002DEST_PATH_IMAGE021
The interval is tracked through five steps of initialization step, estimation step, correction step, exchange step, and verification step, and finally obtains the objective function
Figure 307531DEST_PATH_IMAGE022
solution;

在对路径函数

Figure 805508DEST_PATH_IMAGE013
进行建模的过程中，采取的二维稀疏矩阵作为参变量来降低空间复杂度和时间复杂度；在初始化步中主要对一些全局变量进行初始化；在预估步中采取了首次切线预估其余割线预估的方式进行预估，以此降低时间复杂度；在调换步中监控跟踪步长并按照最优策略进行步长更新；最后一步校验步用来判断跟踪点与实际点的误差是否满足既定的要求，如果满足方法总之，否则继续转到预估步； in the path function
Figure 805508DEST_PATH_IMAGE013
In the process of modeling, the two-dimensional sparse matrix is used as a parameter to reduce the space complexity and time complexity; in the initialization step, some global variables are mainly initialized; in the estimation step, the first tangent is used to estimate the rest Estimate by means of secant estimation to reduce time complexity; monitor the tracking step size in the exchange step and update the step size according to the optimal strategy; the last step of the verification step is used to judge the error between the tracking point and the actual point Whether it meets the established requirements, if it meets the method, otherwise continue to the estimation step;

由于五个步骤进行跟踪是个不断循环的过程，因此各个步骤的良好通信以及参数设置，采用全局变量和局部静态变量的混合管理模式，在主要数据结构的设计时采取的稀疏矩阵和普通矩阵混存动态管理结构，具体步骤如下： Since the five-step tracking is a continuous cycle process, the good communication and parameter setting of each step adopts the mixed management mode of global variables and local static variables, and the mixed storage of sparse matrix and ordinary matrix is adopted in the design of the main data structure. Dynamic management structure, the specific steps are as follows:

(a)  预处理和系数矩阵数据结构的设计 (a) Design of preprocessing and coefficient matrix data structure

为了很好的进行各个步骤的通信我们采取了全局变量的方式，诸如精度、步长、初始点、预估点、校正点、初始预估方向、预估方向等全部封存在一个全局文件当中统一进行监控更新，这样做的好处是在数据交换过程中少了很多中间变量的来回赋值，数据量大的时候赋值时间开销也很大，且便于通信和调试，因此，在跟踪之前，首先要将这些数据进行预处理； In order to communicate well in each step, we adopt the global variable method, such as accuracy, step size, initial point, estimated point, correction point, initial estimated direction, estimated direction, etc., are all sealed in a global file. Monitor and update. The advantage of doing this is that there are fewer round-trip assignments of intermediate variables during the data exchange process. When the amount of data is large, the assignment time overhead is also very large, and it is convenient for communication and debugging. Therefore, before tracking, you must first set the These data are preprocessed;

为了解决非线性规划问题当中向量的非对称性问题，本方法采取了稀疏矩阵的数据结构和正常的二维数组并存的数据结构进行数据的处理，这样针对不同的非线性规划问题，采取两套数据结构及对应矩阵计算方法进行切换，切换的策略是：“非零元的个数是零元个数的三倍以上”，不仅降低了空间开销，而且大大降低了时间复杂度。在这里我们只介绍稀疏矩阵的数据结构体描述： In order to solve the problem of vector asymmetry in the nonlinear programming problem, this method adopts the sparse matrix data structure and the normal two-dimensional array data structure to process the data, so that for different nonlinear programming problems, two sets of The data structure and the corresponding matrix calculation method are switched. The switching strategy is: "the number of non-zero elements is more than three times the number of zero elements", which not only reduces the space overhead, but also greatly reduces the time complexity. Here we only introduce the data structure description of the sparse matrix:

struct Trituple{ struct Trituple{

int row_index;//非零元的行标     int row_index;//The row index of non-zero elements

int col_index;//非零元的列标 int col_index;//The column index of non-zero elements

  double value;//元素值 double value;//element value

}； };

struct  SparseMatrix{ struct SparseMatrix{

  int Mrx_row;//矩阵的行 int Mrx_row;//row of the matrix

  int Mrx_col;//矩阵的列 int Mrx_col;//columns of the matrix

  Trituple* data;//三元组数组 Trituple* data;//Array of triples

}； };

诸如 such as

Figure 2013103485777100002DEST_PATH_IMAGE023
Figure 2013103485777100002DEST_PATH_IMAGE023

这样的矩阵采取稀疏矩阵的结构描述，效果显而易见，而且在实际的非线性规划问题当中这种结构占据的比例偏高一些； Such a matrix adopts the structural description of a sparse matrix, and the effect is obvious, and in the actual nonlinear programming problem, the proportion of this structure is relatively high;

(b)  路径跟踪过程 (b) Path tracing process

在追踪由确定的同伦路径的过程中，方法分以下五个步骤： in tracking by In the process of determining the homotopy path, the method is divided into the following five steps:

① 初始化步:在初始化步中给出三个量：一个初始点

Figure 2013103485777100002DEST_PATH_IMAGE025
，一个初始化步长
Figure 199897DEST_PATH_IMAGE026
，在全局变量step中进行初始化；最后一个容许误差
Figure 2013103485777100002DEST_PATH_IMAGE027
采取宏定义的方式在inf中进行了设定； ① Initialization step: Three quantities are given in the initialization step: an initial point
Figure 2013103485777100002DEST_PATH_IMAGE025
, an initial step size
Figure 199897DEST_PATH_IMAGE026
, initialized in the global variable step; the last allowable error
Figure 2013103485777100002DEST_PATH_IMAGE027
It is set in inf by means of macro definition;

② 预估步:得到初始点后，进行下一个点的预估，第一步采取切线预估，其余采取的是割线预估方式，首先求出在初始点

Figure 285665DEST_PATH_IMAGE028
处的单位切向量
Figure 2013103485777100002DEST_PATH_IMAGE029
， ② Estimation step: After obtaining the initial point, estimate the next point. The first step is to estimate the tangent line, and the rest are estimated by the secant line.
Figure 285665DEST_PATH_IMAGE028
The unit tangent vector at
Figure 2013103485777100002DEST_PATH_IMAGE029
,

计算

Figure 700466DEST_PATH_IMAGE030
得出预估点
Figure 2013103485777100002DEST_PATH_IMAGE031
，后续的预估过程是通过取当前得到的校正点及其上一个校正后的点的差进行割线预估；在这里用到了带列主元的Gauss消元法来求切向量
Figure 643014DEST_PATH_IMAGE029
，下面简单介绍一下带列主元的Gauss消元法； calculate
Figure 700466DEST_PATH_IMAGE030
get estimated point
Figure 2013103485777100002DEST_PATH_IMAGE031
, the subsequent estimation process is to estimate the secant line by taking the difference between the current correction point and the previous correction point; here, the Gauss elimination method with column pivot is used to find the tangent vector
Figure 643014DEST_PATH_IMAGE029
, the following briefly introduces the Gauss elimination method with column pivots;

Figure 80949DEST_PATH_IMAGE032
Figure 80949DEST_PATH_IMAGE032

选取，使得

Figure 317545DEST_PATH_IMAGE034
最大化，并进行如下行交换 select , making
Figure 317545DEST_PATH_IMAGE034
Maximize, and perform the following line exchange

Figure 2013103485777100002DEST_PATH_IMAGE035
Figure 2013103485777100002DEST_PATH_IMAGE035

Figure 790114DEST_PATH_IMAGE036
Figure 790114DEST_PATH_IMAGE036

割线预估主要的方法是通过以计算的相邻两点来确定一个预估方向，具体是过以下公式得到的： The main method of secant prediction is to determine a prediction direction by calculating two adjacent points, which is obtained by the following formula:

Figure 2013103485777100002DEST_PATH_IMAGE037
。
Figure 2013103485777100002DEST_PATH_IMAGE037
.

还有一种预估方式是三次Hermite预估，具体的公式如下：  Another way to estimate is three Hermite estimates, the specific formula is as follows:

Figure 965881DEST_PATH_IMAGE038
Figure 965881DEST_PATH_IMAGE038

由于第一次预估的时候，只有初值点一个点，因此，只能采取切线预估的方式，切线预估在计算切向量的过程中非常耗时，因此，只要得到第一个预估点之后，就采取简单有效的割线预估方式，这个方法比起其他两种方式在执行效率上会快很多，因此采取了第一步切线预估，其余步骤为割线预估的方式； Since there is only one point of initial value in the first estimation, only tangent estimation can be used. Tangent estimation is very time-consuming in the process of calculating the tangent vector. Therefore, as long as the first estimation is obtained After the point, the simple and effective secant estimation method is adopted. This method is much faster in execution efficiency than the other two methods, so the first step of tangent estimation is adopted, and the remaining steps are secant estimation;

③ 校正步：以

Figure 2013103485777100002DEST_PATH_IMAGE039
为初值，用迭代法产生一个序列
Figure 563215DEST_PATH_IMAGE040
，使
Figure 2013103485777100002DEST_PATH_IMAGE041
为
Figure 787523DEST_PATH_IMAGE042
中点的近似且误差小于，如果迭代不收敛，则缩小步长转回预估步，在这里采用牛顿迭代法，步骤如下： ③ Calibration step: take
Figure 2013103485777100002DEST_PATH_IMAGE039
As the initial value, generate a sequence by iteration
Figure 563215DEST_PATH_IMAGE040
,make
Figure 2013103485777100002DEST_PATH_IMAGE041
for
Figure 787523DEST_PATH_IMAGE042
An approximation of the midpoint with an error of less than , if the iteration does not converge, then reduce the step size and return to the estimated step. Here, the Newton iteration method is used, and the steps are as follows:

从一个点

Figure 52283DEST_PATH_IMAGE045
开始，预估
Figure DEST_PATH_IMAGE046
，它给出一个其误差为
Figure 336633DEST_PATH_IMAGE047
粗糙估计
Figure DEST_PATH_IMAGE048
，经若干步Newton迭代校正可防止这个误差传播而得以控制，这个迭代过程的初始值为预估值
Figure 562209DEST_PATH_IMAGE049
，希望迭代收敛于
Figure DEST_PATH_IMAGE050
的解
Figure 590208DEST_PATH_IMAGE051
； from a point
Figure 52283DEST_PATH_IMAGE045
start estimate
Figure DEST_PATH_IMAGE046
, which gives an error of
Figure 336633DEST_PATH_IMAGE047
rough estimate
Figure DEST_PATH_IMAGE048
, after several steps of Newton iterative correction can prevent this error propagation and be controlled, the initial value of this iterative process is the estimated value
Figure 562209DEST_PATH_IMAGE049
, it is hoped that the iteration converges to
Figure DEST_PATH_IMAGE050
solution
Figure 590208DEST_PATH_IMAGE051
;

向量

Figure DEST_PATH_IMAGE052
与路径
Figure 834108DEST_PATH_IMAGE053
在点
Figure DEST_PATH_IMAGE054
相切，经过点
Figure 23781DEST_PATH_IMAGE049
并且与切向量
Figure 736653DEST_PATH_IMAGE052
垂直的
Figure 302763DEST_PATH_IMAGE055
维超平面
Figure DEST_PATH_IMAGE056
在点
Figure 666749DEST_PATH_IMAGE057
(其中
Figure DEST_PATH_IMAGE058
)处切割路径，校正过程就是为了得到这个点，令
Figure 27323DEST_PATH_IMAGE059
’,
Figure DEST_PATH_IMAGE060
表示
Figure 224562DEST_PATH_IMAGE049
的分量，超平面
Figure 594363DEST_PATH_IMAGE056
可写成： vector
Figure DEST_PATH_IMAGE052
with path
Figure 834108DEST_PATH_IMAGE053
at point
Figure DEST_PATH_IMAGE054
Tangent, passing through the point
Figure 23781DEST_PATH_IMAGE049
and with the tangent vector
Figure 736653DEST_PATH_IMAGE052
vertical
Figure 302763DEST_PATH_IMAGE055
dimensional hyperplane
Figure DEST_PATH_IMAGE056
at point
Figure 666749DEST_PATH_IMAGE057
(in
Figure DEST_PATH_IMAGE058
) to cut the path, the calibration process is to get this point, let
Figure 27323DEST_PATH_IMAGE059
',
Figure DEST_PATH_IMAGE060
express
Figure 224562DEST_PATH_IMAGE049
components, the hyperplane
Figure 594363DEST_PATH_IMAGE056
can be written as:

Figure 484959DEST_PATH_IMAGE061
Figure 484959DEST_PATH_IMAGE061

于是校正过程就是解方程组 Then the calibration process is to solve the system of equations

牛顿迭代的迭代格式为： The iteration format of Newton iteration is:

Figure 344330DEST_PATH_IMAGE063
Figure 344330DEST_PATH_IMAGE063

牛顿迭代是局部收敛的，即在

Figure DEST_PATH_IMAGE064
中存在点
Figure 953166DEST_PATH_IMAGE051
的某一领域
Figure 939708DEST_PATH_IMAGE065
，当初值
Figure DEST_PATH_IMAGE066
时，牛顿迭代收敛，如果从
Figure 950389DEST_PATH_IMAGE049
出发的牛顿迭代不收敛，则通过缩小预估步长
Figure 918345DEST_PATH_IMAGE026
，使
Figure 76794DEST_PATH_IMAGE049
落在牛顿迭代收敛的某邻域中； Newton iteration is locally convergent, that is, in
Figure DEST_PATH_IMAGE064
point of existence
Figure 953166DEST_PATH_IMAGE051
a certain field of
Figure 939708DEST_PATH_IMAGE065
, the original value
Figure DEST_PATH_IMAGE066
When , the Newton iteration converges, if from
Figure 950389DEST_PATH_IMAGE049
The starting Newton iteration does not converge, then by reducing the estimated step size
Figure 918345DEST_PATH_IMAGE026
,make
Figure 76794DEST_PATH_IMAGE049
falls in a certain neighborhood where Newton iteratively converges;

迭代停止的判别依据有两种：第一，如果估计出迭代不收敛于一个相近的点，应立即停止迭代；第二，如果迭代收敛，当近似解均在符合规定误差

Figure 788398DEST_PATH_IMAGE027
内，也停止迭代，在方法的设计中，采用用if结构能很好的包括这两种情况，即在过预估点且垂直于预估方向的超平面上进行校正，校正方程组 There are two basis for judging the iteration stop: first, if it is estimated that the iteration does not converge to a similar point, the iteration should be stopped immediately; second, if the iteration converges, when the approximate solutions are within the specified error
Figure 788398DEST_PATH_IMAGE027
In the design of the method, the if structure can be used to cover these two situations well, that is, the correction is performed on the hyperplane that is over-estimated and perpendicular to the estimated direction, and the correction equation

Figure 653586DEST_PATH_IMAGE067
，
Figure 653586DEST_PATH_IMAGE067
,

其中，向量d表示预估方向； Among them, the vector d represents the estimated direction;

④ 调整步长：这一步主要是为了精度以及循环次数做考虑的，在校正过程中，如果满足要求，就要适当的调整步长，否则控制流程返回到预估步，在方法设计的过程中，对步长进行了逐次的标记，由于在每一次的预估校正过程中，这个变量一直在变，因此用一个静态的局部变量来实现； ④ Adjust step size: This step is mainly for the consideration of accuracy and cycle times. During the calibration process, if To meet the requirements, it is necessary to adjust the step size appropriately , otherwise the control flow returns to the estimation step. In the process of method design, the step size is marked successively. Since this variable is always changing during each estimation and correction process, a static local variable is used to fulfill;

⑤ 校验步：这一个步骤是整个路径跟踪的终止信号，一旦

Figure 188921DEST_PATH_IMAGE068
中分量
Figure 438636DEST_PATH_IMAGE012
等于0或接近于0的话，就终止跟踪，牛顿迭代法过程中，每次都对t做检查，如果满足终止的条件，方法就让迭代循环终止并把最终的结果给出来。 ⑤ Check step: This step is the termination signal of the whole path tracing, once
Figure 188921DEST_PATH_IMAGE068
Medium portion
Figure 438636DEST_PATH_IMAGE012
If it is equal to 0 or close to 0, the tracking is terminated. During the Newton iteration method, t is checked each time. If the termination condition is met, the method terminates the iteration loop and gives the final result.

本发明的有益效果是：针对经济学、电子线路设计、自动控制、计算机辅助设计和制造以及计算机图形学等诸多领域中遇到一类问题都可归结为求解某一类非线性规划问题，尤其在神经网络以及图形图像处理中运用极为广泛。路径跟踪方法通过对已构建目标函数的跟踪路径函数

Figure DEST_PATH_IMAGE070
进行建模，并在
Figure 795985DEST_PATH_IMAGE071
区间通过初始化化步、预估步、校正步、调换步、校验步五个步骤进行跟踪，最终能够得到目标函数
Figure 866710DEST_PATH_IMAGE069
的解。  The beneficial effect of the present invention is: for economics, electronic circuit design, automatic control, computer-aided design and manufacture and computer graphics and many other fields encountered a class of problems can be attributed to solving a certain type of nonlinear programming problem, especially It is widely used in neural network and graphics and image processing. The path tracing method passes through the constructed objective function The trace path function of
Figure DEST_PATH_IMAGE070
to model, and to
Figure 795985DEST_PATH_IMAGE071
The interval is tracked through five steps of initialization step, estimation step, correction step, exchange step, and verification step, and finally the objective function can be obtained
Figure 866710DEST_PATH_IMAGE069
solution.

附图说明 Description of drawings

图1是切线预估和割线预估图；  Figure 1 is a diagram of tangent estimation and secant estimation;

图2是校正图； Figure 2 is a calibration map;

图3路径跟踪算法流程图； Fig. 3 path tracking algorithm flow chart;

图4动态数据处理流程图。 Figure 4 is a flow chart of dynamic data processing.

具体实施方式 Detailed ways

下面结合附和实施例对本发明的内容做进一步的详细说明。  The content of the present invention will be further described in detail below in conjunction with the accompanying embodiments. the

 具体步骤如下：  Specific steps are as follows:

针对求解非线性方程组

Figure DEST_PATH_IMAGE072
的结果，首先要选取一个简单的方程，它的解
Figure 572946DEST_PATH_IMAGE010
已知或比较容易求解，然后构造一个带有参数
Figure 115922DEST_PATH_IMAGE012
的光滑函数
Figure 408363DEST_PATH_IMAGE070
，使其满足 For solving systems of nonlinear equations
Figure DEST_PATH_IMAGE072
, first choose a simple equation , its solution
Figure 572946DEST_PATH_IMAGE010
known or relatively easy to solve, and then construct a parameter
Figure 115922DEST_PATH_IMAGE012
smooth function of
Figure 408363DEST_PATH_IMAGE070
, to satisfy

Figure DEST_PATH_IMAGE074
；
Figure DEST_PATH_IMAGE074
;

并且在一定的条件下，方程

Figure 265461DEST_PATH_IMAGE050
的解集合包含一条从
Figure 787445DEST_PATH_IMAGE075
开始，趋近于超平面
Figure DEST_PATH_IMAGE076
的光滑曲线
Figure 439006DEST_PATH_IMAGE018
，的另一端极限点为
Figure 941849DEST_PATH_IMAGE077
，则
Figure 490642DEST_PATH_IMAGE020
是
Figure 578684DEST_PATH_IMAGE072
的解； And under certain conditions, the equation
Figure 265461DEST_PATH_IMAGE050
The solution set of contains a line from
Figure 787445DEST_PATH_IMAGE075
start, approaching the hyperplane
Figure DEST_PATH_IMAGE076
smooth curve of
Figure 439006DEST_PATH_IMAGE018
, The other extreme point of
Figure 941849DEST_PATH_IMAGE077
,but
Figure 490642DEST_PATH_IMAGE020
yes
Figure 578684DEST_PATH_IMAGE072
solution;

所属的一定条件，首先对路径函数

Figure 658766DEST_PATH_IMAGE070
进行建模，接着在
Figure 857666DEST_PATH_IMAGE071
区间通过初始化化步、预估步、校正步、调换步、校验步五个步骤进行跟踪，最终得到目标函数
Figure 260966DEST_PATH_IMAGE069
的解； Belonging to certain conditions, first of all, the path function
Figure 658766DEST_PATH_IMAGE070
to model, then
Figure 857666DEST_PATH_IMAGE071
The interval is tracked through five steps of initialization step, estimation step, correction step, exchange step, and verification step, and finally obtains the objective function
Figure 260966DEST_PATH_IMAGE069
solution;

在对路径函数进行建模的过程中，采取的二维稀疏矩阵作为参变量来降低空间复杂度和时间复杂度；在初始化步中主要对一些全局变量进行初始化；在预估步中采取了首次切线预估其余割线预估的方式进行预估，以此降低时间复杂度；在调换步中监控跟踪步长并按照最优策略进行步长更新；最后一步校验步用来判断跟踪点与实际点的误差是否满足既定的要求，如果满足方法总之，否则继续转到预估步； in the path function In the process of modeling, the two-dimensional sparse matrix is used as a parameter to reduce the space complexity and time complexity; in the initialization step, some global variables are mainly initialized; in the estimation step, the first tangent is used to estimate the rest Estimate by means of secant estimation to reduce time complexity; monitor the tracking step size in the exchange step and update the step size according to the optimal strategy; the last step of the verification step is used to judge the error between the tracking point and the actual point Whether it meets the established requirements, if it meets the method, otherwise continue to the estimation step;

由于五个步骤进行跟踪是个不断循环的过程，因此各个步骤的良好通信以及参数设置，采用全局变量和局部静态变量的混合管理模式，在主要数据结构的设计时采取的稀疏矩阵和普通矩阵混存动态管理结构。 Since the five-step tracking is a continuous cycle process, the good communication and parameter setting of each step adopts the mixed management mode of global variables and local static variables, and the mixed storage of sparse matrix and ordinary matrix is adopted in the design of the main data structure. Dynamic management structure.

按照图3的流程开始，当进入预处理阶段时，我们主要对路径函数进行描述，并将具体内容放在Fun.c文件当中，其函数模型如下：  Start according to the process in Figure 3. When entering the preprocessing stage, we mainly use the path function Describe and put the specific content in the Fun.c file. The function model is as follows:

Path_track(const Matrix& x,const Matrix& y,double t,const Matrix& g) Path_track(const Matrix& x, const Matrix& y, double t, const Matrix& g)

然后将全局的通信变量进行设置，诸如精度要求、步长、初始点、预估点、校正点、初始预估方向、预估方向等。然后进入初始化步，初始化步按照跟踪的路径函数来初始化初始点，步长以及误差三个主要变量，这里特别强调一点，就是初始化初始点的时候一定要根据非线性规划问题的特征进行选取数据保存方式（稀疏和非稀疏）。接着进入预估步，如图1所示，我们第一步采取切线预估，以后均为割线预估的方式进行预估处理，其中，切线预估采取高斯消元法得到预估方向，算法是在公共函数库里static Matrix GaussLin(const Matrix &gsA, const Matrix &gsB)中进行实现的。 Then set the global communication variables, such as accuracy requirements, step size, initial point, estimated point, correction point, initial estimated direction, estimated direction, etc. Then enter the initialization step, which initializes the initial point, step size and error according to the tracked path function. Here is a special emphasis, that is, when initializing the initial point, the data must be selected according to the characteristics of the nonlinear programming problem. mode (sparse and non-sparse). Then enter the estimation step, as shown in Figure 1, we use the tangent estimation as the first step, and then use the secant estimation method to perform estimation processing. Among them, the tangent estimation adopts the Gaussian elimination method to obtain the estimated direction. The algorithm is implemented in static Matrix GaussLin(const Matrix &gsA, const Matrix &gsB) in the public function library.

Figure DEST_PATH_IMAGE078
Figure DEST_PATH_IMAGE078

选取

Figure 73567DEST_PATH_IMAGE079
，使得
Figure DEST_PATH_IMAGE080
最大化，并进行如下行交换  select
Figure 73567DEST_PATH_IMAGE079
, making
Figure DEST_PATH_IMAGE080
Maximize, and perform the following line exchange

Figure 410002DEST_PATH_IMAGE081
Figure 410002DEST_PATH_IMAGE081

Figure DEST_PATH_IMAGE082
Figure DEST_PATH_IMAGE082

割线预估主要的算法思路简单说来就是通过以计算的相邻两点来确定一个预估方向，具体是通过以下公式得到的： The main algorithm idea of secant prediction is simply to determine a prediction direction by calculating two adjacent points, which is obtained by the following formula:

然后根据预估方向和动态步长得到预估点

Figure DEST_PATH_IMAGE084
，在预估步这一步中，要每次更新一下局部静态变量预估点，并对预估点进行判断以便做出下一次预估时采取的数据处理方式，接着转入校正步，如图2所示，当我们有了预估点之后
Figure 878209DEST_PATH_IMAGE084
，以为初值，用迭代法产生一个序列
Figure DEST_PATH_IMAGE086
，使
Figure 875432DEST_PATH_IMAGE087
为
Figure DEST_PATH_IMAGE088
中点的近似且误差小于
Figure 210599DEST_PATH_IMAGE089
。如果迭代不收敛，则缩小步长转回预估步。在这里我们采用了牛顿迭代法。 Then get the estimated point according to the estimated direction and dynamic step size
Figure DEST_PATH_IMAGE084
, in the estimation step, it is necessary to update the local static variable estimation points each time, and judge the estimation points in order to make the data processing method for the next estimation, and then turn to the correction step, as shown in the figure 2, when we have estimated points
Figure 878209DEST_PATH_IMAGE084
,by As the initial value, generate a sequence by iteration
Figure DEST_PATH_IMAGE086
,make
Figure 875432DEST_PATH_IMAGE087
for
Figure DEST_PATH_IMAGE088
An approximation of the midpoint with an error of less than
Figure 210599DEST_PATH_IMAGE089
. If the iteration does not converge, reduce the step size and switch back to the estimated step. Here we use the Newton iteration method.

向量

Figure 1837DEST_PATH_IMAGE052
与路径在点相切。经过点
Figure 84697DEST_PATH_IMAGE049
并且与切向量垂直的
Figure 993539DEST_PATH_IMAGE055
维超平面
Figure 346023DEST_PATH_IMAGE056
在点
Figure 288571DEST_PATH_IMAGE057
(其中
Figure 788823DEST_PATH_IMAGE058
)处切割路径。校正过程就是为了得到这个点（见图2）。令’,表示
Figure 342929DEST_PATH_IMAGE049
的分量。超平面
Figure 268160DEST_PATH_IMAGE056
可写成：  vector
Figure 1837DEST_PATH_IMAGE052
with path at point Tangent. passing point
Figure 84697DEST_PATH_IMAGE049
and with the tangent vector vertical
Figure 993539DEST_PATH_IMAGE055
dimensional hyperplane
Figure 346023DEST_PATH_IMAGE056
at point
Figure 288571DEST_PATH_IMAGE057
(in
Figure 788823DEST_PATH_IMAGE058
) cutting path. The calibration process is to obtain this point (see Figure 2). make ', express
Figure 342929DEST_PATH_IMAGE049
weight. hyperplane
Figure 268160DEST_PATH_IMAGE056
can be written as:

。 .

于是校正过程就是解方程组  Then the calibration process is to solve the system of equations

牛顿迭代的迭代格式为： The iteration format of Newton iteration is:

Figure 166212DEST_PATH_IMAGE063
Figure 166212DEST_PATH_IMAGE063

同样，在这一步中我们依然要更新局部静态变量校正点并对校正点进行判断以便做出下一次校正时采取的数据处理方式（如图3所示），调换步主要是每次按照精度要求来监控更新一个精度变量，在这一步中我们需要设计好多的标记位来判断如何进行步长更新，在我们的算法中我们设计了四种标记，主要是根据路径跟踪函数的特征来设计的，这个涉及到数学当中非线性规划问题的研究，在这里就不做介绍了。最后一步校验步就是一个终止条件的判断，只要符合我们既定的终止条件，那么就可以得出目标问题的解否则转回预估步。整个实施方式就按照上面的方式即可完成。 Similarly, in this step, we still need to update the local static variable correction points and judge the correction points in order to make the data processing method for the next correction (as shown in Figure 3). The exchange step is mainly based on the accuracy requirements each time To monitor and update a precision variable, in this step we need to design a lot of flag bits to determine how to update the step size. In our algorithm, we designed four kinds of flags, mainly based on the characteristics of the path tracking function. This research involving nonlinear programming problems in mathematics will not be introduced here. The final check step is a judgment of the termination condition. As long as it meets our established termination conditions, the solution to the target problem can be obtained, otherwise it will return to the estimation step. The whole implementation mode can be completed according to the above manner.

除说明书所述的技术特征外，均为本专业技术人员的已知技术。  Except for the technical features described in the instructions, all are known technologies by those skilled in the art. the

Claims (1)

1. the path following method based on linux, is characterized in that for solving Nonlinear System of Equations
Figure 247448DEST_PATH_IMAGE001
Result, at first to choose a simple equation , its solution
Figure 835741DEST_PATH_IMAGE003
Known or solve than being easier to, then construct one with parameter
Figure 6DEST_PATH_IMAGE004
Smooth function
Figure 241632DEST_PATH_IMAGE005
, it is met
；
And equation under certain conditions, The solution set comprise one from Start, level off to lineoid Smooth curve
Figure 444074DEST_PATH_IMAGE010
,
Figure 942051DEST_PATH_IMAGE010
Other end limit point be
Figure 448119DEST_PATH_IMAGE011
,
Figure 664337DEST_PATH_IMAGE012
Be
Figure 359891DEST_PATH_IMAGE001
Solution;
Described certain condition is at first to path function
Figure 712375DEST_PATH_IMAGE005
Carry out modeling, then exist
Figure 389344DEST_PATH_IMAGE013
Interval by the initialization step, estimate step, proofread and correct step, transposing step, verification walk five steps and followed the tracks of, and finally obtains objective function
Figure 889596DEST_PATH_IMAGE014
Solution;
To path function
Figure 575792DEST_PATH_IMAGE005
Carry out in the process of modeling, the two-dimentional sparse matrix of taking reduces space complexity and time complexity as parameter; Mainly some global variables are carried out to initialization in the initialization step; In estimating step, take tangent line first to estimate the mode that all the other secants estimate and estimated, with this, reduced time complexity; Monitor tracing step and carry out the step-length renewal according to optimal strategy in the transposing step; Final step verification step is used for judging whether the error of trace point and actual point meets set requirement, if meet method in a word, otherwise continue to forward to, estimates step;
Due to five steps, following the tracks of is a process constantly circulated, therefore good communication and the parameter setting of each step, adopt the managed mixed mode of global variable and local static variable, the sparse matrix of taking when the design of key data structure and common matrix are mixed deposits the dynamic management structure, and concrete steps are as follows:
The design of pre-service and matrix of coefficients data structure
For the communication of well carrying out each step, we have taked the mode of global variable, such as precision, step-length, initial point, estimate point, check point, initially estimate direction, estimate direction etc. and all seal up for safekeeping and unifiedly in the middle of a global profile monitor renewal, the benefit of doing like this is to have lacked the assignment back and forth of a lot of intermediate variables in data exchange process, when data volume is large, the assignment time overhead is also very large, and be convenient to communication and debugging, therefore, before following the tracks of, at first these data to be carried out to pre-service;
In order to solve the asymmetry problem of vector in the middle of nonlinear programming problem, this method has been taked the data structure of sparse matrix and normal two-dimensional array and the data structure of depositing is carried out the processing of data, like this for different nonlinear programming problems, take two sets of data structures and homography computing method to be switched, the strategy of switching is: " number of non-zero entry is more than three times of null element number ", not only reduced space expense, and greatly reduce time complexity, here we only introduce the data structure volume description of sparse matrix:
struct Trituple{
Int row_index; The rower of // non-zero entry
Int col_index; The row mark of // non-zero entry
Double value; // element value
};
struct SparseMatrix{
Int Mrx_row; The row of // matrix
Int Mrx_col; // matrix column
Trituple* data; // tlv triple array
}；
Such as
Figure 782782DEST_PATH_IMAGE015
Such matrix takes the structure of sparse matrix to describe, and effect is apparent, and the ratio that this structure occupies in the middle of actual nonlinear programming problem is more higher;
The path trace process
Follow the trail of by
Figure 896232DEST_PATH_IMAGE016
In the process in the homotopy path of determining, method is divided following five steps:
1. initialization walks: provide three amounts in the initialization step: an initial point
Figure 634512DEST_PATH_IMAGE017
, an initialization step-length , carry out initialization in global variable step; Last allowable error
Figure 185896DEST_PATH_IMAGE019
Take macrodefined mode to set in inf;
2. estimate step: after obtaining initial point, carry out estimating of next point, the first step takes tangent line to estimate, and what all the other were taked is that secant is estimated mode, at first obtains at initial point
Figure 470247DEST_PATH_IMAGE020
The unit tangent vector at place
Figure 679511DEST_PATH_IMAGE021
,
Calculate Draw and estimate a little
Figure 889093DEST_PATH_IMAGE023
, the follow-up process of estimating is that the difference by getting the point after the current check point obtained and a upper correction thereof is carried out secant and estimated; Here used with the Gauss method of elimination of pivot in a column and asked tangent vector
Figure 154465DEST_PATH_IMAGE021
, below simply introduce the Gauss method of elimination with pivot in a column;
Figure 54287DEST_PATH_IMAGE024
Choose
Figure 620398DEST_PATH_IMAGE025
, make
Figure 656487DEST_PATH_IMAGE026
Maximize, and carry out following row exchange
Figure 344957DEST_PATH_IMAGE027
Figure 466497DEST_PATH_IMAGE028
It is that specifically the following formula of mistake obtains by with adjacent 2 of calculating, determining that is estimated a direction that secant is estimated main method:
Also having a kind of mode of estimating is that three Hermite estimate, and concrete formula is as follows:
Figure 805523DEST_PATH_IMAGE030
When estimating for the first time, only has point of initial value point, therefore, the mode that can only take tangent line to estimate, tangent line is estimated in the process of calculating tangent vector very consuming time, therefore, as long as obtain after first estimates a little, just taking simple and effective secant to estimate mode, this method can be fast a lot of on execution efficiency compared with other two kinds of modes, therefore taked first step tangent line to estimate, all the other steps are the mode that secant is estimated;
3. proofread and correct step: with
Figure 602578DEST_PATH_IMAGE031
For initial value, by process of iteration, produce a sequence
Figure 211413DEST_PATH_IMAGE032
, make
Figure 119327DEST_PATH_IMAGE033
For
Figure 192325DEST_PATH_IMAGE034
Approximate and the error of mid point is less than
Figure 160281DEST_PATH_IMAGE035
If iteration does not restrain, dwindle step-length and go back to and estimate step, adopt Newton iteration method here, step is as follows:
From a point
Figure 256413DEST_PATH_IMAGE036
Start, estimate
Figure 781066DEST_PATH_IMAGE037
, it provides its error and is
Figure 911833DEST_PATH_IMAGE038
Coarse estimation
Figure 50691DEST_PATH_IMAGE039
, can prevent this error propagation and be controlled through some step Newton iteration corrections, the initial value of this iterative process is discreet value
Figure 368539DEST_PATH_IMAGE040
, wish iteration convergence in
Figure 946151DEST_PATH_IMAGE041
Solution
Figure 931425DEST_PATH_IMAGE042
Vector
Figure 241183DEST_PATH_IMAGE043
With path
Figure 859378DEST_PATH_IMAGE044
The point
Figure 912784DEST_PATH_IMAGE045
Tangent, through point
Figure 752564DEST_PATH_IMAGE040
And with tangent vector
Figure 233224DEST_PATH_IMAGE043
Vertical
Figure 853561DEST_PATH_IMAGE046
The dimension lineoid
Figure 445080DEST_PATH_IMAGE047
The point
Figure 404946DEST_PATH_IMAGE048
(wherein
Figure 56507DEST_PATH_IMAGE049
) locate cutting path, trimming process is exactly in order to obtain this point, order
Figure 663942DEST_PATH_IMAGE050
',
Figure 59151DEST_PATH_IMAGE051
Mean
Figure 873523DEST_PATH_IMAGE040
Component, lineoid
Figure 758303DEST_PATH_IMAGE047
Can be write as:
Figure 25336DEST_PATH_IMAGE052
So trimming process is exactly solving equations
Figure 224236DEST_PATH_IMAGE053
The Iteration of Newton iteration is:
Newton iteration is local convergence, exists
Figure 699528DEST_PATH_IMAGE055
In exist a little
Figure 453857DEST_PATH_IMAGE042
A certain field
Figure 456448DEST_PATH_IMAGE056
, work as initial value
Figure 42150DEST_PATH_IMAGE057
The time, the Newton iteration convergence, if from
Figure 206416DEST_PATH_IMAGE040
The Newton iteration set out is not restrained, and by dwindling, estimates step-length
Figure 448041DEST_PATH_IMAGE018
, make
Figure 988744DEST_PATH_IMAGE040
Drop in certain neighborhood of Newton iteration convergence;
The distinguishing rule of iteration stopping has two kinds: the first, do not converge on a close point if estimate iteration, and should stop immediately iteration; The second, if iteration convergence, when approximate solution all in error up to specification
Figure 179685DEST_PATH_IMAGE019
In, also stop iteration, in the design of method, adopt well to comprise both of these case with the if structure, mistake estimate a little and perpendicular to the lineoid of estimating direction on proofreaied and correct, the correction equation group
Figure 780430DEST_PATH_IMAGE058
，
Wherein, vector dMean to estimate direction;
4. adjust step-length: this step mainly is considered for precision and cycle index, in trimming process, if
Figure 243773DEST_PATH_IMAGE059
Meet the demands, adjustment step-length that will be suitable
Figure 588166DEST_PATH_IMAGE018
, otherwise control flow turns back to and estimates step, in the process of method design, step-length carried out to mark successively, and in the Predictor Corrector process each time, this variable is becoming always, so realizes with the local variable of a static state;
5. verification walks: this step is the termination signal of whole path trace, once
Figure 882882DEST_PATH_IMAGE059
Middle component
Figure 654528DEST_PATH_IMAGE004
Equal 0 or close to 0, just stop following the tracks of, in the Newton iteration method process, at every turn all right tDo inspection, if the condition meet stopped, method just allow iterative loop stop and final result to out.
CN2013103485777A 2013-08-12 2013-08-12 Path tracking method based on linux Pending CN103425838A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN2013103485777A CN103425838A (en) 2013-08-12 2013-08-12 Path tracking method based on linux

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN2013103485777A CN103425838A (en) 2013-08-12 2013-08-12 Path tracking method based on linux

Publications (1)

Publication Number Publication Date
CN103425838A true CN103425838A (en) 2013-12-04

Family

ID=49650570

Family Applications (1)

Application Number Title Priority Date Filing Date
CN2013103485777A Pending CN103425838A (en) 2013-08-12 2013-08-12 Path tracking method based on linux

Country Status (1)

Country Link
CN (1) CN103425838A (en)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104362664A (en) * 2014-07-28 2015-02-18 浙江工业大学 Grid connection method of medium-voltage microgrid system
CN106181066A (en) * 2016-08-24 2016-12-07 上海柏楚电子科技有限公司 A kind of tubing cutting method based on reverse-engineering
CN108827331A (en) * 2018-06-27 2018-11-16 西南交通大学 A kind of intelligent vehicle method for planning track based on neighborhood system
CN113167586A (en) * 2018-11-30 2021-07-23 泰雷兹控股英国有限公司 Method and apparatus for determining the position of a vehicle

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1059617A2 (en) * 1999-06-10 2000-12-13 Dassault Systèmes Swept volume model
US7849425B1 (en) * 2006-09-29 2010-12-07 Breker Verification Systems, Inc. Generating self-checking test cases from a reduced case analysis graph using path inheritance
CN103139568A (en) * 2013-02-05 2013-06-05 上海交通大学 Video image stabilizing method based on sparseness and fidelity restraining

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1059617A2 (en) * 1999-06-10 2000-12-13 Dassault Systèmes Swept volume model
US7849425B1 (en) * 2006-09-29 2010-12-07 Breker Verification Systems, Inc. Generating self-checking test cases from a reduced case analysis graph using path inheritance
CN103139568A (en) * 2013-02-05 2013-06-05 上海交通大学 Video image stabilizing method based on sparseness and fidelity restraining

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
何杭佳等: "同伦连续方法及其在非线性规划中的应用", 《玉林师范学院学报（自然科学）》 *
同伦连续方法及其在非线性规划中的应用;何杭佳等;《玉林师范学院学报（自然科学）》;20071231;第28卷(第5期);第11-14页 *
王斌: "解非线性规划的同伦JFNK方法", 《中国优秀硕士学位论文全文数据库<基础科学辑>》 *

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104362664A (en) * 2014-07-28 2015-02-18 浙江工业大学 Grid connection method of medium-voltage microgrid system
CN106181066A (en) * 2016-08-24 2016-12-07 上海柏楚电子科技有限公司 A kind of tubing cutting method based on reverse-engineering
CN106181066B (en) * 2016-08-24 2018-05-29 上海柏楚电子科技有限公司 A kind of tubing cutting method based on reverse-engineering
CN108827331A (en) * 2018-06-27 2018-11-16 西南交通大学 A kind of intelligent vehicle method for planning track based on neighborhood system
CN108827331B (en) * 2018-06-27 2021-05-18 西南交通大学 Intelligent vehicle track planning method based on neighborhood system
CN113167586A (en) * 2018-11-30 2021-07-23 泰雷兹控股英国有限公司 Method and apparatus for determining the position of a vehicle
CN113167586B (en) * 2018-11-30 2024-05-28 泰雷兹控股英国有限公司 Method and device for determining the position of a vehicle

Similar Documents

Publication Publication Date Title
CN102915227B (en) Parallel method for large-area drainage basin extraction
CN109446471B (en) A data transfer method for fluid-structure interaction interface considering load uncertainty
CN104361036A (en) Association rule mining method for alarm event
CN105389469A (en) Automatic calibration method of storm water management model parameters
CN103425838A (en) Path tracking method based on linux
CN102722611B (en) Method for carrying out parallelization numerical simulation on hydrodynamic force conditions of river provided with cascade hydropower station
CN119583052B (en) Star-ground continuous variable quantum key distribution modulation variance optimization method and application
CN104993491A (en) Linear power flow calculation method with voltage and reactive power being taken into consideration
CN107871058B (en) Power flow calculation method, device, equipment and storage medium for combined electric and heat system
AU2023203387A1 (en) Method and apparatus for determining degree of quantum entanglement, device and storage medium
CN105490836B (en) A Monte Carlo Evaluation Method for Reliability of Complex Networks
Kerimov et al. State estimation in water distribution system via diffusion on the edge space
CN106096183B (en) A Multiple Parallel Method Based on Feature Line Method
CN105005638B (en) A kind of High Level Synthesis dispatching method based on linear delay model
CN108073776B (en) Complex river network trunk and branch intersection grid drawing and river center continent grid processing method
CN106200655A (en) The FPGA implementation method of BTT guided missile Neural Network Inversion automatic pilot
CN105116721A (en) Water tank system identification method based on least square
CN116244894B (en) A power system transient simulation method and system based on large step size
CN113432608A (en) Generalized high-order CKF algorithm based on maximum correlation entropy and suitable for INS/CNS integrated navigation system
CN113935256B (en) High-dimensional complex aircraft system reduced order characterization method based on error correction
CN114913301B (en) Hexahedral grid self-adaption method based on posterior error estimation
CN103268522A (en) runoff algorithm
CN102650982A (en) LM (Levenberg-Marquard) algorithm realizing method based on FPGA (Field Programmable Gate Array)
CN108233947A (en) A kind of system polarization code encryption algorithm optimization method
He et al. Aerodynamic data fusion with a multi-fidelity surrogate modeling method

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
WD01 Invention patent application deemed withdrawn after publication
WD01 Invention patent application deemed withdrawn after publication

Application publication date: 20131204