Sharp and Fast Bounds for the Celis-Dennis-Tapia Problem
From MaRDI portal
(Redirected from Publication:6161303)
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 re-derive a necessary and optimality condition for the exactness of the dual Lagrangian bound (equivalent to the Shor relaxation bound in this case). Starting from such condition we propose to strengthen 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 [Burer, Anstreicher, 2013].
Recommendations
- Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
- Strong Duality for the CDT Subproblem: A Necessary and Sufficient Condition
- New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem
- Dual bounds and optimality cuts for all-quadratic programs with convex constraints
- On maxima of dual function of the CDT subproblem
Cites work
- A computational study of global optimization solvers on two trust region subproblems
- A note on polynomial solvability of the CDT problem
- A two-variable approach to the two-trust-region subproblem
- Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem
- Computing a Trust Region Step
- Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
- Feasibility testing for systems of real quadratic equations
- scientific article; zbMATH DE number 439380 (Why is no real title available?)
- scientific article; zbMATH DE number 3903874 (Why is no real title available?)
- scientific article; zbMATH DE number 3547015 (Why is no real title available?)
- scientific article; zbMATH DE number 3186512 (Why is no real title available?)
- Kronecker product constraints with an application to the two-trust-region subproblem
- Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
- Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
- New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem
- New Results on Quadratic Minimization
- Newton’s Method with a Model Trust Region Modification
- On Cones of Nonnegative Quadratic Functions
- On the complexity of quadratic programming with two quadratic constraints
- Second-order-cone constraints for extended trust-region subproblems
- Set-valued analysis
- Solving generalized CDT problems via two-parameter eigenvalues
- Solving the trust-region subproblem by a generalized eigenvalue problem
- Strong Duality for the CDT Subproblem: A Necessary and Sufficient Condition
- Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
Cited in
(9)- Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
- Solving generalized CDT problems via two-parameter eigenvalues
- New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem
- An efficient splitting algorithm for solving the CDT subproblem
- Solving two-trust-region subproblems using semidefinite optimization with eigenvector branching
- A slightly lifted convex relaxation for nonconvex quadratic programming with ball constraints
- On the tightness of an SDP relaxation for homogeneous QCQP with three real or four complex homogeneous constraints
- Sum-of-squares hierarchy for the Gromov-Wasserstein problem
- A fast and cheap approach for strengthening Lagrangian bound for the generalized Celis-Dennis-Tapia subproblem
This page was built for publication: Sharp and Fast Bounds for the Celis-Dennis-Tapia Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161303)
