zbMATH — the first resource for mathematics

Strong duality for the CDT subproblem: a necessary and sufficient condition. (English) Zbl 1187.90290
The problem (QP) of minimizing a nonconvex quadratic function subject to two quadratic inequality constraints is considered. It is a Celis, Dennise and Tapia (CDT) type quadratic program proposed in [M. R. Celis, J. E. Dennis and R. A. Tapia, in: Numerical optimization, Proc. SIAM Conf., Boulder/Colo. 1984, 71–82 (1985; Zbl 0566.65048)]. A verifiable condition is presented which indicates whether or not the semidefinite programming (SDP) relaxation for the quadratic program is tight. It is also proved that the result of this paper is equivalent to a necessary and sufficient condition for the strong duality to hold for this class of nonconvex quadratic programs. This necessary and sufficient condition is verifiable and based on an optimal solution of the SDP relaxation or, alternatively, as an easy verifiable condition based on a KKT point in terms of the Lagrangian function and multipliers. An example is presented to show that the information carried by the KKT solutions may not be useful for the optimal solution of the CDT problem when the strong dulaity fails. A numerical implementation of the necessary and sufficient condition is also proposed.

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C51 Interior-point methods
90C05 Linear programming
Full Text: DOI