Том 25, номер 2, 2018 г., Стр. 82-100
УДК 519.8
Просолупов Е. В., Тамасян Г. Ш.
Оценка трудоёмкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции
Аннотация:
Известно, что задача ортогонального проецирования точки на стандартный симплекс сводится к решению скалярного уравнения. В работе анализируется трудоёмкость алгоритма поиска нуля выпуклой кусочно-линейной функции, предложенного в [30]. Проведён анализ лучших и худших случаев входных данных для алгоритма. Для этого изучены наибольшее и наименьшее числа итераций алгоритма как функции от размера входных данных. Показано, что в случае равенства элементов входного множества алгоритм совершает наименьшее число итераций. В случае же различающихся элементов входного множества количество итераций максимально и очень слабо зависит от конкретных значений элементов множества. Приведены результаты вычислительных экспериментов со случайными входными данными высокой размерности.
Табл. 2, ил. 2, библиогр. 34.
Ключевые слова: стандартный симплекс, ортогональное проецирование точки, нули функции.
DOI: 10.17377/daio.2018.25.571
Просолупов Евгений Викторович 1
Тамасян Григорий Шаликович 1
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. |