SpringerLink
Log in

Immobile Indices and CQ-Free Optimality Criteria for Linear Copositive Programming Problems

  • Published:
Set-Valued and Variational Analysis Aims and scope Submit manuscript

Abstract

We consider problems of linear copositive programming where feasible sets consist of vectors for which the quadratic forms induced by the corresponding linear matrix combinations are nonnegative over the nonnegative orthant. Given a linear copositive problem, we define immobile indices of its constraints and a normalized immobile index set. We prove that the normalized immobile index set is either empty or can be represented as a union of a finite number of convex closed bounded polyhedra. We show that the study of the structure of this set and the connected properties of the feasible set permits to obtain new optimality criteria for copositive problems. These criteria do not require the fulfillment of any additional conditions (constraint qualifications or other). An illustrative example shows that the optimality conditions formulated in the paper permit to detect the optimality of feasible solutions for which the known sufficient optimality conditions are not able to do this. We apply the approach based on the notion of immobile indices to obtain new formulations of regularized primal and dual problems which are explicit and guarantee strong duality.

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. 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 

  2. Baumer, L.D.: Extreme copositive quadratic forms. Pac. J. Math. 19(2), 197–204 (1966)

    Article  MathSciNet  Google Scholar 

  3. Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press (2009)

  4. Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, New Jersey (2003). 216 p

    Book  Google Scholar 

  5. 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 

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

    Article  MathSciNet  Google Scholar 

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

    Book  Google Scholar 

  8. Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program 120, 479–495 (2009)

    Article  MathSciNet  Google Scholar 

  9. Borwein, J.M., Wolkowicz, H.: Characterization of optimality for the abstract convex program with finite-dimensional range. J. Aust. Math. Soc., Ser. A 30(4), 390–411 (1980)

    Article  MathSciNet  Google Scholar 

  10. Cánovas, M.J., Kruger, A. Y.a., López, M.A., Parra, J, Théra, M.A.: Calmness modulus of linear semi-infinite programs. SIAM J. Optim. 24(1), 29–48 (2014)

    Article  MathSciNet  Google Scholar 

  11. de Klerk, E, Pasechnik, D.V.: Approximation of the stability number number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002)

    Article  MathSciNet  Google Scholar 

  12. Dickinson, P.J., Dür, M., Gijben, L., Hildebrand, R.: Irreducible elements of the copositive cone. Linear Algebra Appl. 439(6), 1605–1626 (2013)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  14. 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 p. Springer, Berlin (2010)

  15. Jongen, H. T. h., Twilt, F., Weber, G.-W.: Semi-infinite optimization: Structure and stability of the feasible set. J. Optim. Theory Appl. 72, 529–552 (1992)

    Article  MathSciNet  Google Scholar 

  16. Hiriart-Urruty, J.B., Seeger, A.: A variational approach to copositive matrices. SIAM Rev. 52, 593–629 (2010)

    Article  MathSciNet  Google Scholar 

  17. Hettich, R., Kortanek, K.O.: Semi-Infinite programming: Theory, methods and applications. SIAM Rev. 35, 380–429 (1993)

    Article  MathSciNet  Google Scholar 

  18. Hildebrand, R.: Minimal zeros of copositive matrices. Linear Algebra Appl. 459, 154–174 (2014)

    Article  MathSciNet  Google Scholar 

  19. Kostyukova, O.I., Tchemisova, T.V.: Convex SIP problems with finitely representable compact index sets: Immobile indices and the properties of the auxiliary NLP problem. Set-Valued Var. Anal. 23(3), 519–546 (2015)

    Article  MathSciNet  Google Scholar 

  20. 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 

  21. 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 

  22. 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)

    Article  MathSciNet  Google Scholar 

  23. 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 

  24. Kostyukova, O.I., Tchemisova, T.V.: Implicit optimality criterion for convex SIP problem with box constrained index set. TOP 20(2), 475–502 (2012)

    Article  MathSciNet  Google Scholar 

  25. Kruger, A.Ya: Strict (e, d)-subdifferentials and extremality conditions. Optimization 51(3), 539–554 (2002)

    Article  MathSciNet  Google Scholar 

  26. Kruger, A.Ya: Weak stationarity: Eliminating the gap between necessary and sufficient conditions. Optimization 53:2, 147–164 (2004)

    Article  MathSciNet  Google Scholar 

  27. Kruger, A.Ya: About regularity of collections of sets. Set-Valued Anal. 14, 187–206 (2006)

    Article  MathSciNet  Google Scholar 

  28. Kruger, A.Ya.: Generalized differentials of nonsmooth functions and necessary conditions for an extremum. Sib. Math. J. 26, 370–379 (1985)

    Article  MathSciNet  Google Scholar 

  29. Kruger, A.Ya., Minchenko, L., Outrata, J.V.: On relaxing the Mangasarian-Fromovitz constraint qualification. Positivity 18(1), 171–189 (2014)

    Article  MathSciNet  Google Scholar 

  30. Kruger, A.Ya., López, M.A.: Stationarity and regularity of infinite collections of sets. J. Optim Theory Appl 154, 339–369 (2012)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  32. Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533–540 (1965)

    Article  Google Scholar 

  33. Murtu, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117–129 (1987)

    Article  MathSciNet  Google Scholar 

  34. Ngai, H.V., Kruger, A.Ya., Théra, M.A.: Stability of error bounds for convex constraint systems in Banach spaces. SIAM J. Optim. 20(6), 3280–3296 (2010)

    Article  MathSciNet  Google Scholar 

  35. Ngai, H.V., Kruger, A.Ya., Théra, M.A.: Stability of error bounds for semi-infinite convex constraint systems. SIAM J. Optim. 20(4), 2080–2096 (2010)

    Article  MathSciNet  Google Scholar 

  36. Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77, 129–162 (1997)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  39. Weber, G.-W.: Generalized Semi-Infinite Optimization and Related Topics. In: Hofmann, K.H., Wille, R. (eds.) Research and Exposition in Mathematics, vol. 29. Heldermann Publishing House, Lemgo (2003)

  40. Weber, G.-W., Tezel, A.: On generalized semi-infinite optimization of genetic networks. TOP 15(1), 65–77 (2007)

    Article  MathSciNet  Google Scholar 

  41. Yamamoto, S.: Alternative theorems and constraint qualifications in convex optimization. Mem. Gra. Sci. Eng. Shimane Univ. Series B: Math. 50, 11–30 (2017)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work has been supported by the state research program “Convergence” (Republic Belarus), Task 1.3.01 (O.I. Kostyukova), 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 UID/MAT/04106/2019 (T.V.Tchemisova), and by the RUDN University Program 5-100 (O.S.Dudina).

The authors thank the anonymous referees for their valuable comments on 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. CIDMA–Center for Research and Development in Mathematics and Applications, Department of Mathematics, University of Aveiro, Campus Universitário Santiago, 3810-193, Aveiro, Portugal

    T. V. Tchemisova

  3. Belarusian State University, Independence Ave., 4, Minsk, Belarus

    O. S. Dudina

  4. RUDN University, 6, Miklukho-Maklaya st., 117198, Moscow, Russia

    O. S. Dudina

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

  3. O. S. Dudina
    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. & Dudina, O.S. Immobile Indices and CQ-Free Optimality Criteria for Linear Copositive Programming Problems. Set-Valued Var. Anal 28, 89–107 (2020). https://doi.org/10.1007/s11228-019-00527-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11228-019-00527-y

Keywords

Mathematics Subject Classification (2010)

Search

Navigation