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

Almaadeed, Temadher Alassiry; Hamdi, Abdelouahed; Taati, Akram

doi:10.22124/jmm.2025.31942.2884

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

Articles in Press

Document Type : Research Article

Authors

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

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

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

10.22124/jmm.2025.31942.2884

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