半定规划

半定规划张乐天12721208内容基本知识和基本理论用内点法解决半定规划问题基本知识和基本理论1.半定规划定义：半定规划是线性规划的一种推广，它是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大(极小)化的问题。这个约束是非线性、非光滑并且是凸的，因而半定规划是一个非光滑凸优化问题。基本知识和基本理论2.半定规划的标准形式：（1-1）其中𝑏𝑖𝑖=1,···,𝑚为实数；𝐶,𝐴𝑖(𝑖=1,···,𝑚)为n*n的实对称矩阵。基本知识和基本理论我们令：𝑏𝑖𝑖=1,···,𝑚则（1-1）可以写成下面等价形式：（1-2）基本知识和基本理论半定规划的对偶模型：（1-3）基本知识和基本理论对偶理论：半定规划是线性规划的推广，它有如下与线性规划类似的对偶理论。为了叙述方便，先给出两个引理。引理1.1设𝐴,𝐵∈𝑆𝑛且𝐴≥0，𝐵≥0，则𝐴∙𝐵≥0。引理1.2设𝐴,𝐵∈𝑆𝑛且𝐴≥0，𝐵≥0，则𝐴∙𝐵=0。当且仅当𝐴𝐵=0。基本知识和基本理论弱对偶定理：令X,y分别是原问题和对偶问题的可行解，则有𝐶∙𝑋≥𝑏𝑇𝑦。证明：𝐶∙𝑋−𝑏𝑇𝑦=𝐴𝑇𝑦+𝑍,𝑋−𝐴𝑋,𝑌=𝑍,𝑋因为𝑍≥0，𝑋≥0由引理1.1可得𝐶∙𝑋−𝑏𝑇𝑦≥0即𝐶∙𝑋≥𝑏𝑇𝑦。基本知识和基本理论定义对偶间隙𝛽=𝑍,𝑋，记𝑝∗和𝑑∗分别为原规划式（1-2）和对偶规划式（1-3）的最优值即：由弱对偶定理知𝑝∗𝑑∗。基本知识和基本理论定义𝑋𝑜𝑝𝑡和𝑦𝑜𝑝𝑡分别为原规划（1-2）和对偶规划（1-3）的最优解集合，即：基本知识和基本理论下面引进严格可行解的概念：1.X为式(1-2)的严格可行解是指x为式(1-2)的可行解且有XO．如果式(1-2)存在严格可行解则称式(1-2)具有严格可行性。2.y,Z为式(1-3)的严格可行解是指y,Z为式(1-3)的可行解且ZO．如果式(1-3)存在严格可行解则称式(1-3)具有严格可行性．基本知识和基本理论强对偶定理：（1）半定规划问题（1-2）存在严格可行解；（2）半定规划对偶问题（1-3）存在严格可行解。则有下面的结论：（a）如果上面条件至少有一个成立，则𝑝∗=𝑑∗。（b）如果上面两个条件都成立，则𝑝∗=𝑑∗，且𝑋𝑜𝑝𝑡和𝑦𝑜𝑝𝑡均非空。假设式(1-2)和式(1-3)都存在严格可行解，则至少存在一对原始-对偶最优解，即最优解集合𝑋𝑜𝑝𝑡和𝑦𝑜𝑝𝑡都非空，从而就存在可行解X，y使𝐶∙𝑋=𝑏𝑇𝑦=𝑝∗=𝑑∗基本知识和基本理论综上可以得到半定规划的最优条件，若式(1-2)和式(1-3)均有严格可行解，则X为式(1-2)的最优解当且仅当存在𝑋,𝑍∈𝑆𝑛∗𝑆𝑛使得下面条件成立，这就是半定规划的KKT条件，而且该条件是充分必要的。用内点法解决半定规划问题假设原规划和对偶规划问题都存在内点可行解，则主路径可表示为：原半定规划问题的原始对偶方程是一个降值函数：其中𝜌≥0.注意如果X,S为对角矩阵，则可看成是线性规划。用内点法解决半定规划问题如果我们有一个内点可行解（X,y,S），我们可以解下面的原始对偶系统的一些线性等式得到(𝐷𝑋,𝑑𝑦,𝐷𝑠)，并由此产生新的迭代点𝑋+,𝑦+,𝑆+。用内点法解决半定规划问题其中,𝐷=𝑋12(𝑋12𝑆𝑋12)−12𝑋12μ=𝑋∙𝑆/𝑛;𝑋+=𝑋+𝛼𝐷𝑋;𝑦+=𝑦+𝛼𝑑𝑦;𝑆+=𝑠+𝛼𝐷𝑆。用内点法解决半定规划问题因此，我们得到：常数𝛿0.2这给出了一种迭代复杂的限制，使半定规划问题等同于线性规划。谢谢