A new primal-dual path-following interior-point algorithm for linearly constrained convex optimization  

线性约束凸规划的一个新原-对偶路径-跟踪内点算法(英文)

作　　者：张敏 白延琴 王国强 

机构地区：[1]Department of Mathematics, College of Sciences, Shanghai University [2]College of Vocational Technology, Shanghai University of Engineering Science

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

基　　金：supported by the Shanghai Pujiang Program (Grant No.06PJ14039);the Science Foundation of Shanghai Municipal Commission of Education (Grant No.06NS031)

摘　　要：In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization(LCCO) is presented.The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path.At each iteration, only full-Newton steps are used.Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O(√n log n /ε).In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization （LCCO） is presented. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, only full-Newton steps are used. Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O（√nlog n/ε）.

关 键 词：linearly constrained convex optimization （LCCO） interior-point algorithm small-update method polynomial complexity 

分 类 号：O221[理学—运筹学与控制论]