| 摘要: |
| 针对利用CVX软件求解半定规划问题的有效性依赖于该半定规划问题的原始-对偶性,提出利用半定规划问题的强对偶定理和Gershgorin圆盘定理证明在箱子约束及单位球形约束下的凸二次规划问题的半定规划松弛模型解的存在性。该证明方法为嵌入了SeDuMi和SDPT3这两种内点算法的CVX软件提供了有效求解半定规划松弛模型的理论依据；一旦利用该方法证明了半定规划问题解的存在，必然可利用CVX软件有效求解。 |
| 关键词: 二次规划 强对偶定理 Gershgorin圆盘定理 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| 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
|
| Abstract: |
| 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. |
| Key words: quadratic program strong duality theorem Gershgorin circle theorem |
