The paper is devoted to the regularization of linear Copositive Programming problems which consists of transforming a problem to an equivalent form, where the Slater condition is satisfied and therefore the strong duality holds. We describe regularization algorithms based on a concept of immobile indices and on the understanding of the important role that these indices play in the feasible sets' characterization. These algorithms are compared to some regularization procedures developed for a more general case of convex problems and based on a facial reduction approach. We show that the immobile-index-based approach combined with the specifics of copositive problems allows us to construct more explicit and detailed regularization algorithms for linear Copositive Programming problems than those already available.
Keywords: Linear copositive programming, strong duality, normalized immobile index set, regularization, minimal cone, facial reduction, constraint qualifications
@article{RO_2022__56_3_1353_0,
author = {Kostyukova, Olga I. and Tchemisova, Tatiana V.},
title = {Regularization algorithms for linear copositive problems},
journal = {RAIRO. Operations Research},
pages = {1353--1371},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {3},
doi = {10.1051/ro/2022063},
mrnumber = {4431921},
zbl = {1492.90127},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022063/}
}
TY - JOUR AU - Kostyukova, Olga I. AU - Tchemisova, Tatiana V. TI - Regularization algorithms for linear copositive problems JO - RAIRO. Operations Research PY - 2022 SP - 1353 EP - 1371 VL - 56 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022063/ DO - 10.1051/ro/2022063 LA - en ID - RO_2022__56_3_1353_0 ER -
%0 Journal Article %A Kostyukova, Olga I. %A Tchemisova, Tatiana V. %T Regularization algorithms for linear copositive problems %J RAIRO. Operations Research %D 2022 %P 1353-1371 %V 56 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022063/ %R 10.1051/ro/2022063 %G en %F RO_2022__56_3_1353_0
Kostyukova, Olga I.; Tchemisova, Tatiana V. Regularization algorithms for linear copositive problems. RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1353-1371. doi: 10.1051/ro/2022063
[1] , and , Copositive Programming via semi-infinite optimization. J. Optim. Theory Appl. 159 (2013) 322–340. | MR | Zbl | DOI
[2] , (editors), Handbook of Semidefinite, Conic and Polynomial Optimization. International Series in Operational Research and Management Science. Vol. 166. Springer US (2012) 138. | Zbl
[3] , Copositive optimization – recent developments and applications. EJOR 216 (2012) 509–520. | MR | Zbl | DOI
[4] and , Perturbation analysis of optimization problems. Springer-Verlag, New-York, NY (2000) 601. | MR | Zbl
[5] and , Facial reduction for a cone-convex programming problem. J. Austral. Math. Soc. Ser. A. 30 (1981) 369–380. | MR | Zbl | DOI
[6] and , Regularizing the abstract convex program. J. Math. Anal. Appl. 83 (1981) 495–530. | MR | Zbl | DOI
[7] and , Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12 (2002) 875–892. | MR | Zbl | DOI
[8] and , The many faces of degeneracy in conic optimization. In: Foundations and Trends in Optimization. Vol. 3. Now Publishers Inc. (2017) 77–170. | DOI
[9] , Copositive programming – a survey. In: Recent Advances in Optimization and its Applications in Engineering, edited by , , and . Springer-Verlag, Berlin, Heidelberg (2010) 535.
[10] and , Perfect duality in semi-infinite and semidefinite programming. Math. Program. Ser. A 91 (2001) 127–144. | MR | Zbl | DOI
[11] and , Optimality conditions for convex semi-infinite programming problems with finitely representable compact index sets. J. Optim. Theory Appl. 175 (2017) 76–103. | MR | Zbl | DOI
[12] and , On equivalent representations and properties of faces of the cone of copositive matrices. Optimization (2020). DOI: . | DOI | MR | Zbl
[13] and , On strong duality in linear copositive programming. J. Global Optim. (2021) 1–24. DOI: . | DOI | MR | Zbl
[14] , and , Immobile indices and CQ-free optimality criteria for linear copositive programming problems. Set-Valued Var. Anal. 28 (2020) 89–107. | Zbl | MR | DOI
[15] and , A guide to conic optimisation and its applications. RAIRO Oper. Res. 52 (2018) 1087–1106. | MR | Zbl | Numdam | DOI
[16] , Application of E. Helly’s theorem to convex programming, problems of best approximation and related questions. Math. USSR Sbornik 8 (1969) 235–247. | MR | Zbl | DOI
[17] , and , Duality Results for Conic Convex Programming, Econometric institute report no. 9719/a. Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute (1997).
[18] , simple derivation of a facial reduction algorithm and extended dual systems. Preprint available at http://www.unc.edu/pataki/papers/fr.pdf (2000).
[19] , and , Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach. Tech. Report. (2015). DOI: . | DOI | MR | Zbl
[20] and , Exact Duality for Optimization Over Symmetric Cones. AdvOL-Report No. 2007/10. McMaster University, Advanced Optimization Lab., Hamilton, Canada (2007).
[21] , and , Strong duality for semidefinite programming. SIAM J. Optim. 7 (1997) 641–662. | MR | Zbl | DOI
[22] , Constraint qualifications. In: Wiley Encyclopedia of Operations Research and Management Science, edited by , et al. John Wiley & Sons, Inc. (2010).
[23] and , Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. 53 (2013) 619–648. | MR | Zbl | DOI
[24] and , Facial reduction algorithms for conic optimization problems. J. Optim. Theory Appl. 158 (2013) 188–215. | MR | Zbl | DOI
[25] , Generalized semi-infinite optimization and related topics. In: Research and Exposition in Mathematics, edited by , . Vol. 29. Heldermann Publishing House, Lemgo (2003). | MR | Zbl
[26] , and , Handbook of Semidefinite Programming – Theory, Algorithms, and Applications. Kluwer Academic Publishers (2000). | MR | Zbl | DOI
Cité par Sources :
