Optimization of spline parameters in approximation of multivalued functions

Objectives. Methods for spline approximation of a sequence of points in a plane are increasingly used in various disciplines. A spline is defined as a single-valued function consisting of a known number of repeating elements, of which the most widely used are polynomials. When designing the routes of linear structures, it is necessary to consider a problem with an unknown number of elements. An algorithm implemented for solving this problem when designing a longitudinal profile was published earlier. Here, since the spline elements comprise circular arcs conjugated by line segments, the spline is a single-valued function. However, when designing a route plan, the spline is generally a multivalued function. Therefore, the previously developed algorithm is unsuitable for solving this problem, even if the same spline elements are used. The aim of this work is to generalize the obtained results to the case of approximation of multivalued functions while considering various features involved in designing the routes of linear structures. The first stage of this work consisted in determining the number of elements of the approximating spline using dynamic programming. In the present paper, the next stage of solving this problem is carried out.

Methods. The spline parameters were optimized using a new mathematical model in the form of a modified Lagrange function and a special nonlinear programming algorithm. In this case, it is possible to analytically calculate the derivatives of the objective function with respect to the spline parameters in the absence of its analytical expression.

Results. A mathematical model and algorithm were developed to optimize the parameters of a spline as a multivalued function consisting of circular arcs conjugated by line segments. The initial approximation is the spline obtained at the first stage.

Conclusions. The previously proposed two-stage spline approximation scheme for an unknown number of spline elements is also suitable for approximating multivalued functions given by a sequence of points in a plane, in particular, for designing a plan of routes for linear structures.

1. Karpov D.A., Struchenkov V.I. Two-stage splineapproximation in linear structure routing. Russ. Technol. J. 2021;9(5):45−56 (in Russ.). https://doi.org/10.32362/2500-316X-2021-9-5-45-56

2. Karpov D.A., Struchenkov V.I. Spline approximation of multivalued function in leaner structures routing. Russ. Technol. J. 2022;10(4):65–74 (in Russ.). https://doi.org/10.32362/2500-316X-2022-10-4-65-74

3. Li W., Pu H., Schonfeld P., et al. A method for automatically recreating the horizontal alignment geometry of existing railways. Comput.-Aided Civ. Inf. 2019;34(1):71–94. https://doi.org/10.1111/mice.12392

4. Jha M.K., McCall C., Schonfeld P. Using GIS, genetic algorithms, and visualization in highway development. Comput.-Aided Civ. Inf. 2001;16(6):399–414. https://doi.org/10.1111/0885-9507.00242

5. Jha M.K., Schonfeld P. A highway alignment optimization model using geographic information systems. Transportation Research Part A: Policy and Practice. 2004;38(6):455–481. https://doi.org/10.1016/j.tra.2004.04.001

6. Jong J.C., Jha M.K., Schonfeld P. Preliminary highway design with genetic algorithms and geographic information systems. Comput.-Aided Civ. Inf. 2000;15(4):261–271. https://doi.org/10.1111/0885-9507.00190

7. Kang M.W., Schonfeld P., Yang N. Prescreening and repairing in a genetic algorithm for highway alignment optimization. Comput.-Aided Civ. Inf. 2009;24(2): 109–119. https://doi.org/10.1111/j.1467-8667.2008.00574.x

8. Pushak Y., Hare W., Lucet Y. Multiple-path selection for new highway alignments using discrete algorithms. Eur. J. Oper. Res. 2016;248(2):415–27. https://doi.org/10.1016/j.ejor.2015.07.039

9. Sarma K.C., Adeli H. Bilevel parallel genetic algorithms for optimization of large steel structures. Comput.Aided Civ. Inf. 2001;16(5):295–304. https://doi.org/10.1111/0885-9507.00234

10. Shafahi Y., Bagherian M. A customized particle swarm method to solve highway alignment optimization problem. Comput.-Aided Civ. Inf. 2013;28(1):52–67. https://doi.org/10.1111/j.1467-8667.2012.00769.x

11. Bosurgi G., D’Andrea A. A polynomial parametric curve (PPC-curve) for the design of horizontal geometry of highways. Comput.-Aided Civ. Inf. 2012;27(4):303–312. https://doi.org/10.1111/j.1467-8667.2011.00750.x

12. Cerf R. The quasispecies regime for the simple genetic algorithm with roulette wheel selection. Adv. Appl. Probability. 2017;49(3):903–926. https://doi.org/10.1017/apr.2017.26

13. Borodakii Yu.V., Zagrebaev A.M., Kritsyna N.A., Kulyabichev Yu.P., Shumilov Yu.Yu. Nelineinoe programmirovanie v sovremennykh zadachakh optimizatsii (Nonlinear Programming in Modern Optimization Problem). Moscow: NIYAU MEPhI; 2008. 244 р. (in Russ.).

14. Bazaraa M., Sherali Y., Shetty C. Nonlinear programming. Theory and algorithms. 3rd ed. Hoboken, NJ: Wiley; 2006. 872 p. ISBN 978-0-471-48600-8

15. Betts J.T. Practical methods for optimal control using nonlinear programming. Ser. Advances in Design and Control. Philadelphia: SIAM; 2001. 190 p.

16. Lee J., Leyffer S. Mixed integer nonlinear programming. NY: Springer; 2011. 707 p. https://doi.org/10.1007/978-1-4614-1927-3

17. Sun W., Yuan Y.-X. Optimization theory and methods. Nonlinear programming. NY: Springer; 2006. 688 p. https://doi.org/10.1007/b106451

18. Struchenkov V.I. Metody optimizatsii trass v SAPR lineinykh sooruzhenii (Methods for route optimization in CAD of linear structures). Moscow: SOLON-Press; 2014. 271 р. (in Russ.). ISBN 978-5-91359-139-5

19. Gill F., Myurrei U., Rait M. Prakticheskaya optimizatsiya (Practical Optimization): transl. from Engl. Moscow: Mir; 1985. 509 p. (in Russ.).

20. [Gill Ph.E., Murray W., Wright M.H. Practical Optimization. London: Academic Press; 1981. 402 p.]

21. Audet C., Hare W. Derivative-free and blackbox optimization. Springer Series in Operations Research and Financial Engineering. Springer International Publishing; 2017. 302р. https://doi.org/10.1007/978-3-319-68913-5

22. Kokhenderfer M.D., Uiler T.A. Algoritmy optimizatsii (Algorithms for Optimization). Moscow: Vil’yams; 2020. 528 p. (in Russ.). [Kochenderfer M.D., Wheeler T.A. Algorithms for Optimization. London; The MIT Press; 2019. 520 p.]

23. Chernorutskii I.G. Metody optimizatsii. Komp’yuternye tekhnologii (Methods of optimization. Computer technologies). St. Petersburg: BHV-Petersburg; 2011. 329 p. (in Russ.).

24. Larichev O.I., Gorvits G.G. Metody poiska lokal’nykh ekstremumov ovrazhnykh funktsii (Methods for Finding Local Extrema of Ravine Functions). Moscow: Nauka; 1990. 96 p. (in Russ.).

25. Gill F., Myurrei U. Chislennyemetodyuslovnoioptimizatsii (Numerical methods of conditional optimization): transl. from Engl. Moscow: Mir; 1977. 296 p. (in Russ.). [Gill Ph.E., Murray W. Numerical methods for constrained optimization. London: Academic Press; 1974. 283 p.]