New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts

Meiling Wang

doi:10.5802/crmath.661

Article de recherche - Analyse numérique

New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts
[Nouveaux résultats sur l’élimination de l’écart de dualité de la reformulation du cône du second ordre pour le sous-problème de la région de confiance étendue avec deux coupes intersectées]

Meiling Wang ¹

¹ School of Statistics and Data Science, Beijing Wuzi University, Beijing 101149, China

Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1497-1513.

Résumé
Abstract

Dans cet article, nous considérons le sous-problème non convexe de la région de confiance étendue avec deux contraintes d’inégalité linéaires qui se croisent, $({ETR}_{2})$ , et nous utilisons une suite de problèmes de programmation semi-définie (SDP) avec des contraintes de cône de second ordre (SOC) pour éliminer l’écart de dualité de la reformulation SOC pour $({ETR}_{2})$ . Nous réduisons d’abord l’écart de dualité de la reformulation SOC en ajoutant une nouvelle contrainte SOC appropriée, et une condition suffisante est présentée pour caractériser quand la nouvelle contrainte SOC est valide. Ensuite, nous établissons un algorithme itératif et les résultats des expériences numériques montrent que l’algorithme itératif fonctionne efficacement pour éliminer l’écart SDPR-SOCR de $({ETR}_{2})$ .

In this paper, we consider the nonconvex extended trust-region subproblem with two intersecting linear inequality constraints, $({ETR}_{2})$ , and use a sequence of semi-definite programming (SDP) problems with second-order-cone(SOC) constraints to eliminate the duality gap of the SOC reformulation for $({ETR}_{2})$ . We first narrow the duality gap of the SOC reformulation by adding a new appropriate SOC constraint, and a sufficient condition is presented to characterize when the new SOC constraint is valid. Then we establish an iterative algorithm and the results of numerical experiments show that the iterative algorithm works efficiently in eliminating the SDPR-SOCR gap of $({ETR}_{2})$ .

Reçu le : 2022-07-15
Révisé le : 2024-03-21
Accepté le : 2024-06-24
Publié le : 2024-11-14

Zbl

DOI : 10.5802/crmath.661

Classification : 90C20, 90C22, 90C25, 90C26, 90C30
Keywords: Second-order-cone reformulation, extended trust-region subproblem, linear inequality constraints, duality gap, semidefinite programming relaxation
Mots-clés : Reformulation de cône de second ordre, sous-problèmes de domaine de confiance étendu, contraintes d’inégalité linéaire, écart de dualité, relaxation de planification semi-définie

Affiliations des auteurs :

Meiling Wang ¹

¹ School of Statistics and Data Science, Beijing Wuzi University, Beijing 101149, China

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2024__362_G11_1497_0,
     author = {Meiling Wang},
     title = {New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1497--1513},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     year = {2024},
     doi = {10.5802/crmath.661},
     zbl = {07945492},
     language = {en},
}

TY  - JOUR
AU  - Meiling Wang
TI  - New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 1497
EP  - 1513
VL  - 362
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.661
LA  - en
ID  - CRMATH_2024__362_G11_1497_0
ER  -

%0 Journal Article
%A Meiling Wang
%T New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts
%J Comptes Rendus. Mathématique
%D 2024
%P 1497-1513
%V 362
%I Académie des sciences, Paris
%R 10.5802/crmath.661
%G en
%F CRMATH_2024__362_G11_1497_0

Meiling Wang. New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1497-1513. doi : 10.5802/crmath.661. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.661/

Bibliographie
Cité par

[1] Wenbao Ai; Shuzhong Zhang Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J. Optim., Volume 19 (2008) no. 4, pp. 1735-1756 | DOI | MR | Zbl

[2] Samuel Burer; Kurt M. Anstreicher Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., Volume 23 (2013) no. 1, pp. 432-451 | DOI | MR | Zbl

[3] Amir Beck; Dror Pan A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Glob. Optim., Volume 69 (2017) no. 2, pp. 309-342 | DOI | MR | Zbl

[4] Samuel Burer; Boshi Yang The trust region subproblem with non-intersecting linear constraints, Math. Program., Volume 149 (2015) no. 1-2, Ser. A, pp. 253-264 | DOI | MR | Zbl

[5] Jinyu Dai On globally solving the extended trust-region subproblems, Oper. Res. Lett., Volume 48 (2020) no. 4, pp. 441-445 | DOI | MR | Zbl

[6] Jinyu Dai; Shu-Cherng Fang; Wenxun Xing Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints, J. Ind. Manag. Optim., Volume 15 (2019) no. 4, pp. 1677-1699 | DOI | MR | Zbl

[7] Zhibin Deng; Cheng Lu; Ye Tian; Jian Luo Globally solving extended trust region subproblems with two intersecting cuts, Optim. Lett., Volume 14 (2020) no. 7, pp. 1855-1867 | DOI | MR | Zbl

[8] Qingwei Jin; Shu-Cherng Fang; Wenxun Xing On the global optimality of generalized trust region subproblems, Optimization, Volume 59 (2010) no. 8, pp. 1139-1151 | DOI | MR | Zbl

[9] V. Jeyakumar; G. Y. Li Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Math. Program., Volume 147 (2014) no. 1-2, Ser. A, pp. 171-206 | DOI | MR | Zbl

[10] S. Ansary Karbasy; A. Hamdi; M. Salahi; A. Taati An efficient algorithm for large-scale extended trust-region subproblems with non-intersecting linear constraints, Optim. Lett., Volume 15 (2021) no. 4, pp. 1425-1446 | DOI | MR

[11] S. Ansary Karbasy; Maziar Salahi An efficient algorithm for the extended trust-region subproblem with two linear constraints, Bull. Iranian Math. Soc., Volume 48 (2022) no. 2, pp. 715-737 | DOI | MR | Zbl

[12] S. Ansary Karbasy; Maziar Salahi On the branch and bound algorithm for the extended trust-region subproblem, J. Glob. Optim., Volume 83 (2022) no. 2, pp. 221-233 | DOI | MR | Zbl

[13] Marco Locatelli Exactness conditions for an SDP relaxation of the extended trust region problem, Optim. Lett., Volume 10 (2016) no. 6, pp. 1141-1151 | DOI | MR | Zbl

[14] Jos F. Sturm; Shuzhong Zhang On cones of nonnegative quadratic functions, Math. Oper. Res., Volume 28 (2003) no. 2, pp. 246-267 | DOI | MR | Zbl

[15] Yaxiang Yuan Nonlinear programming: trust region algorithms, Proceedings of Chinese SIAM Annual Meeting (S. T. Xiao; F. Wu, eds.), Hsinghua University Press (1994), pp. 83-97

[16] Yaxiang Yuan Trust region algorithms for constrained optimization, Proceedings of Conference on Scientific and Engineering Computing for Young Chinese Scientists (J. Z. Cui; Z. C. Shi; D. L Wang, eds.), National Defence Industry Press (1994), pp. 105-110

[17] Jianhua Yuan; Meiling Wang; Wenbao Ai; Tianping Shuai A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts, Sci. China, Math., Volume 59 (2016) no. 6, pp. 1127-1140 | DOI | MR | Zbl

[18] Jianhua Yuan; Meiling Wang; Wenbao Ai; Tianping Shuai New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem, SIAM J. Optim., Volume 27 (2017) no. 2, pp. 890-909 | DOI | MR | Zbl

[19] Yinyu Ye; Shuzhong Zhang New results on quadratic minimization, SIAM J. Optim., Volume 14 (2003) no. 1, pp. 245-267 | DOI | MR | Zbl

Cité par Sources :

Commentaires - Politique