摘要
以φ(t)=(tp+1-1)-(p+1)ln t作为核函数,讨论半定规划的一类多项式原始对偶内点算法的收敛性及其复杂度.基于这个核函数找到牛顿系统的一个新的搜索方向,从而得到一个新的算法,并给出了其长步长迭代界和短步长迭代界分别为O(n1-pln nε),O(n23-plnεn).
Presents a polynomial primal dual interior point algorithms for SDP based on a kernel function and analyzes its convergence and polynomial complexity. The kernel function is φ（t）=（tp＋1-1）-（P＋1）ln t. A new direction for Newton system and a new algorithm are given based on the new function, and it is induced that the polynomial complexity of algorithms is O（n 1-p ln n/ε）,O（n 3/2-p ln n/ε）.
出处
《福建师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2013年第2期16-22,共7页
Journal of Fujian Normal University：Natural Science Edition
基金
国家自然科学基金资助项目(11071041)
关键词
半定规划
原始对偶内点算法
复杂度
semidefinite optimization
primal-dual interior point algorithm
polynomial complexity
