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

Wang, Meiling

Comptes Rendus. Mathématique, Tome 362 (2024) no. G11, pp. 1497-1513

In this paper, we consider the nonconvex extended trust-region subproblem with two intersecting linear inequality constraints, $\left({\mathrm{ETR}}_2\right)$, 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 $\left({\mathrm{ETR}}_2\right)$. 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 $\left({\mathrm{ETR}}_2\right)$.

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, $\left({\mathrm{ETR}}_2\right)$, 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 $\left({\mathrm{ETR}}_2\right)$. 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 $\left({\mathrm{ETR}}_2\right)$.

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

[1] Ai, Wenbao; Zhang, Shuzhong 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] Burer, Samuel; Anstreicher, Kurt M. Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., Volume 23 (2013) no. 1, pp. 432-451 | DOI | MR | Zbl

[3] Beck, Amir; Pan, Dror 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] Burer, Samuel; Yang, Boshi 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] Dai, Jinyu On globally solving the extended trust-region subproblems, Oper. Res. Lett., Volume 48 (2020) no. 4, pp. 441-445 | DOI | MR | Zbl

[6] Dai, Jinyu; Fang, Shu-Cherng; Xing, Wenxun 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] Deng, Zhibin; Lu, Cheng; Tian, Ye; Luo, Jian Globally solving extended trust region subproblems with two intersecting cuts, Optim. Lett., Volume 14 (2020) no. 7, pp. 1855-1867 | DOI | MR | Zbl

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

[9] Jeyakumar, V.; Li, G. Y. 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] Karbasy, S. Ansary; Hamdi, A.; Salahi, M.; Taati, A. 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] Karbasy, S. Ansary; Salahi, Maziar 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] Karbasy, S. Ansary; Salahi, Maziar 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] Locatelli, Marco 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] Sturm, Jos F.; Zhang, Shuzhong On cones of nonnegative quadratic functions, Math. Oper. Res., Volume 28 (2003) no. 2, pp. 246-267 | DOI | MR | Zbl

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

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

[17] Yuan, Jianhua; Wang, Meiling; Ai, Wenbao; Shuai, Tianping 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] Yuan, Jianhua; Wang, Meiling; Ai, Wenbao; Shuai, Tianping 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] Ye, Yinyu; Zhang, Shuzhong New results on quadratic minimization, SIAM J. Optim., Volume 14 (2003) no. 1, pp. 245-267 | DOI | MR | Zbl