2019 journal article

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

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 15(4), 1677–1699.

By: J. Dai, S. Fang* & W. Xing

author keywords: Trust region subproblem; SOC-SDP relaxation; slater condition; matrix decomposition; recovering algorithm
Source: Web Of Science
Added: July 22, 2019

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.