A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts

作     者：YUAN JianHua WANG MeiLing AI WenBao SHUAI TianPing 

作者机构：School of Science Beijing University of Posts and Telecommunications Automation School Beijing University of Posts and Telecommunications 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2016年第59卷第6期

页      面：1127-1140页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：supported by National Natural Science Foundation of China(Grant Nos.11471052,11171040,11001030 and 61375066) the Grant of China Scholarship Council 

主　　题：trust-region subproblem linear inequality constraints global solutions second-order-cone refor-mulation SDP relaxation 

摘      要：We consider the extended trust-region subproblem with two linear inequalities. In the nonintersecting case of this problem, Burer and Yang(2015) have proved that its semi-definite programming relaxation with second-order-cone reformulation(SDPR-SOCR) is a tight relaxation. In the more complicated intersecting case, which is discussed in this paper, so far there is no result except for a counterexample for the SDPR-SOCR. We present a necessary and sufficient condition for the SDPR-SOCR to be a tight relaxation in both the nonintersecting and intersecting cases. As an application of this condition, it is verified easily that the nonintersecting SDPR-SOCR is a tight relaxation indeed. Furthermore, as another application of the condition, we prove that there exist at least three regions among the four regions in the trust-region ball divided by the two intersecting linear cuts, on which the SDPR-SOCR must be a tight relaxation. Finally, the results of numerical experiments show that the SDPR-SOCR can work efficiently in decreasing or even eliminating the duality gap of the nonconvex extended trust-region subproblem with two intersecting linear inequalities indeed.