Linear semidefinite programming problems: regularisation and strong dual formulations
Abstract
Regularisation consists in reducing a given optimisation problem to an equivalent form where certain regularity conditions, which guarantee the strong duality, are fulfilled. In this paper, for linear problems of semidefinite programming (SDP), we propose a regularisation procedure which is based on the concept of an immobile index set and its properties. This procedure is described in the form of a finite algorithm which converts any linear semidefinite problem to a form that satisfies the Slater condition. Using the properties of the immobile indices and the described regularization procedure, we obtained new dual SDP problems in implicit and explicit forms. It is proven that for the constructed dual problems and the original problem the strong duality property holds true.
References
- 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 Journal of the Belarusian State University. Mathematics and Informatics
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The authors who are published in this journal agree to the following:
- The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
- The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)