下载文档原格式
重庆工商大学学报！自然科学版)J Chongqing Technol&Business UnH(Nat Sei Ed)2020年6月Jun.2020第37卷第3期Vol.37No.3doi：10.16055/j.Hsn.1672-058X.2020-0003-010凸二次规划SDP松弛解的存在性证明张思颖(重庆师范大学数学科学学院，重庆401331)摘要:针对利用CVX软件求解半定规划问题的有效性依赖于该半定规划问题的原始-对偶性,提出利用半定规划问题的强对偶定理和GershyoOn圆盘定理证明在箱子约束及单位球形约束下的凸二次规划问题的半定规划松弛模型解的存在性。
该证明方法为嵌入了SeDuMi和SDPT3这两种内点算法的CVX软件提供了有效求解半定规划松弛模型的理论依据;一旦利用该方法证明了半定规划问题解的存在，必然可利用CVX软件有效求解。
关键词：二次规划；强对偶定理；GershyoOn圆盘定理中图分类号：0224文献标志码:A文章编号：1672-058X(2020)03-0066-040引言二次规划是连续优化理论的基础问题，同时也被认为是最具挑战的组合优化问题之条T*二次规划问题自半定规划(SDP)松弛方法提出以来在连续和组合优化领域得到了广泛的重视和研究[3_4]*本文将考虑两种特殊约束即箱子约束(式(1))和单位球形约束(式(2))下的凸二次规划问题SDP问题的解的存在性*=bx=min2f(x):=X T gx+2c T x]s.y X%[-,1)%(1)=bn l=min{f(x):=lQx+2%x}s.i.X T X(1(2)其中c%R%,Q%R%”为对称半正定矩阵*不失一般性，本文假设Q为对角矩阵，即Q=<=(,g("1,•••,"%)其中0("1("(•••("%SDP问题的解存在并不能确保它就能利用CVX进行有效求解*众所周知，用于求解半定规划CVX软件的两个核心算法SeDuMi和SDPT3都是利 用内点算法法行设计的,这两种算法均是通过问题的原始-对偶信息来判断一个SDP问题是否是超定的、不可行的、无界的、不精确的、可解的和求解失败的*确切地说，利用CVX求解一个SDP问题的有效性依赖于SDP的原始和对偶的可行性、正交性和严格互补条件*如果一个SDP问题满足原始和对偶严格可行性,就能从理论上保证CVX给出其满足任意精度的解*否则，即便一个SDP问题存在最优解，也不能确保CVX能够有效求解，具体的例子可以参见文献[5]中的例4.1*本文将利用SDP的强对偶定理和Gershyorin圆盘定理证明式(1)(2)两种凸二次规划问题SDP松方优的在在性*1预备知识在本文中，用R表示全体实数,R%是%维欧几里得空间,R：表示数"中分量为非负数的向量集合, R：+表示数"中分量全为正数的向量集合*x T表示列向量x的转置，下标变量x=表示向量x的第=个分量或者一个实数，而上标变量x则表示欧几里得空间的一个向量;S%表示%x%实对称矩阵集合,X& 0(x>0)表示X是正半定矩阵(正定矩阵)；1=表示收稿日期：2019-09-16；修回日期：2019-10-11,基金项目：重庆师范大学2019年研究生科研创新项标YKC19003).作者简介:张思颖(1995-,女，四川绵竹人，硕士，从事半定规划研究.第3期张思颖：凸二次规划SDP松弛解的存在性证明67矩阵M第)亍第j列元素*[•，-]为引"中两向量的内积或两矩阵的Fwbenious内积。
主程序
结论与展望原-对偶内点算法融合了对偶原理、Lagrange乘子法、内点罚函数法和Newton法，具有传统优化的特点，同时也大大扩大了内点算法的应用领域；原-对偶内点算法在解决线性规划、二次规划、半定规划、锥规划以及压缩传感、机器学习问题中起到了很好的作用；原-对偶内点算法在初始值的确定上，灵活度远大于一般的内点算法；对于原-对偶内点算法加速技术的研究，主要还是集中在如何快速的求解step3中的线性方程组上；原-对偶内点算法是一类具有广泛应用的算法，值得大家关注，并能在以后的学习和科研中加以运用；参考资料：A Mathematical View of Interior-Point Methods for Convex Optimization等。
半定规划原始对偶内点算法的复杂度分析在数学规划发展的长河中，内点法是解决线性规划的有效方法之一。
半定规划是由线性规划推广而来的。
由于半定规划广泛的应用于组合优化，传感器网络定位，结构设计，电机工程等。
所以，研究半定规划问题的求解方法尤为重要。
内点法是求解半定规划问题主要方法之一。
本文主要研究求解半定规划的原始对偶内点算法。
在原始对偶内点算法中，核函数在定义新的搜索方向方面起到重要作用，因此构造原始对偶内点算法的核心任务是构造一个良好的核函数。
本文构造两个新的核函数，研究其性质，基于这两个核函数，构造求解半定规划问题的原始对偶内点算法，对给出的求解半定规划原始对偶内点算法进行复杂度分析，得到了算法的大步校正和小步校正的理论迭代界，结果能够达到当前已知最好的理论界。
基于本文构造的两个新的核函数，我们也研究了求解线性规划原始对偶内点算法。
由于求解线性规划的原始对偶内点算法与求解半定规划原始对偶内点算法在性质和算法的复杂度分析上十分相似，而且结果相同，所以本文只对半定规划的原始对偶内点算法进行阐述。
内点法介绍（Interior Point Method）在面对无约束的优化命题时，我们可以采用牛顿法等方法来求解。
而面对有约束的命题时，我们往往需要更高级的算法。
单纯形法（Simplex Method）可以用来求解带约束的线性规划命题（LP），与之类似的有效集法（Active Set Method）可以用来求解带约束的二次规划（QP），而内点法（Interior Point Method）则是另一种用于求解带约束的优化命题的方法。
而且无论是面对LP还是QP，内点法都显示出了相当的极好的性能，例如多项式的算法复杂度。
本文主要介绍两种内点法，障碍函数法（Barrier Method）和原始对偶法（Primal-Dual Method）。
其中障碍函数法的内容主要来源于Stephen Boyd与Lieven Vandenberghe的Convex Optimization一书，原始对偶法的内容主要来源于Jorge Nocedal和Stephen J. Wright的Numerical Optimization一书（第二版）。
为了便于与原书对照理解，后面的命题与公式分别采用了对应书中的记法，并且两者方法针对的是不同的命题。
两种方法中的同一变量可能在不同的方法中有不同的意义，如μ。
在介绍玩两种方法后会有一些比较。
障碍函数法Barrier MethodCentral Path举例原始对偶内点法Primal Dual Interior Point Method Central Path举例几个问题障碍函数法（Barrier Method）对于障碍函数法，我们考虑一个一般性的优化命题：minsubject tof0(x)fi(x)≤0,i=1,...,mAx=b(1) 这里f0,...,fm:Rn→R 是二阶可导的凸函数。
同时我也要求命题是有解的，即最优解x 存在，且其对应的目标函数为p。
此外，我们还假设原命题是可行的（feasible）。
原始对偶内点法原始对偶内点法是一种优化算法，常用于线性规划问题的求解。
它是基于对偶理论和内点法的思想而发展起来的一种算法。
在了解原始对偶内点法之前，我们需要先了解一下线性规划问题。
线性规划问题是指在一定的约束条件下，求解一个线性函数的最大值或最小值的问题。
例如，在生产计划中，我们需要在一定的时间、人力和物力约束下，最大化生产利润，这就是一个典型的线性规划问题。
针对这类问题，传统的方法是使用单纯形法。
但是，单纯形法在高维度问题上的计算复杂度会呈指数级增长，使得其在实际问题中的应用受到了很大限制。
于是，内点法被提出来解决这个问题。
内点法是一种求解线性规划问题的有效方法，其基本思想是将可行域的内部作为搜索空间，然后寻找一个可行解。
内点法的优点是计算复杂度低，适用于高维度问题，但是由于其需要保证搜索空间的内部始终是可行的，所以需要使用对偶理论来进行约束条件的转化。
原始对偶内点法结合了内点法和对偶理论的思想，可以更加高效地求解线性规划问题。
其基本思路是在可行域内部搜索最优解，并通过对偶理论将原问题转化为对偶问题，从而可以同时求解原问题和对偶问题，使得求解效率大大提高。
具体来说，原始对偶内点法的求解步骤如下：1. 初始化原始问题和对偶问题的可行解。
2. 在可行域内部搜索最优解。
这里需要使用内点法的思想，通过不断向可行域内部移动来找到最优解。
3. 将原问题转化为对偶问题，并求解对偶问题。
这里需要使用对偶理论的思想，将原问题转化为对偶问题，并通过对偶问题的求解来验证原问题的可行解和最优解。
4. 根据对偶问题的解，更新原始问题的可行解。
这里需要使用原始对偶内点法中的更新公式，通过对偶问题的解来更新原始问题的可行解，从而得到更优的解。
5. 重复步骤2-4，直到找到最优解。
原始对偶内点法是一种高效的求解线性规划问题的方法。
其结合了内点法和对偶理论的优点，可以更加高效地求解线性规划问题，是一种在实际问题中应用广泛的优化算法。
