ИГУ - «Известия Иркутского государственного университета»

«Известия Иркутского государственного университета»

Журнал ИГУ

Список выпусков > Серия «Математика» №3, 2012

Задача сферической бинарной отделимости

Автор(ы)
Т. В. Груздева

Аннотация

Рассматривается задача отделения двух множеств, выпуклые оболочки которых имеют непустое пересечение. Предлагаются алгоритмы локального и глобального поиска в задаче об отделимости множеств сферой минимального радиуса. Эффективность предложенных алгоритмов демонстрируется вычислительным экспериментом.

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

УДК
518.517

Литература

1. Александров А. Д. Поверхности, представимые разностями выпуклых функций // Докл. АН СССP. – 1950. – Т. 72, №4. – С. 613–616.

2. Васильев Ф. П. Методы оптимизации / Ф. П. Васильев. – М. : Факториал-пресс, 2002.

3. Груздева Т. В. Локальный поиск в задачах с невыпуклыми ограничениями / Т. В. Груздева, А. С. Стрекаловский // ЖВММФ. – 2007. – Т. 47, №3. – C. 397–413.

4. Демьянов В. Ф. Недифференцируемая оптимизация / В.Ф. Демьянов, Л. В. Васильев. – М. : Наука, 1981.

5. Еремин И. И. Теория линейной оптимизации / И. И. Еремин. – Екатеринбург : Изд-во ИММ УрО РАН, 1999.

6. Еремин И. И. Противоречивые модели оптимального планирования / И. И. Еремин. – М. : Наука, 1988.

7. Математические методы в экономике / И. И. Еремин, Вл. Д. Мазуров, В. Д. Скарин, М. Ю. Хачай. – Екатеринбург : УрГУ-Центр «Фактория Пресс», 2000.

8. Измаилов А. Ф. Численные методы оптимизации / А. Ф. Измаилов, М. В. Солодов. – М. : ФИЗМАТЛИТ, 2005.

9. Мазуров В. Д.Распознавание образов как средство автоматического выбора процедуры в вычислительных методах // ЖВММФ. – 1970. – Т. 10, № 6. – С. 1520–1525.

10. Мазуров В. Д. Комитетные конструкции / В. Д. Мазуров, М. Ю. Хачай // Изв. УрГУ. Математика и механика. – 1999. – Вып. 2, № 14. – С. 77–108.

11. Михалевич В. С. Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы / В. С. Михалевич, В. А. Трубин, Н. З. Шор. – М. : Наука, гл. ред. физ.-мат. лит., 1986.

12. Орлов А. В. Численное решение задач билинейного программирования // ЖВММФ. – 2008. – Т. 48, № 2. – С. 237–254.

13. Поляк Б. Т. Введение в оптимизацию / Б. Т. Поляк. – М. : Наука, гл. ред. физ.-мат. лит., 1983.

14. Пшеничный Б. Н.Выпуклый анализ и экстремальные задачи / Б. Н. Пшеничный : Наука, гл. ред. физ.-мат. лит., 1980.

15. Стрекаловский А. С. Элементы невыпуклой Оптимизации / А. С. Стрекаловский. Новосибирск : Наука, 2003.

16. Стрекаловский А. С. О минимизации разности двух выпуклых функций на допустимом множестве // ЖВММФ. – 2003. – Т. 43, № 3. – С. 399–409.

17. Шор Н. З. Методы минимизации недифференцируемых функций и их приложения / Н. З. Шор. – Киев: Наукова думка, 1979.

18. Шор Н. З. Монотонные модификации r-алгоритмов и их приложения // Кибернетика и систем. анализ. – 2002. – № 6. – С. 74–95.

19. Astorino A. DC models for spherical separation / A. Astorino, A. Fuduli, M. Gaudioso // Journal of Global Optimization. – 2010. – Vol. 48, N 4. – P. 657–669.

20. Astorino A. A fixed-center spherical separation algorithm with kernel transformations for classification problems / A. Astorino, M. Gaudioso // Computational Management Science. – 2009. – N 6. – P. 357–372.

21. Astorino A. Polyhedral Separability Through Successive LP / A. Astorino, M. Gaudioso // Journal of Optimization theory and applications. – 2002. – Vol. 112, № 2. – P. 265-–293.

22. Ben-Tal A. Non-Euclidean restricted memory level method for large-scale convex optimization / A. Ben-Tal, A. Nemirovski // Mathematical Programming. –2005. – Vol.. 102, N 3. – 407–456.

23. Chapelle O. Semi-supervised classification by low density separation / O. Chapelle, A. Zien // Proceedings of the tenth international workshop on artificial intelligence and statistics. – 2005. – P. 57–64.

24. Tax D. M. J. Uniform object generation for optimizing one-class classifiers / David M. J. Tax, Robert P. W. Duin // The Journal of Machine Learning Research. – 2002. – Vol. 2. – P. 155–173.

25. Hiriart-Urruty J.-B. Convex Analysis and Minimization Algorithms / J.-B. Hiriart-Urruty, C. Lemarshal. – Berlin : Springer Verlag, 1993.

26. Horst R. Introduction to global optimization / R. Horst, P. Pardalos, N. V. Thoai. – Dordrecht–Boston—London : Kluwer Academic Publishers, 1995.

27. Horst R. D.C. Programming: Overview / R. Horst, N. V. Thoai // Journal of Optimization Theory and Applications. – 1999. – Vol. 103, N 1. – P. 1–43.

28. Mangasarian O. L. Linear and Nonlinear Separation of Patterns by Linear Programming // Operations Research. – 1965. – N 13. – P. 444–452.

29. Murphy P. M. UCI repository of machine learning databases [Electronic resource] / P. M. Murphy, D. W. Aha. 1992. – URL: http://www.ics.uci.edu/mlearn/MLRepository.html.

30. Nocedal J. Numerical optimization / J. Nocedal, S. J. Wright. – N. Y. : Springer-Verlag, 1999.

31. Automated star/galaxy discrimination with neural networks / S. Odewahn, E. Stockwell, R. Pennington, R. Humphreys, W. Zumach // Astron. J. – 1992. – Vol. 103. – P. 318-–331.

32. Strekalovsky A. S.On local search in d.c. optimization problems // Optimization Letters. – 2011. – (submitted).

33. Strekalovsky A. S. On computational search for optimistic solutions in bilevel problems / A. S. Strekalovsky, A. V. Orlov, A. V. Malyshev // Journal of Global Optimization. – 2010. – Vol. 48, N 1. – Р. 159–172.

34. Tao P. D. Algorithms for solving a class of non convex optimization. Methods of subgradients / P. D. Tao, L. B. Souad // Fermat Days 85, Mathematics for Optimization / ed. by Hiriart-Urruty J.-B. – North Holland : Elservier Sience Publishers B.V., 1986. – P. 249-271.