Задачи линейного полуопределенного программирования: регуляризация и двойственные формулировки в строгой форме
Аннотация
Регуляризация задачи оптимизации состоит в ее сведении к эквивалентной задаче, удовлетворяющей условиям регулярности, которые гарантируют выполнение соотношений двойственности в строгой форме. В настоящей статье для линейных задач полуопределенного программирования предлагается процедура регуляризации, основанная на понятии неподвижных индексов и их свойствах. Эта процедура описана в виде алгоритма, который за конечное число шагов преобразует любую задачу линейного полубесконечного программирования в эквивалентную задачу, удовлетворяющую условию Слейтера. В результате использования свойств неподвижных индексов и предложенной процедуры регуляризации получены новые двойственные задачи полубесконечного программирования в явной и неявной формах. Доказано, что для этих двойственных задач и исходной задачи соотношения двойственности выполняются в строгой форме.
Литература
- 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.
- 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.
- Kortanek KO, Zhang Q. Perfect duality in semi-infinite and semidefinite programming. Mathematical Programming. 2001;91(1):127–144. DOI: 10.1007/s101070100232.
- Li SJ, Yang XQ, Teo KL. Duality for semidefinite and semi-infinite programming. Optimization. 2003;52:507–528. DOI: 10.1080/02331930310001611484.
- 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.
- Ramana MV, Tuncel L, Wolkowicz H. Strong duality for semidefinite programming. SIAM Journal on Optimization. 1997;7(3):641–662. DOI: 10.1137/S1052623495288350.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
Copyright (c) 2020 Журнал Белорусского государственного университета. Математика. Информатика
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Авторы, публикующиеся в данном журнале, соглашаются со следующим:
- Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).