A new primal-dual interior-point algorithm for convex quadratic optimization  

作　　者：王国强 白延琴 刘勇 张敏 

机构地区：[1]Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China [2]College of Vocational Technology, Shanghai University of Engineering Science, Shanghai 200437, P. R. China

出　　处：《Journal of Shanghai University(English Edition)》2008年第3期189-196,共8页上海大学学报（英文版）

基　　金：the Foundation of Scientific Research for Selecting and Cultivating Young Excellent University Teachers in Shanghai (Grant No.06XPYQ52);the Shanghai Pujiang Program (Grant No.06PJ14039)

摘　　要：In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization （CQO） based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method （IPM） to O（√n log nlog n/e）, which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization （CQO） based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method （IPM） to O（√n log nlog n/e）, which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.

关 键 词：convex quadratic optimization （CQO） interior-point methods （IPMs） large-update method polynomial complexity 

分 类 号：O17[理学—数学]