Title: 
Strong Duality for the CDT Subproblem: A Necessary and
Sufficient Condition

Authors:
Wenbao Ai
School of Science
Beijing University of Posts and Telecommunications
People's Republic of China


Shuzhong Zhang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin, Hong Kong

Abstract:
In this paper we consider the problem of minimizing a
nonconvex quadratic function, subject to two quadratic inequality
constraints. As an application, such quadratic program plays an
important role in the trust region method for nonlinear
optimization; such problem is known as the CDT subproblem in the
literature. The Lagrangian dual of the CDT subproblem is a
Semidefinite Program (SDP), hence convex and solvable. However, a
positive duality gap may exist between the CDT subproblem and its
Lagrangian dual because the CDT subproblem itself is nonconvex. In this
paper, we present a necessary and sufficient condition to characterize when
the CDT subproblem and its Lagrangian dual admits no duality gap
(i.e., the strong duality holds). This necessary and sufficient
condition is easy verifiable and involves only one (any) optimal solution of
the SDP relaxation for the CDT subproblem. Moreover, the condition
reveals that it is actually rare to render a positive duality gap
for the CDT subproblems in general. Moreover, if the strong duality
holds then an optimal solution for the CDT problem can be retrieved
from an optimal solution of the SDP relaxation, by means of a matrix
rank-one decomposition procedure. The same analysis is extended to
the framework where the necessary and sufficient condition is
presented in terms of the Lagrangian multipliers at a KKT point.
Furthermore, we show that the condition is numerically easy to work with approximatively.