A fast and cheap approach for strengthening Lagrangian bound for the generalized Celis-Dennis-Tapia subproblem

Document Type : Research Article

Authors

1 Qatar University-College of Arts and Sciences-Dept Mathematics and Statistics, P.O. Box 2713 Qatar University, Doha- Qatar

2 Qatar University-College of Arts and Sciences-Dept Mathematics and Statistics, P.O. Box 2713, Qatar University, Doha- Qatar

3 Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran.

Abstract

In this paper, we consider the generalized Celis-Dennis-Tapia problem which is the problem of minimizing a nonconvex quadratic function subject to two quadratic inequality constraints, one of which being convex. When there is a positive duality gap, by exploiting an equivalent form of the dual Lagrangian problem, we propose to improve the dual bound by adding one or two linear cuts to the Lagrangian relaxation. The present work is motivated by and generalizes the results of [14] for the problem with two strictly convex quadratic constraints. Our main contribution is to show that one can include the feasible region in a convex set and then follow the approach in [14] to construct the linear cuts based on
supporting hyperplanes of the convex set. Numerical experiments are conducted to assess the quality of the proposed bounds.

Keywords

Main Subjects

References

[1] W. Ai, S. Zhang, Strong duality for the CDT subproblem: a necessary and sufficient condition, SIAM J. Optim. 19 (2009) 1735–1756.
[2] T.A. Almaadeed, A. Taati, M. Salahi, A. Hamdi, The generalized trust-region subproblem with additional linear inequality constraints: two convex quadratic relaxations and strong duality, Symmetry 12 (2020) 1369.
[3] K.M. Anstreicher, Kronecker product constraints with an application to the two-trust-region subproblem, SIAM J. Optim. 27 (2017) 368–378.
[4] D. Bienstock, A note on polynomial solvability of the CDT problem, SIAM J. Optim. 26 (2016) 488–498.
[5] I.M. Bomze, M.L. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math. Program. 151 (2015) 459–476.
[6] S. Burer, K.M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim. 23 (2013) 432–451.
[7] M.R. Celis, J.E. Dennis, R.A. Tapia, A trust region algorithm for nonlinear equality constrained optimization, in: R.T. Boggs, R.H. Byrd, R.B. Schnabel (Eds.), Numerical Optimization, SIAM, Philadelphia, 1984, pp. 71–82.
[8] L. Consolini, M. Locatelli, Sharp and fast bounds for the Celis-Dennis-Tapia problem, SIAM J. Optim. 33 (2023) 868–898.
[9] A. Hamdi, A modified Bregman proximal scheme to minimize the difference of two convex functions, Appl. Math. E-Notes 6 (2006) 132–140.
[10] A. Hamdi, A Moreau-Yosida regularization of a difference of two convex functions, Appl. Math. E-Notes 5 (2005) 164–170.
[11] A. Hamdi, A. Taati, T.A. Al-Maadeed, Quadratic problems with two quadratic constraints: convex quadratic relaxation and strong Lagrangian duality, RAIRO Oper. Res. 55 (2021) 2905–2922.
[12] A. Hamdi, M. Salahi, S. Ansary Karbasy, T.A. Al-Maadeed, Quadratic optimization with a ball and a reverse ball constraints, Commun. Comb. Optim. (2026), in press.
[13] S. Ansary Karbasy, M. Salahi, Quadratic optimization with two ball constraints, Numer. Algebra Control Optim. 10 (2020) 165–175.
[14] S. Ansary Karbasy, M. Salahi, A hybrid algorithm for the two-trust-region subproblem, Comput. Appl. Math. 38 (2019) 1–19.
[15] S. Ansary Karbasy, M. Salahi, An efficient algorithm for the extended trust-region subproblem with two linear constraints, Bull. Iran. Math. Soc. 48 (2022) 715–737.
[16] G. Li, Y. Yuan, Compute a Celis-Dennis-Tapia step, J. Comput. Math. 23 (2005) 463–478.
[17] S. Sakaue, Y. Nakatsukasa, A. Takeda, S. Iwata, Solving generalized CDT problems via two parameters eigenvalues, SIAM J. Optim. 26 (2016) 1669–1694.
[18] M. Salahi, A. Taati, H. Wolkowicz, Local nonglobal minima for solving large-scale extended trust region subproblems, Comput. Optim. Appl. 66 (2017) 223–244.
[19] J. Yuan, M. Wang, W. Ai, T. Shuai, New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem, SIAM J. Optim. 27 (2017) 890–909.
Journal of Mathematical Modeling
Volume 14, Issue 2
May 2026
Pages 595-608

Files

Share

How to cite

Statistics