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

Ключевые слова:

метод симплексных погружений, выпуклая недифференцируемая оптимизация, идентификация неактивных ограничений.

Аннотация

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

Об авторе

А.В. Колосницын,

Институт систем энергетики им. Л.А. Мелентьева СО РАН (ИСЭМ СО РАН)
ул. Лермонтова, 130, 664033, Иркутск
• младший научный сотрудник

Литература

  1. Александров И.А., Анциферов Е.Г., Булатов В.П. К центрированным методам отсечений в выпуклом программировании // Тезисы докл. конф. "Методы математического программирования и их программное обеспечение". Свердловск: Институт математики и механики АН СССР, 1981. 10-11.
  2. Булатов В.П., Шепотько И.О. Метод центров тяжести ортогональных симплексов для решения задачи выпуклого программирования // Методы оптимизации и их приложения. Иркутск: Институт систем энергетики АН СССР, 1982. 79-86.
  3. Yamnitsky B., Levin L.A. An old linear programming algorithm runs in polynomial time // Proc. of the 23rd Annual IEEE Symposium on Foundations of Computer Science, Vol. 1. New York: IEEE Press, 1982. 327-338.
  4. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач // Экономика и мат. методы. 1976. 12, № 2. 357-369.
  5. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования // Кибернетика. 1977. № 1. 94-95.
  6. Александров И.А., Анциферов Е.Г., Булатов В.П. Методы центрированных сечений в выпуклом программировании. Препринт СЭИ АН СССР. Иркутск, 1983.
  7. Анциферов Е.Г., Булатов В.П. Алгоритм симплексных погружений в выпуклом программировании // Ж. выч. мат. и мат. физ. 1987. 27, № 3. 377-384.
  8. Левин А.Ю. Об одном алгоритме минимизации выпуклых функций // Докл. АН СССР. 1965. 160, № 6. 1244-1247.
  9. Newman D.J. Location of the maximum on unimodal surfaces // Journal of the ACM. 1965. Vol. 12, N 3. 395-398.
  10. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
  11. Rademacher L.A. Approximating the centroid is hard // Proc. Symposium on Computational Geometry (SCG07). New York: ACM Press, 2007. 302-305.
  12. Nesterov Yu.E. Introductory lectures on convex programming: a basic course. Boston: Kluwer, 2004.
  13. Goffin J.-L., Vial J.P. Convex nondifferentiable optimization: a survey focused on the analytic center cutting plane method // Optimization Methods and Software. 2002. Vol. 17, N 5. 805-867.
  14. Апекина Е.В., Хамисов О.В. Модифицированный метод симплексных погружений с одновременным введением нескольких секущих плоскостей // Изв. вузов. Серия Матем. 1997. № 12. 16-24.
  15. Колосницын А.В. Применение модифицированного метода симплексных погружений для решения специального класса задач выпуклой недифференцируемой оптимизации // Известия Иркутского государственного университета. Серия Матем. 2015. 11. 54-68.
  16. Kolosnitcyn A.V. Modified simplex imbeddings method in convex non-differentiable optimization // CEUR Workshop Proc. 2016. Vol. 1623. 226-233.
  17. Колосницын А.В. Вычислительная эффективность метода симплексных погружений в задачах выпуклой недифференцируемой оптимизации // Ж. вычисл. матем. и матем. физ. 2018. 58, № 2. 228-236.
  18. Нурминский Е.А. Численные методы выпуклой оптимизации. М.: Наука, 1991.
  19. Bagirov A., Karmitsa N., Makela M.M. Introduction to nonsmooth optimization. Theory, Practice and Software. Cham: Springer, 2014.
Опубликован
2019-10-29
Как цитировать
Колосницын А.В. Модифицированный метод симплексных погружений для решения задач выпуклой оптимизации с большим числом ограничений // Вычислительные методы и программирование. 2019. 20. 428-437. doi 10.26089/NumMet.v20r437
Раздел 1. Вычислительные методы и приложения