«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

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

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

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

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

Ключевые слова
негладкая задача минимизация разности двух выпуклых функций условия оптимальности локальный поиск глобальный поиск
УДК
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.


Полная версия (русская)