Том 25, номер 2, 2018 г., Стр. 82-100

УДК 519.8
Просолупов Е. В., Тамасян Г. Ш.
Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции

Аннотация:
Известно, что задача ортогонального проецирования точки на стандартный симплекс сводится к решению скалярного уравнения. В работе анализируется трудоёмкость алгоритма поиска нуля выпуклой кусочно-линейной функции, предложенного в [30]. Проведён анализ лучших и худших случаев входных данных для алгоритма. Для этого изучены наибольшее и наименьшее числа итераций алгоритма как функции от размера входных данных. Показано, что в случае равенства элементов входного множества алгоритм совершает наименьшее число итераций. В случае же различающихся элементов входного множества количество итераций максимально и очень слабо зависит от конкретных значений элементов множества. Приведены результаты вычислительных экспериментов со случайными входными данными высокой размерности.
Табл. 2, ил. 2, библиогр. 34.

Ключевые слова: стандартный симплекс, ортогональное проецирование точки, нули функции.

DOI: 10.17377/daio.2018.25.571

Просолупов Евгений Викторович ¹
Тамасян Григорий Шаликович ¹
1. Санкт-Петербургский гос. университет,
Университетский пр., 35, 198504 Санкт-Петербург, Россия
е-mail: e.prosolupov@spbu.ru, g.tamasyan@spbu.ru

Статья поступила 10 марта 2017 г.
Исправленный вариант — 26 декабря 2017 г.

Литература

[1] Ахо А., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы. М.: Издат. дом Вильямс, 2003. 384 с.

[2] Величко А. С. О выборе шага в проективных алгоритмах для задач линейного программирования большой размерности // Дальневост. мат. журн. 2012. № 2. C. 160–170.

[3] Демьянов В. Ф., Тамасян Г. Ш. О прямых методах решения вариационных задач // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16, № 5. C. 36–47.

[4] Долгий Д. В., Нурминский Е. А. Ускоренный параллельный метод проекций для решения задачи о наименьшем расстоянии // Вычисл. методы и программирование. 2006. Т. 7, вып. 3. С. 273–277.

[5] Долгополик М. В., Тамасян Г. Ш. Об эквивалентности методов наискорейшего и гиподифференциального спусков в некоторых задачах условной оптимизации // Изв. Саратов. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2014. Т. 14, вып. 4, ч. 2. С. 532–542.

[6] Зоркальцев В. И. Октаэдрические и евклидовы проекции точки на линейное многообразие // Тр. Ин-та математики и механики УрО РАН. 2012. Т. 18, № 3. С. 106–118.

[7] Зоркальцев В. И. Проекции точки на полиэдр // Журн. вычисл. математики и мат. физики. 2013. Т. 53, № 1. С. 4–19.

[8] Малоземов В. Н. МДМ-методу — 40 лет // Вестн. Сыктывкар. ун-та. Сер. 1. 2012. Вып. 15. С. 51–62.

[9] Малоземов В. Н., Певный А. Б. Быстрый алгоритм проектирования точки на симплекс // Вестн. СПбГУ. Сер. 1. 1992. № 1. С. 112–113.

[10] Малоземов В. Н., Тамасян Г. Ш. Два быстрых алгоритма проектирования точки на стандартный симплекс // Журн. вычисл. математики и мат. физики. 2016. Т. 56, № 5. С. 742—755.

[11] Малоземов В. Н., Тамасян Г. Ш. Лемма Гиббса и её приложения // Семинар «Constructive Nonsmooth Analysis and Nondifferentiable Optimization»: Избр. докл. http://www.apmath.spbu.ru/cnsa/pdf/2017/LemmaGibbsa.pdf

[12] Митчелл Б. Ф., Демьянов В. Ф., Малоземов В. Н. Нахождение ближайшей к началу координат точки многогранника // Вестн. ЛГУ. 1971. № 19. С. 38–45.

[13] Нурминский Е. А. Параллельный метод проекции на выпуклую оболочку семейства множеств // Изв. вузов. Математика. 2003. № 12. С. 78–82.

[14] Нурминский Е. А. Проекция на внешне заданные полиэдры // Журн. вычисл. математики и мат. физики. 2008. Т. 48, № 3. С. 387–396.

[15] Тамасян Г. Ш. О методах наискорейшего и гиподифференциального спуска в одной задаче вариационного исчисления // Вычисл. методы и программирование. 2012. Т. 13, № 1. C. 197–217.

[16] Тамасян Г. Ш. Численные методы в задачах вариационного исчисления для функционалов, зависящих от производных высшего порядка // Пробл. мат. анализа. Вып. 67. Новосибирск: Изд-во Тамара Рожковская, 2012. С. 113–132.

[17] Тамасян Г. Ш., Просолупов Е. В., Ангелов Т. А. Сравнительный анализ двух быстрых алгоритмов проецирования точки на стандартный симплекс // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 2. С. 100–123.

[18] Тамасян Г. Ш., Чумаков А. А. Нахождение расстояния между эллипсоидами // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 3. С. 87–102.

[19] Утешев А. Ю., Яшина М. В. Нахождение расстояния от эллипсоида до плоскости и квадрики в $\mathbb R^n$ // Докл. АН. 2008. Т. 419, № 4. С. 471–474.

[20] Brucker P. An $O(n)$ algorithm for quadratic knapsack problems // Oper. Res. Lett. 1984. Vol. 3, No. 3. P. 163–166.

[21] Causa A., Raciti F. A purely geometric approach to the problem of computing the projection of a point on a simplex // J. Optim. Theory Appl. 2013. Vol. 156, No. 2. P. 524–528.

[22] Demyanov V. F. Algorithms for some minimax problems // J. Comput. Syst. Sci. 1968. Vol. 2, No. 4. P. 342–380.

[23] Demyanov V. F., Giannessi F., Tamasyan G. Sh. Variational control problems with constraints via exact penalization // Variational Analysis and Applications. New York: Springer-Verl., 2005. P. 301–342.

[24] Demyanov V. F., Tamasyan G. Sh. Exact penalty functions in isoperimetric problems // Optimization. 2011. Vol. 60, No. 1–2. P. 153–177.

[25] Demyanov V. F., Tamasyan G. Sh. Direct methods in the parametric moving boundary variational problem // Numer. Funct. Anal. Optimization. 2014. Vol. 35, No. 7–9. P. 932–961.

[26] Deutsch F. The method of alternating orthogonal projections // Approximation Theory, Spline Functions and Applications. Dordrecht: Kluwer Acad. Publ., 1992. P. 105–121.

[27] Dolgopolik M. V., Tamasyan G. Sh. Method of steepest descent for two-dimensional problems of calculus of variations // Constructive Nonsmooth Analysis and Related Topics. New York: Springer-Verl., 2014. P. 101–113. (Optim. Its Appl.; Vol. 87).

[28] Held M., Wolfe P., Crowder H. P. Validation of the subgradient optimization // Math. Program. 1974. Vol. 6, No. 1. P. 62–88.

[29] Helgason R. V., Kennington J. L., Lall H. A polynomially bounded algorithm for a singly constrained quadratic program // Math. Program. 1980. Vol. 18, No. 1. P. 338–343.

[30] Maculan N., Galdino de Paula G., Jr. A linear-time median-finding algorithm for projecting a vector on the simplex of $\mathbb R^n$ // Oper. Res. Lett. 1989. Vol. 8, No. 4. P. 219–222.

[31] Michelot C. A finite algorithm for finding the projection of a point ontothe canonical simplex of $\mathbb R^n$ // J. Optim. Theory Appl. 1986. Vol. 50, No. 1. P. 195–200.

[32] Patriksson M. A survey on the continuous nonlinear resource allocation problem // Eur. J. Oper. Res. 2008. Vol. 185, No. 1. P. 1–46.

[33] Tamasyan G., Chumakov A. Finding the distance between the ellipsoid and the intersection of a linear manifold and ellipsoid // Proc. 2015 Int. Conf. Stability and Control Processes in Memory of V. I. Zubov joined with 21st Int. Workshop on Beam Dynamics and Optimization (St. Petersburg, Russia, Oct. 5–9, 2015). Piscataway: IEEE, 2015. P. 357–360.

[34] Tamasyan G., Prosolupov E. Orthogonal projection of a point onto the standard simplex algorithms analysis // Proc. 2015 Int. Conf. Stability and Control Processes in Memory of V. I. Zubov joined with 21st Int. Workshop on Beam Dynamics and Optimization (St. Petersburg, Russia, Oct. 5–9, 2015). Piscataway: IEEE, 2015. P. 353–356.