半定规划.pptxVIP

半定规划张乐容基本知识和基本理论用内点法解决半定规划问题基本知识和基本理论1.半定规划定义：半定规划是线性规划的一种推广，它是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大(极小)化的问题。这个约束是非线性、非光滑并且是凸的，因而半定规划是一个非光滑凸优化问题。基本知识和基本理论?2.半定规划的标准形式： （1-1）其中为实数；为n*n的实对称矩阵。基本知识和基本理论?我们令： 则（1-1）可以写成下面等价形式： （1-2）基本知识和基本理论半定规划的对偶模型： （1-3） 基本知识和基本理论?对偶理论： 半定规划是线性规划的推广，它有如下与线性规划类似的对偶理论。为了叙述方便，先给出两个引理。引理1.1设引理1.2设 基本知识和基本理论? 弱对偶定理：令X , y分别是原问题和对偶问题的可行解，则有证明：因为由引理1.1可得即。基本知识和基本理论? 定义对偶间隙，记分别为原规划式（1-2）和对偶规划式（1-3）的最优值即：由弱对偶定理知 基本知识和基本理论?定义分别为原规划（1-2）和对偶规划（1-3）的最优解集合，即：基本知识和基本理论下面引进严格可行解的概念：X为式(1-2)的严格可行解是指x为式(1-2)的可行解且有XO．如果式(1-2)存在严格可行解则称式(1-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条件，而且该条件是充分必要的。用内点法解决半定规划问题?假设原规划和对偶规划问题都存在内点可行解，则主路径可表示为：原半定规划问题的原始对偶方程是一个降值函数：其中注意如果X,S为对角矩阵，则可看成是线性规划。用内点法解决半定规划问题?如果我们有一个内点可行解（X,y,S），我们可以解下面的原始对偶系统的一些线性等式得到，并由此产生新的迭代点用内点法解决半定规划问题?其中, μ= 。用内点法解决半定规划问题?因此，我们得到：常数这给出了一种迭代复杂的限制，使半定规划问题等同于线性规划。谢谢