DOI: https://doi.org/10.26089/NumMet.v20r437

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

Авторы

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

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

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

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2019-10-29

Выпуск

Том 20 (2019): Выпуск 4.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

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

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

Библиографические ссылки

  1. I. A. Aleksandrov, E. G. Antsiferov, and V. P. Bulatov, “On the Centered Cutting Methods in Convex Programming,” in Proc. Conf. on Methods of Mathematical Programming and Software Sverdlovsk, USSR, April 14-17, 1981 (Inst. Mat. Mekh. Akad. Nauk SSSR, Sverdlovsk, 1981), pp. 10-11.
  2. V. P. Bulatov and I. O. Shepot’ko, “The Gravity Center Method of Orthogonal Simplexes for Solving Convex Programming Problems,” in Optimization Methods and Their Applications (Energy Systems Inst. Akad. Nauk SSSR, Irkutsk, 1982), pp. 79-86.
  3. B. Yamnitsky and L. A. Levin, “An Old Linear Programming Algorithm Runs in Polynomial Time,” in Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago, USA, November 3-5, 1982 (IEEE Press, New York, 1982), Vol. 1, pp. 327-338.
  4. D. B. Yudin and A. S. Nemirovskii, “Informational Complexity and Effective Methods for the Solution of Convex Extremal Problems,” Ekonomika Mat. Metody 12 (2), 357-369 (1976).
  5. N. Z. Shor, “A Cutting Method with Space Dilation for Solving Convex Programming Problems,” Kibernetika, No. 1, 94-95 (1977).
  6. I. A. Aleksandrov E. G. Antsiferov, and V. P. Bulatov, Centered Cutting Methods in Convex Programming , Preprint (Energy Systems Inst. Akad. Nauk SSSR, Irkutsk, 1983).
  7. E. G. Antsiferov and V. P. Bulatov, “An Algorithm of Simplex Imbeddings in Convex Programming,” Zh. Vychisl. Mat. Mat. Fiz. 27 (3), 377-384 (1987) [USSR Comput. Math. Math. Phys. 27 (2), 36-41 (1987)].
  8. A. Yu. Levin, “A Minimization Algorithm for Convex Functions,” Dokl. Akad. Nauk SSSR 160 (6), 1244-1247 (1965).
  9. D. J. Newman, “Location of the Maximum on Unimodal Surfaces,” J. ACM 12 (3), 395-398 (1965).
  10. B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983; Optimization Software, New York, 1987).
  11. L. A. Rademacher, “Approximating the Centroid is Hard,” in Proc. 23rd Annual Symp. on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007 (ACM Press, New York, 2007), pp. 302-305.
  12. Yu. E. Nesterov, Introductory Lectures on Convex Programming: A Basic Course (Kluwer, Boston, 2004).
  13. J.-L. Goffin and J. P. Vial, “Convex Nondifferentiable Optimization: A Survey Focused on the Analytic Center Cutting Plane Method,” Optim. Methods Softw. 17 (5), 805-867 (2002).
  14. Y. V. Apekina and O. V. Khamisov, “A Modified Simplex Immersions Method with Simultaneous Introduction of Several Intersecting Planes,” Izv. Vyssh. Uchebn. Zaved., Mat., No. 12, 16-24 (1997) [Russ. Math. 41 (12), 14-22 (1997)].
  15. A. V. Kolosnitcyn, “Using of Modified Simplex Imbeddings Method for Solving Special Class of Convex Non-Differentiable Optimization Problems,” Vestn. Irkutsk Gos. Univ., Ser. Mat. 11, 54-68 (2015).
  16. A. Kolosnitcyn, “Modified Simplex Imbeddings Method in Convex Non-differentiable Optimization,” in Proc. 9th Int. Conf. on Discrete Optimization and Operations Research, Vladivostok, Russia, September 19-23, 2016 CEUR Workshop Proc. 1623, 226-233 (2016).
  17. A. V. Kolosnitsyn, “Computational Efficiency of the Simplex Embedding Method in Convex Nondifferentiable Optimization,” Zh. Vychisl. Mat. Mat. Fiz. 58 (2), 228-236 (2018) [Comput. Math. Math. Phys. 58 (2), 215-222 (2018)].
  18. E. A. Nurminskii, Numerical Methods of Convex Optimization (Nauka, Moscow, 1991) [in Russian].
  19. A. Bagirov, N. Karmitsa, and M. M. Makela, Introduction to Nonsmooth Optimization. Theory, Practice and Software (Springer, Cham, 2014).