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

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