Linear semidefinite programming problems: regularisation and strong dual formulations

  • Olga I. Kostyukova Institute of Mathematics, National Academy of Sciences of Belarus, 11 Surhanava Street, Minsk 220072, Belarus
  • Tatiana V. Tchemisova University of Aveiro, Campus Universitário de Santiago, 3810-193, Aveiro, Portugal https://orcid.org/0000-0002-2678-2552
DOI: https://doi.org/10.33581/2520-6508-2020-3-17-27

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.

Author Biographies

Olga I. Kostyukova, Institute of Mathematics, National Academy of Sciences of Belarus, 11 Surhanava Street, Minsk 220072, Belarus

doctor of science (physics and mathematics), full professor; chief researcher

Tatiana V. Tchemisova, University of Aveiro, Campus Universitário de Santiago, 3810-193, Aveiro, Portugal

PhD (physics and mathematics); associate professor at the department of mathematics

References

  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.
Published
2020-12-08
Keywords: linear semidefinite programming, strong duality, normalised immobile index set, regularisation, constraint qualifications
Supporting Agencies This work was partially supported by the state research program «Convergence» (task 1.3.01, Republic of Belarus), by Portuguese funds through the Center for Research and Development in Mathematics and Applications (CIDMA), and the Foundation for Science and Technology (FCT, project UIDB/04106/2020).
How to Cite
Kostyukova, O. I., & Tchemisova, T. V. (2020). Linear semidefinite programming problems: regularisation and strong dual formulations. Journal of the Belarusian State University. Mathematics and Informatics, 3, 17-27. https://doi.org/10.33581/2520-6508-2020-3-17-27
Issue
No 3 (2020): Journal of the Belarusian State University. Mathematics and Informatics
Section
Differential Equations and Optimal Control

Copyright (c) 2020 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

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:

  1. 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).
  2. 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.
  3. 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.)