zldmЗаводская лаборатория. Диагностика материаловIndustrial laboratory. Diagnostics of materials1028-68612588-0187ООО «Издательство «ТЕСТ-ЗЛ»10.26896/1028-6861-2025-91-3-83-92zldm-2429Research ArticleМАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯMATHEMATICAL METHODS OF INVESTIGATIONМодифицированный алгоритм градиентного спуска по узловым прямым в задаче регрессионного анализаModified gradient descent algorithm along nodal straight lines in regression analysis problemГоловановО. А.GolovanovO. A.

Олег Александрович Голованов

620014, Екатеринбург, ул. Московская, д. 29

Oleg A. Golovanov

29, Moskovskaya ul., Yekaterinburg, 620014

ТырсинА. Н.TyrsinA. N.

Александр Николаевич Тырсин

620014, Екатеринбург, ул. Московская, д. 29; 620002, Екатеринбург, ул. Мира, д. 19

Alexander N. Tyrsin

29, Moskovskaya ul., Yekaterinburg, 620014; 19, ul. Mira, Yekaterinburg, 620002

at2001@yandex.ruИнститут экономики Уральского отделения РАНРоссияInstitute of Economics, Ural Branch of RASRussian FederationИнститут экономики Уральского отделения РАН; Уральский федеральный университет имени первого Президента России Б.Н. ЕльцинаРоссияInstitute of Economics, Ural Branch of RAS; The first President of Russia B. N. Yeltsin Ural Federal UniversityRussian Federation2025200320259138392Copyright © Голованов О.А., Тырсин А.Н., 20252025Голованов О.А., Тырсин А.Н.Golovanov O.A., Tyrsin A.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.zldm.ru/jour/article/view/2429

Рассмотрены вопросы создания вычислительно эффективных алгоритмов реализации метода наименьших модулей для оценивания регрессионных зависимостей. Цель работы — повышение быстродействия градиентного спуска по узловым прямым за счет учета геометрии целевой функции вблизи минимума, а также его сравнительный анализ с алгоритмом проектирования градиента. Предложен модифицированный алгоритм градиентного спуска для регрессионного оценивания методом наименьших модулей. Эффективность достигнута за счет исключения вычислений значений целевой функции в минимумах узловых прямых и определения улучшенного начального приближения на части выборки. В результате удалось уменьшить зависимость времени вычислений от объема выборки и расширить область использования метода наименьших модулей. Алгоритм проектирования градиента для построения линейных регрессионных зависимостей не гарантирует нахождение точного решения и значительно проигрывает в быстродействии алгоритмам спуска по узловым прямым.

The issues of creating computationally efficient algorithms for implementing the least absolute deviation method for estimating regression dependencies are considered. The purpose of the work is to improve the performance of gradient descent along nodal lines by considering the geometry of the objective function near the minimum, as well as its comparative analysis with the gradient projection algorithm. A modified gradient descent algorithm for regression estimation using the least absolute deviation method is proposed. Efficiency was achieved by excluding the calculation of the objective function values in the minimums of the nodal lines and determining an improved initial approximation on part of the sample. As a result, it was possible to reduce the dependence of computation time on sample size and expand the application area of the least absolute deviation method. The gradient projection algorithm for constructing linear regression dependencies does not guarantee finding an exact solution and is significantly inferior in performance to algorithms for descending along nodal lines.

метод наименьших модулейлинейная регрессияузловая прямаясимплекс-алгоритмградиентвычислительная эффективностьleast absolute deviations methodlinear regressionnodal straight linesimplex algorithmgradientcomputational efficiencyReferencesВероятность и математическая статистика: Энциклопедия / Гл. ред. Ю. В. Прохоров. — М.: Большая Российская энциклопедия, 1999. — 910 с.Probability and mathematical statistics: Encyclopedia / Yu. V. Prokhorov, Chief editor. — Moscow: Bol’shaya Rossiiskaya Éntsiklopediya, 1999. — 910 p. [in Russian].Акимов П. А., Матасов А. И. Итерационный алгоритм для l1-аппроксимации в динамических задачах оценивания / Автоматика и телемеханика. 2015. № 5. С. 7 – 26.Akimov P. A., Matasov A. I. An iterative algorithm for l1-norm approximation in dynamic estimation problems / Automation and Remote Control. 2015. Vol. 76. No. 5. P. 733 – 748. DOI: 10.1134/S000511791505001XDarlington R. B., Hayes A. F. Regression Analysis and Linear Models. Concepts, Applications, and Implementation. — New York – London: The Guilford Press, 2017. — 661 p.Darlington R. B., Hayes A. F. Regression Analysis and Linear Models. Concepts, Applications, and Implementation. — New York – London: The Guilford Press, 2017. — 661 p.Christensen R. Analysis of Variance, Design, and Regression Linear Modeling for Unbalanced Data. 2nd ed. — CRC Press, 2016. — 603 p.Christensen R. Analysis of Variance, Design, and Regression Linear Modeling for Unbalanced Data. 2nd ed. — CRC Press, 2016. — 603 p.Мудров В. И., Кушко В. Л. Методы обработки измерений. Квазиправдоподобные оценки. — М.: Радио и связь, 1983. — 304 с.Mudrov V. I., Kushko V. L. Measurement processing methods. Quasi-plausible estimates. — Moscow: Radio i svyaz’, 1983. — 304 p. [in Russian].Орлов А. И. Многообразие моделей регрессионного анализа (обобщающая статья) / Заводская лаборатория. Диагностика материалов. 2018. Т. 84. № 5. С. 63 – 73. DOI: 10.26896/1028-6861-2018-84-5-63-73Orlov A. I. Diversity of the models for regression analysis (generalizing article) / Industr. Lab. Mater. Diagn. 2018. Vol. 84. No. 5. P. 63 – 73 [in Russian]. DOI: 10.26896/1028-6861-2018-84-5-63-73Нелюбин А. П., Подиновский В. В. Аппроксимация таблично заданных функций: многокритериальный подход / Журнал вычислительной математики и математической физики. 2023. Т. 63. № 5. С. 717 – 730. DOI: 10.31857/S0044466923050174Nelyubin A. P., Podinovski V. V. Approximation of functions defined in tabular form: multicriteria approach / Computational Mathematics and Mathematical Physics. 2023. Vol. 63. No. 5. P. 730 – 742. DOI: 10.1134/S0965542523050147Sheynin O. B. R. J. Boscovich’s work on probability / Archive for History of Exact Sciences. 1973. Vol. 9. Nos. 4 – 5. P. 306 – 324. DOI: 10.1007/BF00348366Sheynin O. B. R. J. Boscovich’s work on probability / Archive for History of Exact Sciences. 1973. Vol. 9. Nos. 4 – 5. P. 306 – 324. DOI: 10.1007/BF00348366Laplace P. S. Sur Quelques du Systeme du Monde. Memories de l’Academie Royale des Science de Paris, 1789. — Paris: Gauthier-Villars, 1895.Laplace P. S. Sur Quelques du Systeme du Monde. Memories de l’Academie Royale des Science de Paris, 1789. — Paris: Gauthier-Villars, 1895.Stigler S. M. Studies in the History of Probability and Statistics. XXXII: Laplace, Fisher and the Discovery of the Concept of Sufficiency / Biometrika. 1973. Vol. 60. No. 3. P. 439 – 445. DOI: 10.1093/biomet/60.3.439Stigler S. M. Studies in the History of Probability and Statistics. XXXII: Laplace, Fisher and the Discovery of the Concept of Sufficiency / Biometrika. 1973. Vol. 60. No. 3. P. 439 – 445. DOI: 10.1093/biomet/60.3.439Basset G., Koenker R. Asymptotic Theory of Least Absolute Error Regression / J. Am. Statist. Assoc. 1978. Vol. 73. No. 363. P. 618 – 622. DOI: 10.1080/01621459.1978.10480065Basset G., Koenker R. Asymptotic Theory of Least Absolute Error Regression / J. Am. Statist. Assoc. 1978. Vol. 73. No. 363. P. 618 – 622. DOI: 10.1080/01621459.1978.10480065Болдин М. В., Симонова Г. И., Тюрин Ю. Н. Знаковый статистический анализ линейных моделей. — М.: Наука; Физматлит, 1997. — 288 с.Boldin M. V., Simonova G. I., Tyurin Yu. N. Sign-based methods in linear statistical models. Translations of Mathematical Monographs. Vol. 162. — Providence, RI: American Mathematical Society. 1997. — 234 p.Тырсин А. Н., Азарян А. А. Точное оценивание линейных регрессионных моделей методом наименьших модулей на основе спуска по узловым прямым / Вестник ЮУрГУ. Серия «Математика. Механика. Физика». 2018. Т. 10. № 2. С. 47 – 56. DOI: 10.14529/mmph180205Tyrsin A. N., Azaryan A. A. Exact evaluation of linear regression models by the least absolute deviations method based on the descent through the nodal straight lines / Vestn. YuUrGU. Ser. «Matem. Mekh. Fiz». 2018. Vol. 10. No. 2. P. 47 – 56 [in Russian]. DOI: 10.14529/mmph180205Тырсин А. Н. Алгоритмы спуска по узловым прямым в задаче оценивания регрессионных уравнений методом наименьших модулей / Заводская лаборатория. Диагностика материалов. 2021. Т. 87. № 5. С. 68 – 75. DOI: 10.26896/1028-6861-2021-87-5-68-75Tyrsin A. N. Algorithms for descending along nodal lines in the problem of estimating regression equations by the method of least modules / Industr. Lab. Mater. Diagn. 2021. Vol. 87. No. 5. P. 68 – 75 [in Russian]. DOI: 10.26896/1028-6861-2021-87-5-68-75Narula S. C., Wellington J. F. Algorithm AS108: Multiple linear regression with minimum sum of absolute errors / Appl. Statistics. 1977. Vol. 26. P. 106 – 111.Narula S. C., Wellington J. F. Algorithm AS108: Multiple linear regression with minimum sum of absolute errors / Appl. Statistics. 1977. Vol. 26. P. 106 – 111.Armstrong R. D., Kung D. S. Algorithm AS132: Least absolute value estimates for a simple linear regression problem / Appl. Statistics. 1978. Vol. 27. P. 363 – 366.Armstrong R. D., Kung D. S. Algorithm AS132: Least absolute value estimates for a simple linear regression problem / Appl. Statistics. 1978. Vol. 27. P. 363 – 366.Панюков А. В., Мезал Я. А. Параметрическая идентификация квазилинейного разностного уравнения / Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика. 2019. Т. 11. № 4. С. 32 – 38. DOI: 10.14529/mmph190404Panyukov A. V., Mezal Ya. A. Parametric identification of quasilinear difference equation / Vestn. YuUrGU. Ser. «Matem. Mekh. Fiz». 2019. Vol. 11. No. 4. P. 32 – 38 [in Russian]. DOI: 10.14529/mmph190404Мезал Я. А. Квазилинейный анализ дискретных моделей нелинейной динамики (временных рядов): дис. ... канд. физ.-мат. наук. — Челябинск, 2020. — 134 с.Mezaal Ya. A. Quasi-linear analysis of discrete models of nonlinear dynamics (time series): Candidate’s Thesis. — Chelyabinsk, 2020. — 134 p. [in Russian].Тырсин А. Н., Голованов О. А. Спуск по узловым прямым и симплекс-алгоритм — два варианта регрессионного анализа на основе метода наименьших модулей / Заводская лаборатория. Диагностика материалов. 2024. Т. 90. № 5. С. 79 – 87. DOI: 10.26896/1028-6861-2024-90-5-79-87Tyrsin A. N., Golovanov O. A. Descent along nodal straight lines and simplex algorithm: two variants of regression analysis based on the least absolute deviation method / Industr. Lab. Mater. Diagn. 2024. Vol. 90. No. 5. P. 79 – 87 [in Russian]. DOI: 10.26896/1028-6861-2024-90-5-79-87Rosen J. B. The gradient projection method for nonlinear programming. Part 1: Linear constraints / J. Soc. Industr. Appl. Math. 1960. Vol. 8. No. 1. P. 181 – 217. DOI: 10.1137/0108011Rosen J. B. The gradient projection method for nonlinear programming. Part 1: Linear constraints / J. Soc. Industr. Appl. Math. 1960. Vol. 8. No. 1. P. 181 – 217. DOI: 10.1137/0108011The travelling salesman problem: a guided tour of combinatorial optimization / E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys, Eds. — J. Wiley & Sons, 1985. — 465 p.The travelling salesman problem: a guided tour of combinatorial optimization / E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys, Eds. — J. Wiley & Sons, 1985. — 465 p.Мину М. Математическое программирование. Теория и алгоритмы / Пер. с франц. — М.: Наука, 1990. — 488 с.Minoux M. Mathematical Programming: Theory and Algorithms. — New York: Wiley, 1986. — 489 p.Barbu A., Zhu S.-C. Monte Carlo Methods. — Springer Nature Singapore Pte Ltd., 2020. — 422 p. DOI: 10.1007/978-981-13-2971-5_1Barbu A., Zhu S.-C. Monte Carlo Methods. — Springer Nature Singapore Pte Ltd., 2020. — 422 p. DOI: 10.1007/978-981-13-2971-5_1Тырсин А. Н. Метод подбора наилучшего закона распределения непрерывной случайной величины на основе обратного отображения / Вестник ЮУрГУ. Серия «Математика. Механика. Физика». 2017. Т. 9. № 1. С. 31 – 38. DOI: 10.14529/mmph170104Tyrsin A. N. The method of selecting the best distribution law for continuous random variables on the basis of inverse mapping / Vestn. YuUrGU. Ser. «Matem. Mekh. Fiz». 2017. Vol. 9. No. 1. P. 31 – 38 [in Russian]. DOI: 10.14529/mmph170104

The authors declare that there are no conflicts of interest present.