| The paper analyses polynomial primal dual interior point algorithms for SDP based on a kernel function. It contains tree parts.The first part introduces the development of interior point algorithms and semidefinite optimization, the main process of interior-point method to solve semidef-inite programming, and the meaning of the kernel function. In addition, this part introduces some marks, terminologies, definitions and theorems which are used in this paper.The second part discusses properties of the function ip（t）=tp-1/p-∫1teg（ξ）dξ, and studies the rationality, complexity and convergence of the interior point algorithms with the kernel function φ（t）, where g（t）=a1logt+b（ta2-1）, a1<-1,6≥1,a2<0,p∈[l,2].In the first section of the second chapter, if the interior point algorithm uses φ（t）=tp-1/p-∫1teg（ξ）dξ as the kernel function, where g（t）=a1logt+b（ta2-1）, a1≤-1, b>1,a2<0,p∈[1,2], then its complexity is described as follows:If τ=O（n）,θ6=（?）（1）, then its complexity is O（np-1/p （logn） a1+a2-1/a2） log n/ε.If τ=O（l）, θ=（?）B(1/n1/2), then its complexity is O（n2p-1/2p（log n）a1+a2-1/a2’） logn/ε.The second section of the second chapter considers the special case of p=2and gets a better polynomial complexity of the interior point algorithms, which is presented as follows:If τr=O（n）,θ9=（?）（1）, then the algorithmic complexity is O（n1/2（log n）a1+a2-1/a2） logn/ε.If τ=O（1）,θ=（?）(1/n1/2), then the algorithmic complexity is O（n1/2） logn/ε.The third section of the second chapter analyzes the relationship between the polynomial complexity and its parameters, and explains why the complexity in the second section is better than that in the first section.The third part proves the proposition: If N is the upper bound of the iterations of the interior point algorithm with a kernel function φ（t） which is an e-function, then kφ（t） is an e-function and k2N is the upper bound of the iterations of the interior point algorithm with a kernel function kip（t）, where k>1, which is showed by an example. |
PDF Full Text Request