Том 22, номер 1, 2015 г., cтр. 64-85

УДК 519.853.4
А. В. Орлов
Численный поиск глобальных решений в задачах несимметричной билинейной отделимости

Аннотация:
Исследуется задача билинейной отделимости двух множеств (несимметричный случай). Для ее решения применяется оптимизационный подход, базирующийся на редукции к эквивалентной задаче билинейной оптимизации с несвязанными переменными. В соответствии с теорией глобального поиска, разработанной А. С. Стрекаловским, построены специальные методы локального и глобального поисков в исследуемой задаче. Представлены результаты вычислительного эксперимента по решению сгенерированных тестовых задач билинейной отделимости.
Ил. 5, табл. 3, библиогр. 29.

Ключевые слова: задача классификации, билинейная отделимость, оптимизационный подход, локальный поиск, глобальный поиск, генерация тестовых задач, вычислительный эксперимент.

DOI: 10.17377/daio.2015.22.450

Андрей Васильевич Орлов ¹
1. Институт динамики систем и теории управления СО РАН,
ул. Лермонтова, 134, 664033 Иркутск, Россия
е-mail: anor@icc.ru

Статья поступила 25 марта 2014 г.
Исправленный вариант — 26 августа 2014 г.

Литература

[1] Вапник В. Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 449 с.

[2] Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. М.: Наука, 1974. 416 c.

[3] Васильев Ф. П. Методы оптимизации. М.: Факториал-пресс, 2002. 824 с.

[4] Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Пробл. кибернетики. 1978. Вып. 33. С. 5–68.

[5] Кельманов А. В., Пяткин А. В. О сложности некоторых задач кластерного анализа векторных последовательностей // Дискрет. анализ и исслед. операций. 2013. T. 20, № 2. С. 47–57.

[6] Кельманов А. В., Хандеев В. И. Полиномиальный алгоритм с оценкой точности 2 для решения одной задачи кластерного анализа // Дискрет. анализ и исслед. операций. 2013. T. 20, № 4. С. 36–45.

[7] Мазуров В. Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. 246 c.

[8] Мазуров В. Д., Хачай М. Ю., Рыбин А. И. Комитетные конструкции для решения задач выбора, диагностики и прогнозирования // Тр. ИММ УрО РАН. 2002. Т. 8, №1. С. 66–102.

[9] Орлов А. В. Численное решение задач билинейного программирования // Журн. вычисл. математики и мат. физики. 2008. Т. 48, №2. С. 237–254.

[10] Орлов А. В. Глобальный поиск оптимистических решений в двухуровневой задаче оптимального выбора тарифов телекоммуникационным оператором // Изв. Иркут. гос. ун-та. Сер. Математика. 2013. Т. 6, №1. С. 57–71.

[11] Орлов А. В., Стрекаловский А. С. О численном поиске ситуации равновесия в биматричных играх // Журн. вычисл. математики и мат. физики. 2005. Т. 45, №6. С. 983–997.

[12] Рудаков К. В. О некоторых классах алгоритмов распознавания (общие результаты). М.: ВЦ РАН СССР, 1980. 66 с.

[13] Рязанов В. В. Комитетный синтез алгоритмов распознавания и классификации // Журн. вычисл. математики и мат. физики. 1981. Т. 21, № 6. С. 1533–1543.

[14] Стрекаловский А. С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003. 356 с.

[15] Стрекаловский А. С., Орлов А. В. Биматричные игры и билинейное программирование. М.: Физматлит, 2007. 224 с.

[16] Стрекаловский А. С., Орлов А. В., Малышев А. В. Локальный поиск в квадратично-линейной задаче двухуровневого программирования // Сиб. журн. вычисл. математики. 2010. Т. 13, № 1. С. 75–88.

[17] Стрекаловский А. С., Орлов А. В., Малышев А. В. Численное решение одного класса задач двухуровневого программирования // Сиб. журн. вычисл. математики. 2010. Т. 13, № 2. С. 201–212.

[18] Astorino A., Gaudioso M. Polyhedral separability through successive LP // J. Optim. Theory Appl. 2002. Vol. 112, No. 2. P. 265–293.

[19] Astorino A., Gaudioso M. A fixed-center spherical separation algorithm with kernel transformations for classification problems // Comput. Manage. Sci. 2009. Vol. 6, No. 3. P. 357–372.

[20] Bagirov A. M., Rubinov A. M., Soukhoroukova N. V., Yearwood J. Unsupervised and supervised data classification via nonsmooth and global optimization // Top. 2003. Vol. 11, No. 1. P. 1–75.

[21] Bennett K. P., Mangasarian O. L. Bilinear separation of two sets in n-space // Comput. Optim. Appl. 1993. Vol. 2, No. 3. P. 207–227.

[22] Mangasarian O. L. Linear and nonlinear separation of patterns by linear programming // Oper. Res. 1965. Vol. 13, No. 3. P. 444–452.

[23] Mangasarian O. L. Mathematical programming in neural networks // ORSA J. Computing. 1993. Vol. 5, No. 4. P. 349–360.

[24] Mangasarian O. L. Misclassification minimization // J. Global Optim. 1994. Vol. 5, No. 4. P. 309–323.

[25] MATLAB — The language of technical computing.

[26] Megiddo N. On the complexity of polyhedral separability // Discrete Comput. Geom. 1988. Vol. 3, No. 4. P. 325–337.

[27] Rosen J. B. Pattern separation by convex programming // J. Math. Anal. Appl. 1965. Vol. 10. P. 123–134.

[28] Shavlik J. W., Mooney R. J., Towell G. G. Symbolic and neural network learning algorithms: An experimental comparison // Machine Learning. 1991. Vol. 6, No. 2. P. 111–143.

[29] Zhang G. P. Neural networks for classification: a survey // IEEE Trans. Systems, Man and Cybernetics. Part C: Applications and reviews. 2000. Vol. 30, No. 4. P. 451–462.