Dynamic Implementation of Modified Gradient Descent Along Nodal Lines: A Brief Overview

Abstract


Dynamic monitoring of rapidly varying processes requires high-speed and robust methods for estimating system parameters in real-time, ensuring timely detection of critical deviations. Linear regression analysis remains a key tool for solving such problems; however, the classical least squares method exhibits a reduction in accuracy when the conditions of error normality are violated and in the presence of outliers in the data, which limits its applicability under conditions of stochastic data heterogeneity. The alternative least absolute deviations method provides increased robustness of estimates to anomalies and heavy-tailed distributions. However, its traditional implementation is associated with low computational speed, which hinders its use in streaming data analysis tasks.The aim of the article is to present improved algorithms of coordinate descent along nodal lines for solving the least absolute deviations problem. Key optimizations include the use of directional derivatives along nodal lines, analysis of their slope angle, and application of a first approximation strategy. This allowed for a significant reduction in the computational complexity of the algorithm compared to the base implementation. For real-time monitoring tasks, a dynamic version of the algorithm is proposed, based on a sliding observation window and using the solution from the previous step as the initial approximation.Research results demonstrate a significant increase in the computational efficiency of descent along nodal lines while maintaining estimation accuracy. The algorithm's complexity has been reduced to a level acceptable for processing high-dimensional data in real-time. Comparative analysis confirms the advantages of the proposed approach over-known optimization methods (simplex method, interior point method, gradient projection method) both in terms of operating speed and asymptotic complexity. The dynamic implementation of the algorithm brings the analysis time closer to that of the least squares method, eliminating the historical lag of the least absolute deviations method in computational costs.

Full Text

3

About the authors

O. A Golovanov

Institute of Economics, Ural Branch, Russian Academy of Science

References

  1. Волкова, В.Н. Теория систем и системный анализ: учебник / В.Н. Волкова, А.А. Денисов. – 2-е изд., перераб. и доп. – М.: Юрайт, 2014. – 616 с.
  2. Zeigler, B.P. Theory of Modeling and Simulation / B.P. Zeigler, H. Praehofer, T.G. Kim. – 2nd ed. – San Diego: Academic Press, 2000. – 510 p.
  3. Богданофф, Дж. Вероятностные модели накопления повреждений / Дж. Богданофф, Ф. Козин. – М.: Мир, 1989. – 344 с.
  4. Гражданская защита: энциклопедия: в 4 т. Т. 2: К–О. – М.: ФГБУ ВНИИ ГОЧС (ФЦ), 2015. – 624 с.
  5. Шихалев, Д.В. Проблемы управления системой обеспечения пожарной безопасности объекта. Ч. 2. Методы мониторинга / Д.В. Шихалев // Проблемы управления. – 2022. – № 2. – С. 3–11. – doi: 10.25728/pu.2022.2.1
  6. Пресняков, В.Ф. Параметры и показатели мониторинга состояния предприятия / В.Ф. Пресняков // Экономика и математические методы. – 2022. – Т. 58, № 3. – С. 70–78. – doi: 10.31857/S042473880021700-9.
  7. Голованов, О.А. Спуск по узловым прямым в задачах устойчивого мониторинга динамических регрессионных моделей / О.А. Голованов, А.Н. Тырсин // Информационные технологии и вычислительные системы. – 2025. – № 2. – С. 51–63. doi: 10.14357/20718632250205
  8. Савоскина, Е.В. Анализ инновационных механизмов решения жилищных проблем в Российской Федерации / Е.В. Савоскина, Н.А. Солопов, Е.П. Акри, С.В. Домнина // Вестник МГСУ. – 2022. – Т. 17, № 8. – С. 1096–1112. doi: 10.22227/1997-0935.2022.8.1096-1112
  9. Акимов, П.А. Итерационный алгоритм для l₁-аппроксимации в динамических задачах оценивания / П.А. Акимов, А.И. Матасов // Автоматика и телемеханика. – 2015. – № 5. – С. 7–26.
  10. Демиденко, Е.З. Линейная и нелинейная регрессия / Е.З. Демиденко. – М.: Финансы и статистика, 1981. – 302 с.
  11. Мудров, В.И. Методы обработки измерений: квазиправдоподобные оценки / В.И. Мудров, В.Л. Кушко. – М.: Радио и связь, 1983. – 304 с.
  12. Айвазян, С.А. Прикладная статистика. Исследование зависимостей / С.А. Айвазян, И.С. Енюков, Л.Д. Мешалкин. – М.: Финансы и статистика, 1985. – 488 с.
  13. Greene, W. H. Econometric Analysis / W. H. Greene. – 8th global ed. – London: Pearson Education, 2020. – 1320 p.
  14. Орлов, А.И. Часто ли распределение результатов наблюдений является нормальным? / А.И. Орлов // Заводская лаборатория. – 1991. – Т. 57, № 7. – С. 64–66.
  15. Tukey, J.W. The Future of Data Analysis / J.W. Tukey // Breakthroughs in Statistics: Methodology and Distribution. – New York: Springer, 1962. – P. 408–452. doi: 10.1007/978-1-4612-4380-9_31
  16. Ершов, А.А. Стабильные методы оценивания параметров (обзор) / А.А. Ершов // Автоматика и телемеханика. – 1978. – № 8. – С. 66–100.
  17. Dantzig, G.B. Maximization of a Linear Function of Variables Subject to Linear Inequalities / G.B. Dantzig // Activity Analysis of Production and Allocation. – 1951. – Vol. 13. – P. 339–347.
  18. Панюков, А.В. Параметрическая идентификация квазилинейного разностного уравнения / А.В. Панюков, Я.А. Мезал // Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика. – 2019. – Т. 11, № 4. – С. 32–38. doi: 10.14529/mmph190404
  19. Зоркальцев, В.И. Метод внутренних точек: история и перспективы / В.И. Зоркальцев // Журнал вычислительной математики и математической физики. – 2019. – Т. 59, № 10. – С. 1649–1665. doi: 10.1134/S0044466919100181
  20. Дикин, И.И. Итеративное решение задач линейного и квадратичного программирования / И.И. Дикин // Доклады АН СССР. – 1967. – Т. 174, № 4. – С. 747–748.
  21. Тырсин, А.Н. Алгоритмы спуска по узловым прямым в задаче оценивания регрессионных уравнений методом наименьших модулей / А.Н. Тырсин // Заводская лаборатория. Диагностика материалов. – 2021. – Т. 87, № 5. – С. 68–75. doi: 10.26896/1028-6861-2021-87-5-68-75
  22. Голованов, О.А. Модифицированный алгоритм градиентного спуска по узловым прямым в задаче регрессионного анализа / О.А. Голованов, А.Н. Тырсин // Заводская лаборатория. Диагностика материалов. – 2025. – Т. 91, № 3. – С. 83–92. doi: 10.26896/1028-6861-2025-91-3-83-92
  23. Тырсин, А.Н. Точное оценивание линейных регрессионных моделей методом наименьших модулей на основе спуска по узловым прямым / А.Н. Тырсин, А.А. Азарян // Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика. – 2018. – Т. 10, № 2. – С. 47–56. doi: 10.14529/mmph180205
  24. Голованов, О.А. Регрессионный анализ данных на основе метода наименьших модулей в динамических задачах оценивания / О.А. Голованов, А.Н. Тырсин // Заводская лаборатория. Диагностика материалов. – 2023. – Т. 89, № 5. – С. 71–80. doi: 10.26896/1028-6861-2023-89-5-71-80
  25. Голованов, О.А. Устойчивое регрессионное моделирование: методы внутренней точки, симплекс-метод, спуск по узловым прямым / О.А. Голованов, А.Н. Тырсин // Автоматика и телемеханика. – 2025. – № 3. – С. 100–118. doi: 10.31857/S0005231025030063

Statistics

Views

Abstract - 96

PDF (Russian) - 63

Refbacks

  • There are currently no refbacks.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies