In the Celis--Dennis--Tapia (CDT) problem a quadratic function is minimized over a region defined by two strictly convex quadratic constraints. In this paper we rederive a necessary and sufficient optimality condition for the exactness of the dual Lagrangian bound (equivalent to the Shor relaxation bound in this case). Starting from such a condition, we propose strengthening the dual Lagrangian bound by adding one or two linear cuts to the Lagrangian relaxation. Such cuts are obtained from supporting hyperplanes of one of the two constraints. Thus, they are redundant for the original problem, but they are not for the Lagrangian relaxation. The computational experiments show that the new bounds are effective and require limited computing times. In particular, one of the proposed bounds is able to solve all but one of the 212 hard instances of the CDT problem presented in [S. Burer and K. M. Anstreicher, SIAM J. Optim., 23 (2013), pp. 432--451].

Sharp and Fast Bounds for the Celis-Dennis-Tapia Problem / Consolini, Luca; Locatelli, Marco. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - 33:2(2023), pp. 868-898. [10.1137/21M144548X]

Sharp and Fast Bounds for the Celis-Dennis-Tapia Problem

Consolini, Luca;Locatelli, Marco
2023-01-01

Abstract

In the Celis--Dennis--Tapia (CDT) problem a quadratic function is minimized over a region defined by two strictly convex quadratic constraints. In this paper we rederive a necessary and sufficient optimality condition for the exactness of the dual Lagrangian bound (equivalent to the Shor relaxation bound in this case). Starting from such a condition, we propose strengthening the dual Lagrangian bound by adding one or two linear cuts to the Lagrangian relaxation. Such cuts are obtained from supporting hyperplanes of one of the two constraints. Thus, they are redundant for the original problem, but they are not for the Lagrangian relaxation. The computational experiments show that the new bounds are effective and require limited computing times. In particular, one of the proposed bounds is able to solve all but one of the 212 hard instances of the CDT problem presented in [S. Burer and K. M. Anstreicher, SIAM J. Optim., 23 (2013), pp. 432--451].
2023
Sharp and Fast Bounds for the Celis-Dennis-Tapia Problem / Consolini, Luca; Locatelli, Marco. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - 33:2(2023), pp. 868-898. [10.1137/21M144548X]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2971032
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact