Методы негладкого анализа в задаче минимизации суммы модулей от аффинных функций

Методы негладкого анализа в задаче минимизации суммы модулей от аффинных функций

Тамасян Г. Ш., Шульга Г. С.
Дискретный анализ и исследование операций, 31, 4, 168-185 (2024)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2024.31.799

Аннотация:

Демонстрируется применение аппарата конструктивного негладкого анализа на задаче минимизации выпуклой кусочно аффинной функции, заданной в виде суммы модулей от аффинных. Для общего случая использовалось гиподифференциальное исчисление, в скалярном — субдифференциальное. Из анализа критерия оптимальности получено, что точку, доставляющую глобальный минимум, можно найти, решая соответствующую задачу линейного программирования. В скалярном же случае решением задачи является взвешенная медиана узлов ломаной. 
Библиогр. 30.

Литература:
  1. Мудров В. И., Кушко В. Л. Методы обработки измерений: квазиправдоподобные оценки. М.: Радио и связь, 1983. 304 с.
     
  2. Зуховицкий С. И. О приближении несовместной системы линейных уравнений по принципу минимизации суммы модулей всех уклонений // Докл. АН СССР. 1962. Т. 143, № 5. С. 1030–1033.
     
  3. Акимов П. А., Матасов А. И. Итерационный алгоритм для $l_1$-аппроксимации в динамических задачах оценивания // Автоматика и телемеханика. 2015. № 5. С. 7–26.
     
  4. Лакеев А. В., Носков С. И. Метод наименьших модулей для линейной регрессии: число нулевых ошибок аппроксимации // Современные технологии. Системный анализ. Моделирование. 2012. № 2. С. 48–50.
     
  5. Горелик В. А., Трембачева О. С. Решение задачи линейной регрессии с использованием методов матричной коррекции в метрике $l_1$ // Журн. вычисл. математики и мат. физики. 2016. Т. 56, № 2. С. 202–207.
     
  6. Сурин В. А., Тырсин А. Н. Применение обобщенного метода наименьших модулей в задачах обработки и анализа изображений // Вестн. Астрахан. гос. техн. ун-та. Сер. Управление, вычисл. техника и информатика. 2020. № 2. С. 45–55. DOI: 10.24143/2072-9502-2020-2-45-55.
     
  7. Тамасян Г. Ш. О диких точках // Семинар по оптимизации, машинному обучению и искусственному интеллекту. Избр. докл. С.-Пб.: С.-Петербург. гос. ун-т, 2023. 5 с. URL: oml.cmlaboratory.com/reps23.shtml (дата обращения: 27.10.2024).
     
  8. Шарый С. П. Сильная согласованность в задаче восстановления зависимостей при интервальной неопределенности данных // Вычисл. технологии. 2017. Т. 22, № 2. С. 150–172.
     
  9. Шарый С. П., Шарая И. А. Распознавание разрешимости интервальных уравнений и его приложения к анализу данных // Вычисл. технологии. 2013. Т. 18, № 3. С. 80–109.
     
  10. Ерёмин И. И. Метод «штрафов» в выпуклом программировании // Докл. АН СССР. 1967. Т. 173, № 4. С. 748–751.
     
  11. Долгополик М. В. Основы теории точных штрафных функций // Семинар по конструктивному негладкому анализу и недифференцируемой оптимизации. Избр. докл. С.-Пб.: С.-Петербург. гос. ун-т, 2015. 17 с. URL: cnsa.cmlaboratory.com/reps15.shtml (дата обращения: 27.10.2024).
     
  12. Полякова Л. Н. Метод точных штрафов: другой подход // Семинар по конструктивному негладкому анализу и недифференцируемой оптимизации. Избр. докл. С.-Пб.: С.-Петербург. гос. ун-т, 2014. 16 с. URL: cnsa.cmlaboratory.com/reps14.shtml (дата обращения: 27.10.2024).
     
  13. Демьянов В. Ф., Малозёмов В. Н. Введение в минимакс. М.: Наука, 1972. 368 с.
     
  14. Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. М.: Наука, 1981. 384 с.
     
  15. Демьянов В. Ф., Рубинов А. М. Основы негладкого анализа и квазидифференциальное исчисление. М.: Наука, 1990. 432 с.
     
  16. Полякова Л. Н. Непрерывные методы безусловной минимизации гиподифференцируемых функций // Вестн. С.-Петербург. ун-та. Сер. 10. 2007. Вып. 3. С. 71–81.
     
  17. Долгополик М. В. О непрерывной кодифференцируемости // Семинар по конструктивному негладкому анализу и недифференцируемой оптимизации. Избр. докл. С.-Пб.: С.-Петербург. гос. ун-т, 2019. 19 с. URL: cnsa.cmlaboratory.com/reps19.shtml (дата обращения: 27.10.2024).
     
  18. Залгаллер В. А. О представлении функций нескольких переменных разностью выпуклых функций // Зап. науч. сем. ПОМИ. 1997. Т. 246. С. 36–65.
     
  19. Melzer D. On the expressibility of piecewise linear continuous functions as the difference of two piecewise linear convex functions // Quasidifferential calculus. Amsterdam: North-Holland, 1986. P. 118–134. (Math. Program. Stud.; V. 29).
     
  20. Kripfganz A., Schulze R. Piecewise affine functions as a difference of two convex functions // Optimization. 1987. V. 18, No. 1. P. 23–29. DOI: 10.1080/ 02331938708843210.
     
  21. Gorokhovik V. V., Zorko O. I., Birkhoff G. Piecewise affine functions and polyhedral sets // Optimization. 1994. V. 31, No. 3. P. 209–221. DOI: 10.1080/ 02331939408844018.
     
  22. Gorokhovik V. V. Geometrical and analytical characteristic properties of piecewise affine mappings. Ithaca, NY: Cornell Univ., 2011. 12 p. (Cornell Univ. Libr. e-Print Archive; arXiv:1111.1389). DOI: 10.48550/arXiv.1111.1389. 
     
  23. Ангелов Т. А. Представление кусочно аффинных функций в виде разности полиэдральных // Вестн. С.-Петербург. ун-та. Сер. 10. 2016. Вып. 1. С. 4–18.
     
  24. Тамасян Г. Ш. О компактном представлении кодифференциала непрерывной ломаной, заданной в форме Бернштейна // Семинар по оптимизации, машинному обучению и искусственному интеллекту. Избр. докл. С.-Пб.: С.-Петербург. гос. ун-т, 2023. 10 с. URL: oml.cmlaboratory.com/ reps23.shtml (дата обращения: 27.10.2024).
     
  25. Гавурин М. К., Малозёмов В. Н. Экстремальные задачи с линейными ограничениями. Л.: Изд-во ЛГУ, 1984. 176 с.
     
  26. Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М.: МЦНМО, 2020. 416 с.
     
  27. Тамасян Г. Ш., Шульга Г. С. К вопросу о минимизации выпуклой кусочно аффинной функции // Семинар по оптимизации, машинному обучению и искусственному интеллекту. Избр. докл. С.-Пб.: С.-Петербург. гос. ун-т, 2022. 5 с. URL: oml.cmlaboratory.com/reps22.shtml (дата обращения: 27.10.2024).
     
  28. Малистов А. С. О поиске медианы массива за линейное время // Мат. просвещение. Сер. 3. Вып. 21. М.: МЦНМО, 2017. С. 265–270.
     
  29. Тамасян Г. Ш., Шульга Г. С. Быстрый алгоритм минимизации выпуклой ломаной // Семинар по конструктивному негладкому анализу и недифференцируемой оптимизации. Избр. докл. С.-Пб.: С.-Петербург. гос. ун-т, 2021. 6 с. URL: cnsa.cmlaboratory.com/reps21.shtml (дата обращения: 27.10.2024).
     
  30. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2013. 1328 с.

Результаты разд. 3–5 получены в Институте проблем машиноведения РАН за счёт Российского научного фонда (проект № 23–41–00060). В остальном исследование выполнено за счёт бюджетов организаций, указанных авторами на первой странице статьи. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Тамасян Григорий Шаликович
  1. Военно-космическая академия им. А. Ф. Можайского, 
    ул. Ждановская, 13, 197082 Санкт-Петербург, Россия
  2. Институт проблем машиноведения, 
    Большой пр., 61, В. О., 199178 Санкт-Петербург, Россия

E-mail: grigoriytamasjan@mail.ru

Шульга Георгий Сергеевич
  1. Санкт-Петербургский гос. университет, 
    Университетская наб., 7–9, 199034 Санкт-Петербург, Россия
  2. Институт проблем машиноведения, 
    Большой пр., 61, В. О., 199178 Санкт-Петербург, Россия

E-mail: gdextrous@gmail.com

Статья поступила 26 марта 2024 г.
После доработки — 20 апреля 2024 г.
Принята к публикации 22 июня 2024 г.

Abstract:

An application of constructive nonsmooth analysis methods to the problem of minimizing a convex piecewise affine function defined as the sum of absolute values of affine functions is demonstrated. Hypodifferential calculus was used in the general (multidimensional) case, while subdifferential calculus was employed in the scalar case. Analyzing the optimality criterion, one can reveal that the point delivering the global minimum can be found by solving the corresponding linear programming problem. In the scalar case, the solution can also be found in closed form as the weighted median of the nodes of a broken line. 
Bibliogr. 30.

References:
  1. V. I. Mudrov and V. L. Kushko, Methods of Processing Measurements: Quasiplausible Estimates (Radio Svyaz’, Moscow, 1983) [Russian].
     
  2. S. I. Zukhovitskii, On the approximation of an incompatible system of linear equations using the principle of minimizing the sum of the moduli of all deviations, Dokl. Akad. Nauk SSSR 143 (5), 1030–1033 (1962).
     
  3. P. A. Akimov and A. I. Matasov, An iterative algorithm for $l_1$-norm approximation in dynamic estimation problems, Avtom. Telemekh., No. 5, 7–26 (2015) [Russian] [Autom. Remote Control 76 (5), 733–748 (2015)].
     
  4. A. V. Lakeev and S. I. Noskov, The method of least moduli for linear regression: The number of zero approximation errors, Sovrem. Tekhnol., Sist. Anal., Model., No. 2, 48–50 (2012) [Russian].
     
  5. V. A. Gorelik and O. S. Trembacheva, Solution of the linear regression problem using matrix correction methods in the $l_1$-metric, Zh. Vychisl. Mat. Mat. Fiz. 56 (2), 202–207 (2016) [Russian] [Comput. Math. Math. Phys. 56 (2), 200–205 (2016)].
     
  6. V. A. Surin and A. N. Tyrsin, Application of the generalized method of least moduli in problems of image processing and analysis, Vestn. Astrakhan. Gos. Tekhn. Univ., Ser. Upr. Vychisl. Tekhn. Inform., No. 2, 45–55 (2020), DOI: 10.24143/2072-9502-2020-2-45-55 [Russian].
     
  7. G. Sh. Tamasyan, On wild points, in Sel. Talks Semin. Optimization, Machine Learning and Artificial Intelligence (St. Petersb. Gos. Univ, St. Petersburg, 2023) [Russian], URL: oml.cmlaboratory.com/reps23.shtml (accessed: Oct. 27, 2024).
     
  8. S. P. Sharyi, Strong consistency in the problem of dependence recovery under interval data uncertainty, Vychisl. Tekhnol. 22 (2), 150–172 (2017) [Russian].
     
  9. S. P. Sharyi and I. A. Sharaya, Recognition of solvability of interval equations and its applications to data analysis, Vychisl. Tekhnol. 18 (3), 80–109 (2013) [Russian].
     
  10. I. I. Eremin, The “penalty” method in convex programming, Dokl. Akad. Nauk SSSR 173 (4), 748–751 (1967) [Russian].
     
  11. M. V. Dolgopolik, Fundamentals of the theory of exact penalty functions, in Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization (St. Petersb. Gos. Univ, St. Petersburg, 2015) [Russian], URL: cnsa.cmlaboratory.com/reps15.shtml (accessed: Oct. 27, 2024).
     
  12. L. N. Polyakova, The Method of exact penalties: Another approach, in Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization (St. Petersb. Gos. Univ, St. Petersburg, 2014) [Russian], URL: cnsa.cmlaboratory.com/reps14.shtml (accessed: Oct. 27, 2024).
     
  13. V. F. Demyanov and V. N. Malozyomov, Introduction to Minimax (Nauka, Moscow, 1972) [Russian].
     
  14. V. F. Demyanov and L. V. Vasilyev, Nondifferentiable Optimization (Nauka, Moscow, 1981) [Russian].
     
  15. V. F. Demyanov and A. M. Rubinov, Fundamentals of Nonsmooth Analysis and Quasidifferential Calculus (Nauka, Moscow, 1990) [Russian].
     
  16. L. N. Polyakova, Continuous methods for unconditional minimization of hypodifferentiable functions, Vestn. St. Petersb. Univ., Ser. 10, No. 3, 71–81 (2007) [Russian].
     
  17. M. V. Dolgopolik, On continuous codifferentiability, in Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization (St. Petersb. Gos. Univ, St. Petersburg, 2019) [Russian], URL: cnsa.cmlaboratory. com/reps19.shtml (accessed: Oct. 27, 2024).
     
  18. V. A. Zalgaller, Representation of functions of several variables by differences of convex functions, Zap. Nauchn. Semin. POMI 246, 36–65 (1997) [Russian] [J. Math. Sci., New York 100 (3), 2209–2227 (2000)].
     
  19. D. Melzer, On the expressibility of piecewise linear continuous functions as the difference of two piecewise linear convex functions, in Quasidifferential Calculus (North-Holland, Amsterdam, 1986), pp. 118–134 (Math. Program. Stud., Vol. 29).
     
  20. A. Kripfganz and R. Schulze, Piecewise affine functions as a difference of two convex functions, Optimization 18 (1), 23–29 (1987), DOI: 10.1080/ 02331938708843210.
     
  21. V. V. Gorokhovik, O. I. Zorko, and G. Birkhoff, Piecewise affine functions and polyhedral sets, Optimization 31 (3), 209–221 (1994), DOI: 10.1080/ 02331939408844018.
     
  22. V. V. Gorokhovik, Geometrical and analytical characteristic properties of piecewise affine mappings (Cornell Univ., Ithaca, NY, 2011) (Cornell Univ. Libr. e-Print Archive, arXiv:1111.1389), DOI: 10.48550/arXiv.1111.1389.
     
  23. T. A. Angelov, Representation of piecewise affine functions as a difference of polyhedral ones, Vestn. St. Petersb. Univ., Ser. 10, No. 1, 4–18 (2016) [Russian].
     
  24. G. Sh. Tamasyan, On a compact representation of the codifferential of a continuous broken line given in the Bernstein form, in Sel. Talks Semin. Optimization, Machine Learning and Artificial Intelligence (St. Petersb. Gos. Univ, St. Petersburg, 2023) [Russian], URL: oml.cmlaboratory.com/reps23.shtml (accessed: Oct. 27, 2024).
     
  25. M. K. Gavurin and V. N. Malozyomov, Extremum Problems with Linear Constraints (Izd. LGU, Leningrad, 1984) [Russian].
     
  26. F. P. Vasilyev and A. Yu. Ivanitskii, Linear Programming (MTsNMO, Moscow, 2020) [Russian].
     
  27. G. Sh. Tamasyan and G. S. Shulga, To the question of minimization of a convex piecewise affine function, in Sel. Talks Semin. Optimization, Machine Learning and Artificial Intelligence (St. Petersb. Gos. Univ, St. Petersburg, 2022) [Russian], URL: oml.cmlaboratory.com/reps22.shtml (accessed: Oct. 27, 2024).
     
  28. A. S. Malistov, On finding the median of an array in linear time, in Mat. Prosveshch., Ser. 3, No. 21 (MTsNMO, Moscow, 2017), pp. 265–270 [Russian].
     
  29. G. Sh. Tamasyan and G. S. Shulga, Fast algorithm for minimizing a convex broken line, in Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization (St. Petersb. Gos. Univ, St. Petersburg, 2021) [Russian], URL: cnsa.cmlaboratory.com/reps21.shtml (accessed: Oct. 27, 2024).
     
  30. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (MIT Press, Cambridge, MA, 2009; Vilyams, Moscow, 2013 [Russian]).