Соотношения эквивалентности в выпуклой оптимизации

Соотношения эквивалентности в выпуклой оптимизации

Нурминский Е. А.
Дискретный анализ и исследование операций, 30, 2, 81-90 (2023)
Скачать статью

УДК 519.853.3 
DOI: 10.33048/daio.2023.30.762

Аннотация:

Сформулированы и доказаны общие соотношения эквивалентности между вычислениями опорных функций выпуклых множеств и операциями проекции на них: асимптотическая эквивалентность операции проекции и вычисления опорной функции произвольного выпуклого замкнутого ограниченного множества, эквивалентность задачи об элементе минимальной нормы и регуляризованной задачи суплинейной оптимизации. Приведённые результаты существенно упрощают и обобщают полученные ранее доказательства для аналогичных соотношений в задачах линейной оптимизации. 
Ил. 1, библиогр. 10.

Литература:
  1. Nurminski E. A. Single-projection procedure for linear optimization // J. Glob. Optim. 2016. V. 66, No. 1. P. 95–110.
     
  2. Нурминский Е. А. Проекция на внешне заданные полиэдры // Журн. вычисл. математики и мат. физики. 2008. Т. 48, № 3. С. 387–396.
     
  3. Аблаев С. С., Макаренко Д. В., Стонякин Ф. С., Алкуса М. С., Баран И. В. Субградиентные методы для задач негладкой оптимизации с некоторой релаксацией условия острого минимума // Компьют. исследования и моделирование. 2022. Т. 14, № 2. С. 473–495.
     
  4. Bui H. T., Burachik R. S., Nurminski E. A., Tam M. K. Single-projection procedure for infinite dimensional convex optimization problems. Ithaca, NY: Cornell Univ., 2022. (Cornell Univ. Libr. e-Print Archive; arXiv:2210.11252).
     
  5. Нурминский Е. А. Ускорение итеративных методов проекции на многогранник // Дальневосточный математический сборник. Вып. 1. Владивосток: Ин-т прикл. математики, 1995. С. 51-62.
     
  6. Dolgopolik M. V. Exact penalty functions with multidimensional penalty parameter and adaptive penalty updates // Optim. Lett. 2022. V. 16, No. 4. P. 1281–1300.
     
  7. Bauschke H. H., Borwein J. M. On projection algorithms for solving convex feasibility problems // SIAM Rev. 1996. V. 38. P. 367–426.
     
  8. Gould N. I. M. How good are projection methods for convex feasibility problems? // Comput. Optim. Appl. 2008. V. 40, No. 1. P. 1–12.
     
  9. Censor Y., Chen W., Combettes P. L., Davidi R., Herman G. T. On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints // Comput. Optim. Appl. 2012. V. 51, No. 3. P. 1065–1088.
     
  10.  Johnstone P. R., Eckstein J. Convergence rates for projective splitting // SIAM J. Optim. 2019. V. 29, No. 3. P. 1931–1957.

Исследование выполнено при финансовой поддержке Министерства науки и высшего образования (соглашение № 075–02–2023–946).

Нурминский Евгений Алексеевич
  1. Дальневосточный федеральный университет, 
    пос. Аякс, 10, 690922 Владивосток, Россия

E-mail: nurminskiy.ea@dvfu.ru

Статья поступила 1 января 2023 г. 
После доработки — 21 февраля 2023 г. 
Принята к публикации 22 февраля 2023 г.

Abstract:

This article formulates and proves several useful correlations between support functions of convex sets and projection operations over them, such as asymptotic equivalence of projection operations and computation of support functions for general convex closed bounded sets, as well as equivalence between least-norm and regularized convex suplinear optimization problems. These results generalize previously known equivalences for linear optimization problems and provide new and greatly simplified proofs for them. 
Illustr. 1, bibliogr. 10.

References:
  1. E. A. Nurminski, Single-projection procedure for linear optimization, J. Glob. Optim. 66 (1), 95–110 (2016).
     
  2. E. A. Nurminski, Projection onto polyhedra in outer representation, Zh. Vychisl. Mat. Mat. Fiz. 48 (3), 387–396 (2008) [Russian] [Comput. Math. Math. Phys. 48 (3), 367–375 (2008)].
     
  3. S. S. Ablaev, D. V. Makarenko, F. S. Stonyakin, M. S. Alkousa, and I. V. Baran, Subgradient methods for non-smooth optimization problems with some relaxation of sharp minimum, Kompyut. Issled. Model. 14 (2), 473–495 (2022) [Russian].
     
  4. H. T. Bui, R. S. Burachik, E. A. Nurminski, and M. K. Tam, Single-projection procedure for infinite dimensional convex optimization problems (Cornell Univ., Ithaca, NY, 2022) (Cornell Univ. Libr. e-Print Archive, arXiv:2210.11252).
     
  5. E. A. Nurminski, Accelerating iterative methods for projection on polyhedrons, in Dalnevostochnyi Matematicheskii Sbornik, No. 1 (Inst. Prikl. Mat., Vladivostok, 1995), pp. 51-62 [Russian].
     
  6. M. V. Dolgopolik, Exact penalty functions with multidimensional penalty parameter and adaptive penalty updates, Optim. Lett. 16 (4), 1281–1300 (2022).
     
  7. H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Rev. 38, 367–426 (1996).
     
  8. N. I. M. Gould, How good are projection methods for convex feasibility problems? Comput. Optim. Appl. 40 (1), 1–12 (2008).
     
  9. Y. Censor, W. Chen, P. L. Combettes, R. Davidi, and G. T. Herman, On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints, Comput. Optim. Appl. 51 (3), 1065–1088 (2012).
     
  10. P. R. Johnstone and J. Eckstein, Convergence rates for projective splitting, SIAM J. Optim. 29 (3), 1931–1957 (2019).