zldmЗаводская лаборатория. Диагностика материаловIndustrial laboratory. Diagnostics of materials1028-68612588-0187ООО «Издательство «ТЕСТ-ЗЛ»10.26896/1028-6861-2024-90-5-79-87zldm-2202Research ArticleМАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯMATHEMATICAL METHODS OF INVESTIGATIONСпуск по узловым прямым и симплекс-алгоритм — два варианта регрессионного анализа на основе метода наименьших модулейDescent along nodal straight lines and simplex algorithm: two variants of regression analysis based on the least absolute deviation methodГоловановО. А.GolovanovO. A.

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

620002, Екатеринбург, ул. Мира, д. 19

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

Oleg A. Golovanov

19, ul. Mira, Yekaterinburg, 620002

29, ul. Moskovskaya, Yekaterinburg, 620014

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

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

620002, Екатеринбург, ул. Мира, д. 19

620049, Екатеринбург, ул. Студенческая, д. 54а

Alexander N. Tyrsin

19, ul. Mira, Yekaterinburg, 620002

54a, ul. Studencheskaya, Yekaterinburg, 620049

at2001@yandex.ruУральский федеральный университет имени первого Президента России Б. Н. Ельцина; Институт экономики Уральского отделения РАНРоссияThe First President of Russia B. N. Yeltsin Ural Federal University; Institute of Economics, Ural Branch of RASRussian FederationУральский федеральный университет имени первого Президента России Б. Н. Ельцина; Научно-инженерный центр «Надежность и ресурс больших систем и машин» Уральского отделения РАНРоссияThe First President of Russia B. N. Yeltsin Ural Federal University; Science and Engineering Center «Reliability and Resource of Large Systems and Machines», Ural Branch of RASRussian Federation2024230520249057987Copyright © Голованов О.А., Тырсин А.Н., 20242024Голованов О.А., Тырсин А.Н.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/2202

Проведен сравнительный анализ вычислительной сложности точных алгоритмов оценивания линейных регрессионных уравнений методом наименьших модулей. Цель работы — сравнение вычислительной эффективности точных алгоритмов спуска по узловым прямым и алгоритмов, основанных на решении задачи линейного программирования. Для этого рассмотрены алгоритм градиентного спуска по узловым прямым и алгоритмы решения эквивалентной прямой и двойственной задач линейного программирования с использованием симплекс-метода. Выполнена оценка вычислительной сложности алгоритмов реализации метода наименьших модулей с помощью решения прямой и двойственной задач линейного программирования. Также с помощью метода статистических испытаний Монте-Карло проведено сравнение среднего времени определения коэффициентов регрессии с помощью решения прямой и двойственной задач линейного программирования со средним временем градиентного спуска по узловым прямым. Установлено, что оба варианта значительно уступают градиентному спуску по узловым прямым как в плане вычислительной сложности алгоритмов, так и по времени вычисления. При этом выигрыш алгоритма спуска по узловым прямым растет с увеличением объема выборки, достигая сотни и более раз.

A comparative analysis of the computational complexity of exact algorithms for estimating linear regression equations was conducted using the least absolute deviation method. The goal of the study is to compare the computational efficiency of exact algorithms for descent along nodal lines and algorithms based on solving linear programming problems. For this purpose, the algorithm of gradient descent along nodal lines and algorithms for solving the equivalent primal and dual linear programming problems using the simplex method were considered. The computational complexity of algorithms for implementing the method of least modules in solving direct and dual linear programming problems was estimated. A comparison between the average time for determining the regression coefficients using the primal and dual linear programming problems and the average time for gradient descent along nodal lines was conducted using the Monte Carlo method of statistical experiments. It is shown that both options are significantly inferior behind gradient descent along nodal lines, both in terms of the computational complexity of the algorithms and in terms of computation time, and this advantage increases with the sample size, reaching hundred times or more.

метод наименьших модулейлинейная регрессиясимплекс-алгоритмузловая прямаявычислительная эффективностьleast absolute deviations methodlinear regressionsimplex algorithmnodal straight linecomputational efficiencyReferencesМудров В. И., Кушко В. Л. Методы обработки измерений. Квазиправдоподобные оценки. — М.: Радио и связь, 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. N 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., Podinovskiy V. V. Approximation of tabular given functions: multicriteria approach / Computational Mathematics and Mathematical Physics. 2023. Vol. 63. N 5. P. 739 – 742. DOI: 10.1134/S0965542523050147Basset G., Koenker R. Asymptotic theory of least absolute error regression / Journal of the American Statistical Association. 1978. Vol. 73. N 363. P. 618 – 622.Basset G., Koenker R. Asymptotic theory of least absolute error regression / Journal of the American Statistical Association. 1978. Vol. 73. N 363. P. 618 – 622.Birkes D., Dodge Y. Alternative Methods of Regression. — John Wiley & Sons, 1993. — 239 p.Birkes D., Dodge Y. Alternative Methods of Regression. — John Wiley & Sons, 1993. — 239 p.Болдин М. В., Симонова Г. И., Тюрин Ю. Н. Знаковый статистический анализ линейных моделей. — М.: Наука. Физматлит, 1997. — 288 с.Boldin M. V., Simonova G. I., Tyurin Yu. N. Sign statistical analysis of linear models. — Moscow: Nauka. Fizmatlit, 1997. — 288 p. [in Russian].Wei Xue, Wensheng Zhang, Gaohang Yu. Least absolute deviations learning of multiple tasks / Journal of Industrial & Management Optimization. 2018. N 14(2). P. 719 – 729. DOI: 10.3934/jimo.2017071Wei Xue, Wensheng Zhang, Gaohang Yu. Least absolute deviations learning of multiple tasks / Journal of Industrial & Management Optimization. 2018. N 14(2). P. 719 – 729. DOI: 10.3934/jimo.2017071Вучков И., Бояджиева Л., Солаков Е. Прикладной линейный регрессионный анализ / Пер. с болг. — М.: Финансы и статистика, 1987. — 239 с.Vuchkov I., Boyadzhieva L., Solakov E. Applied linear regression analysis. — Moscow: Finansy i statistika, 1987. — 239 p. [Russian translation].Авдюшев В. А., Мезенцева А. Д. Метод наименьших модулей и его эффективность при обработке измерений с ошибками различного распределения / Известия вузов. Физика. 2012. Т. 55. № 10-2. С. 68 – 76.Avdyushev V. A., Mezentseva A. D. The method of least modules and its effectiveness in processing measurements with errors of various distributions / Izv. Vuzov. Fizika. 2012. Vol. 55. N 10 – 2. P. 68 – 76 [in Russian].Тырсин А. Н., Азарян А. А. Точное оценивание линейных регрессионных моделей методом наименьших модулей на основе спуска по узловым прямым / Вестник ЮУрГУ. Серия «Математика. Механика. Физика». 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. Yuzh.-Ural. Gos. Univ. Ser. Matem. Mekh. Fizika. 2018. Vol. 10. No. 2. P. 47 – 56 [in Russian]. DOI: 10.14529/mmph180205Bloomfield P., Steiger W. L. Least Absolute Deviations: Theory, Applications, and Algorithms. — Boston – Basel – Stuttgart: Birkhauser, 1983. — 349 p.Bloomfield P., Steiger W. L. Least Absolute Deviations: Theory, Applications, and Algorithms. — Boston – Basel – Stuttgart: Birkhauser, 1983. — 349 p.Азарян А. А. Быстрые алгоритмы моделирования многомерных линейных регрессионных зависимостей на основе метода наименьших модулей: дис. ... канд. физ.-мат. наук. — Екатеринбург, 2018.Azaryan A. A. Fast algorithms for modeling multivariate linear regression dependencies based on the least modulus method. Candidate’s thesis. — Yekaterinburg, 2018 [in Russian].Тырсин А. Н. Алгоритмы спуска по узловым прямым в задаче оценивания регрессионных уравнений методом наименьших модулей / Заводская лаборатория. Диагностика материалов. 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. N 5. P. 68 – 75 [in Russian]. DOI: 10.26896/1028-6861-2021-87-5-68-75Barrodale I., Roberts F. D. K. An improved algorithm for discrete L1 linear approximation / SIAM Journal on Numerical Analysis. 1973. Vol. 10. P. 839 – 848.Barrodale I., Roberts F. D. K. An improved algorithm for discrete L1 linear approximation / SIAM Journal on Numerical Analysis. 1973. Vol. 10. P. 839 – 848.Narula S. C., Wellington J. F. Algorithm AS108: Multiple linear regression with minimum sum of absolute errors / Applied Statistics. 1977. Vol. 26. P. 106 – 111.Narula S. C., Wellington J. F. Algorithm AS108: Multiple linear regression with minimum sum of absolute errors / Applied 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 / Applied 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 / Applied 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. Yuzh.-Ural. Gos. Univ. Ser. Matem. Mekh. Fizika. 2019. Vol. 11. N 4. P. 32 – 38 [in Russian]. DOI 10. 14529/mmph190404Голованов О. А., Тырсин А. Н. Регрессионный анализ данных на основе метода наименьших модулей в динамических задачах оценивания / Заводская лаборатория. Диагностика материалов. 2023. Т. 89. № 5. С. 71 – 80. DOI: 10.26896/1028-6861-2023-89-5-71-80Golovanov O. A., Tyrsin A. N. Regression analysis of data based on the method of least absolute deviations in dynamic estimation problems / Industr. Lab. Mater. Diagn. 2023. Vol. 89. N 5. P. 71 – 80 [in Russian]. DOI: 10.26896/1028-6861-2023-89-5-71-80Wesolowsky G. O. A new descent algorithm for the least absolute value regression problem / Communications in Statistics, Simulation and Computation. 1981. Vol. 10. N 5. P. 479 – 491. DOI: 10.1080/03610918108812224Wesolowsky G. O. A new descent algorithm for the least absolute value regression problem / Communications in Statistics, Simulation and Computation. 1981. Vol. 10. N 5. P. 479 – 491. DOI: 10.1080/03610918108812224Hawley R. W., Gallagher Jr. N. C. On Edgeworth’s method for minimum absolute error linear regression / IEEE Transactions on Signal Processing. 1994. Vol. 42. N 8. P. 2045 – 2054. DOI: 10.1109/78.301827Hawley R. W., Gallagher Jr. N. C. On Edgeworth’s method for minimum absolute error linear regression / IEEE Transactions on Signal Processing. 1994. Vol. 42. N 8. P. 2045 – 2054. DOI: 10.1109/78.301827Тырсин А. Н., Максимов К. Е. Оценивание линейных регрессионных уравнений с помощью метода наименьших модулей / Заводская лаборатория. Диагностика материалов. 2012. Т. 78. № 7. С. 65 – 71.Tyrsin A. N., Maksimov K. Ye. Estimation of linear regression equations using the method of least modules / Industr. Lab. Mater. Diagn. 2012. Vol. 78. N 7. P. 65 – 71 [in Russian].Богданова Е. Л., Соловейчик К. А., Аркина К. Г. Оптимизация в проектном менеджменте. Линейное программирование. — СПб.: Университет ИТМО, 2017. — 165 с. https://books.ifmo.ru/file/pdf/2252.pdfBogdanova Ye. L., Soloveychik K. A., Arkina K. G. Optimization in project management: linear programming. — St. Petersburg: ITMO University, 2017. — 165 p. [in Russian] https://books.ifmo.ru/file/pdf/2252.pdfTukey J. W. A Survey of Sampling from Contaminated Distribution / Contributions to Probability and Statistics. — Stanford: Stanford Univ. Press, 1960. P. 443 – 485.Tukey J. W. A Survey of Sampling from Contaminated Distribution / Contributions to Probability and Statistics. — Stanford: Stanford Univ. Press, 1960. P. 443 – 485.Хьюбер П. Робастность в статистике / Пер. с англ. — М.: Мир, 1984. — 304 с.Huber P. Robust Statistics. — John Wiley & Sons, 1981. — 320 p.Chow G. C. Tests of equality between sets of coefficients in two linear regressions / Econometrica. 1960. Vol. 28. N 3. P. 591 – 605. DOI: 10.2307/1910133Chow G. C. Tests of equality between sets of coefficients in two linear regressions / Econometrica. 1960. Vol. 28. N 3. P. 591 – 605. DOI: 10.2307/1910133

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