凸二次规划SDP松弛解的存在性证明  

The Existence Proof of the Solution of SDP Relaxation for Convex Quadratic Program

作　　者：张思颖 ZHANG Si-ying(School of Mathematical Science,Chongqing Normal University,Chongqing 401331,China)

机构地区：[1]重庆师范大学数学科学学院,重庆401331

出　　处：《重庆工商大学学报（自然科学版）》2020年第3期66-69,共4页Journal of Chongqing Technology and Business University:Natural Science Edition

基　　金：重庆师范大学2019年研究生科研创新项目(YKC19003).

摘　　要：针对利用CVX软件求解半定规划问题的有效性依赖于该半定规划问题的原始-对偶性,提出利用半定规划问题的强对偶定理和Gershgorin圆盘定理证明在箱子约束及单位球形约束下的凸二次规划问题的半定规划松弛模型解的存在性。该证明方法为嵌入了SeDuMi和SDPT3这两种内点算法的CVX软件提供了有效求解半定规划松弛模型的理论依据;一旦利用该方法证明了半定规划问题解的存在,必然可利用CVX软件有效求解。Because the problem of quadratic program has received extensive attention and research in the field of continuous and combinatorial optimization since the semi-definite planning(SDP)relaxation method was proposed,because the effectiveness of the solution of SDP by using CVX software relies on the primal SDP and dual SDP,this paper proposes to use the strong duality theorem and Gershgorin circle theorem to prove the existence of the solution of SDP relaxation model of convex quadratic program under the condition of box constraints and unit spherical constraints.The new proof method of the existence of the solution of the SDP lays the theoretical foundation of the effectiveness for solving the SDP relaxation model by the CVX software with the two kinds of interior point algorithms of SeDuMi and SDPT3.Once this method is used to prove the existence of the solution of SDP,it is necessary to use CVX software to receive effective solution.

关 键 词：二次规划 强对偶定理 Gershgorin圆盘定理 

分 类 号：O224[理学—运筹学与控制论]