Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений

Авторы

  • А.В. Ершова
  • И.М. Соколинская

Ключевые слова:

сильная отделимость
фейеровские отображения
параллельное программирование
псевдопроекция
итерационный процесс
распознавание образов

Аннотация

Рассматривается задача разделения двух выпуклых непересекающихся многогранников слоем наибольшей толщины. Предлагается параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений, допускающий эффективную реализацию на многопроцессорных системах с массовым параллелизмом. Приводятся результаты вычислительных экспериментов, подтверждающие эффективность предложенного подхода. Работа выполнена при финансовой поддержке РФФИ (код проекта 09-01-00546а).

Новые вычислительные технологии

Загрузки

Опубликован

2011-11-03

Выпуск

Том 12 (2011): Выпуск 4.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.В. Ершова

Южно-Уральский государственный университет,
Высшая школа электроники и компьютерных наук
просп. Ленина, 76, 454080, Челябинск
• преподаватель

И.М. Соколинская

Южно-Уральский государственный университет,
Высшая школа электроники и компьютерных наук
просп. Ленина, 76, 454080, Челябинск
• доцент

Библиографические ссылки

  1. Боровкова В.А. Рынок ценных бумаг. СПб.: Питер, 2005.
  2. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во «Екатеринбург», 1999.
  3. Еремин И.И. Фейеровские методы сильной отделимости выпуклых полиэдральных множеств // Известия вузов. Сер. матем. 2006. N 12. 33-43.
  4. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979.
  5. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. 2009. N 1. 53-56.
  6. Ершова А.В., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Сер. «Матем. моделирование и программирование». 2011. N 37(254), вып.10. 12-21.
  7. Майоров С.И. Алгоритмическая торговля - за и против // Биржевое обозрение. 2010. N 1(73). 9-18.
  8. Boser B., Guyon I., Vapnik V. A training algorithm for optimal margin classifiers // Proc. of the 5th Annual ACM Workshop on Computational Learning Theory. Pittsburgh: ACM Press, 1992. 144-152.
  9. Dongarra J.J., Otto S.W., Snir M., Walker D. A message passing standard for MPP and workstations // Communications of the ACM. 1996. 39, N 7. 84-90.
  10. Forrest J.J. H., Tomlin J.A. Implementing the simplex method for the optimization subroutine library // IBM Systems Journal. 1992. 31, N 1. 11-25.
  11. Lampert A., Dale R., Paris C. Segmenting email message text into zones // Proc. of the 2009 Conference on Empirical Methods in Natural Language Processing: ACL and AFNLP. Singapore: World Scientific, 2009. 919-928.
  12. Markowitz H. Portfolio selection // J. of Finance. 1952. 7, N 1. 77-91.
  13. Zhang L., Zhu J., Yao T. An evaluation of statistical spam filtering techniques // Transactions on Asian Language Information Processing. 2004. 3, N 4. 243-269.