二次半定规划一个原始对偶路径跟踪算法

A Primal-dual Path-following Algorithm for Quadratic Semi-definite Programming

本文提出求解二次半定规划的一个基于H..K..M方向的原始对偶路径跟踪算法.文中首先导出确定H..K..M方向的线性方程组,并证明该搜索方向的存在唯一性;然后给出算法的具体步骤,并证明算法产生的迭代点列落在中心路径的某个邻域内.最后采用Matlab(R2011b)数学软件编程对算法进行数值试验.数值结果表明算法是有效的.

A primal-dual path-following algorithm based o n H..K..M direction for quadraticsemi-definite p r o g r a m m i n g p r o b l e m s(Q S D P)is proposed.Firstly?the s y s t e m of linear e q u a tionsyielding the H..K..M direction are derived?a n d the existence a n d uniqueness of thesearch direction are s h o w n;S e c o n d l y,the algorithm is described in detail.W e s h o w that the iteratesgenerated b y the algorithm can fall into s o m e n e i g h b o r h o o d of the central path unders o m e mild conditions.Finally,a preliminary numerical exp e r i m e n t is p e r f o r m e d for the algorithmb y using M a t l a b(R2011b)m a t hematical software?a n d the numerical results s h o w thatthe proposed algorithm is effective.