Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function  

作　　者：金正静 白延琴 

机构地区：[1]College of Sciences, Shanghai University [2]College of Sciences, Zhejiang Forestry University

出　　处：《Journal of Shanghai University(English Edition)》2009年第4期333-339,共7页上海大学学报（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant No.10771133);the Shanghai Leading Academic Discipline Project (Grant No.S30101);the Research Foundation for the Doctoral Program of Higher Education (Grant No.200802800010)

摘　　要：The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.

关 键 词：linear optimization self-concordant function finite barrier interior-point methods polynomial-time complexity 

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