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 con-
vex 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, StrongdualityfortheCDTsubproblem: anecessaryandsufficientcondition,
SIAMJ.Optim.19(4)(2009)1735–1756.
[2] T.A.Almaadeed,A.Taati,M.Salahi,A.Hamdi, Thegeneralizedtrust-regionsubproblemwith
additionallinearinequalityconstraints:twoconvexquadraticrelaxationsandstrongduality,Sym
metry12(9)(2020)1369.
[3]K.M.Anstreicher,Kroneckerproductconstraintswithanapplicationtothetwo-trust-regionsub
problem,SIAMJ.Optim.27(2)(2017)368–378
[4] D. Bienstock, A note on polynomial solvability of the CDT problem, SIAM J. Optim. 26(1) (2016)
488–498.
[5] I.M. Bomze, M.L.Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math.
Program. 151(2) (2015) 459–476.
[6] S. Burer, K.M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems,
SIAMJ. Optim. 23(1) (2013) 432–451.
[7] M.R. Celis, J.E. Dennis, R. A. Tapia, A trust region algorithm for nonlinear equality constrained
optimization, in Numerical Optimization, R.T. Boggs, R.H. Byrd, and R.B. Schnabel, eds., SIAM,
Philadelphia, (1984) 71–82.
[8] L. Consolini, M. Locatelli, Sharp and fast bounds for the Celis-Dennis-Tapia problem, SIAM J.
Optim. 33(2) (2023) 868–898.
[9] A.Hamdi, AmodifiedBregmanproximalschemetominimize 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 constrains, Commun. Comb. Optim. (2026), in press.
[13] S. Ansary Karbasy, M. Salahi, Quadratic optimization with two ball constraints, Numer. Algebra
Control Optim. 10(2) (2020) 165–175.
[14] S. Ansary Karbasy, M. Salahi, A hybrid algorithm for the two-trust-region subproblem, Comput.
Appl. Math. 38(3) (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(2) (2022) 715–737.
[16] G. Li, Y. Yuan, Compute a Celis-Dennis-Tapia step, J. Comput. Math. 23(5) (2005) 463–478.
[17] S. Sakaue, Y. Nakatsukasa, A. Takeda, S. Iwata, Solving generalized CDT problems via two
parameters eigenvalues, SIAM J. Optim. 26(3) (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(2) (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(2) (2017) 890–909
Journal of Mathematical Modeling
Volume 14, Issue 2
May 2026
Pages 595-608

Files

Share

How to cite

Statistics