RECOVERING OPTIMAL SOLUTIONS VIA SOC-SDP RELAXATION OF TRUST REGION SUBPROBLEM WITH NONINTERSECTING LINEAR CONSTRAINTS

摘要

In this paper, we study an extended trust region subproblem (eTRS) in which the unit ball intersects with m linear inequality constraints. In the literature, Burer et al. proved that an SOC-SDP relaxation (SOCSDPr) of eTRS is exact, under the condition that the nonredundant constraints do not intersect each other in the unit ball. Furthermore, Yuan et al. gave a necessary and sufficient condition for the corresponding SOCSDPr to be a tight relaxation when m = 2. However, there lacks a recovering algorithm to generate an optimal solution of eTRS from an optimal solution X* of SOCSDPr when rank(X*) >= 2 and m >= 3. This paper provides such a recovering algorithm to complement those known works.