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

  • Ольга Ивановна Костюкова Институт математики НАН Беларуси, ул. Сурганова, 11, г. Минск, 220072, Беларусь
  • Татьяна Владимировна Чемисова Авейрусский университет, кампус Университета Сантьяго, 3810-193, г. Авейру, Португалия https://orcid.org/0000-0002-2678-2552
DOI: https://doi.org/10.33581/2520-6508-2020-3-17-27

Аннотация

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

Биографии авторов

Ольга Ивановна Костюкова, Институт математики НАН Беларуси, ул. Сурганова, 11, г. Минск, 220072, Беларусь

доктор физико-математических наук, профессор; главный научный сотрудник

Татьяна Владимировна Чемисова, Авейрусский университет, кампус Университета Сантьяго, 3810-193, г. Авейру, Португалия

кандидат физико-математических наук; доцент факультета математики

Литература

  1. Wolkowicz H, Saigal R, Vandenberghe L, editors. Handbook of semidefinite programming. Theory, algorithms, and applications. New York: Springer; 2000. 654 p. (International Series in Operations Research & Management Science; volume 27). DOI: 10.1007/978-1-4615-4381-7.
  2. Anjos MF, Lasserre JB, editors. Handbook of semidefinite, conic and polynomial optimization. New York: Springer; 2012. 138 p. (International Series in Operational Research & Management Science; volume 166). DOI: 10.1007/978-1-4614-0769-0.
  3. Kortanek KO, Zhang Q. Perfect duality in semi-infinite and semidefinite programming. Mathematical Programming. 2001;91(1):127–144. DOI: 10.1007/s101070100232.
  4. Li SJ, Yang XQ, Teo KL. Duality for semidefinite and semi-infinite programming. Optimization. 2003;52:507–528. DOI: 10.1080/02331930310001611484.
  5. Solodov MV. Constraint qualifications. In: Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, editors. Wiley encyclopedia of operations research and management science. Hoboken: John Wiley & Sons; 2010. DOI: 10.1002/9780470400531.eorms0978.
  6. Ramana MV, Tuncel L, Wolkowicz H. Strong duality for semidefinite programming. SIAM Journal on Optimization. 1997;7(3):641–662. DOI: 10.1137/S1052623495288350.
  7. Tunçel L, Wolkowicz H. Strong duality and minimal representations for cone optimization. Computational Optimization and Applications. 2012;53(2):619–648. DOI: 10.1007/s10589-012-9480-0.
  8. Waki H, Muramatsu M. Facial reduction algorithms for conic optimization problems. Journal of Optimization Theory and Applications. 2013;158(1):188–215. DOI: 10.1007/s10957-012-0219-y.
  9. Drusvyatskiy D, Wolkowicz H. The many faces of degeneracy in conic optimization. Foundations and Trends in Optimization. 2017;3(2):77–170. DOI: 10.1561/2400000011.
  10. Ramana MV. An exact duality theory for semidefinite programming and its complexity implications. Mathematical Programming. Series A and B. 1997;77(1):129–162. DOI: 10.1007/BF02614433.
  11. Kostyukova OI, Tchemisova TV. Optimality conditions for convex semi-infinite programming problems with finitely representable compact index sets. Journal of Optimization Theory and Applications. 2017;175(1):76–103. DOI: 10.1007/s10957-017-1150-z.
  12. Kostyukova OI, Tchemisova TV. Optimality criteria without constraint qualification for linear semidefinite problems. Journal of Mathematical Sciences. 2012;182(2):126–143. DOI: 10.1007/s10958-012-0734-2.
  13. Kostyukova OI, Tchemisova TV, Dudina OS. Immobile indices and CQ-free optimality criteria for linear copositive programming problems. Set-Valued and Variational Analysis. 2020;28:89–107. DOI: 10.1007/s11228-019-00527-y.
  14. Levin VL. Application of E. Helly’s theorem to convex programming, problems of best approximation and related questions. Mathematics of the USSR-Sbornik. 1969;8(2):235–247. DOI: 10.1070/SM1969v008n02ABEH001118.
Опубликован
2020-12-08
Ключевые слова: линейное полуопределенное программирование, сильная двойственность, нормализован- ный набор неподвижных индексов, регуляризация, квалификация ограничений
Поддерживающие организации Исследование выполнено в рамках государственной научной программы «Конвергенция» (задание 1.3.01, Республика Беларусь) и поддержано Центром исследований и разработок в области математики и приложений (CIDMA, Португалия) и Португальским фондом по развитию науки и технологий (FCT, проект UIDB/04106/2020).
Как цитировать
Костюкова, О. И., & Чемисова, Т. В. (2020). Задачи линейного полуопределенного программирования: регуляризация и двойственные формулировки в строгой форме. Журнал Белорусского государственного университета. Математика. Информатика, 3, 17-27. https://doi.org/10.33581/2520-6508-2020-3-17-27
Выпуск
№ 3 (2020): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дифференциальные уравнения и оптимальное управление

Copyright (c) 2020 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).