Том 23, номер 2, 2016 г., Стр. 100-123

УДК 519.85
Тамасян Г. Ш., Просолупов Е. В., Ангелов Т. А.
Сравнительное изучение двух быстрых алгоритмов проецирования точки на стандартный симплекс

Аннотация:
Рассматриваются два алгоритма ортогонального проецирования точки на стандартный симплекс. Алгоритмы принципиально различны по своей природе, однако их связывает тот факт, что когда один из них имеет максимальную трудоёмкость, у другого трудоёмкость минимальна. Приводятся конкретные области, точки из которых проецируются рассматриваемыми алгоритмами за минимальное и максимальное число шагов. Корректность полученных выводов подтверждается численными экспериментами, реализованными в среде MatLab и независимо на языке Java.
Ил. 11, библиогр. 23.

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

DOI: 10.17377/daio.2016.23.510

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

Статья поступила 11 сентября 2015 г.
Исправленный вариант — 19 октября 2015 г.

Литература

[1] Гавурин М. К., Малозёмов В. Н. Экстремальные задачи с линейными ограничениями. Л.: Изд-во ЛГУ, 1984. 176 с.

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

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

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

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

[6] Малозёмов В. Н., Тамасян Г. Ш. Два быстрых алгоритма проектирования точки на стандартный симплекс // Журн. вычисл. математики и мат. физики. 2016. DOI: 10.7868/S0044466916050148 (в печати).

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

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

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

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

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

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

[13] Demyanov V. F., Giannessi F., Tamasyan G. Sh. Variational control problems with constraints via exact penalization // Variational Analysis and Applications. Eds. F. Giannessi, A. Maugeru. New York: Springer-Verl., 2005. P. 301–342. (Nonconvex Optim. Its Appl.; Vol. 79).

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

[15] 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.

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

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

[18] 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.

[19] 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.

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

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

[22] Tamasyan G. Sh., Chumakov A. 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 (SCP) joined with 21st Int. Workshop on Beam Dynamics and Optimization (BDO) (St. Petersburg, Russia, Oct. 5–9, 2015). IEEE, 2015. P. 357–360.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342138

[23] 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 (SCP) joined
with 21st Int. Workshop on Beam Dynamics and Optimization (BDO) (St. Petersburg, Russia, Oct. 5–9, 2015). IEEE, 2015. P. 353–356.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342137