A parallel algorithm for solving strong separability problem on the basis of Fejer mappings

Authors

Keywords:

strong separability, Fejer mappings, parallel programming, pseudoprojection, iterative process, pattern recognition

Abstract

An approach to solving the problem of separating two convex nonintersecting polyhedrons by the layer of maximum thickness is proposed. A parallel algorithm based on a method of using Fejer mappings is described. This algorithm admits an efficient implementation on the massively parallel multiprocessor systems. The results of computing experiments confirming the efficiency of the proposed approach are discussed. This work was supported by the Russian Foundation for Basic Research (project N 09-01-00546а).

Author Biographies

A.V. Ershova

I.M. Sokolinsky

References

  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.

Published

2011-11-03

How to Cite

Ершова А.В., Соколинская И.М. A Parallel Algorithm for Solving Strong Separability Problem on the Basis of Fejer Mappings // Numerical methods and programming. 2011. 12. 423-434

Issue

Section

Section 1. Numerical methods and applications