Задача сферической бинарной отделимости
| Авторы: | Т. В. Груздева |
| Аннотация: | Рассматривается задача отделения двух множеств, выпуклые оболочки которых имеют непустое пересечение. Предлагаются алгоритмы локального и глобального поиска в задаче об отделимости множеств сферой минимального радиуса. Эффективность предложенных алгоритмов демонстрируется вычислительным экспериментом. |
| Ключевые слова: | негладкая задача; минимизация разности двух выпуклых функций; условия оптимальности; локальный поиск; глобальный поиск |
| УДК: | 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. |