«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2012. Vol. 3

The Problem of Spherical Binary Separability

Author(s)
T. V. Gruzdeva
Abstract

The problem of separation of two sets, whose convex hulls have a nonempty intersection, is considered. Algorithms of local and global search are developed for this. The efficiency of the developed algorithms is demonstrated by computational simulations on test examples.

Keywords
nonsmooth problem d.c. minimization global optimality conditions local search global search algorithm
UDC
518.517
References

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.


Full text (russian)