基于半定规划原始对偶内点法的一种新的核函数

陈言

〔关键词〕 半定规划；原始对偶内点法；核函数

〔中图分类号〕 G643.8 〔文献标识码〕 A

〔文章编号〕 1004—0463（2014）22—0092—02

迄今为止，半定规划问题（SDP）成为了数学规划领域最热门的研究课题之一.半定规划之所以得到越来越多的研究者的关注得益于以下的原因：首先，在Karmarkar的突破性的文章中，他提出了一种有效的处理线性规划问题的多项式算法——内点法（IPM）.在这之后，许多的研究者比如Nesterov、Nemirovsky和Todd开始研究和分析如何去利用内点法对有效地解决各种各样的凸规划问题，比如二阶锥规划和半定规划.其次，半定规划在各个领域都有着广泛的应用，比如工程领域和数据结构领域.在本文中，我们利用原始对偶内点算法去求解半定规划问题.在理论分析中，我们给出了一种基于原始对偶内点法的新的核函数.我们考虑的半定规划问题（P）及对偶问题（D）如下：

（P）minC·X （D）maxbty

s.t.Ai·X=bi，i=1，2，……，m s.t.■yiAi+S=C

X？叟0. S？叟0.

在这里Ai∈Sn，并且假设他们是线性无关的，其中b∈Rm，X∈■，S∈Sn.Nesterov和Nemirovsky在1988年研究了障碍函数的自协调性，他们认为内点法从理论上讲能够应用与所有的凸优化问题.因为半定规划是线性规划的推广，所以基于线性规划的内点法也能够被推广至求解半定规划.基于大多数线性规划问题的原始对偶内点法利用一个经典的对数障碍函数如下：

？椎c（x，s，？滋）=■-■log（■）-n.

通过引入向量如下：

v=■，

并且定义如下函数：

？准c（t）=■-log（t），t>0

上述函数成为对数障碍函数的核函数，能够被表达为向量的函数，形式如下：

？椎c（x，s，？滋）=2？准c（v）=2■？准c（vi）

这个经典的核函数已经被证明基于大步迭代和小步迭代的迭代上界分别为O（nlog（■））和O（■log（■））.尽管比起小步迭代，大步迭代有着更好的迭代上界，但是上面的结果并不是令人满意的.因此无论是基于半定规划还是线性规划，一个新的研究方向是如何找到一种更好的核函数，使得基于这种核函数的原始对偶算法有着更小的理论迭代上界，下表是一些来自不同文献[4-7]的研究成果：

表1 一些核函数的重要结果

■

在本文中，我们提出的新的核函数如下所示：

？准（t）=■-■loglog（e-1）t+1.

这个核函数并没有在其他的文献中出现过，我们能够证明这个核函数有着较好的迭代上界.在大步迭代中它的理论迭代上界是■■32■（V）+1+32e）log（■）.这是本文中给出的新的结果.在本文中■是指每个分量都大于等于0的维向量，而是指每个分量都大于0的n维向量。Sn，■，■分别表示对称矩阵，半定矩阵，和正定矩阵全体构成的锥.对于对称矩阵A，B A？叟B，A？叟B分别指A-B是半定矩阵和正定矩阵.A·B=Tr（AtB），对于任何的V∈■，我们假定V的特征值是按照单调递减的顺序排列，即？姿1（V）>？姿2（V）…>？姿3（V）.

本文基于半定规划问题给出了原始对偶内点法的一种新的核函数，并在理论上推导了其迭代上界.其理论分析步骤和复杂性分析结果[8-10]如下：

第一步：输入核函数，更新参数？兹，0<？兹<1，截止参数？子和精度参数？着.

第二步：求解方程-■？准'（t）=s，如果不能得到反函数的解析解，则需要估计反函数的上下界.

第三步：计算最优的迭代步，并且在对核函数的下降做出估计，通过求解

f（■）？燮-■.

第四步：估计的下界.

？啄（V）？叟-■.

第五步：利用第三步和第四步的结果估计

f（■）？燮-k？准c（V）1-？酌.

第六步：估计核函数的上界

？准c（v+）？燮L？准（n，？兹，？子）=n？准（■）.

第七步：计算总共的迭代步数

■log■？燮■■ log■.

第八步：代入新的核函数计算大步迭代上界为.

■■32■+1）+32elog（■）.

？笙 编辑：谢颖丽endprint