SpringerLink
Log in

On strong duality in linear copositive programming

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The paper is dedicated to the study of strong duality for a problem of linear copositive programming. Based on the recently introduced concept of the set of normalized immobile indices, an extended dual problem is deduced. The dual problem satisfies the strong duality relations and does not require any additional regularity assumptions such as constraint qualifications. The main difference with the previously obtained results consists in the fact that now the extended dual problem uses neither the immobile indices themselves nor the explicit information about the convex hull of these indices. The strong duality formulations presented in the paper for linear copositive problems have similar structure and properties as that proposed in the works by M. Ramana, L. Tuncel, and H. Wolkowicz, for semidefinite programming.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anh Truong, V., Tunçel, L.: Geometry of homogeneous convex cones, duality map**, and optimal self-concordant barriers. Math. Program. Ser. A 100, 295–316 (2004)

    Article  MathSciNet  Google Scholar 

  2. Ahmed, F., Dür, M., Still, G.: Copositive Programming via semi-infinite optimization. J. Optim. Theory Appl. 159, 322–340 (2013)

    Article  MathSciNet  Google Scholar 

  3. Berman, A., Shaked-Monderer, N.: Completely Positive Matrices, p. 216. World Scientific, New Jersey, London, Singapore, Hong Kong (2003)

    Book  Google Scholar 

  4. Bomze, I.M., Dür, M., de Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On Copositive Programming and standard quadratic optimization problems. J. Global Optim. 18, 301–320 (2000)

    Article  MathSciNet  Google Scholar 

  5. Bomze, I.M.: Copositive optimization - recent developments and applications. EJOR 216(3), 509–520 (2012)

    Article  MathSciNet  Google Scholar 

  6. Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems, p. 601. Springer-Verlag, New-York (NY) (2000)

    Book  Google Scholar 

  7. Chua, C.B., Tunçel, L.: Invariance and efficiency of convex representations. Math. Program. 111, 113–140 (2008)

    Article  MathSciNet  Google Scholar 

  8. Dickinson, P.J.C., Hildebrand, R.: Considering copositivity locally. J. Math. Anal. Appl. 437(2), 1184–1195 (2016)

    Article  MathSciNet  Google Scholar 

  9. Dür, M.: Copositive Programming - a Survey. In: Diehl, M., Glineur, F., Jarlebring, E., Michielis, W. (eds.) Recent Advances in Optimization and its Applications in Engineering, p. 535. Springer-Verlag, Berlin, Heidelberg (2010)

    Google Scholar 

  10. Gowda, M.S., Sznajder, R.: On the non-homogeneity of completely positive cones, Technical Report trGOW11-04, Department of Mathematics and Statistics University of Maryland Baltimore County Baltimore, MD 21250 USA November (2011) Available at https://www.optimization-online.org/DB HTML/2012/05/3464.html

  11. Jeyakumar, V., Lee, G.M., Dihn, N.: New sequential Lagrange multiplier conditions characterizing optimality without constraint qualification for convex programs. SIAM J. Optim. 14(2), 534–547 (2003)

    Article  MathSciNet  Google Scholar 

  12. Kortanek, K.O., Zhang, Q.: Perfect duality in semi-infinite and semidefinite programming. Math. Program. Ser. A 91, 127–144 (2001)

    Article  MathSciNet  Google Scholar 

  13. Kostyukova, O.I., Tchemisova, T.V.: Optimality conditions for convex Semi-Infinite Programming problems with finitely representable compact index sets. J. Optim. Theory Appl. 175(1), 76–103 (2017)

    Article  MathSciNet  Google Scholar 

  14. Kostyukova, O.I., Tchemisova, T.V., Dudina, O.S.: Immobile indices and CQ-free optimality criteria for Linear Copositive Programming problems. Set-Valued Var. Anal. 28, 89–107 (2020)

    Article  MathSciNet  Google Scholar 

  15. Kostyukova, O.I., Tchemisova, T.V.: On a constructive approach to optimality conditions for convex SIP problems with polyhedral index sets. Optimization 63(1), 67–91 (2014)

    Article  MathSciNet  Google Scholar 

  16. Kostyukova, O.I., Tchemisova, T.V.: Optimality criteria without constraint qualification for Linear Semidefinite Problems. Special Issue ”Algebraic techniques in Graph Theory and Optimization”. J. Math. Sci. 182(2), 126–143 (2012)

  17. Kostyukova, O.I., Tchemisova, T.V.: Optimality conditions for Linear Copositive Programming problems with isolated immobile indices. Optimization 69(1), 145–164 (2020)

    Article  MathSciNet  Google Scholar 

  18. Levin, V.L.: Application of E.Helly’s theorem to convex programming, problems of best approximation and related questions. Math. USSR Sbornik 8(2), 235–247 (1969)

    Article  Google Scholar 

  19. Li, S.J., Yang, X.Q., Teo, K.L.: Duality for semi-definite and semi-infinite programming. Optimization 52, 507–528 (2003)

    Article  MathSciNet  Google Scholar 

  20. Luo, Z.-Q., Sturm, F.J., Zhang, S.: Duality results for conic convex programming. Econometric institute report no. 9719/a, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute (1997)

  21. Magnus, J.R., Neudecker, H.: Matrix differential calculus with applications in statistics and econometrics, 3rd edn. John Wiley & sons, New Jersey (2007)

    MATH  Google Scholar 

  22. Motzkin, T.: Copositive quadratic forms. National Bureau of Standards Report 1818, pp. 11–12 (1952)

  23. Pataki, G.: A simple derivation of a facial reduction algorithm and extended dual systems. Preprint available https://www.unc.edu/pataki/papers/fr.pdf (2000)

  24. Pólik, I., Terlaky, T.: Exact duality for optimization over symmetric cones, AdvOL-Report No. 2007/10 McMaster University, Advanced Optimization Lab., Hamilton, Canada (2007)

  25. Ramana, M.V.: An exact duality theory for Semidefinite Programming and its complexity implications. DIMACS Technical report 95-02R, RUTCOR, Rutgers University, New Brunswick (NJ) (1995)

  26. Ramana, M.V., Tuncel, L., Wolkowicz, H.: Strong duality for Semidefinite Programming. SIAM J. Optim. 7(3), 641–662 (1997)

    Article  MathSciNet  Google Scholar 

  27. Shapiro, A.: Duality, optimality conditions and perturbation analysis. In: Saigal, R., Vandenberghe, L., Wolkowicz, H. (eds.) Semidefinite Programming and Applications Handbook, pp. 67–92. Kluwer Academic Publishers, Boston (2000)

    Chapter  Google Scholar 

  28. Tunçel, L., Wolkowicz, H.: Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. 53, 619–648 (2013)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work was partially supported by the state research program “Convergence -2025”(Republic Belarus) and by Portuguese funds through CIDMA - Center for Research and Development in Mathematics and Applications, and FCT - Portuguese Foundation for Science and Technology, within the project UIDB/04106/2020. The authors thank the anonymous referees for their very helpful comments and suggestions which aided us in considerably improving the presentation of this paper.

Author information

Authors and Affiliations

  1. Institute of Mathematics, National Academy of Sciences of Belarus, Surganov str. 11, 220072, Minsk, Belarus

    O. I. Kostyukova

  2. Department of Mathematics, CIDMA–Center for Research and Development in Mathematics and Applications, University of Aveiro, Campus Universitário Santiago, 3810-193, Aveiro, Portugal

    T. V. Tchemisova

Authors
  1. O. I. Kostyukova
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. V. Tchemisova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to T. V. Tchemisova.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kostyukova, O.I., Tchemisova, T.V. On strong duality in linear copositive programming. J Glob Optim 83, 457–480 (2022). https://doi.org/10.1007/s10898-021-00995-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-021-00995-3

Keywords

Mathematics Subject Classification

Search

Navigation