Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization

作     者：钱忠根 白延琴 王国强 QIAN Zhong-gen;BAI Yan-qin;WANG Guo-qiang

作者机构：Department of Basic Courses Jiangsu Teachers University of Technology Changzhou 213001 P. R. China Department of Mathematics College of Sciences Shanghai University Shanghai 200444 P. R. China College of Vocational Technology Shanghai University of Engineering Science Shanghai 200437 P. R. China 

出 版 物：《Journal of Shanghai University(English Edition)》 (上海大学学报（英文版）)

年 卷 期：2008年第12卷第5期

页      面：388-394页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Project supported by the National Natural Science Foundation of China (Grant No. 10117733)  the Shanghai Leading Academic Discipline Project (Grant No.J50101)  and the Foundation of Scientific Research for Selecting and Cultivating Young Excellent University Teachers in Shanghai (Grant No.06XPYQ52) 

主　　题：interior-point algorithm primal-dual method semidefinite optimization (SDO) polynomial complexity 

摘      要：Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.