A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem
Lists
Only you see this
Abstract
<p style='text-indent:20px;'>This paper proposes a second-order cone programming (SOCP) relaxation for the generalized trust-region problem by exploiting the property that any symmetric matrix and identity matrix can be simultaneously diagonalizable. We show that our proposed SOCP relaxation can provide a lower bound as tight as that of the standard semidefinite programming (SDP) relaxation. Moreover, we provide a sufficient condition under which the proposed SOCP relaxation is exact. Since the standard SDP relaxation suffers from a much heavier computing burden, the proposed SOCP relaxation has a much higher efficiency in solving process. Then we design a branch-and-bound algorithm based on this SOCP relaxation to obtain the global optimal solution for a general problem. Three types of numerical experiments are carried out to demonstrate the effectiveness and efficiency of our proposed SOCP relaxation.
BibTeX
@article{zhou2019socp,
author = {Jing Zhou and Cheng Lu and Ye Tian and Xiaoying Tang},
title = {{A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem}},
journal = {Journal of Industrial and Management Optimization},
year = {2019},
doi = {10.3934/jimo.2019104},
}Loading related content...