 ### Journals Information

Mathematics and Statistics Vol. 9(4), pp. 411 - 420
DOI: 10.13189/ms.2021.090401
Reprint (PDF) (622Kb)

## Two-Stage Spline-Approximation with an Unknown Number of Elements in Applied Optimization Problem of a Special Kind

V. I. Struchenkov *, D. A. Karpov
Department of General Informatics, Institute of Cybernetics of the Russian Technological University (MIREA), Russia

ABSTRACT

Being a continuation of the paper published in Mathematics and Statistics, vol. 7, No. 5, 2019, this article describes the algorithm for the first stage of spline- approximation with an unknown number of elements of the spline and constraints on its parameters. Such problems arise in the computer-aided design of road routes and other linear structures. In this article we consider the problem of a discrete sequence approximation of points on a plane by a spline consisting of line segments conjugated by circular arcs. This problem occurs when designing the longitudinal profile of new and reconstructed railways and highways. At the first stage, using a special dynamic programming algorithm, the number of elements of the spline and the approximate values of its parameters that satisfy all the constraints are determined. At the second stage, this result is used as an initial approximation for optimizing the spline parameters using a special nonlinear programming algorithm. The dynamic programming algorithm is practically the same as in the mentioned article published earlier, with significant simplifications due to the absence of clothoids when connecting straight lines and curves. The need for the second stage is due to the fact that when designing new roads, it is impossible to implement dynamic programming due to the need to take into account the relationship of spline elements in fills and in cuts, if fills will be constructed from soils of cuts. The nonlinear programming algorithm is based on constructing a basis in zero spaces of matrices of active constraints and adjusting this basis when changing the set of active constraints in an iterative process. This allows finding the direction of descent and solving the problem of excluding constraints from the active set without solving systems of linear equations in general or by solving linear systems of low dimension. As an objective function, instead of the traditionally used sum of squares of the deviations of the approximated points from the spline, the article proposes other functions, taking into account the specifics of a specific project task.

KEYWORDS
Route, Plan and Longitudinal Profile, Spline, Nonlinear Programming, Objective Function, Constraints, Basis

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
 V. I. Struchenkov , D. A. Karpov , "Two-Stage Spline-Approximation with an Unknown Number of Elements in Applied Optimization Problem of a Special Kind," Mathematics and Statistics, Vol. 9, No. 4, pp. 411 - 420, 2021. DOI: 10.13189/ms.2021.090401.

(b). APA Format:
V. I. Struchenkov , D. A. Karpov (2021). Two-Stage Spline-Approximation with an Unknown Number of Elements in Applied Optimization Problem of a Special Kind. Mathematics and Statistics, 9(4), 411 - 420. DOI: 10.13189/ms.2021.090401.