Исследование устойчивости параллельного алгоритма решения задачи сильной отделимости на базе Фейеровских отображений

В теории распознавания образов важное значение имеет задача сильной отделимости, заключающаяся в разделении двух выпуклых непересекающихся многогранников слоем наибольшей толщины. В работе рассматриваются нестационарные задачи сильной отделимости, то есть задачи, исходные данные которых меняются в ходе вычислительного процесса. Алгоритмы решения таких задач должны обладать двумя свойствами: автокорректируемостью и устойчивостью. Автокорректируемость подразумевает, что алгоритм может эффективно продолжать свою работу после единичного изменения входных данных. Устойчивость означает, что малое изменение входных данных приводит к малому изменению результата. Свойством автокорректируемости обладают итерационные алгоритмы, использующие фейеровские процессы. В статье описывается параллельный алгоритм решения задачи сильной отделимости на базе фейеровских отображений, допускающий эффективную реализацию на многопроцессорных системах с массовым параллелизмом. Вводится понятие устойчиво фейеровского отображения. Доказывается теорема, определяющая условия, при которых Фейеровское отображение будет устойчиво Фейеровским.

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

Фейеровское отображение, задача сильной отделимости, итерационный метод, псевдопроекция точки, устойчиво фейеровское отображение.

Литература

1. Еремин, И.И. Фейеровские методы сильной отделимости выпуклых полиэдральных множеств / И.И. Еремин // Известия вузов. Сер. Математика. - 2006. - № 12. - C. 33 - 43.
2. Boser, B. A training algorithm for optimal margin classifiers / B. Boser, I. Guyon, V. Vapnik // Proc. of the 5th Annual ACM Workshop on Computational Learning Theory. Pittsburgh: ACM Press, 1992. - P. 144 - 152.
3. Еремин, И.И. Нестационарные процессы математического программирования / И.И. Еремин, В.Д. Мазуров. - М.: Наука, 1979. - 288 с.
4. Ершова, А.В. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений / А.В. Ершова, И.М. Соколинская // Вычислительные методы и программирование. - 2011. - Т. 12, № 2. - С. 53 - 56.
5. Еремин, И.И. Теория линейной оптимизации / И.И. Еремин. - Екатеринбург: 'Екатеринбург', 1999. - 312 с.
6. Ершова, А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений / А.В. Ершова // Системы управления и информационные технологии. - 2009. - № 1(35). - С. 53 - 56.
7. Черников, С.Н. Линейные неравенства / С.Н. Черников. - М.: Наука, 1968. - 488 с.